Primal ve Dual Solution aynı değil

Question

Diyelim ki, aşağıdaki dışbükey optimizasyon problemimiz var: $$\ \min_x\psi(x) \ \ s.t. \ \phi(x) \leq 0 $$ İlk problemi şu şekilde yazabiliriz: $$\ \min_x\max_{\lambda\geq 0} \psi(x) + \lambda\phi(x) $$ ve ikili problem şu şekildedir: $$\ \max_{\lambda\geq 0}\min_x \psi(x) + \lambda\phi(x) $$ Diyelimki $(\bar x, \bar \lambda)$ birincil problemin çözümü ve $(x^*, \lambda^*)$ikili soruna çözüm. Varsayım$\psi$ ve $\phi$ kesinlikle dışbükey değildir, birincil çözümün ikili çözümle aynı olması gerekmez, yani $x^* \neq \bar x$ ve $\lambda^* \neq \bar\lambda$. Ancak güçlü dualite bize şunu söyler:$\mathcal L (\bar x, \bar \lambda) = \mathcal L(x^*, \lambda^*)$. Aynı şey için beni ilginç bir örneğe yönlendirebilir misin veya bir sezgi verebilir misin? Sorunun benzersiz bir eyer noktası olmadığını ve dolayısıyla bu sorunu anlıyorum. Hala kavramsal şüphelerim var$(x^*, \lambda^*)$ orijinal kısıtlı optimizasyon problemi için KKT koşullarını karşılamıyor mu?

Düzenleme: Kafam karıştı çünkü insanlar genellikle ikili çözümden birincil çözüm elde etme yöntemlerinden bahsediyorlar. Kağıt Sayfası 56 (Minimax teorem çizgisinin uygulanması), yaklaşık çözümün çift yinelemelerin dışbükey kabuğunda olduğunu söyler. Peki benim sorum neden dual'in son yinelemesini almıyoruz?

Answer 1

İlkel ve ikili problemin KKT koşulları, ilk çözüme ulaşılırsa aynıdır. Temel sorun şudur:$$\ \min_x\max_{\lambda\geq 0} \psi(x) + \lambda\phi(x) \qquad(P) $$ KKT koşulları $\phi(x) \leq 0$ (birincil fizibilite), $\lambda\geq 0$ (ikili fizibilite) $\psi'(x) + \lambda \phi'(x)=0$ (durağanlık) ve $\lambda \phi(x)=0$ (tamamlayıcılık).

İkili sorun şudur: $$\ \max_{\lambda\geq 0}\min_x \psi(x) + \lambda\phi(x) \qquad(D) $$ şuna eşdeğerdir: $$\ \max_{\lambda} \min_{y\geq 0, x} \psi(x) + \lambda\phi(x) + \lambda y \qquad(D) $$ Durağanlık koşulu $\phi(x) + y = 0$ (yani, $\phi(x)\leq 0$). İlk fizibilite koşulları$\lambda \geq 0$ (aksi takdirde değeri $\min_{y\geq 0}$ dır-dir $-\infty$) ve $\min_x \psi(x) + \lambda \phi(x)>-\infty$. İkincisi için, eğer minimum seviyeye ulaşılırsa (yani, temel problem çözülebilirse),$\psi'(x) + \lambda \phi'(x)=0$. Tamamlayıcılık koşulu:$\lambda y = 0$ (Hangi ima $\lambda \phi(x)=0$ durağanlık koşulu ile).