Eclats de vers : Matemat 10 : Optimisation - 4

Il est important de se rendre compte que si \(\xi\) est la solution de :

\[\partial \varphi(\xi) = 0\]

on sait que :

\[\xi \in \arg\min_{x \in \setR^n} \varphi(x)\]

mais rien ne nous dit que \(\xi\) respecte les contraintes exigées ! On ne peut donc pas dans le cas général appliquer la technique classique de la minimisation libre pour résoudre des problèmes de minimisation contraints.

Nous venons de voir que les conditions de Kuhn-Tucker remplies sur \(\Omega \times \mathcal{P}\) nous offraient un point de selle sur \(\setR^n \times \mathcal{P}\). Nous allons voir que la réciproque est également vraie. Supposons que \((\gamma,\lambda) \in \setR^n \times \mathcal{P}\) soit un point de selle du lagrangien :

\[\lagrangien(\gamma,y) \le \lagrangien(\gamma,\lambda) \le \lagrangien(x,\lambda)\]

pour tout \((x,y) \in \setR^n \times \mathcal{P}\). On a :

\[\lagrangien(\gamma,y) - \lagrangien(\gamma,\lambda) = (y - \lambda)^\dual \cdot \omega(\gamma) \le 0\]

relation qui doit être valable pour tout \(y \ge 0\). Fixons \(i \in \{1,2,...,m\}\) et choisissons :

on en déduit que \((y - \lambda)^\dual \cdot \omega(\gamma) = -\lambda_i \cdot \omega_i(\gamma) \le 0\), c'est-à-dire :

\[\lambda_i \cdot \omega_i(\gamma) \ge 0\]

Considérons à présent le choix :

On en déduit alors que :

\[(y - \lambda)^\dual \cdot \omega(\gamma) = \lambda_i \cdot \omega_i(\gamma) \le 0\]

On conclut de ces deux inégalités que :

\[\lambda_i \cdot \omega_i(\gamma) = 0\]

Enfin, si nous prenons :

on voit que :

\[(y - \lambda)^\dual \cdot \omega(\gamma) = 1 \cdot \omega_i(\gamma) = \omega_i(\gamma) \le 0\]

ce qui nous montre que \(\gamma \in \Omega\).

De plus, comme :

\[\gamma \in \arg\min_{x \in \setR^n} \lagrangien(x,\lambda)\]

les propriétés des fonctions dérivables nous imposent que \(\partial_x \lagrangien(\gamma,\lambda) = 0\).

Remarquons que nous n'avons pas utilisé la convexité de \(\varphi\) ou de \(\omega\) pour démontrer que \(\gamma\) est bien la solution de notre problème. On peut donc appliquer la technique du point de selle du lagrangien à une classe de fonctions beaucoup plus générale.

Attention, si \(\varphi\) et/ou \(\omega\) ne sont plus supposées convexes, le point de selle impliquera toujours les conditions de Kuhn-Tucker mais l'inverse ne sera plus vrai. En pratique, on essaiera malgré tout de trouver une solution aux conditions de Kuhn-Tucker, et on déterminera a posteriori :

• si le minimum trouvé est bien un minimum local (test de la Hessienne définie positive au \(\gamma\) obtenu)
• si ce minimum local est aussi un minimum sur \(\Omega\)

On sait que maximiser \(\psi\) revient à minimiser \(-\psi\). Comme \(-\psi\) et \(-\vartheta\) sont convexes, on peut utiliser le lagrangien défini par :

\[\lagrangien_{\min}(x,y) = \Big[-\psi(x)\Big] + y^\dual \cdot \Big[-\vartheta(x)\Big] = -\psi(x) - y^\dual \cdot \vartheta(x)\]

pour tout \((x,y) \in \setR^n \times \mathcal{P}\). La solution \((\gamma,\lambda)\) vérifie alors :

\[\lagrangien_{\min}(\gamma,y) \le \lagrangien_{\min}(\gamma,\lambda) \le \lagrangien_{\min}(x,\lambda)\]

On voit que la fonction opposée :

\[\lagrangien_{\max}(x,y) = - \lagrangien_{\min}(x,y) = \psi(x) + y^\dual \cdot \vartheta(x)\]

vérifie les conditions du point de selle inversées :

\[\lagrangien_{\max}(x,\lambda) \le \lagrangien_{\max}(\gamma,\lambda) \le \lagrangien_{\max}(\gamma,y)\]

Il s'agit du lagrangien natif du problème de maximisation. Il est maximisé par rapport à \(x\) et minimisé par rapport aux multiplicateurs de Lagrange.

Les conditions de Kuhn-Tucker associées à \(\lagrangien_{\min}\) s'écrivent :

Elles sont équivalentes aux conditions analogues associées à \(\lagrangien_{\max}\) :

On peut réécrire l'ensemble \(\Phi\) sous la forme :

\[\Phi = \{ x \in \setR^n : \varrho(x) \le 0, \ \varrho(x) \ge 0 \}\]

On introduit donc deux séries de multiplicateurs et le lagrangien défini par :

\[L(x,y,z) = \varphi(x) + y^\dual \cdot \varrho(x) + z^\dual \cdot (-\varrho(x))\]

pour tout \((x,y,z) \in \setR^n \times \mathcal{P} \times \mathcal{P}\). On constate qu'il ne dépend que de \(x\) et de \(y - z\) :

\[L(x,y,z) = \varphi(x) + (y - z)^\dual \cdot \varrho(x)\]

On voit que \(u = y - z\) est libre d'aller où il veut dans \(\setR^m\). On pose :

\[\lagrangien(x,u) = \varphi(x) + u^\dual \cdot \varrho(x)\]

pour tout \((x,u) \in \setR^n \times \setR^m\).

Comme on veut que \(\gamma\) minimise \(\lagrangien\) par rapport à la variable \(x\) sur \(\setR^n\), on impose \(\partial_x \lagrangien(\gamma,\lambda) = 0\). On doit avoir aussi \(\varrho(x) = 0\). Mais comme \(\partial_u \lagrangien(x,u) = \varrho(x)\), on se retrouve finalement avec les conditions nécessaires de Kuhn-Tucker :

Nous allons montrer que tout point de selle est solution du problème de minimisation. Soit \((\gamma,\lambda)\) tel que :

\[\lagrangien(\gamma,u) \le \lagrangien(\gamma,\lambda) \le \lagrangien(x,\lambda)\]

pour tout \((x,u) \in \setR^n \times \setR^m\). On en déduit que :

\[\lagrangien(\gamma,u) - \lagrangien(\gamma,\lambda) \le 0\]

pour tout \(u \in \setR^m\), c'est-à-dire :

\[(u - \lambda)^\dual \cdot \varrho(\gamma) \le 0\]

Considérons la base canonique \((\canonique_1,...,\canonique_m)\) de \(\setR^m\). Si on prend \(u = \lambda + \canonique_i\), on obtient la condition

\[(u - \lambda)^\dual \cdot \varrho(\gamma) = \varrho_i(\gamma) \le 0\]

Mais comme \(u\) n'est pas forcément positif, on peut aussi prendre \(u = \lambda - \canonique_i\). On obtient alors la condition :

\[(u - \lambda)^\dual \cdot \varrho(\gamma) = -\varrho_i(\gamma) \le 0\]

On déduit de ces deux inégalités que \(\varrho(\gamma) = 0\), c'est à dire \(\gamma \in \Phi\).

A présent, soit \(x \in \Phi\). Comme \(\varrho(\gamma) = \varrho(x) = 0\), on a :

\[\varphi(\gamma) = \lagrangien(\gamma,\lambda) \le \lagrangien(x,\lambda) = \varphi(x)\]

Le \(\gamma\) issu du point de selle est donc bien la solution de notre problème de minimisation contraint.

Si on veut minimiser \(\varphi\) sur \(\Omega\), on utilisera le lagrangien défini par :

\[\lagrangien(x,y,z,u) = \varphi(x) + y^\dual \cdot \omega(x) - z^\dual \cdot \vartheta(x) + u^\dual \cdot \varrho(x)\]

pour tout \((x,y,z,u)\) tels que \(y,z \ge 0\). Le point de selle \((\gamma,\lambda,\mu,\nu)\) vérifiera :

\[\lagrangien(\gamma,y,z,u) \le \lagrangien(\gamma,\lambda,\mu,\nu) \le \lagrangien(x,\lambda,\mu,\nu)\]

Les conditions de Kuhn-Tucker s'écriront :

Si on veut maximiser \(\psi\) sur \(\Omega\), on utilisera le lagrangien défini par :

\[\lagrangien(x,y,z,u) = \psi(x) - y^\dual \cdot \omega(x) + z^\dual \cdot \vartheta(x) + u^\dual \cdot \varrho(x)\]

pour tout \((x,y,z,u)\) tels que \(y,z \ge 0\). Le point de selle \((\gamma,\lambda,\mu,\nu)\) vérifiera :

\[\lagrangien(x,\lambda,\mu,\nu) \le \lagrangien(\gamma,\lambda,\mu,\nu) \le \lagrangien(\gamma,y,z,u)\]

Les conditions de Kuhn-Tucker s'écriront :

On exprime parfois ces problèmes en utilisant des contraintes équivalentes. Si on pose \(s = - \omega(x)\), on a \(s \ge 0\). De même, on pose \(t = \vartheta(x) \ge 0\). On définit alors \(\Gamma\) comme l'ensemble des \((x,s,t)\) vérifiant les conditions :

\begin{align} s,t &\ge 0 \\ s + \omega(x) &= 0 \\ t - \vartheta(x) &= 0 \\ \varrho(x) &= 0 \end{align}

Et on minimise \(\varphi(x)\) (ou on maximise \(\psi(x)\)) sur les \((x,s,t) \in \Gamma\).

Soit le problème de minimisation :

\[\gamma \in \arg\min_{x \in \Omega} \varphi(x)\]

où :

\[\Omega^+ = \{ x \in \corps^n : \omega(x) \le 0, \ x \ge 0 \}\]

La condition \(x \ge 0\) est équivalente à \(-x \le 0\). On définit le lagrangien :

\[L(x,y,z) = \varphi(x) + y^\dual \cdot \omega(x) - z^\dual \cdot x\]

La solution de notre problème vérifie les conditions du point de selle :

\[L(\gamma,y,z) \le L(\gamma,\lambda,\mu) \le L(x,\lambda,\mu)\]

pour tout \(x \in \setR^n\) et \(y,z \ge 0\). Si \(x \ge 0\), on a :

\[-z^\dual \cdot x \le 0\]

par positivité de \(z\). On a alors :

\[L(x,y,z) = \varphi(x) + y^\dual \cdot \omega(x) - z^\dual \cdot x \le \varphi(x) + y^\dual \cdot \omega(x) = L(x,y,0)\]

On en conclut qu'un choix permettant de maximiser \(L\) par rapport à son troisième argument est \(\mu = 0\). Introduisons le lagrangien modifié :

\[\lagrangien(x,y) = L(x,y,0) = \varphi(x) + y^\dual \cdot \omega(x)\]

Le problème du point de selle est équivalent à trouver \((\gamma,\lambda) \ge 0\) tel que :

\[\lagrangien(\gamma,y) \le \lagrangien(\gamma,\lambda) \le \lagrangien(x,\lambda)\]

pour tout \((x,y) \ge 0\). La différence est qu'on ne fait plus apparaître explicitement la contrainte de positivité de \(x\) dans le lagrangien.

Soit le problème de minimisation :

\[\gamma \in \arg\max_{x \in \Theta} \psi(x)\]

où :

\[\Theta = \{ x \in \corps^n : \vartheta(x) \ge 0, \ x \ge 0 \}\]

On pose le lagrangien :

\[L(x,y,z) = \psi(x) + y^\dual \cdot \omega(x) + z^\dual \cdot x\]

La solution de notre problème vérifie les conditions du point de selle inversé :

\[L(x,\lambda,\mu) \le L(\gamma,\lambda,\mu) \le L(\gamma,y,z)\]

pour tout \(x \in \setR^n\) et \(y,z \ge 0\). Si \(x \ge 0\), on a :

\[z^\dual \cdot x \ge 0\]

par positivité de \(z\). On a alors :

\[L(x,y,z) \ge L(x,y,0)\]

On en conclut qu'un choix permettant de minimiser \(L\) par rapport à son troisième argument est \(\mu = 0\). Introduisons le lagrangien modifié :

\[\lagrangien(x,y) = L(x,y,0) = \psi(x) + y^\dual \cdot \vartheta(x)\]

Le problème du point de selle est équivalent à trouver \((\gamma,\lambda) \ge 0\) tel que :

\[\lagrangien(x,\lambda) \le \lagrangien(\gamma,\lambda) \le \lagrangien(\gamma,y)\]

pour tout \((x,y) \ge 0\).

Soit une matrice réelle \(A\) de taille \((m,n)\), l'ensemble :

\[\Theta = \{ x \in \setR^n : A \cdot x \le b, \ x \ge 0 \}\]

et le vecteur \(c \in \setR^n\). Nous nous intéressons au problème de maximisation linéaire sous contrainte :

\[\gamma \in \arg\max_{x \in \Theta} \big[ c^\dual \cdot x \big]\]

La contrainte \(A \cdot x \le b\) est équivalente à :

\[b - A \cdot x \ge 0\]

On introduit donc le lagrangien :

\begin{align} \lagrangien(x,y) &= c^\dual \cdot x + y^\dual \cdot (b - A \cdot x) \\ &= c^\dual \cdot x + y^\dual \cdot b - y^\dual \cdot A \cdot x \end{align}

défini pour tout \((x,y) \ge 0\).

Comme on travaille dans les réels, on a par symétrie du produit scalaire :

\begin{align} c^\dual \cdot x &= x^\dual \cdot c \\ y^\dual \cdot b &= b^\dual \cdot y \\ y^\dual \cdot A \cdot x &= (A \cdot x)^\dual \cdot y = x^\dual \cdot A^\dual \cdot y \end{align}

Le lagrangien du problème primal peut donc se réécrire :

\begin{align} \lagrangien(x,y) &= x^\dual \cdot c + b^\dual \cdot y - x^\dual \cdot A^\dual \cdot y \\ &= b^\dual \cdot y + x^\dual \cdot (c - A^\dual \cdot y) \end{align}

On voit que la fonction duale définie par :

\[\lagrangien^\dual(y,x) = \lagrangien(x,y) = b^\dual \cdot y + x^\dual \cdot (c - A^\dual \cdot y)\]

pour tout \((y,x) \ge 0\) peut également être considérée comme un lagrangien formé à partir de l'objectif \(y \mapsto b^\dual \cdot y\) et d'une des deux contraintes suivantes :

Résoudre le problème primal revient à trouver un point \((\gamma,\lambda) \ge 0\) vérifiant :

\[\lagrangien(x,\lambda) \le \lagrangien(\gamma,\lambda) \le \lagrangien(\gamma,y)\]

pour tout \(x,y \ge 0\). En utilisant la définition de \(\lagrangien^\dual\), ces conditions se réécrivent :

\[\lagrangien^\dual(\lambda,x) \le \lagrangien^\dual(\lambda,\gamma) \le \lagrangien^\dual(y,\gamma)\]

Le couple \((\lambda,\gamma)\) est donc solution d'un problème de minimisation en \(y\). Dans un problème de minimisation, les contraintes associées aux multiplicateurs de lagrange doivent être négatives. On a donc \(c - A^\dual \cdot y \le 0\), autrement dit :

\[A^\dual \cdot y \ge c\]

Le problème primal est donc équivalent au problème dual suivant.

Trouver :

\[\lambda \in \arg\min_{y \in \Omega} (b^\dual \cdot y)\]

où :

\[\Omega = \{ y \in \setR^m : A^\dual \cdot y \ge c, \ y \ge 0 \}\]

Les conditions de Khun-Tucker des problèmes primal et dual impliquent :

Les valeurs des lagrangiens aux points de selle s'écrivent donc :

La définition du lagrangien dual implique que :

\[\lagrangien(\gamma,\lambda) = \lagrangien^\dual(\lambda,\gamma)\]

c'est-à-dire :

\[c^\dual \cdot \gamma = b^\dual \cdot \lambda\]

Le maximum de \(x \mapsto c^\dual \cdot x\) sur \(\Theta\) est donc égal au minimum de \(y \mapsto b^\dual \cdot y\) sur \(\Omega\). Dans la suite, on note :

\[V = \max_{x \in \Theta} (c^\dual \cdot x) = \min_{y \in \Omega} (b^\dual \cdot y)\]

Par définition des maxima et minima, on a :

\[c^\dual \cdot x \le V \le b^\dual \cdot y\]

pour tout \(x \in \Theta\) et \(y \in \Omega\). Si les deux valeurs \(c^\dual \cdot x\) et \(b^\dual \cdot y\) sont proches, les éléments \(x\) et \(y\) sont presque optimaux.

Ne pas confondre la notion de dualité \(\max - \min\) avec la dualité au sens des applications linéaires.