Lien de la note Hackmd
KKT: Karush-Kuhn-Tucker
On va s’attaquer a des problemes de la forme:
\[\begin{matrix} &\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{matrix}\] \[x\in C\Leftrightarrow\begin{cases} g_i(x)\le 0 &\forall i=1,\dots,m&g_i\text{ convexe}\\ h_j(x)=0 &\forall j=1,\dots,p&h_j\text{ affine} \end{cases}\]$C$ defini l’ensemble des points admissibles.
\[\boxed{ \begin{matrix} &\text{minimiser } f(x) &\text{equivalent a} &\text{minimiser } f(x), x\in\mathbb R^n\\ &x\in C & &\text{tq} \begin{cases} g_i(x)\le 0 &\forall i=1,\dots,n\\ h_j(x)=0&\forall j=1,\dots,p \end{cases} \end{matrix}\\ \color{red}{\text{(OPT)}}}\]- valeur optimale $p^{*}=f(x^{*})$
- point optimal $x^{*}\in\mathbb R^n$
Sans contrainte: $f$ convexe: $x^{*}$ optimal $\Leftrightarrow\nabla f(x^{*})=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{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}^m\alpha_ig_i(x)+\sum_{j=1}^p\beta_jh_j(x) \end{aligned}\\ \begin{aligned} &\text{variables duales}\begin{cases} \alpha=\begin{pmatrix} \alpha_1\\ \vdots\\ \alpha_m \end{pmatrix}\in\mathbb R^m\\ \beta=\begin{pmatrix} \beta_1\\ \vdots\\ \beta_p \end{pmatrix}\in\mathbb R^p \end{cases}\\ &\Leftrightarrow\text{multiplications de Lagrange}\\ &\Leftrightarrow\text{cout associe a chaque contrainte} \end{aligned}\]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{aligned} \theta_p:\mathbb R^n&\to\mathbb R\\ x&\mapsto \max_{\alpha,\beta \\ \alpha\ge 0\forall i} \mathscr L(x,\alpha, \beta) \end{aligned}\]On appelle probleme primal le probleme d’optimisation sans contrainte: \(\min_{x\in\mathbb R^n}\theta_{p}(x)\)
$x\in\mathbb R^n$ est primal admissible ssi
\[\begin{cases} g_i(x)\le 0&\forall i\\ h_j(x)=0 &\forall j \end{cases}\]On va noter $p^{*}$ la valeur optimale de $(P)$ et $x^{*}$ le point optimal, $p^{*}=\theta_{p}(x^{*})$
On appelle fonction objective duale:
\[\begin{aligned} \theta_D:\mathbb R^m\times\mathbb R^p&\to\mathbb R\\ (\alpha,\beta)&\mapsto\min_{x\in\mathbb R^n}\mathscr L(x,\alpha,\beta) \end{aligned}\]On appelle probleme dual le probleme d’optimisation avec contrainte
\[(D)\quad \max_{\alpha,\beta \\ \alpha_i\ge 0}\theta_D(\alpha, \beta) = \max_{\alpha, \beta \\ \alpha_i\ge 0}\min_{x}\mathscr L(x,\alpha, \beta)\]$(\alpha,\beta)$ est dual admissible ssi $\alpha_i\ge0$ $\forall i$.
On note egalement $(\alpha^{*}, \beta^{*})$ la solution de $(D)$ et $d^{*} = \theta_D(\alpha^{*}, \beta^{*})$
Interpretation du probleme primal
Dans le cas ou on a $g(x)\le0$ convexe et $h(x)=0$ affine.
Dans ce cas, le Lagrange est:
\[\begin{aligned} \mathscr L:\mathbb R^n\times\mathbb R\times\mathbb R&\to\mathbb R\\ (x,\alpha,\beta)&\mapsto\mathscr L(x,\alpha,\beta)=f(x)+\alpha g(x)+\beta h(x) \end{aligned}\]On a:
\[\begin{aligned} \theta_p:\mathbb R^n&\to\mathbb R\\ x&\mapsto \max_{\alpha,\beta \\ \alpha\ge 0\forall i} \mathscr L(x,\alpha, \beta) \end{aligned}\]Dans ce cas:
\[\begin{aligned} x&\mapsto \max_{\alpha,\beta \\ \alpha\ge 0\forall i} \mathscr L(x,\alpha, \beta)\\ \theta_{p}(x) &= \max_{\alpha, \beta \\ \alpha\ge 0}[f(x)+\alpha g(x)+\beta h(x)] \end{aligned}\]$\theta_p(x)$ est convexe car la somme ponderee de fonctions convexes est convexe, et le $\max$ de fonctions convexes est convexe.
- Si $g(x)\gt 0$, le crochet est maximise pour $\alpha=+\infty$ et vaut $+\infty$
- Si $g(x)\le 0$, le crochet est maximise pour $\alpha=0$
- Si $h(x)\neq 0$, le crochet est maximiser pour $\beta=(\text{signe de }h(x))\infty$ et vaut $+\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 $+\infty$.