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:05] 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 135: | Line 135: | ||
| <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.1759881923.txt.gz · Last modified: 2025/10/08 02:05 by rdouc
Page Tools
