Lien de la note Hackmd

But

Resoudre:

$$\begin{array}{ccc}(OPT)& \text{minimiser }f(x)& \\ \text{tel que}& g_i(x)\le 0& i=1,\dots ,m\\ & h_j(x)=0& j=1,\dots ,p\end{array}$$

Avec

$f,g_i$ convexes et

$h_j$ affines

$p^{\text{*}}=$ valeur optimale

$=f(x^{\text{*}})$ point optimal avec

$$\begin{array}{rl}f:{\mathbb{R}}^n& \to \mathbb{R}\\ x& \mapsto f(x)\end{array}$$

$x$ est admissible ssi il verifie les contraintes

Lagrangien de (OPT):

$$\begin{gathered} \begin{array}{rl}\mathcal{L}:{\mathbb{R}}^n\times {\mathbb{R}}^m\times {\mathbb{R}}^p& \to \mathbb{R}\\ (x,\alpha ,\beta )& \mapsto \mathcal{L}(x,\alpha ,\beta )=f(x)+\sum _{i=1}^n{\alpha }_i{g}_i(x)+\sum _{j=i}^p{\beta }_j{h}_j(x)\end{array} \\ \begin{array}{r}\alpha \in {\mathbb{R}}^m\\ \beta \in {\mathbb{R}}^p\end{array}\}\text{variables duales/multiplicateurs de Lagrange} \end{gathered}$$

Fonction primale et probleme primal

Fonction objective primale:

$$\begin{gathered} {\theta }_p(x)=\underset{\alpha ,\beta \\ \alpha \ge 0\iff {\alpha }_i\ge 0\mathrm{\forall }i}{max}\mathcal{L}(x,\alpha ,\beta ) \end{gathered}$$

et probleme primal

$(Q)$

$$\underset{x}{min}{\theta }_p(x)$$

• $x$ est primal admissible ssi
  $g_i(x)\le 0$
  $\mathrm{\forall }i$
  $h_j(x)=0$
  $\mathrm{\forall }j$
• $x^{\text{*}}$ primal optimal et
  $p^{\text{*}}={\theta }_p(x^{\text{*}})$ valeur optimale

Dans le cas ou on a une seule contrainte

$g(x)\le 0$ et une seule contrainte

$h(x)=0$

$$\begin{gathered} \mathcal{L}(x,\alpha ,\beta )=f(x)+\alpha g(x)+\beta h(x) \\ \begin{array}{rl}\underset{\text{fonction convexe}}{\underbrace{{\theta }_p(x)}}& =\underset{\alpha ,\beta \\ \alpha \ge 0}{max}\mathcal{L}(x,\alpha ,\beta )\\ & =\underset{\alpha ,\beta \\ \alpha \ge 0}{max}[f(x)+\alpha g(x)+\beta h(x)]\\ & =f(x)+\underset{\alpha ,\beta \\ \alpha \ge 0}{max}[\alpha g(x)+\beta h(x)]\end{array} \end{gathered}$$

$g(x)>0\to \alpha =+\mathrm{\infty }$	$h(x)\ne 0,\beta =signe(h(x))\mathrm{\infty }$
$g(x)\le 0\to \alpha =0$	$h(x)=0,$ peu importe $\beta$

$$\begin{gathered} {\theta }_p(x)=f(x)+\{\begin{array}{ll}0& \text{si }g(x)\le 0\text{ et }h(x)=0\\ +\mathrm{\infty }& \text{sinon}\end{array} \\ \iff x\text{ primal admissible} \end{gathered}$$

$y=x^2$:

$$\begin{array}{rl}minf(x)& ={\mathrm{\infty }}^2\\ x+1& \le 0\end{array}$$

$\text{color}red\boxed{{\displaystyle }}$ : lieu des points primaux admissible

Fonction duale et probleme dual

Fonction objective duale

$${\theta }_D(\alpha ,\beta )=\underset{x}{min}\mathcal{L}(x,\alpha ,\beta )$$

et probleme dual

$$\begin{gathered} (D)\underset{\alpha ,\beta \\ \alpha \ge 0}{max}{\theta }_D(\alpha ,\beta ) \end{gathered}$$

$(\alpha ,\beta )$ dual admissible ssi

$\alpha \le 0$ (

${\alpha }_i\ge 0$

$\mathrm{\forall }i$)

$({\alpha }^{\text{*}},{\beta }^{\text{*}})$ dual optimal ssi solution de

$(D)$ et

$d^{\text{*}}={\theta }_D({\alpha }^{\text{*}},{\beta }^{\text{*}})$

$$\begin{array}{rl}\underset{\text{fonction concave}}{\underbrace{{\theta }_D(\alpha ,\beta )}}& =\underset{x}{min}\mathcal{L}(x,\alpha ,\beta )\\ & =\underset{x}{min}[\underset{\text{affine (a }x\text{) fixe relativement a }\alpha \text{ et }\beta \text{ et }min(\text{fcts concaves})=\text{fct concave}}{\underbrace{f(x)+\alpha g(x)+\beta h(x)}}]\end{array}$$

Lemme

Si

$$\begin{gathered} (\alpha ,\beta ) \\ \alpha \ge 0 \end{gathered}$$ dual admissible,

${\theta }_D(\alpha ,\beta )\le p^{\text{*}}$

Preuve

$$\begin{array}{rl}{\theta }_D(\alpha ,\beta )& =\underset{x}{min}\mathcal{L}(x,\alpha ,\beta )\\ & \le \mathcal{L}(x^{\ast },\alpha ,\beta )=f(x^{\ast })+\underset{\le 0}{\underbrace{\stackrel{\ge 0}{\overbrace{\alpha }}\stackrel{\le 0}{\overbrace{g(x^{\ast })}}}}+\stackrel{=0}{\overbrace{\beta h(x^{\ast })}}\begin{array}{c}\text{avec }{x}^{\ast }\text{ primal optimal}\\ \to g(x^{\ast })\le 0\text{ et }h(x^{\ast })=0\end{array}\\ & \le f(x^{\ast })=p^{\ast }\end{array}$$

Toutes les valeurs du probleme dual minorent la valeur optimale du probleme primal

Probleme dual

$$\begin{gathered} \to \underset{\alpha ,\beta \\ \alpha \ge 0}{max}{\theta }_D(\alpha ,\beta )=d^{\ast }\le p^{\ast }\to p^{\ast }-d^{\ast }\ge 0 \end{gathered}$$ 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^{\ast }-d^{\ast }$ soit egaux a

$0\to p^{\ast }=d^{\ast }$

On peut resoudre le primal en resolvant le dual

On a cherche les conditions ("qualifications de contraintes") pour que

$p^{\ast }=d^{\ast }$.

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})<0)\iff$ l'ensemble admissible doit avoir un point interieur

Lemme (complementarite)
Si la dualite forte est verifiee, on a

$\boxed{{\displaystyle {\alpha }^{\text{*}}g(x^{\text{*}})=0}}$

Si on a plusieurs contraintes,

${\alpha }_i^{\text{*}}{g}_i(x^{\text{*}})=0$

$\mathrm{\forall }i$

Preuve

Dualite forte:

$$\begin{gathered} \begin{array}{rl}{p}^{\ast }=d^{\ast }& ={\theta }_D({\alpha }^{\ast },{\beta }^{\ast })\\ & =\underset{x}{min}\mathcal{L}(x,{\alpha }^{\ast },{\beta }^{\ast })\\ & \le \mathcal{L}(x^{\ast },{\alpha }^{\ast }{\beta }^{\ast })=\underset{p^{\ast }}{\underbrace{f(x^{\ast })}}+\underset{\le 0}{\underbrace{\stackrel{\ge 0}{\overbrace{{\alpha }^{\ast }}}\stackrel{\le 0}{\overbrace{g(x^{\ast })}}}}+\stackrel{=0}{\overbrace{{\beta }^{\ast }\underset{=0}{\underbrace{h(x^{\ast })}}}}\end{array} \\ {p}^{\ast }\le p^{\ast }+\underset{\le 0}{\underbrace{{\alpha }^{\ast }}}\to {\alpha }^{\ast }+g(x^{\ast })=0 \\ \{\begin{array}{ll}{\alpha }^{\ast }>0& \to g(x^{\ast })=0\\ g(x^{\ast })<0& \to {\alpha }^{\ast }=0\end{array} \end{gathered}$$

Conditions de Karush-Kuhn-Tucker (KKT pour les intimes)

Conditions KKT

Conditions necessaires pour la resolution de (OPT):

$$\begin{array}{ccc}(OPT)& \text{minimiser }f(x)& \\ \text{tel que}& g_i(x)\le 0& i=1,\dots ,m\\ & h_j(x)=0& j=1,\dots ,p\end{array}$$

Soient

$x^{\text{*}}\in {\mathbb{R}}^n$,

${\alpha }^{\text{*}}\in {\mathbb{R}}^m$ et

${\beta }^{\text{*}}\in {\mathbb{R}}^p$ satisfait les conditions:

1. Stationnarite de
   $\mathcal{L}$:
   $${\mathrm{\nabla }}_x\mathcal{L}(x^{\ast },{\alpha }^{\ast },{\beta }^{\ast })={\mathrm{\nabla }}_{x}f(x^{\ast })+\sum _{i=1}^n{\alpha }_i^{\ast }\mathrm{\nabla }{g}_i(x^{\ast })+\sum _{j=1}^p{\beta }_j^{\ast }{\mathrm{\nabla }}_{x}h(x^{\ast })=0$$
2. Admissibilite primale:
   $g_i(x^{\text{*}})\le 0$
   $\mathrm{\forall }i$ et
   $h_j(x^{\text{*}})=0$
   $\mathrm{\forall }j$
3. Admissibilite duale:
   ${\alpha }_i^{\text{*}}\ge 0$
   $\mathrm{\forall }i$
4. Complementarite:
   ${\alpha }_i^{\text{*}}{g}_i(x^{\text{*}})=0$
   $\mathrm{\forall }i$

Alors

$x^{\text{*}}$ est optimal pour le probleme primal, et

$({\alpha }^{\text{*}},{\beta }^{\text{*}})$ 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 ?

1. On ecrit le Lagrangien
   $\mathcal{L}(x,\alpha ,\beta )$ et on calcule
   ${\mathrm{\nabla }}_x\mathcal{L}(x,\alpha ,\beta )$
2. On utilise la stationnarite
   ${\mathrm{\nabla }}_x\mathcal{L}(x,\alpha ,\beta )=0$ pour trouver une relation entre
   $x$ et
   $\alpha /\beta$
3. On remplace
   $x$ par
   $\alpha /\beta$ dans le Lagrangien
   $\to$ ecrire la fonction objective duale
4. On resout le dual, eventuellement en se servant de la complementarite

Exemple

$$\begin{array}{rl}\underset{x\in {\mathbb{R}}^2}{min}& \frac{1}{2}(x_1^2+x_2^2)\\ \text{tel que }& \underset{g(x_1,x_2)}{\underbrace{x_1-2x_2+2}}\le 0\end{array}$$

1. $$\mathcal{L}(x,x_2,{\alpha }_2)=\frac{1}{2}(x_1^2+x_2^2)+\alpha (x_1-2x_2+2)$$
2. $$\begin{array}{rl}{\mathrm{\nabla }}_x\mathcal{L}=0& \to \frac{\partial \mathcal{L}}{\partial x_1}=x_1+\alpha =0\to x_1=-\alpha \\ & \frac{\partial \mathcal{L}}{\partial x_2}=x_2-2\alpha =0\to x_2=2\alpha \end{array}$$
3. $$\begin{array}{rl}\mathcal{L}(\alpha )(\equiv {\theta }_D(\alpha ))& =\frac{1}{2}((-{\alpha }^2)+(2\alpha {)}^2)+\alpha (-\alpha -4\alpha +2)\\ & =\frac{5}{2}{\alpha }^2-5{\alpha }^2+2\alpha \\ & =-\frac{5}{2}{\alpha }^2+2\alpha \end{array}$$
4. On resout

$$\begin{array}{rl}\underset{\alpha \ge 0}{max}{\theta }_D(\alpha )\to {\mathrm{\nabla }}_{\alpha }{\theta }_D(\alpha )& =-5\alpha +2=0\\ {\alpha }^{\ast }& =\frac{2}{5}\to x_1^{\ast }=-\frac{2}{5}\text{ et }{x}_2^{\ast }=\frac{4}{5}\end{array}$$