Optimalité sous contraintes et certificats duaux

Sur la frontière imposée par une contrainte, un optimum peut avoir un gradient non nul. Pour prouver son optimalité, on peut établir une borne inférieure valable pour tous les points admissibles, puis montrer qu’un candidat l’atteint. Les multiplicateurs de Lagrange qui produisent cette borne constituent un certificat dual. Cet argument et les conditions d’optimalité sont développés au chapitre 5 de Boyd et Vandenberghe.

La vue d’ensemble de l’optimisation convexe présente les liens entre convexité et KKT ; la note sur le gradient et l’optimisation multidimensionnelle explique le gradient et la hessienne. Pour choisir les variables, l’objectif et l’ensemble admissible, voir la modélisation d’un problème d’optimisation. Ces notions se rejoignent ici dans un calcul complet.

Objectif et ensemble admissible

Pour deux variables réelles $x,y$, le problème primal est

$$\begin{aligned} \text{minimize}\quad & f(x,y)=\frac12\bigl((x-2)^2+(y-1)^2\bigr) \\ \text{subject to}\quad & c_1(x,y)=x+y-2\le0, \\ & c_2(x,y)=-x\le0, \\ & c_3(x,y)=-y\le0. \end{aligned}$$

L’ensemble admissible $C=\{(x,y):x\ge0,\ y\ge0,\ x+y\le2\}$ est un triangle fermé. L’objectif est la moitié du carré de la distance au point $(2,1)$. Comme $C$ est non vide et compact et que l’objectif est continu, le minimum est atteint. La hessienne est la matrice identité : l’objectif est strictement convexe et le minimiseur est unique.

On retrouve la forme de l’exemple de programme quadratique de CVXPY : $\frac12z^TPz+q^Tz$, avec $Gz\le h$ et $P$ positive semi-définie. Ici, $z=(x,y)^T$, $P=I_2$, $q=(-2,-1)^T$, et

$$G=\begin{pmatrix}1&1\\-1&0\\0&-1\end{pmatrix},\qquad h=\begin{pmatrix}2\\0\\0\end{pmatrix},\qquad f(z)=\frac12z^Tz+q^Tz+\frac52.$$

La constante $5/2$ ne change pas le minimiseur. Il faut la conserver pour obtenir les valeurs de $f$ et $g$ définies ici ; la soustraire des deux laisse l’écart primal–dual inchangé.

Calculer un candidat

Le minimum sans contraintes, $(2,1)$, viole $x+y\le2$. Essayons la frontière $x+y=2$, en remplaçant $y$ par $2-x$ :

$$f(x,2-x)=\frac12\bigl((x-2)^2+(1-x)^2\bigr) =\left(x-\frac32\right)^2+\frac14.$$

Sur ce côté du triangle, le minimum est donc

$$(x_*,y_*)=\left(\frac32,\frac12\right),\qquad f(x_*,y_*)=\frac14.$$

Les deux coordonnées sont positives : le candidat appartient bien à ce côté. Minimiser sur un seul côté ne suffit toutefois pas à exclure de meilleurs points ailleurs dans le triangle. La borne duale donnera la preuve globale.

Une contrainte est active en un point lorsqu’elle est satisfaite avec égalité. Ici, $c_1=0$, tandis que $c_2=-3/2$ et $c_3=-1/2$ : seule la contrainte sur la somme est active. Le gradient de l’objectif vaut $\nabla f=(-1/2,-1/2)$. Suivre le gradient négatif augmenterait $x+y$ et ferait sortir de l’ensemble admissible.

Lagrangien et borne duale

Avec la convention $c_i\le0$, associons aux trois contraintes les multiplicateurs non négatifs $\lambda,\mu,\nu$. Selon Boyd et Vandenberghe, §§5.1.1–5.1.3, le lagrangien est

$$L(x,y,\lambda,\mu,\nu) =f(x,y)+\lambda(x+y-2)-\mu x-\nu y.$$

Pour des multiplicateurs fixés, la fonction duale est l’infimum de $L$ sur le domaine des variables :

$$g(\lambda,\mu,\nu)=\inf_{(x,y)\in\mathbb R^2}L(x,y,\lambda,\mu,\nu).$$

Cet infimum porte sur tout $\mathbb R^2$. Les trois inégalités figurent déjà dans $L$ ; restreindre ce calcul au triangle changerait la fonction duale.

La hessienne de $L$ par rapport à $(x,y)$ reste $I_2$. Annuler ses dérivées partielles donne donc son unique minimum global :

$$\partial_x L=x-2+\lambda-\mu=0,\qquad \partial_y L=y-1+\lambda-\nu=0,$$

soit $x_L=2-\lambda+\mu$ et $y_L=1-\lambda+\nu$. En complétant les carrés, on obtient

$$\begin{aligned} L&=\frac12\bigl((x-x_L)^2+(y-y_L)^2\bigr)+g(\lambda,\mu,\nu),\\ g(\lambda,\mu,\nu) &=\lambda-2\mu-\nu-\frac12\bigl((\lambda-\mu)^2+(\lambda-\nu)^2\bigr). \end{aligned}$$

Le problème dual maximise $g$ sous $\lambda,\mu,\nu\ge0$. Ici, $g$ est finie pour tous les multiplicateurs finis. Pour tout point admissible $(x,y)$ et tous multiplicateurs non négatifs,

$$g(\lambda,\mu,\nu)\le L(x,y,\lambda,\mu,\nu)\le f(x,y).$$

La seconde inégalité tient au fait que chaque terme ajouté multiplie un multiplicateur non négatif par une valeur de contrainte non positive. Notons $p_*$ la valeur optimale primale et $d_*=\sup_{\lambda,\mu,\nu\ge0}g$ la valeur optimale duale. Alors $d_*\le p_*$ : c’est la dualité faible. Cet argument ne suppose pas la convexité.

Calculer les multiplicateurs et vérifier les quatre conditions KKT

La complémentarité impose que chaque multiplicateur multiplié par la valeur de sa contrainte soit nul. Comme $x_*,y_*>0$, on a $\mu_*=\nu_*=0$. Les équations de stationnarité donnent alors

$$-\frac12+\lambda_*=0 \quad\Longrightarrow\quad (\lambda_*,\mu_*,\nu_*)=\left(\frac12,0,0\right).$$

Voici les quatre conditions KKT du §5.5.3 du manuel, vérifiées une à une :

Condition	Calcul	Résultat
Admissibilité primale	$(c_1,c_2,c_3)=(0,-3/2,-1/2)$	Toutes les valeurs sont non positives
Non-négativité des multiplicateurs	$(\lambda_*,\mu_*,\nu_*)=(1/2,0,0)$	Tous les multiplicateurs sont non négatifs
Stationnarité	$\nabla_{x,y}L=(-1/2+1/2,-1/2+1/2)$	$(0,0)$
Complémentarité	$(\lambda_*c_1,\mu_*c_2,\nu_*c_3)=(0,0,0)$	Tous les produits sont nuls

Pour obtenir une borne duale finie, il faut aussi que $g>-\infty$. C’est automatique dans ce programme quadratique, mais les signes des multiplicateurs ne suffisent pas à le garantir pour un problème général.

Un multiplicateur positif impose que la contrainte correspondante soit active ; une contrainte inactive impose un multiplicateur nul. Une contrainte active peut néanmoins avoir un multiplicateur nul. Si l’on remplace la borne par $3$, le minimum sans contraintes $(2,1)$ se trouve sur $x+y=3$, avec tous les multiplicateurs nuls.

Pour un problème convexe différentiable, dont l’objectif et les fonctions d’inégalité sont convexes et les égalités affines, les conditions KKT suffisent à certifier l’optimalité globale. Ici, le certificat donne aussi une égalité numérique :

$$g\left(\frac12,0,0\right)=\frac12-\left(\frac12\right)^2=\frac14 =f\left(\frac32,\frac12\right).$$

L’objectif de tout point admissible vaut au moins $1/4$, et le candidat atteint cette borne. Ainsi, $p_*=d_*=1/4$. Les carrés donnent directement la même conclusion :

$$f(x,y)-\frac14 =\frac12\left(\left(x-\frac32\right)^2+\left(y-\frac12\right)^2\right) +\frac12(2-x-y)\ge0\qquad ((x,y)\in C).$$

L’égalité n’est possible qu’en $(3/2,1/2)$. Cela prouve l’optimalité et l’unicité sans parcourir tous les points admissibles.

Borner l’erreur d’un candidat avec l’écart primal–dual

Pour un point primal admissible et des multiplicateurs duaux admissibles, l’écart primal–dual vaut $f(x,y)-g(\lambda,\mu,\nu)$. Il majore l’écart entre la valeur du candidat et la valeur optimale :

$$0\le f(x,y)-p_*\le f(x,y)-g(\lambda,\mu,\nu).$$

Chaque ligne ci-dessous associe un point primal et des multiplicateurs duaux admissibles. Dans les deux premières, les multiplicateurs ne sont pas optimaux.

$(x,y)$	$(\lambda,\mu,\nu)$	$f$	$g$	$f-g$
$(1,1)$	$(0,0,0)$	$1/2$	$0$	$1/2$
$(1,1)$	$(1/4,0,0)$	$1/2$	$3/16$	$5/16$
$(3/2,1/2)$	$(1/2,0,0)$	$1/4$	$1/4$	$0$

La deuxième ligne donne $3/16\le p_*\le1/2$ et une erreur d’au plus $5/16=0.3125$. L’erreur réelle du candidat vaut $1/2-1/4=1/4$. Un écart positif pour un couple de candidats n’établit pas un écart positif entre les valeurs optimales : ici, l’écart de dualité optimal $p_*-d_*$ est nul.

Ce que garantissent la régularité et la convexité

Un optimum convexe peut ne pas avoir de multiplicateurs KKT

La condition de Slater, §5.2.3, demande qu’un problème convexe possède un point dans l’intérieur relatif de son domaine commun, satisfaisant les égalités et toutes les inégalités strictement. Elle garantit la dualité forte et, si la valeur optimale est finie, l’existence de multiplicateurs finis atteignant l’optimum dual. Avec la différentiabilité, KKT devient nécessaire et suffisant pour l’optimalité. La version affinée du manuel permet aux inégalités affines de ne pas être strictes.

Dans notre programme quadratique, $(1/2,1/2)$ satisfait strictement les trois inégalités : Slater est vérifiée. Elle garantit l’existence d’un certificat optimal. En revanche, la suffisance d’un certificat KKT déjà établi pour un problème convexe ne demande pas Slater.

Considérons un autre problème convexe :

$$\min_{x\in\mathbb R}x\quad\text{subject to}\quad x^2\le0.$$

Le seul point admissible est $x_*=0$, et $p_*=0$. Aucun point ne satisfait $x^2<0$ : Slater échoue. L’équation de stationnarité de $L=x+\lambda x^2$ est $1+2\lambda x=0$. Aucun multiplicateur fini ne peut la satisfaire en $x_*=0$.

Pour $\lambda>0$, le minimum de $L$ se situe en $-1/(2\lambda)$, d’où $g(\lambda)=-1/(4\lambda)$ ; pour $\lambda=0$, $g(0)=-\infty$. Ainsi, $d_*=\sup_{\lambda\ge0}g(\lambda)=0=p_*$, mais aucun multiplicateur fini n’atteint ce supremum. Dans cet exemple, l’existence des multiplicateurs et la nécessité de KKT échouent ; la dualité forte reste valable.

Un point KKT non convexe peut être un maximum

Considérons

$$\min_{x\in\mathbb R}-x^2\quad\text{subject to}\quad x-1\le0,\quad -x-1\le0.$$

L’ensemble admissible est $[-1,1]$, mais l’objectif n’est pas convexe. En $x=0$, avec les deux multiplicateurs nuls, l’admissibilité primale, la non-négativité des multiplicateurs, la stationnarité et la complémentarité sont toutes vérifiées. Pourtant, $f(0)=0$ et $f(-1)=f(1)=-1$ : ce point KKT est le maximum strict sur l’ensemble admissible.

Le point stationnaire de $L=-x^2$ n’est pas un minimum global ; $\inf_{x\in\mathbb R}L=-\infty$. En fait, des multiplicateurs finis ne font qu’ajouter des termes affines, sans changer la courbure négative du terme quadratique. Ici, $d_*=-\infty$. La dualité faible reste valable, mais ne fournit aucune borne inférieure finie. Bien que $x=0$ satisfasse strictement les deux contraintes, le théorème de Slater pour les problèmes convexes ne s’applique pas à cet objectif non convexe.

Refaire les calculs avec Python

Ce programme utilise uniquement l’arithmétique rationnelle de la bibliothèque standard de Python. Il vérifie le point et les multiplicateurs calculés, puis recalcule les écarts et les contre-exemples. L’infimum global nécessaire au certificat découle de la mise sous forme de carrés obtenue plus haut.

from fractions import Fraction as F


def objective(x, y):
    return F(1, 2) * ((x - 2)**2 + (y - 1)**2)


def dual(lam, mu, nu):
    return lam - 2*mu - nu - F(1, 2)*((lam-mu)**2 + (lam-nu)**2)


def vector(values):
    return '(' + ', '.join(map(str, values)) + ')'


x, y = F(3, 2), F(1, 2)
lam, mu, nu = F(1, 2), F(0), F(0)
constraints = (x+y-2, -x, -y)
multipliers = (lam, mu, nu)
stationarity = (x-2+lam-mu, y-1+lam-nu)
kkt = (
    all(c <= 0 for c in constraints),
    all(m >= 0 for m in multipliers),
    all(s == 0 for s in stationarity),
    all(m*c == 0 for m, c in zip(multipliers, constraints)),
)
assert all(kkt)
print('x=' + vector((x, y)) + ', multipliers=' + vector(multipliers))
print('constraints=' + vector(constraints))
print('stationarity=' + vector(stationarity))
print('KKT=' + vector(kkt))
for label, a, b, l in [('candidate', F(1), F(1), F(1, 4)),
                     ('optimum', x, y, lam)]:
    p, d = objective(a, b), dual(l, F(0), F(0))
    print(f'{label}: f={p}, g={d}, gap={p-d}')
for l in (F(1), F(10), F(100)):
    z = -1/(2*l)
    g = z + l*z*z
    assert g == -1/(4*l)
    print(f'degenerate: lambda={l}, x_min_L={z}, g={g}')
z = F(0)
nonconvex_constraints = (z-1, -z-1)
nonconvex_multipliers = (F(0), F(0))
nonconvex_kkt = (
    all(c <= 0 for c in nonconvex_constraints),
    all(m >= 0 for m in nonconvex_multipliers),
    -2*z + nonconvex_multipliers[0] - nonconvex_multipliers[1] == 0,
    all(m*c == 0 for m, c in zip(nonconvex_multipliers, nonconvex_constraints)),
)
print('nonconvex: KKT=' + vector(nonconvex_kkt)
      + f', f(0)={-z*z}, f(-1)=f(1)={-F(1)**2}')

Sortie obtenue :

x=(3/2, 1/2), multipliers=(1/2, 0, 0)
constraints=(0, -3/2, -1/2)
stationarity=(0, 0)
KKT=(True, True, True, True)
candidate: f=1/2, g=3/16, gap=5/16
optimum: f=1/4, g=1/4, gap=0
degenerate: lambda=1, x_min_L=-1/2, g=-1/4
degenerate: lambda=10, x_min_L=-1/20, g=-1/40
degenerate: lambda=100, x_min_L=-1/200, g=-1/400
nonconvex: KKT=(True, True, True, True), f(0)=0, f(-1)=f(1)=-1

Pour des programmes quadratiques plus grands, l’exemple CVXPY lit les multiplicateurs avec l’attribut dual_value d’un objet contrainte. Il faut conserver le même ordre des contraintes et la même convention de signe, puis vérifier l’admissibilité, les résidus de stationnarité, les produits de complémentarité et la borne donnée par la fonction duale effectivement calculée. Un petit résidu de stationnarité ne suffit pas à exclure le maximum non convexe ci-dessus.

Mes lectures · Les notes ouvertes sont mémorisées dans ce navigateur.