Esta página aún no se ha traducido para esta versión. Puede ver la versión más reciente de esta página en inglés.

Algoritmos de mínimos cuadrados (ajuste de modelo)

Definición de mínimos cuadrados

Los mínimos cuadrados, en general, es el problema de encontrar un vector que es un minimizador local a una función que es una suma de cuadrados, posiblemente sujeto a algunas restricciones:x

minxF(x)22=minxiFi2(x)

tal que A·x ≤ b, Aeq·x = beq, lb ≤ x ≤ ub.

Hay varios solucionadores disponibles para varios tipos de () y varios tipos de restricciones:Optimization Toolbox™Fx

Solver( )FxRestricciones
mldivideC·xdNinguno
lsqnonnegC·xd≥ 0x
lsqlinC·xdEncuadernado, lineal
lsqnonlinGeneral ()FxLímite
lsqcurvefit( , ) –FxxdataydataLímite

Hay cuatro algoritmos de mínimos cuadrados en los solucionadores, además de los algoritmos utilizados en:Optimization Toolboxmldivide

  • Confianza-región-reflexivo

  • Levenberg-Marquardt

  • interior-puntolsqlin

  • El algoritmo utilizado porlsqnonneg

Todos los algoritmos son a gran escala; Ver.Algoritmos a gran escala frente a mediano escala Para ver una encuesta general de los métodos de mínimos cuadrados no lineales, consulte Dennis.[8] Los detalles específicos sobre el método Levenberg-Marquardt se pueden encontrar en Moré.[28]

Trust-region-reflectivos mínimos cuadrados

Algoritmo de mínimos cuadrados de confianza-región-reflexivo

Muchos de los métodos utilizados en los solucionadores se basan en un concepto simple pero potente en la optimización.Optimization Toolboxtrust regions,

Para comprender el enfoque de optimización de la región de confianza, considere el problema de minimización sin restricciones, minimice (), donde la función toma argumentos vectoriales y devuelve escalares.fx Supongamos que está en un punto en el espacio y desea mejorar, es decir, pasar a un punto con un valor de función inferior.xn La idea básica es aproximarse con una función más simple, que refleja razonablemente el comportamiento de la función en un vecindario alrededor del punto.fqfNx Este vecindario es la región de confianza. Un paso de prueba se calcula minimizando (o aproximadamente minimizando) más.sN Este es el subproblema de la región de confianza,

mins{q(s), sN}.(1)

El punto actual se actualiza para ser + sixs f(x + s) < f(x); de lo contrario, el punto actual permanece sin cambios y, la región de confianza, se encogió y se repite el cálculo del paso de prueba.N

Las preguntas clave en la definición de un enfoque específico de la región de confianza para minimizar () son cómo elegir y calcular la aproximación (definida en el punto actual), cómo elegir y modificar la región de confianza y cómo resolver con precisión el subproblema de la región de confianza.fxqxN Esta sección se centra en el problema sin restricciones. Las secciones posteriores discuten complicaciones adicionales debido a la presencia de restricciones en las variables.

En el método de la región de confianza estándar (), la aproximación cuadrática se define por los dos primeros términos de la aproximación de Taylor a en; la vecindad es generalmente esférica o elipsoidal en forma.[48]qFxN Matemáticamente el subproblema de la región de confianza normalmente se indica

min{12sTHs+sTg  such that  DsΔ},(2)

donde está el gradiente de en el punto actual, es la matriz de hessian (la matriz simétrica de segundo derivados), es una matriz de escalado diagonal, Δ es un escalar positivo, y ∥. ∥ es la norma 2.gfxHD Existen buenos algoritmos para resolver (ver); Estos algoritmos suelen implicar el cálculo de todos los valores propios y un proceso de Newton aplicado a laEcuación 2[48]H ecuación secular

1Δ1s=0.

Estos algoritmos proporcionan una solución precisa.Ecuación 2 Sin embargo, requieren tiempo proporcional a varias factorizaciones de.H Por lo tanto, para los problemas de la región de confianza se necesita un enfoque diferente. Varias estrategias de aproximación y heurística, basadas en, se han propuesto en la literatura (y).Ecuación 2[42][50] El enfoque de aproximación seguido en los solucionadores es restringir el subproblema de la región de confianza a un subespacio bidimensional (y).Optimization ToolboxS[39][42] Una vez que se ha calculado el subespacio, el trabajo a resolver es trivial incluso si se necesita información completa de eigenvalue/Eigenvector (ya que en el subespacio, el problema es sólo bidimensional).SEcuación 2 La obra dominante se ha desplazado ahora a la determinación del subespacio.

El subespacio bidimensional se determina con la ayuda de unS proceso de gradiente conjugada precondicionado descrito a continuación. El solucionador define como el espacio lineal extendido porSs1 Ys2Dóndes1 está en la dirección del degradado ygs2 es un aproximado Newton Dirección, es decir, una solución para

Hs2=g,(3)

o una dirección de curvatura negativa,

s2THs2<0.(4)

La filosofía detrás de esta elección es forzar la convergencia global (a través de la dirección de descenso más pronunciada o dirección de curvatura negativa) y lograr una rápida convergencia local (a través del paso de Newton, cuando existe).S

Un boceto de minimización sin restricciones utilizando ideas de la región de confianza es ahora fácil de dar:

  1. Formule el subproblema de la región de confianza bidimensional.

  2. Resuelva para determinar el paso de prueba.Ecuación 2s

  3. Si f(x + s) < f(x)Entonces x = x + s.

  4. Ajuste Δ.

Estos cuatro pasos se repiten hasta la convergencia. La dimensión de la región de confianza Δ se ajusta según las reglas estándar. En particular, se disminuye si no se acepta el paso de prueba, es decir, f(x + s) ≥ f(x). Ver y para una discusión de este aspecto.[46][49]

solucionadores tratan algunos casos especiales importantes de funciones especializadas: mínimos cuadrados no lineales, funciones cuadráticas y mínimos cuadrados lineales.Optimization Toolboxf Sin embargo, las ideas algorítmicas subyacentes son las mismas que para el caso general. Estos casos especiales se discuten en secciones posteriores.

Los mínimos cuadrados no lineales de gran escala

Un caso especial importante para () es el problema de mínimos cuadrados no linealesfx

minxifi2(x)=minxF(x)22,(5)

Where () es una función con valores vectoriales con componente de () igual aFxiFx Fi( ).x El método básico utilizado para resolver este problema es el mismo que en el caso general descrito en.Métodos de la región de confianza para la minimización no lineal Sin embargo, la estructura del problema de mínimos cuadrados no lineales se aprovecha para mejorar la eficiencia. En particular, un aproximado Gauss-Newton Dirección, es decir, una solución paras

minJs+F22,(6)

(donde está el jacobiano de ()) se utiliza para ayudar a definir el subespacio bidimensional.JFxS Segunda derivada de la función componente Fi() no se utilizan.x

En cada iteración, el método de gradientes conjugados preacondicionados se utiliza para resolver aproximadamente las ecuaciones normales, es decir,

JTJs=JTF,

Aunque las ecuaciones normales no se forman explícitamente.

Los cuadrados mínimos lineales de gran escala

En este caso la función () a resolver esfx

f(x)=Cx+d22,

posiblemente sujeto a restricciones lineales. El algoritmo genera iterados estrictamente factibles que convergen, en el límite, en una solución local. Cada iteración implica la solución aproximada de un gran sistema lineal (de orden, donde es la longitud de).nnx Las matrices de iteración tienen la estructura de la matriz.C En particular, el método de gradientes conjugados preacondicionados se utiliza para resolver aproximadamente las ecuaciones normales, es decir,

CTCx=CTd,

Aunque las ecuaciones normales no se forman explícitamente.

El método de la región de confianza de subespacio se utiliza para determinar una dirección de búsqueda. Sin embargo, en lugar de restringir el paso a (posiblemente) un paso de reflexión, como en el caso de minimización no lineal, se lleva a cabo una búsqueda de línea reflexiva por tramos en cada iteración, como en el caso cuadrático. Consulte para obtener más información sobre la búsqueda de líneas.[45] En última instancia, los sistemas lineales representan un enfoque de Newton que captura las condiciones de optimalidad de primer orden en la solución, lo que resulta en fuertes tasas de convergencia local.

Función de multiplicación jacobiana.  puede resolver el problema de mínimos cuadrados con restricciones linealmente sin usar la matriz explícitamente.lsqlinC En su lugar, utiliza una función de multiplicación jacobiana,jmfun

W = jmfun(Jinfo,Y,flag)

que proporcione. La función debe calcular los siguientes productos para una matriz:Y

  • Si entonces.flag == 0W = C'*(C*Y)

  • Si entonces.flag > 0W = C*Y

  • Si entonces.flag < 0W = C'*Y

Esto puede ser útil si es grande, pero contiene suficiente estructura que se puede escribir sin formar explícitamente.CjmfunC Para ver un ejemplo, vea.Función de multiplicación jacobiana con mínimos cuadrados lineales

Los cuadrados mínimos lineales de punto interior

El algoritmo utiliza el.lsqlin'interior-point'Algoritmointerior-point-convexquadprog La definición del problema quadprog es minimizar una función cuadrática

minx12xTHx+cTx

sujetas a restricciones lineales y restricciones enlazadas. La función minimiza la norma cuadrada 2 del vector sujeto a restricciones lineales y restricciones enlazadas.lsqlinCx – d En otras palabras, minimizalsqlin

Cxd22=(Cxd)T(Cxd)=(xTCTdT)(Cxd)=(xTCTCx)(xTCTddTCx)+dTd=12xT(2CTC)x+(2CTd)Tx+dTd.

Esto encaja en el marco estableciendo la matriz en 2quadprogHCTC y el vector parac (–2CTd). (El término aditivo DTD no tiene ningún efecto sobre la ubicación del mínimo.) Después de esta reformulación del problema, el algoritmo calcula la solución.lsqlinquadprog'interior-point-convex'

Nota

El algoritmo tiene dos rutas de código.quadprog'interior-point-convex' Se necesita uno cuando la matriz de Hessian es una matriz ordinaria (completa) de dobles, y se toma la otra cuando es una matriz dispersa.HH Para obtener información detallada sobre el tipo de datos dispersos, consulte.Matrices dispersas (MATLAB) Por lo general, el algoritmo es más rápido para problemas grandes que tienen relativamente pocos términos distintos de cero cuando se especifica como.Hsparse Del mismo modo, el algoritmo es más rápido para problemas pequeños o relativamente densos cuando se especifica como.Hfull

El método Levenberg-Marquardt

En el problema de mínimos cuadrados, se minimiza una función () que es una suma de cuadrados.fx

minxf(x)=F(x)22=iFi2(x).(7)

Los problemas de este tipo se producen en un gran número de aplicaciones prácticas, especialmente al ajustar las funciones del modelo a los datos, es decir, la estimación de parámetros no lineales. También son prevalentes en el control donde desea que la salida, (), siga alguna trayectoria del modelo continuo, (), para vector y escalar.yx,t φtxt Este problema se puede expresar como

minxnt1t2(y(x,t)φ(t))2dt,(8)

Where () y () son funciones escalares.yx,t φt

Cuando la integral se discretiza utilizando una fórmula de cuadratura adecuada, lo anterior se puede formular como un problema de mínimos cuadrados:

minxnf(x)=i=1m(y¯(x,ti)φ¯(ti))2,(9)

Dónde y¯ Y φ¯ incluir los pesos del esquema de cuadratura. Tenga en cuenta que en este problema el vector () esFx

F(x)=[y¯(x,t1)φ¯(t1)y¯(x,t2)φ¯(t2)...y¯(x,tm)φ¯(tm)].

En este tipo de problemas, el Residual F(x)∥ es probable que sea pequeño en el óptimo, ya que es la práctica general para establecer trayectorias objetivo realistas alcanzables. Aunque la función en LS se puede minimizar utilizando una técnica de minimización general sin restricciones, como se describe en, algunas características del problema a menudo se pueden explotar para mejorar la eficiencia iterativa del procedimiento de solución.Fundamentos de la optimización sin restricciones El gradiente y la matriz Hessiana de LS tienen una estructura especial.

Denotando la matriz jacobiana de () como (), el vector de degradado de () as (), la matriz Hessiana de () as () y la matriz Hessiana de cadamnFxJxfxGxfxHx Fi() comox Hi(), tienex

G(x)=2J(x)TF(x)H(x)=2J(x)TJ(x)+2Q(x),(10)

Dónde

Q(x)=i=1mFi(x)Hi(x).

La Matrix () tiene la propiedad que cuando el residuoQx F(x)∥ tiende a cero como Xk se aproxima a la solución, entonces () también tiende a cero.Qx Así, cuando F(x)∥ es pequeña en la solución, un método muy eficaz es utilizar la dirección de Gauss-Newton como base para un procedimiento de optimización.

En el método Gauss-Newton, una dirección de búsqueda, Dk, se obtiene en cada iteración importante, que es una solución del problema lineal de mínimos cuadrados:k

minxnJ(xk)F(xk)22.(11)

La dirección derivada de este método equivale a la dirección de Newton cuando se pueden ignorar los términos de ().Qx La dirección de búsqueda Dk se puede utilizar como parte de una estrategia de búsqueda de líneas para asegurarse de que en cada iteración la función () disminuye.fx

El método Gauss-Newton a menudo encuentra problemas cuando el término de segundo orden () es significativo.Qx Un método que supera este problema es el método Levenberg-Marquardt.

El método Levenberg-Marquardt y utiliza una dirección de búsqueda que es una solución del conjunto lineal de ecuaciones[25][27]

(J(xk)TJ(xk)+λkI)dk=J(xk)TF(xk),(12)

o, opcionalmente, de las ecuaciones

(J(xk)TJ(xk)+λkdiag(J(xk)TJ(xk)))dk=J(xk)TF(xk),(13)

donde el escalar Λk controla tanto la magnitud como la dirección de Dk. Establezca la opción a elegir y establezca a elegir.ScaleProblem'none'Ecuación 12ScaleProblem'Jacobian'Ecuación 13

Se establece el valor inicial del parámetroλ0 utilizando la opción.InitDamping Ocasionalmente, el valor predeterminado de esta opción puede ser inadecuado.0.01 Si encuentra que el algoritmo Levenberg-Marquardt hace poco progreso inicial, intente establecer un valor diferente al predeterminado, tal vez.InitDamping1e2

Cuando Λk es cero, la dirección Dk es idéntica a la del método Gauss-Newton. Como Λk tiende al infinito, Dk tiende hacia la dirección de descenso más pronunciada, con una magnitud que tiende a cero. Esto implica que para algunos suficientemente grandes Λk, el término F(xk + dk) <  F(xk) Se aplica. El término Λk por lo tanto, se puede controlar para garantizar el descenso, incluso cuando se encuentran los términos de segundo orden, que restringen la eficiencia del método Gauss-Newton. Cuando el paso es exitoso (da un valor de función más bajo), el algoritmo estableceλk+1 = Λk10. Cuando el paso no se realiza correctamente, el algoritmo estableceλk+1 = Λk10.

Internamente, el algoritmo de Levenberg-Marquardt utiliza una tolerancia de optimalidad (criterio de parada) de veces la tolerancia de la función.1e-4

Por lo tanto, el método Levenberg-Marquardt utiliza una dirección de búsqueda que es un cruce entre la dirección Gauss-Newton y la dirección de descenso más pronunciada. Esto se ilustra en.Figura 12-1, Método Levenberg-Marquardt en la función de Rosenbrock La solución para La función de Rosenbrock converge después de 90 evaluaciones de función en comparación con 48 para el método Gauss-Newton. La eficiencia más pobre es en parte porque el método Gauss-Newton es generalmente más eficaz cuando el residuo es cero en la solución. Sin embargo, dicha información no siempre está disponible de antemano, y la mayor robustez del método Levenberg-Marquardt compensa su eficiencia ocasional más pobre.

Figura 12-1, Método Levenberg-Marquardt en la función de Rosenbrock

Para obtener una descripción más completa de esta figura, incluidos los scripts que generan los puntos iterativos, consulte.Función de banana minimización