User Tools
world:kkt
Differences
This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision Next revision | Previous revision | ||
|
world:kkt [2026/04/08 11:34] rdouc |
world:kkt [2026/04/09 23:17] (current) rdouc |
||
|---|---|---|---|
| Line 45: | Line 45: | ||
| The rhs is called the <color red>//primal problem//</color>, while the lhs is referred to as the <color red>//dual problem//</color>. Since $x \mapsto \mcl(x,\lambda,\mu)$ is convex, the dual problem $\sup_{\lambda\geq 0,\mu}\inf_{x \in \Xset} \mcl(x,\lambda,\mu)$ is equivalent to | The rhs is called the <color red>//primal problem//</color>, while the lhs is referred to as the <color red>//dual problem//</color>. Since $x \mapsto \mcl(x,\lambda,\mu)$ is convex, the dual problem $\sup_{\lambda\geq 0,\mu}\inf_{x \in \Xset} \mcl(x,\lambda,\mu)$ is equivalent to | ||
| $$ | $$ | ||
| - | \sup \{\mcl(x,\lambda,\mu)\,:\lambda \geq 0, \mu \mbox{ and }\nabla_x \mcl(x,\lambda)=0\} | + | \sup \{\mcl(x,\lambda,\mu)\,:\lambda \geq 0, \mu \mbox{ and }\nabla_x \mcl(x,\lambda,\mu)=0\} |
| $$ | $$ | ||
| Line 144: | Line 144: | ||
| This chain of inequalities implies strong duality (see \eqref{eq:weak} for the reverse inequality). | This chain of inequalities implies strong duality (see \eqref{eq:weak} for the reverse inequality). | ||
| - | Moreover, the upper bound in the saddle point property, which holds for all $\lambda \geq 0, \mu$, implies that $h_i(x^*) \leq 0$ and $g_j(x^*) = 0$. | + | Moreover, the upper bound in the saddle point property, which holds for all $\lambda \geq 0, \mu$, implies that $\sup_{\lambda \geq 0, \mu} \mcl(x^*, \lambda, \mu) <\infty$ and hence $h_i(x^*) \leq 0$ and $g_j(x^*) = 0$. |
| Finally, choosing $\lambda = 0$ and $\mu = 0$, we obtain | Finally, choosing $\lambda = 0$ and $\mu = 0$, we obtain | ||
| $$ | $$ | ||
| - | f(x^*) = \mcl(x^*, 0, 0) \le \mcl(x, \lambda^*, \mu^*) \le f(x), \quad \forall x \in \mcD, | + | f(x^*) = \mcl(x^*, 0, 0) \le \sup_{\lambda \geq 0, \mu} \mcl(x^*, \lambda, \mu) |
| + | = \inf_{x \in \Xset} \mcl(x, \lambda^*, \mu^*) \le \mcl(x, \lambda^*, \mu^*) \le f(x), \quad \forall x \in \mcD, | ||
| $$ | $$ | ||
| which shows that $x^*$ minimizes $f$ over $\mcD$ and that $\lambda_i^* h_i(x^*) = 0$ for all $i$ where the last identity follows from the above inequality with $x=x^*$. | which shows that $x^*$ minimizes $f$ over $\mcD$ and that $\lambda_i^* h_i(x^*) = 0$ for all $i$ where the last identity follows from the above inequality with $x=x^*$. | ||
| Line 171: | Line 172: | ||
| g_j(x) = a_j^T x - b_j, \quad j=1,\dots,m. | g_j(x) = a_j^T x - b_j, \quad j=1,\dots,m. | ||
| $$ | $$ | ||
| - | Without loss of generality, we assume that $(a_j)_{1\leq j \leq m}$ are \textbf{linearly independent}. | + | Without loss of generality, we assume that $(a_j)_{1\leq j \leq m}$ are **linearly independent**. |
| We define the set $U$ as | We define the set $U$ as | ||
| $$ | $$ | ||
world/kkt.1775640871.txt.gz · Last modified: 2026/04/08 11:34 by rdouc
Page Tools
