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.

Medida de optimización de primer orden

¿Qué es la medida de optimización de primer orden?

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

  • La medida de optimización de primer orden debe ser cero como mínimo.

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

Para obtener información general sobre la optimización de primer orden, consulte Nocedal y Wright [31]. Para obtener información específica acerca de las medidas de optimización de primer orden para los solucionadores de Optimization Toolbox , consulte Optimización no restringida, Teoría de la optimalidad restringiday Optimización restringida en forma de Solver.

Detener reglas relacionadas con la optimización de primer orden

La tolerancia OptimalityTolerance se relaciona con la medida de optimización de primer orden. Normalmente, si la medida de optimización de primer orden es menor que OptimalityTolerance, las iteraciones de Solver terminan.

Algunos solucionadores o algoritmos utilizan la optimalidad de primer orden de Relativa como criterio de parada. Las iteraciones de Solver terminan si la medida de optimización de primer orden es menor que μ veces OptimalityTolerance, donde μ es cualquiera de las dos:

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

  • La norma Infinity (máximo) de insumos al Solver, como f o b en linprog o H en quadprog

Una medida relativa intenta explicar la magnitud de un problema. La multiplicación de 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 detención relativo, pero sí la cambia por una sin escala.

Los solucionadores con estado mensajes de salida mejorados , en los detalles de los criterios de detención, cuando utilizan la optimización relativa de primer orden.

Optimización no restringida

Para un problema sin restricciones,

minxf(x),

la medida de optimización de primer orden es la norma de infinito (que significa el valor absoluto máximo) de f(x), que es:

first-order optimality measure = maxi|(f(x))i|=f(x).

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 optimización de primer orden es casi nula, la función objetiva tiene un gradiente casi nulo, por lo que la función objetiva podría estar cerca de un mínimo. Si la medida de optimización de primer orden no es pequeña, la función objetiva no es mínima.

Teoría de la optimalidad restringida

Esta sección resume la teoría detrás de la definición de la medida de la optimización de primer orden para los problemas limitados. La definición que se usa en las funciones de Optimization Toolbox es en Optimización restringida en forma de Solver.

Para un problema restringido sin problemas, deje que g y h sean funciones vectoriales que representen todas las restricciones de desigualdad e igualdad, respectivamente (restricciones de significado, lineal e inlineal):

minxf(x) subject to g(x)0, h(x)=0.

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

Las condiciones KKT utilizan el auxiliar Función Lagrange:

L(x,λ)=f(x)+λg,igi(x)+λh,ihi(x).(1)
El vector λ, que es la concatenación de Λg Y Λh, es el vector multiplicador de Lagrange. Su longitud es el número total de restricciones.

Las condiciones KKT son:

xL(x,λ)=0,(2)
λg,igi(x)=0 i,(3)
{g(x)0,h(x)=0,λg,i0.(4)
Los solucionadores no utilizan las tres expresiones en Ecuación 4 en el cálculo de la medida de la optimización.

La medida de la optimación asociada a Ecuación 2 es

xL(x,λ=f(x)+λg,igi(x)+λh,ihh,i(x).(5)
La medida de la optimación asociada a Ecuación 3 es
λgg(x),(6)
donde la norma en Ecuación 6 significa la norma de infinito (máximo) del vector λg,igi(x).

La medida de optimización combinada es el máximo de los valores calculados en Ecuación 5 y Ecuación 6. Los solucionadores que aceptan funciones de restricción no lineales reportan infracciones de restricción g(x) > 0 o |h(x)| > 0 como violaciones ConstraintTolerance . Véase Tolerancias y criterios de parada.

Optimización restringida en forma de Solver

La mayoría de los solucionadores de cajas de herramientas restringidos separan su cálculo de la medida de optimización 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 Ecuación 5 y Ecuación 6:

xL(x,λ=f(x)+ATλineqlin+AeqTλeqlin                       +λineqnonlin,ici(x)+λeqnonlin,iceqi(x),(7)
|lixi|λlower,i,|xiui|λupper,i,|(Axb)i|λineqlin,i,|ci(x)|λineqnonlin,i,(8)

donde la norma de los vectores en Ecuación 7 y Ecuación 8 es la norma de infinito (máximo). Los subíndices de los multiplicadores de Lagrange corresponden a las estructuras de multiplicador de Lagrange de Solver. Véase Estructuras multiplicadoras de Lagrange. Las adiciones en Ecuación 7 gama 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.

Sólo las igualdades lineales

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

Limitadores mínimos y confianza-región-solucionadores reflexivos

Para los resolutores de mínimos cuadrados y los algoritmos de confianza-región-reflexivo, en problemas con límites solo, la medida de optimización de primer orden es el máximo sobre i de |vi*gi|. Aquí Gi es el componente ith del gradiente, x es el punto actual, y

vi={|xibi|if the negative gradient points toward bound bi1otherwise.

Si xi está en un límite, Vi es cero. Si xi no está en un límite, entonces en un punto de minimización el gradiente Gi debe ser cero. Por lo tanto la medida de la optimización del primero-orden debe ser cero en un punto de minimización.