Differences

This shows you the differences between two versions of the page.

--- world:kkt [2025/10/08 01:51]
rdouc [Necessary conditions and strong duality]
+++ world:kkt [2025/10/08 02:30] (current)
rdouc
@@ Line 10: / Line 10: @@
 ====== 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)
@@ Line 44: / Line 44: @@
 \end{equation}
 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^*)
@@ Line 105: / Line 105: @@
 <WRAP center round box 80%>
 __**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>
@@ Line 113: / Line 113: @@
 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
@@ Line 120: / Line 120: @@
 \end{equation}
 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
@@ Line 131: / Line 131: @@
 <WRAP center round box 80%>
 __**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>
 <hidden Click here to see the proof>
 $\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)
 $$
 so that $(x^*,\lambda^*)$ is a saddle point and this implies that the strong duality holds (as we have seen in the previous section). This concludes the proof.
-$\eproof$
-</hidden>
-<WRAP center round box 80%>
-__**Convex Farkas Lemma (extended)**__
-Let $f, h_1, \dots, h_n: \Xset \to \mathbb{R}$ be convex functions on $\Xset = \mathbb{R}^p$, and assume that there exists a **Slater point** $\tilde x \in \Xset$ such that $h_i(\tilde x) < 0$ for all $i = 1,\dots,n$.
-Then, the following are equivalent:
-  * $\{x \in \Xset : h_i(x) \le 0 \text{ for all } i, \ f(x) < 0\} = \emptyset$
-    (i.e., $f(x) \ge 0$ on the feasible set $\mcD = \{x: h_i(x) \le 0\}$).
-  * There exists $\lambda^* \ge 0$ such that
-    $$f(x) + \sum_{i=1}^n \lambda_i^* h_i(x) \ge 0, \quad \forall x \in \Xset.$$
-In other words, under Slater’s condition, if $f$ is nonnegative on the feasible set $\mcD$, then there exists a nonnegative multiplier $\lambda^*$ such that the **Lagrangian function** $x \mapsto f(x) + \sum_i \lambda_i^* h_i(x)$ is globally nonnegative on $\Xset$.
-</WRAP>
-<hidden Click here to see the corrected proof>
-$\bproof$
-Soit
-$$
-\mcD = \{x \in \Xset : h_i(x) \le 0, \ i=1,\dots,n\}.
-$$
-On suppose qu’il existe un **Slater point** $\tilde x \in \mcD$ avec $h_i(\tilde x) < 0$ pour tout $i$.
-On considère l’ensemble convexe
-$$
-U = \{u = (u_0,\dots,u_n) \in \mathbb{R}^{n+1} : \exists x \in \Xset, f(x) < u_0, \ h_i(x) \le u_i, \ i=1,\dots,n \}.
-$$
-L’hypothèse $\{x \in \mcD: f(x) < 0\} = \emptyset$ équivaut à dire que $0 \notin U$. Par le **théorème de séparation des convexes**, il existe un vecteur non nul $\phi = (\phi_0,\dots,\phi_n) \in \mathbb{R}^{n+1}$ tel que
-$$
-\phi^T u \ge 0, \quad \forall u \in U.
-$$
-Pour chaque $i \in \{0,\dots,n\}$, considérons $u + t e_i \in U$ avec $t > 0$, où $e_i$ est la base canonique. Alors $\phi^T (u + t e_i) = \phi^T u + t \phi_i \ge 0$ pour tout $t > 0$, donc $\phi_i \ge 0$.
-Ainsi, $\phi \ge 0$. De plus, $\phi_0 \neq 0$ car sinon, en évaluant l’inégalité au Slater point $\tilde x$, on aurait $\sum_{i=1}^n \phi_i h_i(\tilde x) \ge 0$ avec $\phi_i \ge 0$ et $h_i(\tilde x) < 0$, ce qui implique $\phi_i = 0$ pour tout $i$, contradiction avec $\phi \neq 0$.
-On pose donc
-$$
-\lambda_i^* = \frac{\phi_i}{\phi_0} \ge 0.
-$$
-Par construction, pour **tout $x \in \Xset$** :
-$$
-f(x) + \sum_{i=1}^n \lambda_i^* h_i(x) = \frac{1}{\phi_0} \left(\phi_0 f(x) + \sum_{i=1}^n \phi_i h_i(x)\right) \ge 0,
-$$
-car $(f(x),h_1(x),\dots,h_n(x)) \in U$ et $\phi^T u \ge 0$ pour tout $u \in U$.
-Ceci montre l’existence d’un vecteur $\lambda^* \ge 0$ tel que
-$$
-f(x) + \sum_{i=1}^n \lambda_i^* h_i(x) \ge 0 \quad \forall x \in \Xset.
-$$
 $\eproof$
 </hidden>

Welcome to Randal Douc's wiki

User Tools

Site Tools

Differences

Page Tools