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 [2022/10/03 00:23] rdouc |
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 105: | Line 105: | ||
| <WRAP center round box 80%> | <WRAP center round box 80%> | ||
| __**The convex Farkas lemma**__ | __**The convex Farkas lemma**__ | ||
| - | Assume that there exists a Slater point. Then, $\{f<0\} \cap \mcD =\emptyset$ iff there exists $\lambda^* \geq 0$ such that for all $x\in \mcD$, $f(x)+\sum_{i=1}^n \lambda^*_i h_i(x) \geq 0$. | + | Assume that there exists a Slater point. Then, $\{f<0\} \cap \mcD =\emptyset$ iff there exists $\lambda^* \geq 0$ such that for all $x\in \Xset$, $f(x)+\sum_{i=1}^n \lambda^*_i h_i(x) \geq 0$. |
| </WRAP> | </WRAP> | ||
| + | |||
| + | |||
| <hidden Click here to see the proof> | <hidden Click here to see the proof> | ||
| $\bproof$ | $\bproof$ | ||
| Set | Set | ||
| $$ | $$ | ||
| - | U=\{u=u_{0:n} \in \rset^{n+1}; \exists\ x \in \mcD, f(x)<u_0 \ \mbox{and} \ h_i(x)\leq u_i \mbox{ for all } i \in [1:n]\}. | + | U=\{u=u_{0:n} \in \rset^{n+1}; \exists\ x \in \Xset, f(x)<u_0 \ \mbox{and} \ h_i(x)\leq u_i \mbox{ for all } i \in [1:n]\}. |
| $$ | $$ | ||
| The condition $\{f<0\} \cap \mcD =\emptyset$ is equivalent to saying that $0 \notin U$ and since $U$ is clearly a convex set, by a separation argument, there exists a __**non-null**__ vector $\phi \in \rset^{n+1}$ such that | The condition $\{f<0\} \cap \mcD =\emptyset$ is equivalent to saying that $0 \notin U$ and since $U$ is clearly a convex set, by a separation argument, there exists a __**non-null**__ vector $\phi \in \rset^{n+1}$ such that | ||
| Line 118: | Line 120: | ||
| \end{equation} | \end{equation} | ||
| Take an arbitrary $i \in [0:n]$. | Take an arbitrary $i \in [0:n]$. | ||
| - | If $u\in U$ then $u+t e_i \in U$ where $t>0$ and $e_i=(\indiacc{k=i})_{k \in [0:n]} \in \rset^{n+1}$. The previous inequality implies $\phi^T (u+t e_i)=\phi^T u + t\phi_i \geq 0$ for all $t>0$, therefore $\phi_i\geq 0$. Now, since $\phi^T u\geq 0$ for all $u \in U$, a simple limiting argument yields for all $x\in \mcD$, | + | If $u\in U$ then $u+t e_i \in U$ where $t>0$ and $e_i=(\indiacc{k=i})_{k \in [0:n]} \in \rset^{n+1}$. The previous inequality implies $\phi^T (u+t e_i)=\phi^T u + t\phi_i \geq 0$ for all $t>0$, therefore $\phi_i\geq 0$. Now, since $\phi^T u\geq 0$ for all $u \in U$, a simple limiting argument yields for all $x\in \Xset$, |
| $$ | $$ | ||
| \phi_0 f(x)+\sum_{i=1}^n \phi_i h_i(x) \geq 0 | \phi_0 f(x)+\sum_{i=1}^n \phi_i h_i(x) \geq 0 | ||
| Line 129: | 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 \mcD$, | + | 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.1664749407.txt.gz · Last modified: 2022/10/03 00:23 by rdouc
Page Tools
