Soluzione primaria e doppia non sono la stessa cosa

Question

Supponiamo di avere il seguente problema di ottimizzazione convessa: $$\ \min_x\psi(x) \ \ s.t. \ \phi(x) \leq 0 $$ Possiamo scrivere il problema principale come: $$\ \min_x\max_{\lambda\geq 0} \psi(x) + \lambda\phi(x) $$ e il duplice problema come: $$\ \max_{\lambda\geq 0}\min_x \psi(x) + \lambda\phi(x) $$ Diciamo $(\bar x, \bar \lambda)$ è la soluzione al problema principale e $(x^*, \lambda^*)$soluzione al doppio problema. Supponendo$\psi$ e $\phi$ non sono strettamente convesse, la soluzione primaria non deve necessariamente essere la stessa della soluzione duale cioè $x^* \neq \bar x$ e $\lambda^* \neq \bar\lambda$. Per quanto forte dualità ci dica che,$\mathcal L (\bar x, \bar \lambda) = \mathcal L(x^*, \lambda^*)$. Puoi indicarmi qualche esempio interessante per lo stesso o dare un'intuizione? Capisco che il problema non ha un punto di sella unico e quindi questo problema. Ho ancora dubbi concettuali, lo farò$(x^*, \lambda^*)$ non soddisfa le condizioni KKT per il problema di ottimizzazione vincolata originale?

Modifica: sono confuso perché spesso le persone parlano di metodi per ottenere la soluzione primaria dalla soluzione duale. Il documento a pagina 56 (Applicazione della linea del teorema di Minimax) dice che la soluzione approssimativa si trova nello scafo convesso delle doppie iterazioni. Bene, la mia domanda è: perché non prendere l'ultima iterazione di dual?

Answer 1

Le condizioni KKT del problema primario e del problema duale sono identiche se viene raggiunta la soluzione primaria. Il problema principale è:$$\ \min_x\max_{\lambda\geq 0} \psi(x) + \lambda\phi(x) \qquad(P) $$ Le sue condizioni KKT sono $\phi(x) \leq 0$ (fattibilità primaria), $\lambda\geq 0$ (doppia fattibilità) $\psi'(x) + \lambda \phi'(x)=0$ (stazionarietà) e $\lambda \phi(x)=0$ (complementarità).

Il duplice problema è: $$\ \max_{\lambda\geq 0}\min_x \psi(x) + \lambda\phi(x) \qquad(D) $$ che è equivalente a: $$\ \max_{\lambda} \min_{y\geq 0, x} \psi(x) + \lambda\phi(x) + \lambda y \qquad(D) $$ La condizione di stazionarietà è $\phi(x) + y = 0$ (cioè, $\phi(x)\leq 0$). Le condizioni di fattibilità primarie sono$\lambda \geq 0$ (altrimenti il ​​valore di $\min_{y\geq 0}$ è $-\infty$) e $\min_x \psi(x) + \lambda \phi(x)>-\infty$. Per quest'ultimo, se viene raggiunto il minimo (cioè, il problema principale può essere risolto), hai$\psi'(x) + \lambda \phi'(x)=0$. La condizione di complementarità è$\lambda y = 0$ (il che implica $\lambda \phi(x)=0$ tramite la condizione di stazionarietà).