Complementary Slackness duda teórica

Complementary Slackness duda teórica

de Karolina Soca Rosas -
Número de respuestas: 4

Buenas, que tal?

Tengo una duda sobre esto, leo el teórico y dice "Al haber demostrado que las desigualdades son en realidad igualdades en la prueba anterior, se deduce la condición de complementary slackness..." (pág. 8) No entiendo a qué desigualdades hace referencia, seguramente es re boba mi duda, pero no me está permitiendo entenderlo. Es decir no entiendo bajo qué condiciones puedo usar la deducción de que \mu_i g_i(x^*) = 0 .

Desde ya muchas gracias.

Saludos,

Karolina 
En respuesta a Karolina Soca Rosas

Re: Complementary Slackness duda teórica

de Matías Valdés -
Buenas.

Se refiere a las desigualdades que están inmediatamente después de la Ecuación (6).

Para probar "Complementary Slackness", las desigualdades relevantes a las que se refiere son: f(x^*) \leq f(x^*) + \sum \limits_{i=1}^M \mu_i^* g_i(x^*) + \sum \limits_{j=1}^P \lambda_j^* h_j(x^*) \leq f(x^*) . Restando f(x^*) en todos los térmnos, se deduce que:

0 \leq \sum \limits_{i=1}^M \mu_i^* g_i(x^*) + \sum \limits_{j=1}^P \lambda_j^* h_j(x^*) \leq 0 \Rightarrow \sum \limits_{i=1}^M \mu_i^* g_i(x^*) + \sum \limits_{j=1}^P \lambda_j^* h_j(x^*) = 0

Por otro lado, vos sabés que el punto x^* , donde se alcanza el óptimo del primal, cumple: h_j(x^*)=0, \, \forall \, j . Es decir que la igualdad anterior equivale a: \sum \limits_{i=1}^M \mu_i^* g_i(x^*) = 0 .

Pero además se cumple: g_i(x^*) \leq 0, \, \mu_i^* \geq 0, \, \forall \, i . Es decir que cada sumando es no positivo: \mu_i^* g_i(x^*) \leq 0, \, \forall \, i .

Es decir: estás sumando cosas que son todas de igual signo, y te está dando cero. La única posibilidad es que cada sumando sea cero: \mu_i^* g_i(x^*) = 0, \, \forall \, i .

Lo que prueba entonces es que: si se tiene dualidad fuerte, entonces la propiedad de CS es una condición (necesaria) que debe cumplir cualquier "terna óptima" x^*, \mu^*, \lambda^* .

La condición de CS es parte de las condiciones de KKT. Estas últimas son un conjunto de condiciones necesarias para que un punto sea mínimo local de un problema primal con restricciones de desigualdad.

En el libro de Bertsekas las condiciones de KKT están en la Proposición 3.3.1 (donde no asume dualidad fuerte). La presentación en el libro de Boyd (página 243) es más similar a la de las notas de teórico, ya que asume dualidad fuerte (gap de dualidad nulo).

Saludos.
Matías.
En respuesta a Matías Valdés

Re: Complementary Slackness duda teórica

de Ignacio Ramirez -
Gracias Matías. Un comentario al respecto de la conexión entre las KKT como las vimos en el tema 2 y como se ven con dualidad, porque sin dudas puede resultar confuso. La diferencia principal es en la hipótesis que nos permite pasar de condición necesaria a condición suficiente. Como lo vimos antes, se requería doble diferenciabilidad y que la Hessiana fuera definida positiva en las direcciones factibles. En este caso no se requiere eso, y alcanza con que se cumpla CS. No hay una mejor que otra, simplemente son distintas. Verificar CS puede ser difícil. Si la función no es doblemente diferenciable, tampoco se puede aplicar lo que vimos en el cap. 2. En definitiva, son dos formas alternativas de ver lo mismo.
En respuesta a Ignacio Ramirez

Re: Complementary Slackness duda teórica

de Karolina Soca Rosas -
Muchas gracias por las aclaraciones, es un tema que me resulta confuso de entender, voy a volverlo a leer y con sus explicaciones intentar procesarlo mejor.
Me queda una duda Ignacio cuando decir que son formas alternativas de ver lo mismo, en qué sentido lo decis?

Muchas gracias nuevamente.

Saludos,

Karolina
En respuesta a Karolina Soca Rosas

Re: Complementary Slackness duda teórica

de Ignacio Ramirez -

El tema de la dualidad es confuso, sí.

Mi frase no fue muy precisa. Quise decir que son formas alternativas de probar lo mismo, es decir, optimalidad de un problema con restricciones de igualdad y desigualdad. Las KKT en realidad sólo son las condiciones necesarias. Para la suficiencia tenemos dos alternativas:

* Si se cumplen las condiciones KKT y  hay diferenciabilidad doble, entonces se puede garantizar que una solución es óptima  si  la Hessiana del Lagrangeano es definida positiva en las direcciones factibles.

* Si se cumplen las KKT y se cumple Complementary Slackness, también. Esa de hecho es la más fácil de ver, y es la que se ve en este tema. No tiene mucha vuelta, es lo que dijo Matías. Es simplemente pedir que los signos de las cosas sean de tal manera que se cumpla la optimalidad sí o sí :)

Dicho lo anterior, a veces no se puede aplicar _ninguna_ de esas dos cosas, y no tenemos forma de saber si un punto es óptimo.

En esos casos, lo mejor que podemos hacer (si es que se puede hacer) es maximizar la función dual y con eso tener una cota inferior de la función de costo.

Ya que estamos aclarando, y a riesgo de oscurecer, hay que tener claro que si bien la función dual es cóncava, hallar su forma implica minimizar de manera _exacta_ el Lagrangeano para cada par (lambda,mu). A veces se puede, y a veces no.