Argmin para problema con dual sin máximo y dualidad fuerte

Argmin para problema con dual sin máximo y dualidad fuerte

de Andoni Fabricio Alvarellos Vazquez -
Número de respuestas: 3

Buenas, me queda una duda teórica. En la mayoría de los casos (incluido las clases grabadas) el problema dual se define como  \underset{\mu}{\text{ max }} \left\{ \underset{x}{\text{ inf }} L(x,\mu,)\right\} / Sin embargo en las notas está planteado el caso general  \underset{\mu}{\text{ sup }} \left\{ \underset{x}{\text{ inf }} L(x,\mu,)\right\} .


Para los casos en los que la función dual no tiene máximo, pero sí supremo, podemos obtener una solución del dual d^* , pero ese valor no se obtiene en la función dual, por lo que no existiría el multiplicador óptimo \mu^* ¿es correcto? Suponiendo que tenemos dualidad fuerte, podríamos obtener la solución del problema primal x^* como el valor que minimiza el Lagrangiano para \mu^* ¿cómo lo hacemos en este caso? ¿Tiene sentido estudiar el límite? ¿o no podemos obtenerlo? Gracias.
En respuesta a Andoni Fabricio Alvarellos Vazquez

Re: Argmin para problema con dual sin máximo y dualidad fuerte

de Matías Valdés -

Respondiendo a tu primera pregunta: sí, es correcto tu análisis. En ese caso no va a existir un multiplicador óptimo.

Con respecto a la segunda pregunta: entiendo que lo que te gustaría saber es si: minimizando el lagrangeano, se puede obtener una solución x^* del problema primal (asumiendo que la función dual tiene supremo pero no lo alcanza en ningún punto). La respuesta es que no, y una forma de verlo sería la siguiente:

1. supongamos por absurdo que la respuesta es que sí. Es decir, si x^* es el punto donde se alcanza el valor mínimo del primal, entonces existe \hat{ \mu } \geq 0 tal que: f(x^*) = \min_{x} L(x,\hat{ \mu }) .

2. Entonces, por definición de la función dual: f(x^*) = \min_{x} L(x,\hat{ \mu }) = d(\hat{ \mu }) .

3. Por otro lado, usando la dualidad débil (y el hecho de que el supremo es una cota superior), se tiene: d(\hat{ \mu }) \leq \sup_{\mu \geq 0} d(\mu) \leq \inf_{g(x) \leq 0} f(x) = f(x^*) .

4. Los puntos 2 y 3 implican la igualdad entre todos los términos de las desigualdades anteriores. En particular: d(\hat{ \mu }) = \sup_{\mu \geq 0} d(\mu) . Esto es absurdo, pues va en contra de la hipótesis de que el dual no alcanza su supremo en ningún punto (no tiene máximo).

Sobre si tiene sentido tomar límite. Probablemente sí, porque, por definición de valor supremo, se puede llegar tan cerca como se quiera de dicho valor (en este caso moviéndose en el dominio \mu \geq 0 ).

Saludos.

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

Re: Argmin para problema con dual sin máximo y dualidad fuerte

de Ignacio Ramirez -
Muy lindo análisis Matías!
Si bien no vi nada parecido (en las notas asumimos "max" para evitar estas situaciones), me pregunto si no tendrá sentido igual definir dualidad fuerte en ese sentido (de que la diferencia es arbitrariamente pequeña).
Desde el punto de vista práctico es muy útil porque la cota es un ínfimo ajustado, por lo que alcanzarlo (por ej. numéricamente) igual aseguraría la optimalidad global de la solución!
En respuesta a Matías Valdés

Re: Argmin para problema con dual sin máximo y dualidad fuerte

de Andoni Fabricio Alvarellos Vazquez -
Buenísimo, me queda claro ¡gracias!

Éste caso me quedó en el ejercicio d del obligatorio. El dual me quedo sin máximo pero tomando el supremo, esa solucion me dio igual a la solución del primal entonces tenía gap 0. En este caso, al menos, el límite de la x que anula el lagrangiano, con el \mu acercándose al valor que daría el supremo me dio el valor de x^* . Mas allá del ejercicio, de ahí la curiosidad.