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 [2025/10/08 02:01] rdouc [Necessary conditions and strong duality] |
world:kkt [2025/10/08 02:30] (current) rdouc |
||
|---|---|---|---|
| Line 10: | Line 10: | ||
| ====== Weak duality ====== | ====== Weak duality ====== | ||
| - | Let $f$ and $(h_i)_{1 \leq i \leq n}$ be convex differentiable functions on $\Xset=\rset^p$. Let $\mcD=\cap_{i=1}^n \{h_i \leq 0\}\neq \emptyset$ and note that by convexity of the functions $h_i$, the set $\mcD$ is actually a convex set. We are interested in the infimum of the convex function $f$ on the convex set $\mcD$. Define the Lagrange function | + | Let $f$ and $(h_i)_{1 \leq i \leq n}$ be convex differentiable functions on $\Xset=\rset^p$ with $\lim_{|x| \to \infty} f(x)=\infty$. Let $\mcD=\cap_{i=1}^n \{h_i \leq 0\}\neq \emptyset$ and note that by convexity of the functions $h_i$, the set $\mcD$ is actually a convex set. We are interested in the infimum of the convex function $f$ on the convex set $\mcD$. Define the Lagrange function |
| $$ | $$ | ||
| \mcl(x,\lambda)=f(x)+\sum_{i=1}^n \lambda_i h_i(x) | \mcl(x,\lambda)=f(x)+\sum_{i=1}^n \lambda_i h_i(x) | ||
| Line 44: | Line 44: | ||
| \end{equation} | \end{equation} | ||
| and for all $i \in [1:n]$, we have either $\lambda^*_i=0$ or $h_i(x^*)=0$ . | and for all $i \in [1:n]$, we have either $\lambda^*_i=0$ or $h_i(x^*)=0$ . | ||
| - | Then, the strong duality holds and | + | Then, the <color /yellow>strong duality holds</color> and |
| $$ | $$ | ||
| f(x^*)=\inf_{x \in \mcD} f(x)=\mcl(x^*,\lambda^*) | f(x^*)=\inf_{x \in \mcD} f(x)=\mcl(x^*,\lambda^*) | ||
| Line 131: | Line 131: | ||
| <WRAP center round box 80%> | <WRAP center round box 80%> | ||
| __**The necessary condition**__ | __**The necessary condition**__ | ||
| - | Assume that $f(x^*)=\inf_{x\in \mcD} f(x)$ for some $x^* \in\mcD$ and that there exists a Slater point. Then there exist $\lambda^* \geq 0$ such that $(x^*,\lambda^*)$ is a saddle point and by the Saddle point lemma, the strong duality holds. | + | Assume that $f(x^*)=\inf_{x\in \mcD} f(x)$ for some $x^* \in\mcD$ and that there exists a Slater point. Then there exist $\lambda^* \geq 0$ such that $(x^*,\lambda^*)$ is a saddle point and by the Saddle point lemma, the <color /yellow>strong duality holds</color>. |
| </WRAP> | </WRAP> | ||
| <hidden Click here to see the proof> | <hidden Click here to see the proof> | ||
| $\bproof$ | $\bproof$ | ||
| - | Assume now that $f(x^*)=\inf_{x\in \mcD} f(x)$ for some $x^* \in\mcD$. Then, $\{f-f(x^*)<0\} \cap \mcD =\emptyset$ so that there exists $\lambda^* \geq 0$ satisfying for all $x\in \mcD$, $f(x)-f(x^*)+\sum_{i=1}^n \lambda^*_i h_i(x) \geq 0$. And this implies that $(x^*,\lambda^*)$ is a saddle point since: for all $\lambda \geq 0$ and $x \in \Xset$, | + | Assume now that $f(x^*)=\inf_{x\in \mcD} f(x)$ for some $x^* \in\mcD$. Then, $\{f-f(x^*)<0\} \cap \mcD =\emptyset$ so that there exists $\lambda^* \geq 0$ satisfying for all $x\in \Xset$, $f(x)-f(x^*)+\sum_{i=1}^n \lambda^*_i h_i(x) \geq 0$. And this implies that $(x^*,\lambda^*)$ is a saddle point since: for all $\lambda \geq 0$ and $x \in \Xset$, |
| $$ | $$ | ||
| f(x^*)+\sum_{i=1}^n \lambda_i h_i(x^*) \leq f(x^*) \leq f(x)+\sum_{i=1}^n \lambda^*_i h_i(x) | f(x^*)+\sum_{i=1}^n \lambda_i h_i(x^*) \leq f(x^*) \leq f(x)+\sum_{i=1}^n \lambda^*_i h_i(x) | ||
world/kkt.1759881661.txt.gz · Last modified: 2025/10/08 02:01 by rdouc
Page Tools
