Medida de optimalidad de primer orden

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

La optimalidad de primer orden es una medida de cuán cerca está un punto de óptimo.x La mayoría de los solucionadores utilizan esta medida, aunque tiene diferentes definiciones para diferentes algoritmos.Optimization Toolbox™ 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 como 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 detalles sobre las medidas de optimalidad de primer orden para solucionadores, vea y.Optimization ToolboxOptimalidad sin restriccionesTeoría de optimalidad restringidaOptimalidad restringida en forma de Solver

Detener las reglas relacionadas con la optimalidad de primer orden

La tolerancia se relaciona con la medida de optimalidad de primer orden.OptimalityTolerance Normalmente, si la medida de optimalidad de primer orden es menor que, las iteraciones del solucionador terminan.OptimalityTolerance

Algunos solucionadores o algoritmos utilizan optimalidad de primer orden como criterio de detención.Relativa Las iteraciones del solucionador finalizan si la medida de optimalidad de primer orden es menor que la hora, donde está cualquiera:μOptimalityToleranceμ

• La norma de infinito (máximo) del gradiente de la función objetiva enx0

• La norma de infinito (máximo) de entradas para el solucionador, como o enfblinprogHquadprog

Una medida relativa intenta tener en cuenta la escala de un problema. Multiplicar una función objetiva por un número muy grande o pequeño no cambia la condición de detención para un criterio de parada relativa, pero sí lo cambia para una no escalada.

Solvers con el estado, en los detalles de los criterios de detención, cuando usan optimalidad relativa de primer orden.mensajes de salida mejorados

Optimalidad sin restricciones

Para un problema sin restricciones,

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

la medida de optimalidad de primer orden es la norma de infinito (que significa 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 familiar para una función suave para lograr 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 objetiva tiene un gradiente casi cero, por lo que la función objetiva podría estar cerca de un mínimo. Si la medida de optimalidad de primer orden no es pequeña, la función objetiva no es mínima.

Teoría de optimalidad restringida

Esta sección resume la teoría detrás de la definición de la medida de optimalidad de primer orden para los problemas restringidos. La definición que se utiliza en las funciones está en.Optimization ToolboxOptimalidad restringida en forma de Solver

Para un problema suave y restringido, deje y sea funciones vectoriales que representen todas las restricciones de desigualdad e igualdad respectivamente (lo que significa restricciones enlazadas, lineales y no lineales):gh

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

El significado de la optimalidad de primer orden en este caso es más complejo que para problemas sin restricciones. La definición se basa en el Condiciones de Karush-Kuhn-Tucker (KKT). Las condiciones KKT son análogas a la condición de que el degradado debe ser cero como mínimo, modificado para tener en cuenta las restricciones. La diferencia es que las condiciones KKT tienen problemas restringidos.

Las condiciones de KKT utilizan el auxiliar Función lagrangia:

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

(1)

λ Λ_g Y Λ_h, es el vector multiplicador 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)

Ecuación 4

La medida de optimalidad asociada a esEcuación 2

$$\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)

Ecuación 3

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

(6)

Ecuación 6 $$\overrightarrow{{\lambda }_{g,i}{g}_i}(x)$$.

La medida de optimalidad combinada es el máximo de los valores calculados en y.Ecuación 5Ecuación 6 Los solucionadores que aceptan funciones de restricción no lineal informan de infracciones g(x) > 0 O |h(x)| > 0 como violaciones.ConstraintTolerance Ver.Tolerancias y criterios de detención

Optimalidad restringida en forma de Solver

Los solucionadores de Toolbox más restringidos separan su 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 normas siguientes, que corresponden a y:Ecuación 5Ecuació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 en y es la norma de infinito (máximo).Ecuación 7Ecuación 8 Los subsubscriptores de los multiplicadores de Lagrange corresponden al solucionador de las estructuras multiplicadoras de Lagrange. Ver.Las estructuras multiplicador de Lagrange Las sumas en el rango sobre todas las restricciones.Ecuación 7 Si un límite es ±, ese término no está restringido, por lo que no es parte de la suma.Inf

Ecualidades lineales sólo

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

Los solvers reflectantes de mínimos cuadrados y de región de confianza

Para los solucionadores de mínimos cuadrados y los algoritmos de confianza-región-reflexivo, en problemas con los límites solo, la medida de optimalidad de primer orden es el máximo dei |v_i*g_i|. Aquí G_i es el componente th del degradado, es el punto actual yix

$$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 está en un límite, V_i es cero. Si X_i no está en un límite, a continuación, en un punto de minimización el degradado G_i debe ser cero. Por lo tanto, la medida de optimalidad de primer orden debe ser cero en un punto de minimización.

Temas relacionados

• Salidas de Solver y visualización iterativa