DokuWiki

Strong Duality

We show Slater's condition holds for the convex optimization problem:

$\begin{eqnarray*} &\min_{A,\;\eta,\;\xi\geq 0} & \lambda_A\|A\|_* + \lambda_{\eta} \|\eta^2\| + \sum_{i=1}^m \xi_i \nonumber \\ &s.t. & s(\hat{Y}^i(w)) \geq s( \tilde{Y}^i(w)) + F(\hat{Y}^i(w), \tilde{Y}^i(w))- \xi_i \end{eqnarray*}$

Proof

Let $A$ and $\eta$ be any value, and set $\xi_i = \max\left\lbrace 1, s( \tilde{Y}^i(w)) + F(\hat{Y}^i(w), \tilde{Y}^i(w)) - s(\hat{Y}^i(w)) + 1\right\rbrace$ .

$\begin{eqnarray*} & \xi_i \geq s( \tilde{Y}^i(w)) + F(\hat{Y}^i(w), \tilde{Y}^i(w)) - s(\hat{Y}^i(w)) + 1 \\ \Rightarrow & s(\hat{Y}^i(w)) \geq s( \tilde{Y}^i(w)) + F(\hat{Y}^i(w), \tilde{Y}^i(w))- \xi_i + 1 \\ \Rightarrow & s(\hat{Y}^i(w)) > s( \tilde{Y}^i(w)) + F(\hat{Y}^i(w), \tilde{Y}^i(w))- \xi_i \end{eqnarray*}$

and also,

$\xi_i \geq 1 > 0$

.

Therefore strong duality holds ■

DokuWiki

User Tools

Site Tools

Strong Duality

Proof

Page Tools