원시 및 이중 솔루션이 동일하지 않음

Question

다음과 같은 볼록 최적화 문제가 있다고 가정합니다. $$\ \min_x\psi(x) \ \ s.t. \ \phi(x) \leq 0 $$ 원시 문제를 다음과 같이 작성할 수 있습니다. $$\ \min_x\max_{\lambda\geq 0} \psi(x) + \lambda\phi(x) $$ 이중 문제는 다음과 같습니다. $$\ \max_{\lambda\geq 0}\min_x \psi(x) + \lambda\phi(x) $$ 의 말을하자 $(\bar x, \bar \lambda)$ 원초적 문제에 대한 해결책이며 $(x^*, \lambda^*)$이중 문제에 대한 해결책. 가정$\psi$ 과 $\phi$ 엄격하게 볼록하지 않습니다. 원시 솔루션은 이중 솔루션과 동일 할 필요가 없습니다. $x^* \neq \bar x$ 과 $\lambda^* \neq \bar\lambda$. 그러나 강력한 이중성은 우리에게 말합니다.$\mathcal L (\bar x, \bar \lambda) = \mathcal L(x^*, \lambda^*)$. 저에게 동일한 것에 대한 흥미로운 예를 알려주거나 직감을 줄 수 있습니까? 나는 문제가 독특한 안장 포인트가 없기 때문에이 문제를 이해합니다. 나는 여전히 개념적 의구심이 있습니다.$(x^*, \lambda^*)$ 원래 제약 된 최적화 문제에 대한 KKT 조건을 충족하지 않습니까?

편집 : 사람들이 종종 이중 솔루션에서 원시 솔루션을 얻는 방법에 대해 이야기하기 때문에 혼란 스럽습니다. Paper Page 56 (Applying Minimax theorem line)은 근사 솔루션이 이중 반복의 볼록 껍질에 있음을 알려줍니다. 내 질문은 왜 이중의 마지막 반복을하지 않는 것입니까?

Answer 1

Primal 솔루션이 얻어지면 Primal과 Dual 문제의 KKT 조건은 동일합니다. 근본적인 문제는 다음과 같습니다.$$\ \min_x\max_{\lambda\geq 0} \psi(x) + \lambda\phi(x) \qquad(P) $$ KKT 조건은 다음과 같습니다. $\phi(x) \leq 0$ (원시적 타당성), $\lambda\geq 0$ (이중 타당성) $\psi'(x) + \lambda \phi'(x)=0$ (정상 성) 및 $\lambda \phi(x)=0$ (상보성).

이중 문제는 다음과 같습니다. $$\ \max_{\lambda\geq 0}\min_x \psi(x) + \lambda\phi(x) \qquad(D) $$ 이는 다음과 같습니다. $$\ \max_{\lambda} \min_{y\geq 0, x} \psi(x) + \lambda\phi(x) + \lambda y \qquad(D) $$ 정상 상태는 다음과 같습니다. $\phi(x) + y = 0$ (즉, $\phi(x)\leq 0$). 원시 타당성 조건은 다음과 같습니다.$\lambda \geq 0$ (그렇지 않은 경우 $\min_{y\geq 0}$ 이다 $-\infty$) 및 $\min_x \psi(x) + \lambda \phi(x)>-\infty$. 후자의 경우 최소값에 도달하면 (즉, 원시 문제를 해결할 수 있음)$\psi'(x) + \lambda \phi'(x)=0$. 상보성 조건은 다음과 같습니다.$\lambda y = 0$ (이는 $\lambda \phi(x)=0$ 정상 상태를 통해).