Diferencia entre las condiciones Fritz John y Karush-Kuhn-Tucker

Question

Soy estudiante de Informática y actualmente estoy aprendiendo sobre optimización. Hemos conocido las condiciones de Fritz-John y Karush-Kuhn-Tucker para las optimizaciones convexas.

Creo que entiendo lo que quieren decir, en el sentido de que estas condiciones tienen que cumplirse para que un punto sea un óptimo.

Sin embargo, no entiendo realmente el diferencia entre ambos y mis apuntes de clase no son muy buenos para dejar clara esta diferencia. De hecho, soy alérgico a la notación matemática, así que agradecería una respuesta concisa y breve en inglés sencillo, quizá con un ejemplo.

Gracias.

Answer 1

Ambos conjuntos de condiciones son necesarios para que un punto sea óptimo, pero no son exactamente lo mismo desde el punto de vista matemático. Las condiciones KKT son más restrictivas y, por lo tanto, reducen la clase de puntos (a partir de los que satisfacen las condiciones de Fritz John) que deben comprobarse para determinar la optimalidad. La restricción adicional con KKT es que el multiplicador de Lagrange en el gradiente de la función objetivo no puede ser cero. Una de las diferencias resultantes más importantes es que los puntos KKT para programas lineales deben ser óptimos, mientras que los puntos Fritz John para programas lineales no tienen por qué serlo.

La sección sobre Condiciones KKT en Bazarra, Sherali y Shetty's Programación no lineal: Teoría y Algoritmos (segunda edición) tiene una buena discusión de los temas. Hay varios ejemplos buenos, especialmente uno en el que se demuestra que un punto de Fritz John para un programa lineal no es óptimo. Eso no puede ocurrir con los puntos KKT para programas lineales.

Answer 2

La diferencia crucial entre los dos conjuntos de condiciones de optimalidad es que cuando hay al menos una restricción no lineal, debe satisfacerse una condición de cualificación de la restricción (CQ) para que las condiciones KKT sean necesarias para la optimalidad. Las condiciones de Fritz-John se mantienen en cualquier minimizador local independientemente de si se cumple o no una CQ. Consideremos, por ejemplo $$ \min_x \ x \quad \text{s.t.} \ x^2 = 0. $$ La (única) solución es claramente $x^*=0$ (es el único punto factible). Ahora escriba las condiciones de Fritz-John y las condiciones KKT una al lado de la otra. Las condiciones KKT no tienen solución, es decir, es imposible encontrar multiplicadores de Lagrange para que se satisfagan en $x^*=0$ . Pero puedes encontrar multiplicadores Fritz-John (poniendo el multiplicador objetivo a cero).

Las condiciones de Fritz-John son útiles para demostrar que un problema es degenerado (es decir, que no satisface una CQ). Si se obliga a fijar el multiplicador del gradiente del objetivo en cero, se tiene algo como $$ J_E(x)^T y_E + J_I(x)^T y_I = 0, \quad (c_I(x), y_I) \geq 0, \quad c_I(x) \cdot y_I = 0, \quad c_E(x) = 0 $$ donde $J_E$ es el jacobiano de las restricciones de igualdad ( $c_E(x)=0$ ), $J_I$ es el jacobiano de las restricciones de desigualdad ( $c_I(x) \geq 0$ ), $y_E$ son los multiplicadores de las restricciones de igualdad y $y_I \geq 0$ son los multiplicadores de las restricciones de desigualdad. Mi notación $c_I(x) \cdot y_I = 0$ significa que el producto desaparece en sus componentes.

Ahora es posible demostrar que, si al menos uno de los $y$ es distinto de cero, esto demuestra que la calificación de la restricción de Magasarian y Fromovitz (MFCQ) no se cumple en $x$ . Para ello se utiliza el lema de Farkas o el teorema de Motzkin de la alternativa (véase, por ejemplo, el libro "Nonlinear Programming" de Olvi Mangasarian, publicado por SIAM, para esos teoremas). Por lo tanto, tampoco se cumple la cualificación más fuerte de la restricción de independencia lineal (LICQ).

Answer 3

Las condiciones Fritz John o las condiciones John proporcionan más información sobre el problema que las condiciones KKT. Además, se puede demostrar que el multiplicador asociado al gradiente de la función objetivo es 1 en las condiciones de John a partir de las condiciones del propio problema. Este hecho es cierto a menos que se tenga una situación muy patológica en la que sólo haya un punto en el conjunto factible. Las condiciones KKT son un corolario fácil de las condiciones de John.

Obsérvese que para un determinado mínimo local puede haber más de un conjunto de multiplicadores de John que le corresponda. Además, hay que tener en cuenta que si la calificación de la restricción de Mangasarian-Fromovitz falla, siempre tenemos un vector de multiplicadores de John con el multiplicador correspondiente a la función objetivo es cero. Por lo tanto, cualquier calificación de la restricción que sea más débil que Mangasarian-Fromovitz, como la CQ de Guignard o Abadie, sólo puede mostrar que existe un conjunto de multiplicadores de John con el multiplicador asociado al gradiente del objetivo que es uno. Nunca pueden garantizar que todos los multiplicadores de John sean multiplicadores KKT. Por lo tanto, las condiciones de John deberían desempeñar un papel más importante en la optimización que las de KKT. Sin embargo, apenas se menciona. Echa un vistazo al hermoso libro OPTIMIZATION : INSIGHTS AND APPLICATIONS de Brinkhuis y Tihkomirov publicado por Princeton University Press. Una vez que lea el libro se dará cuenta del verdadero poder de las condiciones de John. Cuando se empieza con el tema más allá de MFCQ no hay que pensar mucho en las calificaciones de las restricciones. Tenga en cuenta que si MFCQ falla no significa que no haya un vector de multiplicadores de John con los multiplicadores asociados al gradiente del objetivo como uno. Típicamente se puede obtener un multiplicador de John con el multiplicador asociado al objetivo como 1 independientemente de la satisfacción de cualquier CQ o no. Este es el hecho central de la optimización y las condiciones de John son lo principal.

Joydeep Dutta IIT Kanpur, India

Answer 4

Las condiciones son matemáticamente las mismas, enunciadas de forma diferente. La forma en que KKT establece las condiciones facilita la búsqueda de un conjunto de puntos que satisfagan las condiciones de optimalidad necesarias y sean potencialmente los puntos óptimos locales del problema.

Pero si para un punto concreto se quiere ver si puede ser un óptimo local, entonces es fácil verificar las condiciones de Fritz-John. La razón es que se sabe qué restricciones están activas o inactivas.