Medida de optimalidad de primer orden

¿Qué es una medida de optimalidad de primer orden?

La optimalidad de primer orden es una medida de cuán cerca está un punto x a óptimo. La mayoría de los solvers de Optimization Toolbox™ utiliza esta medida, aunque tiene diferentes definiciones para distintos algoritmos. La optimalidad de primer orden es una condición necesaria, pero no es una condición suficiente. En otras palabras:

• La medida de optimalidad de primer orden debe ser cero en un mínimo.

• Un punto con optimalidad de primer orden igual a cero no es necesariamente un mínimo.

Para obtener información general sobre la optimalidad de primer orden, consulte Nocedal y Wright [31]. Para obtener datos específicos sobre las medidas de optimalidad de primer orden para solvers de Optimization Toolbox, consulte Optimalidad no restringida, Teoría de optimalidad restringida y Optimalidad restringida en formato de solver.

Reglas de detención relacionadas con la optimalidad de primer orden

La tolerancia OptimalityTolerance está relacionada con la medida de optimalidad de primer orden. Habitualmente, si la medida de optimalidad de primer orden es menor que OptimalityTolerance, las iteraciones de solver finalizan.

Algunos solvers o algoritmos utilizan optimalidad de primer orden relativa como criterio de detención. Las iteraciones de solver finalizan si la medida de optimalidad de primer orden es de menos de μ veces OptimalityTolerance, donde μ es una de estas posibilidades:

• La norma infinito (máxima) del gradiente de la función objetivo en x0

• La norma infinito (máxima) de entradas para el solver, como f o b en linprog o H en quadprog

Una medida relativa intenta justificar la escala de un problema. Multiplicar una función objetivo por un número muy grande o muy pequeño no cambia la condición de detención para un criterio de detención relativo, pero sí la cambia para uno no escalado.

Los solvers con mensajes de salida ampliados indican, en los detalles del criterio de detención, cuándo utilizan optimalidad de primer orden relativa.

Optimalidad no restringida

Para un problema no restringido suave,

$$\underset{x}{\min }f(x),$$

la medida de optimalidad de primer orden es la norma infinito (es decir, el valor absoluto máximo) de ∇f(x), que es:

$$\text{first-order optimality measure = }\underset{i}{\max }\left|{\left(\nabla f(x)\right)}_i\right|={\Vert \nabla f(x)\Vert }_{\infty }.$$

Esta medida de optimalidad se basa en la condición conocida de una función suave para alcanzar un mínimo: su gradiente debe ser cero. Para problemas sin restricciones, cuando la medida de optimalidad de primer orden es casi cero, la función objetivo tiene un gradiente de casi cero, por lo que la función objetivo podría estar cerca de un mínimo. Si la medida de optimalidad de primer orden no es pequeña, la función objetivo no es mínima.

Teoría de optimalidad restringida

Esta sección resume la teoría que subyace a la definición de la medida de optimalidad de primer orden para problemas restringidos. La definición que se utiliza en las funciones de Optimization Toolbox está en Optimalidad restringida en formato de solver.

Para un problema restringido suave, deje que g y h sean funciones de vector que representen todas las restricciones de desigualdad e igualdad respectivamente (es decir, restricciones de límite, lineales y no lineales):

$$\underset{x}{\min }f(x)\text{ subject to }g(x)\le 0,h(x)=0.$$

En este caso, el significado de la optimalidad de primer orden es más complejo que para problemas no restringidos. La definición se basa en las condiciones de Karush-Kuhn-Tucker (KKT). Las condiciones de KKT son análogas a la condición de que el gradiente debe ser cero en un mínimo, modificadas para tener en cuenta las restricciones. La diferencia es que las condiciones de KKT se mantienen para los problemas restringidos.

Las condiciones de KKT utilizan la función del lagrangiano auxiliar:

$$L(x,\lambda )=f(x)+{\displaystyle \sum {\lambda }_{g,i}{g}_i(x)}+{\displaystyle \sum {\lambda }_{h,i}{h}_i(x)}.$$

(1)

El vector λ, que es la concatenación de λ_g y λ_h, es el vector de multiplicadores de Lagrange. Su longitud es el número total de restricciones.

Las condiciones de KKT son:

$${\nabla }_{x}L(x,\lambda )=0,$$

(2)

$${\lambda }_{g,i}{g}_i(x)=0\forall i,$$

(3)

$$\{\begin{array}{c}g(x)\le 0,\\ h(x)=0,\\ {\lambda }_{g,i}\ge 0.\end{array}$$

(4)

Los solvers no utilizan las tres expresiones de Ecuación 4 en el cálculo de la medida de optimalidad.

La medida de optimalidad asociada a Ecuación 2 es

$$\Vert {\nabla }_{x}L(x,\lambda )\Vert =\Vert \nabla f(x)+{\displaystyle \sum {\lambda }_{g,i}\nabla g_i(x)+{\displaystyle \sum {\lambda }_{h,i}\nabla h_{h,i}(x)}}\Vert .$$

(5)

La medida de optimalidad asociada a Ecuación 3 es

$$\Vert \overrightarrow{{\lambda }_{g}g}(x)\Vert ,$$

(6)

, donde la norma de Ecuación 6 significa la norma infinito (máximo) del vector $$\overrightarrow{{\lambda }_{g,i}{g}_i}(x)$$.

La medida de optimalidad combinada es el máximo de los valores calculados en Ecuación 5 y Ecuación 6. Los solvers que aceptan funciones de restricción no lineales informan de vulneraciones de restricciones g(x) > 0 o de |h(x)| > 0 como vulneraciones de ConstraintTolerance. Consulte Tolerancias y criterios de detención.

Optimalidad restringida en formato de solver

La mayoría de solvers de la toolbox restringidos separa el cálculo de la medida de optimalidad de primer orden en límites, funciones lineales y funciones no lineales. La medida es el máximo de las dos siguientes normas, que se corresponden con Ecuación 5 y Ecuación 6:

$$\begin{array}{l}\Vert {\nabla }_{x}L(x,\lambda )\Vert =\Vert \nabla f(x)+A^T{\lambda }_{ineqlin}+Ae{q}^T{\lambda }_{eqlin}\\ +{\displaystyle \sum {\lambda }_{ineqnonlin,i}\nabla c_i(x)+{\displaystyle \sum {\lambda }_{eqnonlin,i}\nabla ce{q}_i(x)}}\Vert ,\end{array}$$

(7)

$$\Vert \overrightarrow{\left|l_i-x_i\right|{\lambda }_{lower,i}},\overrightarrow{\left|x_i-u_i\right|{\lambda }_{upper,i}},\overrightarrow{\left|{(Ax-b)}_i\right|{\lambda }_{ineqlin,i}},\overrightarrow{\left|c_i(x)\right|{\lambda }_{ineqnonlin,i}}\Vert ,$$

(8)

donde la norma de los vectores de Ecuación 7 y Ecuación 8 es la norma infinito (máximo). Los subíndices de los multiplicadores de Lagrange se corresponden con las estructuras de multiplicadores de Lagrange de solvers. Consulte Estructuras de multiplicadores de Lagrange. Las sumas de Ecuación 7 se extienden sobre todas las restricciones. Si un límite es ±Inf, ese término no está restringido, por lo que no es parte de la suma.

Solo igualdades lineales

Para algunos problemas a gran escala solo con igualdades lineales, la medida de optimalidad de primer orden es la norma infinito del gradiente proyectado. En otras palabras, la medida de optimalidad de primer orden es el tamaño del gradiente proyectado en el espacio nulo de Aeq.

Mínimos cuadrados acotados y solvers trust-region-reflective

Para solvers de mínimos cuadrados y algoritmos trust-region-reflective, en problemas solo con límites, la medida de optimalidad de primer orden es el máximo sobre i de |v_i*g_i|. Aquí g_i es el i-ésimo componente del gradiente, x es el punto actual y

$$v_i=\{\begin{array}{ll}\left|x_i-b_i\right|\hfill & \text{if the negative gradient points toward bound }{b}_i\hfill \\ 1\hfill & \text{otherwise}\text{.}\hfill \end{array}$$

Si x_i se encuentra en un límite, v_i es cero. Si x_i no se encuentra en un límite, entonces en un punto de minimización el gradiente g_i debería ser cero. Por lo tanto, la medida de optimalidad de primer orden debería ser cero en un punto de minimización.

Temas relacionados

• Salidas de solver y visualización iterativa