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.
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
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 enf
b
linprog
H
quadprog
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
Para un problema sin restricciones,
la medida de optimalidad de primer orden es la norma de infinito (que significa valor absoluto máximo) de ∇f(x), que es:
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.
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
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:
(1) |
Las condiciones de KKT son:
(2) |
(3) |
(4) |
La medida de optimalidad asociada a esEcuación 2
(5) |
(6) |
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
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
(7) |
(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
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
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 |vi*gi|. Aquí Gi es el componente th del degradado, es el punto actual yix
Si Xi está en un límite, Vi es cero. Si Xi no está en un límite, a continuación, en un punto de minimización el degradado Gi debe ser cero. Por lo tanto, la medida de optimalidad de primer orden debe ser cero en un punto de minimización.