OCVX2: Optimisation sous contrainte par la methode des multiplicateurs de Lagrangre et conditions KKT

KKT: Karush-Kuhn-Tucker

On va s'attaquer a des problemes de la forme:

$$\begin{array}{cccc}& \text{minimiser }f(x)& f:{\mathbb{R}}^n\to \mathbb{R}& f\text{ convexe}\\ & x\in C& x\in {\mathbb{R}}^n& C=\text{ensemble convexe}\end{array}$$

$$x\in C\iff \{\begin{array}{lll}{g}_i(x)\le 0& \mathrm{\forall }i=1,\dots ,m& g_i\text{ convexe}\\ h_j(x)=0& \mathrm{\forall }j=1,\dots ,p& h_j\text{ affine}\end{array}$$

$C$ defini l'ensemble des points admissibles.

$$\begin{gathered} \boxed{{\displaystyle \begin{array}{cccc}& \text{minimiser }f(x)& \text{equivalent a}& \text{minimiser }f(x),x\in {\mathbb{R}}^n\\ & x\in C& & \text{tq}\{\begin{array}{ll}{g}_i(x)\le 0& \mathrm{\forall }i=1,\dots ,n\\ h_j(x)=0& \mathrm{\forall }j=1,\dots ,p\end{array}\end{array} \\ \text{(OPT)}}} \end{gathered}$$

• valeur optimale
  $p^{\text{*}}=f(x^{\text{*}})$
• point optimal
  $x^{\text{*}}\in {\mathbb{R}}^n$

Sans contrainte:

$f$ convexe:

$x^{\text{*}}$ optimal

$\iff \mathrm{\nabla }f(x^{\text{*}})=0$

Cette conditions d'optimalite n'est plus vraie des lors que l'on a des contraintes.

Dualite de Lagrange

:::

Lagrangien

On definit le Lagrangien de (OPT) comme la fonction:

$$\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}^m{\alpha }_i{g}_i(x)+\sum _{j=1}^p{\beta }_j{h}_j(x)\end{array} \\ \begin{array}{rl}& \text{variables duales}\{\begin{array}{l}\alpha =\left(\begin{array}{c}{\alpha }_1\\ ⋮\\ {\alpha }_m\end{array}\right)\in {\mathbb{R}}^m\\ \beta =\left(\begin{array}{c}{\beta }_1\\ ⋮\\ {\beta }_p\end{array}\right)\in {\mathbb{R}}^p\end{array}\\ & \iff \text{multiplications de Lagrange}\\ & \iff \text{cout associe a chaque contrainte}\end{array} \end{gathered}$$

Lagrangien

$\equiv$ version sans contrainte du probleme (OPT)

Intuition

Intuition: pour chaque probleme d'optimisation avec contraintes, il existe un certain parametrage des variables duales tel que le minimum sans contrainte du Lagrangien par rapport a la variable primale

$\equiv x$ (a variables duales fixees) coincide avec la solution du probleme de contraintes.

On appelle fonction objective primale

$$\begin{gathered} \begin{array}{rl}{\theta }_p:{\mathbb{R}}^n& \to \mathbb{R}\\ x& \mapsto \underset{\alpha ,\beta \\ \alpha \ge 0\mathrm{\forall }i}{max}\mathcal{L}(x,\alpha ,\beta )\end{array} \end{gathered}$$

On appelle probleme primal le probleme d'optimisation sans contrainte:

$$\underset{x\in {\mathbb{R}}^n}{min}{\theta }_p(x)$$

$x\in {\mathbb{R}}^n$ est primal admissible ssi

$$\{\begin{array}{ll}{g}_i(x)\le 0& \mathrm{\forall }i\\ h_j(x)=0& \mathrm{\forall }j\end{array}$$

On va noter

$p^{\text{*}}$ la valeur optimale de

$(P)$ et

$x^{\text{*}}$ le point optimal,

$p^{\text{*}}={\theta }_p(x^{\text{*}})$

On appelle fonction objective duale:

$$\begin{array}{rl}{\theta }_D:{\mathbb{R}}^m\times {\mathbb{R}}^p& \to \mathbb{R}\\ (\alpha ,\beta )& \mapsto \underset{x\in {\mathbb{R}}^n}{min}\mathcal{L}(x,\alpha ,\beta )\end{array}$$

On appelle probleme dual le probleme d'optimisation avec contrainte

$$\begin{gathered} (D)\underset{\alpha ,\beta \\ {\alpha }_i\ge 0}{max}{\theta }_D(\alpha ,\beta )=\underset{\alpha ,\beta \\ {\alpha }_i\ge 0}{max}\underset{x}{min}\mathcal{L}(x,\alpha ,\beta ) \end{gathered}$$

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

${\alpha }_i\ge 0$

$\mathrm{\forall }i$.

On note egalement

$({\alpha }^{\text{*}},{\beta }^{\text{*}})$ la solution de

$(D)$ et

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

Interpretation du probleme primal

Dans le cas ou on a

$g(x)\le 0$ convexe et

$h(x)=0$ affine.

Dans ce cas, le Lagrange est:

$$\begin{array}{rl}\mathcal{L}:{\mathbb{R}}^n\times \mathbb{R}\times \mathbb{R}& \to \mathbb{R}\\ (x,\alpha ,\beta )& \mapsto \mathcal{L}(x,\alpha ,\beta )=f(x)+\alpha g(x)+\beta h(x)\end{array}$$

On a:

$$\begin{gathered} \begin{array}{rl}{\theta }_p:{\mathbb{R}}^n& \to \mathbb{R}\\ x& \mapsto \underset{\alpha ,\beta \\ \alpha \ge 0\mathrm{\forall }i}{max}\mathcal{L}(x,\alpha ,\beta )\end{array} \end{gathered}$$

Dans ce cas:

$$\begin{gathered} \begin{array}{rl}x& \mapsto \underset{\alpha ,\beta \\ \alpha \ge 0\mathrm{\forall }i}{max}\mathcal{L}(x,\alpha ,\beta )\\ {\theta }_p(x)& =\underset{\alpha ,\beta \\ \alpha \ge 0}{max}[f(x)+\alpha g(x)+\beta h(x)]\end{array} \end{gathered}$$

${\theta }_p(x)$ est convexe car la somme ponderee de fonctions convexes est convexe, et le

$max$ de fonctions convexes est convexe.

$$\begin{gathered} {\theta }_p(x)=f(x)+\underset{\alpha ,\beta \\ \alpha \ge 0}{max}[\alpha g(x)+\beta h(x)] \end{gathered}$$

• Si
  $g(x)>0$, le crochet est maximise pour
  $\alpha =+\mathrm{\infty }$ et vaut
  $+\mathrm{\infty }$
• Si
  $g(x)\le 0$, le crochet est maximise pour
  $\alpha =0$
• Si
  $h(x)\ne 0$, le crochet est maximiser pour
  $\beta =(\text{signe de }h(x))\mathrm{\infty }$ et vaut
  $+\mathrm{\infty }$
• Si
  $h(x)=0$, le crochet vaut
  $0$ peu importe la valeur de
  $\beta$

Donc si

$x$ primal admissible

$(g(x)\le 0$ et

$h(x)=0)$, alors le crochet vaut

$0$.

Si

$x$ ne verifie pas les contraintes, alors le crochet vaut

$+\mathrm{\infty }$.

$${\theta }_p(x)=f(x)+\{\begin{array}{ll}0& \text{si }x\text{ primal admissible}\\ +\mathrm{\infty }& \text{si }x\text{ pas primal admissible}\end{array}$$

$$\begin{array}{rl}(P):& \underset{x\in {\mathbb{R}}^n}{min}{\theta }_p(x)\\ & \underset{x\in {\mathbb{R}}^n}{min}f(x)+\{\begin{array}{ll}0& \text{si }x\text{ primal admissible}\\ +\mathrm{\infty }& \text{si }x\text{ pas primal admissible}\end{array}\end{array}$$