Main Content

Algoritmos de resolución de ecuaciones

Definición de resolución de ecuaciones

Dado un conjunto de n funciones no lineales Fi(x), donde n es el número de componentes en el vector x, la meta de la resolución de ecuaciones es encontrar un vector x que hace que toda Fi(x) = 0.

fsolve intenta resolver un sistema de ecuaciones minimizando la suma de los cuadrados de los componentes. Si la suma de los cuadrados es cero, el sistema de ecuaciones se resuelve. fsolve tiene tres algoritmos:

  • Trust-region

  • Trust-region-dogleg

  • Levenberg-Marquardt

Todos los algoritmos son a gran escala; consulte Algoritmos a gran escala frente a algoritmos a media escala.

La función fzero resuelve una ecuación única de una dimensión.

La función mldivide resuelve un sistema de ecuaciones lineales.

Algoritmo trust-region

Muchos de los métodos utilizados en los solvers de Optimization Toolbox™ se basan en regiones de confianza, un concepto sencillo, pero potente de optimización.

Para comprender el enfoque trust-region de la optimización, considere el problema de minimización no restringida, minimice f(x), donde la función toma argumentos de vector y devuelve escalares. Suponga que el punto actual es x en el espacio n y desea mejorar moviéndose a un punto con un valor de función inferior. Para hacerlo, el algoritmo aproxima f con una función más sencilla q, que refleja razonablemente el comportamiento de la función f en un entorno N alrededor del punto x. Este entorno es la región de confianza. El solver calcula un paso de prueba s minimizando (o minimizando aproximadamente) en N. El subproblema trust-region es

mins{q(s), sN}.

El solver actualiza el punto actual a x + s si f(x + s) < f(x); de lo contrario, el punto actual permanece sin cambiar y el solver disminuye N (la región de confianza) y repite el cálculo del paso de prueba.

Las principales cuestiones al definir un enfoque específico trust-region para minimizar f(x) son cómo elegir y calcular la aproximación q (definida en el punto actual x), cómo elegir y modificar la región de confianza N y cómo resolver de forma precisa el subproblema trust-region.

En el método estándar trust-region ([48]), la aproximación cuadrática q se define por los dos primeros términos de la aproximación de Taylor a F en x. El entorno de N tiene normalmente forma de esfera o de elipsoide. En términos matemáticos, el subproblema trust-region se indica, por lo general, como

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

donde g es el gradiente de f en el punto actual x, H es la matriz hessiana (la matriz simétrica de segundas derivadas), D es una matriz de escalado diagonal, Δ es un escalar positivo y ‖ . ‖ es la norma euclídea. Para resolver Ecuación 1, un algoritmo (consulte [48]) puede calcular todos los valores propios de H y, después, aplicar un proceso de Newton a la ecuación secular

1Δ1s=0.

Un algoritmo así proporciona una solución precisa para Ecuación 1. Sin embargo, esto requiere tiempo proporcional a varias factorizaciones de H. Por lo tanto, los problemas trust-region requieren un enfoque diferente. Varias estrategias heurísticas y de aproximación, basadas en Ecuación 1, se han propuesto en la literatura ([42] y [50]). Los solvers de Optimization Toolbox siguen un enfoque de aproximación que restringe el subproblema trust-region a un subespacio bidimensional S ([39] y [42]). Después de que el solver calcula el subespacio S, el trabajo para resolver Ecuación 1 es trivial ya que, en el subespacio, el problema solo es bidimensional. El trabajo dominante se desplaza ahora a la determinación del subespacio.

El solver determina el subespacio bidimensional S con la ayuda de un método de gradiente conjugado precondicionado (descrito en la siguiente sección). El solver define S como el espacio lineal que abarcan s1 y s2, donde s1 está en la dirección del gradiente g y s2 es una dirección de Newton aproximada, es decir, una solución para

Hs2=g,

o una dirección de curvatura negativa,

s2THs2<0.

La filosofía sobre la que se basa esta elección de S es forzar la convergencia global (mediante la dirección de descenso más pronunciado o la dirección de curvatura negativa) y lograr una convergencia local rápida (mediante el paso de Newton, cuando exista).

Ahora, el proceso de la minimización no restringida utilizando el enfoque trust-region es fácil de especificar:

  1. Formule el subproblema trust-region bidimensional.

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

  3. Si f(x + s) < f(x), entonces x = x + s.

  4. Ajuste Δ.

El solver repite estos cuatro pasos hasta la convergencia, ajustando la dimensión Δ de la región de confianza de acuerdo con las reglas estándar. En particular, el solver reduce el tamaño de la región de confianza si no acepta el paso de prueba, cuando f(x + s) ≥ f(x). Consulte [46] y [49] para ver una exposición sobre este aspecto.

Los solvers de Optimization Toolbox tratan casos importantes de f con funciones especializadas: mínimos cuadrados no lineales, funciones cuadráticas y mínimos cuadrados lineales. Sin embargo, las ideas algorítmicas subyacentes son las mismas que para el caso general.

Método del gradiente conjugado precondicionado

Una forma popular de resolver sistemas definidos grandes, simétricos y positivos de ecuaciones lineales Hp = –g es el método de los gradientes conjugados precondicionados (PCG). Este enfoque iterativo requiere la capacidad de calcular productos de matriz-vector de la forma H·v, donde v es un vector arbitrario. La matriz definida simétrica positiva M es un precondicionador para H. Es decir, M = C2, donde C–1HC–1 es una matriz bien condicionada o una matriz con valores propios agrupados.

En un contexto de minimización, puede dar por supuesto que la matriz hessiana H es simétrica. Sin embargo, está garantizado que H solo sea definida positiva en el entorno de un minimizador fuerte. El algoritmo PCG existe cuando encuentra una dirección de curvatura negativa (o cero), es decir, dTHd ≤ 0. La dirección de salida PCG p es una dirección de curvatura negativa o una solución aproximada al sistema de Newton Hp = –g. En cualquier caso, p ayuda a definir el subespacio bidimensional utilizado en el enfoque trust-region abordado en Métodos trust-region para la minimización no lineal.

Algoritmo trust-region-dogleg

Otro enfoque es resolver un sistema lineal de ecuaciones para encontrar la dirección de búsqueda. El método de Newton especifica que debe resolverse la dirección de búsqueda dk de forma que

J(xk)dk = –F(xk)
xk + 1 = xk + dk,

donde J(xk) es la matriz jacobiana de n por n

J(xk)=[F1(xk)TF2(xk)TFn(xk)T].

El método de Newton puede ser problemático. J(xk) puede ser singular, en cuyo caso el paso de Newton dk no está siquiera definido. Asimismo, el paso de Newton exacto dk puede ser costoso de calcular. Además, puede que el método de Newton no converja si el punto de partida está lejos de la solución.

Usar técnicas trust-region (presentado en Métodos trust-region para la minimización no lineal) gestiona el caso cuando J(xk) es singular y mejora la robustez cuando el punto de partida está lejos de la solución. Para usar una estrategia trust-region, necesita una función de mérito para decidir si xk + 1 es mejor o peor que xk. Una posible elección es

mindf(d)=12F(xk+d)TF(xk+d).

Pero un mínimo de f(d) no es necesariamente una raíz de F(x).

El paso de Newton dk es una raíz de

M(xk + d) = F(xk) + J(xk)d,

así que también es un mínimo de m(d), donde

mindm(d)=12M(xk+d)22=12F(xk)+J(xk)d22=12F(xk)TF(xk)+dTJ(xk)TF(xk)+12dTJ(xk)TJ(xk)d.(2)

m(d) es una elección mejor de la función de mérito que f(d), de manera que el subproblema trust-region es

mind[12F(xk)TF(xk)+dTJ(xk)TF(xk)+12dTJ(xk)TJ(xk)d],(3)

de forma que D·d‖ ≤ Δ. Puede resolver este subproblema con eficiencia utilizando una estrategia dogleg.

Para una visión general de los métodos trust-region, consulte Conn [4] y Nocedal [31].

Implementación del algoritmo trust-region-dogleg

La característica principal del algoritmo trust-region-dogleg es el uso del procedimiento dogleg de Powell para calcular el paso d, lo que minimiza Ecuación 3. Para obtener una descripción detallada, consulte Powell [34].

El algoritmo construye el paso d a partir de una combinación convexa de un paso de Cauchy (un paso en la dirección de descenso más pronunciado) y un paso de Gauss-Newton para f(x). El paso de Cauchy se calcula como

dC = –αJ(xk)TF(xk),

donde α minimiza Ecuación 2.

El paso de Gauss-Newton se calcula resolviendo

J(xkdGN = –F(xk),

utilizando el operador mldivide (división izquierda de matriz) de MATLAB®.

El algoritmo elige el paso d de modo que

d = dC + λ(dGNdC),

donde λ es el valor mayor en el intervalo [0,1] para que d‖ ≤ Δ. Si Jk es (casi) singular, d es solo la dirección de Cauchy.

El algoritmo trust-region-dogleg es eficiente porque solo requiere una resolución lineal por iteración (para el cálculo del paso de Gauss-Newton). Adicionalmente, el algoritmo puede ser más robusto que usar el método de Gauss-Newton con una búsqueda de recta.

Método de Levenberg-Marquardt

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

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

o, de manera opcional, de las ecuaciones

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

donde el escalar λk controla la magnitud y la dirección de dk. Establezca la opción ScaleProblem de fsolve en 'none' para usar Ecuación 4 o establezca esta opción en 'jacobian' para usar Ecuación 5.

Cuando λk es cero, la dirección dk es el método de Gauss-Newton. A medida que λk tiende al infinito, dk tiende a la dirección de descenso más pronunciado, con una magnitud que tiende a cero. La implicación es que, para algunos términos λk suficientemente grandes, el término F(xk + dk) < F(xk) se mantiene verdadero. Por tanto, el algoritmo puede controlar el término λk para garantizar el descenso pese a los términos de segundo orden, que restringen la eficiencia del método de Gauss-Newton. El algoritmo Levenberg-Marquardt, por tanto, utiliza una dirección de búsqueda que es un cruce entre la dirección de Gauss-Newton y la dirección de descenso más pronunciado. Para obtener más detalles, consulte Método de Levenberg-Marquardt en la documentación sobre mínimos cuadrados.

Algoritmo fzero

fzero trata de encontrar la raíz de una función escalar f de una variable escalar x.

fzero busca un intervalo alrededor del punto inicial de forma que f(x) cambia de signo. Si especifica un intervalo inicial en lugar de un punto inicial, fzero lo comprueba para asegurarse de que f(x) tiene signos diferentes en los extremos del intervalo. El intervalo inicial debe ser finito; no puede contener ±Inf.

fzero utiliza una combinación de bisección de intervalo, interpolación lineal e interpolación cuadrática inversa para localizar una raíz de f(x). Para obtener más información, consulte fzero.

Algoritmo \

El algoritmo \ se describe en la sección de operadores aritméticos de MATLAB para mldivide.

Consulte también

|

Temas relacionados