Lien de la note Hackmd
But
Resoudre:
\[\begin{matrix} (OPT)&\text{minimiser } f(x)& \\ \text{tel que} &g_i(x)\le0&i=1,\dots,m\\ &h_j(x)=0&j=1,\dots,p \end{matrix}\]Avec $f, g_i$ convexes et $h_j$ affines
$p^{*}=$ valeur optimale $=f(x^{*})$ point optimal avec
\[\begin{aligned} f:\mathbb R^n&\to\mathbb R\\ x&\mapsto f(x) \end{aligned}\]$x$ est admissible ssi il verifie les contraintes
Lagrangien de (OPT):
\[\begin{aligned} \mathscr L:\mathbb R^n\times\mathbb R^m\times\mathbb R^p&\to\mathbb R\\ (x,\alpha,\beta)&\mapsto\mathscr L(x,\alpha,\beta)=f(x)+\sum_{i=1}^n\alpha_ig_i(x)+\sum_{j=i}^p\beta_jh_j(x) \end{aligned}\\ \begin{aligned} \alpha\in\mathbb R^m\\ \beta\in\mathbb R^p \end{aligned}\biggr\}\text{variables duales/multiplicateurs de Lagrange}\]Fonction primale et probleme primal
Fonction objective primale:
\[\theta_p(x)=\max_{\alpha,\beta \\ \alpha\ge0\Leftrightarrow \alpha_i\ge0\forall i}\mathscr L(x,\alpha,\beta)\]et probleme primal $(Q)$ \(\min_x\theta_p(x)\)
- $x$ est primal admissible ssi $g_i(x)\le0$ $\forall i$ $h_j(x)=0$ $\forall j$
- $x^{*}$ primal optimal et $p^{*}=\theta_p(x^{*})$ valeur optimale
Dans le cas ou on a une seule contrainte $g(x)\le0$ et une seule contrainte $h(x)=0$
\[\mathscr L(x,\alpha,\beta)=f(x)+\alpha g(x)+\beta h(x)\\ \begin{aligned} \underbrace{\theta_p(x)}_{\text{fonction convexe}}&=\max_{\alpha,\beta \\ \alpha\ge 0}\mathscr L(x,\alpha,\beta)\\ &=\max_{\alpha, \beta \\ \alpha\ge 0}[f(x)+\alpha g(x)+\beta h(x)]\\ &= f(x) + \max_{\alpha,\beta \\ \alpha\ge0}[\alpha g(x)+\beta h(x)] \end{aligned}\]| $g(x)\gt0\to\alpha=+\infty$ | $h(x)\neq0, \beta=signe(h(x))\infty$ |
|---|---|
| $g(x)\le0\to\alpha=0$ | $h(x)=0,$ peu importe $\beta$ |
$y=x^2$:
$\color{red}{\boxed{}}$ : lieu des points primaux admissible
Fonction duale et probleme dual
Fonction objective duale \(\theta_D(\alpha,\beta)=\min_x\mathscr L(x,\alpha,\beta)\)
et probleme dual \((D) \max_{\alpha,\beta \\ \alpha\ge0}\theta_D(\alpha,\beta)\)
$(\alpha, \beta)$ dual admissible ssi $\alpha\le0$ ($\alpha_i\ge0$ $\forall i$)
$(\alpha^{*}, \beta^{*})$ dual optimal ssi solution de $(D)$ et $d^{*}=\theta_D(\alpha^{*},\beta^{*})$
\[\begin{aligned} \underbrace{\theta_D(\alpha,\beta)}_{\text{fonction concave}} &=\min_x\mathscr L(x,\alpha,\beta)\\ &= \min_x[\underbrace{f(x)+\alpha g(x)+\beta h(x)}_{\text{affine (a } x \text{) fixe relativement a }\alpha\text{ et }\beta\text{ et }\min(\text{fcts concaves}) = \text{fct concave}}] \end{aligned}\]Lemme
Si $(\alpha,\beta) \ \alpha\ge0$ dual admissible, $\theta_D(\alpha,\beta)\le p^{*}$
Preuve
\[\begin{aligned} \theta_D(\alpha, \beta) &=\min_x\mathscr L(x, \alpha, \beta)\\ &\le\mathscr L(x^*,\alpha,\beta)=f(x^*)+\underbrace{\overbrace{\alpha}^{\ge0}\overbrace{g(x^*)}^{\le0}}_{\le0} + \overbrace{\beta h(x^*)}^{=0}\quad\begin{matrix}\text{avec }x^*\text{ primal optimal} \\ \to g(x^*)\le0\text{ et } h(x^*)=0\end{matrix}\\ &\le f(x^*)=p^* \end{aligned}\]Toutes les valeurs du probleme dual minorent la valeur optimale du probleme primal
Probleme dual \(\to\max_{\alpha,\beta \\ \alpha\ge0}\theta_D(\alpha,\beta)=d^*\le p^*\to p^*-d^*\ge0\) saut de dualite
C’est le principe de dualite faible: vrai pour tout probleme primal et dual
On aimerait ici que le saut de dualite $p^*-d^*$ soit egaux a $0\to p^*=d^*$
On peut resoudre le primal en resolvant le dual
On a cherche les conditions (“qualifications de contraintes”) pour que $p^*=d^*$.
Dans le cas ou tout est convexe:
Condition de Slater Le saut de dualite est nul s’il existe un $\tilde x$ qui est srictement admissible $(g(\tilde x)\lt0)\Leftrightarrow$ l’ensemble admissible doit avoir un point interieur
Lemme (complementarite) Si la dualite forte est verifiee, on a $\boxed{\alpha^{*}g(x^{*})=0}$
Si on a plusieurs contraintes, $\alpha^{*}_ig_i(x^{*})=0$ $\forall i$
Preuve
Dualite forte:
\[\begin{aligned} p^{*}=d^{*}&=\theta_D(\alpha^{*},\beta^{*})\\ &= \min_x\mathscr L(x,\alpha^{*},\beta^{*})\\ &\le\mathscr L(x^*,\alpha^*,\beta^*)=\underbrace{f(x^*)}_{p^*}+\underbrace{\overbrace{\alpha^*}^{\ge0}\overbrace{g(x^*)}^{\le0}}_{\le0}+\overbrace{\beta^*\underbrace{h(x^*)}_{=0}}^{=0} \end{aligned}\\ p^*\le p^*+\underbrace{\alpha^*g(x^*)}_{\le0}\to\alpha^*+g(x^*)=0\\ \begin{cases} \alpha^*\gt0&\to g(x^*)=0\\ g(x^*)\lt0&\to\alpha^*=0 \end{cases}\]Conditions de Karush-Kuhn-Tucker (KKT pour les intimes)
Conditions KKT
Conditions necessaires pour la resolution de (OPT):
\[\begin{matrix} (OPT)&\text{minimiser } f(x)& \\ \text{tel que} &g_i(x)\le0&i=1,\dots,m\\ &h_j(x)=0&j=1,\dots,p \end{matrix}\]Soient $x^{*}\in\mathbb R^n$, $\alpha^{*}\in\mathbb R^m$ et $\beta^{*}\in\mathbb R^p$ satisfait les conditions:
- Stationnarite de $\mathscr L$: \(\nabla_x\mathscr L(x^*,\alpha^*,\beta^*)=\nabla_x f(x^*)+\sum_{i=1}^n\alpha_i^*\nabla_x g_i(x^*)+\sum_{j=1}^p\beta_j^*\nabla_x h_j(x^*)=0\)
- Admissibilite primale: $g_i(x^{*})\le0$ $\forall i$ et $h_j(x^{*})=0$ $\forall j$
- Admissibilite duale: $\alpha_i^{*}\ge0$ $\forall i$
- Complementarite: $\alpha_i^{*}g_i(x^{*})=0$ $\forall i$
Alors $x^{*}$ est optimal pour le probleme primal, et $(\alpha^{*}, \beta^{*})$ optimal pour le dual.
Si de plus la dualite forte est verifiee, alors n’importe quelles solutions du primal et du dual verifient $1)-4)$
En pratique
Comment on s’en sort ?
- On ecrit le Lagrangien $\mathscr L(x,\alpha,\beta)$ et on calcule $\nabla_x\mathscr L(x,\alpha,\beta)$
- On utilise la stationnarite $\nabla_x\mathscr L(x,\alpha,\beta)=0$ pour trouver une relation entre $x$ et $\alpha/\beta$
- On remplace $x$ par $\alpha/\beta$ dans le Lagrangien $\to$ ecrire la fonction objective duale
- On resout le dual, eventuellement en se servant de la complementarite
Exemple
\[\begin{aligned} \min_{x\in\mathbb R^2}&\frac{1}{2}(x_1^2+x_2^2)\\ \text{tel que }&\underbrace{x_1-2x_2+2}_{g(x_1,x_2)}\le0 \end{aligned}\]- \[\mathscr L(x,x_2,\alpha_2)=\frac{1}{2}(x_1^2+x_2^2)+\alpha(x_1-2x_2+2)\]
- \[\begin{aligned}\nabla_x\mathscr L = 0 &\to \frac{\partial\mathscr L}{\partial x_1}=x_1+\alpha=0\to x_1=-\alpha \\ &\frac{\partial \mathscr L}{\partial x_2} = x_2-2\alpha=0\to x_2=2\alpha\end{aligned}\]
- \[\begin{aligned}\mathscr L(\alpha)(\equiv\theta_D(\alpha))&=\frac{1}{2}\biggr((-\alpha^2)+(2\alpha)^2\biggr) + \alpha(-\alpha-4\alpha+2) \\ &= \frac{5}{2}\alpha^2-5\alpha^2+2\alpha \\ &=-\frac{5}{2}\alpha^2+2\alpha\end{aligned}\]
- On resout