Traitez les contraintes d'égalité avec Lagrange

Une entreprise de livraison veut installer un entrepôt pour desservir trois gros clients de la métropole rennaise. Sans contrainte, elle le placerait au « centre » de ses clients. Mais la mairie impose une condition : l’entrepôt doit être construit le long de la rocade, pour ne pas faire traverser la ville aux camions. Le minimum libre n’est plus accessible ; où se trouve le meilleur point sur la route ?

Dans la deuxième partie, les minimums annulaient le gradient. Avec une contrainte d’égalité, ce n’est plus vrai : le gradient au meilleur point de la route n’a aucune raison d’être nul. Ce chapitre présente l’outil qui remplace la condition $\nabla f = 0$ : les multiplicateurs de Lagrange. Cet entrepôt sera notre fil rouge pour toute la troisième partie.

Le fil rouge : placer un entrepôt

Plaçons un repère (en kilomètres) sur la carte. Les trois clients sont en $C_1 = (0, 0)$, $C_2 = (4, 0)$ et $C_3 = (2, 6)$. Pour un entrepôt en $p = (x, y)$, on mesure l’effort de livraison par la somme des carrés des distances :

$$f(p) = \lVert p - C_1 \rVert^2 + \lVert p - C_2 \rVert^2 + \lVert p - C_3 \rVert^2$$

Le carré n’est pas qu’une commodité de calcul : il pénalise fortement les clients très éloignés. Le gradient vaut $\nabla f(p) = 2\sum_i (p - C_i) = 6\,(p - G)$, où $G = (2, 2)$ est le barycentre (le point moyen) des trois clients. Sans contrainte, le minimum est donc en $G$, là où le gradient s’annule. On peut même écrire $f(p) = 3 \lVert p - G \rVert^2 + 32$ : les lignes de niveau de $f$ sont des cercles centrés sur $G$.

La rocade, dans notre repère, est la droite $x + y = 2$. On l’écrit sous la forme d’une contrainte $h(p) = 0$ :

$$\min_{p} \; f(p) \quad \text{s.c.} \quad h(p) = x + y - 2 = 0$$

La condition de tangence

Imaginez que vous vous promenez le long de la rocade en surveillant la valeur de $f$. Tant que la route coupe une ligne de niveau de $f$, vous pouvez continuer dans un sens où $f$ diminue. Le meilleur point est donc celui où la route ne coupe plus les lignes de niveau mais les touche : la ligne de niveau y est tangente à la contrainte.

Or le gradient de $f$ est perpendiculaire aux lignes de niveau, et le gradient de $h$ est perpendiculaire à la contrainte. Si les deux courbes sont tangentes, leurs perpendiculaires sont alignées : $\nabla f(p^*)$ et $\nabla h(p^*)$ sont colinéaires. Il existe donc un nombre $\lambda$ tel que

$$\nabla f(p^*) + \lambda \, \nabla h(p^*) = 0$$

Ce nombre $\lambda$ s’appelle le multiplicateur de Lagrange de la contrainte.

Loin de p*, ∇f n'est pas aligné avec ∇h : sa composante le long de la route indique qu'on peut encore descendre. Au point optimal (1, 1), les deux gradients sont colinéaires, ∇f = −6 ∇h.

Le lagrangien et la méthode

Pour ne rien oublier, on regroupe tout dans une seule fonction, le lagrangien :

$$L(x, \lambda) = f(x) + \sum_{j=1}^{m} \lambda_j \, h_j(x)$$

• $f$ est l’objectif et $h_1, \dots, h_m$ les contraintes d’égalité $h_j(x) = 0$ ;
• $\lambda_j$ est le multiplicateur associé à la contrainte $j$, un réel de signe quelconque.

Le théorème de Lagrange s’énonce alors ainsi. Si $x^*$ est un minimum local de $f$ sous les contraintes $h_j(x) = 0$, que $f$ et les $h_j$ sont $C^1$, et que les gradients $\nabla h_1(x^*), \dots, \nabla h_m(x^*)$ sont linéairement indépendants (c’est la condition de qualification), alors il existe des multiplicateurs $\lambda_1, \dots, \lambda_m$ tels que

$$\nabla_x L(x^*, \lambda) = \nabla f(x^*) + \sum_{j} \lambda_j \nabla h_j(x^*) = 0 \qquad \text{et} \qquad h_j(x^*) = 0 \text{ pour tout } j$$

Remarquez que la seconde condition s’écrit aussi $\partial L / \partial \lambda_j = 0$ : on cherche simplement les points critiques du lagrangien, en toutes ses variables. On obtient $n + m$ équations pour $n + m$ inconnues.

Exemple

Pour l’entrepôt, $L(x, y, \lambda) = f(x, y) + \lambda (x + y - 2)$. Les conditions s’écrivent :

$$6(x - 2) + \lambda = 0, \qquad 6(y - 2) + \lambda = 0, \qquad x + y = 2$$

Les deux premières donnent $x = y = 2 - \lambda / 6$. En reportant dans la contrainte, $4 - \lambda / 3 = 2$, d’où $\lambda = 6$, puis $x = y = 1$.

L’entrepôt doit être construit en $p^* = (1, 1)$, pour un coût $f(p^*) = 2 + 10 + 26 = 38$ (contre 32 au barycentre, inaccessible). C’est le point de la rocade le plus proche de $G$ : la projection orthogonale du barycentre sur la route.

À retenir

Pour minimiser $f$ sous des contraintes $h_j(x) = 0$ : écrire le lagrangien $L = f + \sum_j \lambda_j h_j$, puis résoudre $\nabla_x L = 0$ et $h_j = 0$. À l’optimum, le gradient de $f$ est une combinaison des gradients des contraintes : les lignes de niveau sont tangentes à l’ensemble réalisable.

Ce que dit le multiplicateur

Le multiplicateur n’est pas qu’un intermédiaire de calcul. Supposons que la rocade soit en fait la droite $x + y = b$, et notons $V(b)$ le coût optimal correspondant. On montre (sous des hypothèses de régularité) que

$$\frac{dV}{db} = -\lambda$$

avec la convention $h(x) = x + y - b$. Le multiplicateur mesure la sensibilité du coût optimal à la contrainte, exactement comme les variables duales du chapitre 4 mesuraient la valeur d’une ressource. Ce n’est pas une coïncidence : les variables duales d’un programme linéaire sont des multiplicateurs de Lagrange.

Exemple

Vérifions sur l’entrepôt. Pour une route $x + y = b$, le même calcul donne $p^* = (b/2, b/2)$ et $V(b) = 32 + \tfrac32 (4 - b)^2$. Donc $V'(b) = -3(4 - b)$, qui vaut $-6$ pour $b = 2$ : c’est bien $-\lambda$. Si la route était décalée de 100 mètres vers le barycentre ($b = 2{,}1$), le coût baisserait d’environ $6 \times 0{,}1 = 0{,}6$.

La pente de V en b = 2 vaut −6 = −λ : rapprocher la route du barycentre fait baisser le coût d'environ 6 par unité de déplacement.

Attention

Le signe de $\lambda$ dépend de la façon d’écrire la contrainte : $x + y - 2 = 0$ ou $2 - x - y = 0$ donnent des multiplicateurs opposés. Pour une contrainte d’égalité, ce n’est pas grave, car $\lambda$ peut être de signe quelconque. Ce le sera au chapitre suivant, où le signe des multiplicateurs des inégalités fait partie des conditions.

Candidat ou solution ? Vérifier la conclusion

Les conditions de Lagrange sont nécessaires : elles fournissent des candidats, pas forcément des minimums. Un maximum sous contrainte les vérifie aussi, tout comme un point selle. Pour conclure, trois arguments sont possibles.

1. La convexité. Si $f$ est convexe et les contraintes $h_j$ affines, tout candidat est un minimum global. C’est le cas de l’entrepôt : $f$ est une somme de carrés et la rocade une droite, donc $(1, 1)$ est bien le minimum global.
2. L’existence et la comparaison. Si l’ensemble réalisable est compact, le minimum existe (Weierstrass) et c’est forcément l’un des candidats : on les évalue tous et l’on garde le plus petit.
3. Les conditions du second ordre. On étudie la Hessienne du lagrangien, restreinte aux directions tangentes à la contrainte. C’est plus technique, et on l’utilise quand les deux premiers arguments échouent.

Exemple

Cherchons les extremums de $f(x, y) = x + y$ sur le cercle $x^2 + y^2 = 2$. Le lagrangien est $L = x + y + \lambda (x^2 + y^2 - 2)$, et les conditions donnent $1 + 2\lambda x = 0$ et $1 + 2\lambda y = 0$, donc $x = y = -1/(2\lambda)$. La contrainte impose $2/(4\lambda^2) = 2$, soit $\lambda = \pm \tfrac12$.

• $\lambda = \tfrac12$ : le point $(-1, -1)$, où $f = -2$ ;
• $\lambda = -\tfrac12$ : le point $(1, 1)$, où $f = 2$.

Le cercle est compact et $f$ continue : le minimum et le maximum existent et sont parmi les candidats. Le minimum vaut $-2$ en $(-1, -1)$, le maximum vaut $2$ en $(1, 1)$. Ici, la convexité ne s’appliquait pas : un cercle n’est pas défini par une contrainte affine.

Deux droites de niveau sont tangentes au cercle : les conditions de Lagrange donnent donc deux candidats, un maximum en (1, 1) et un minimum en (−1, −1). Seule la comparaison des valeurs les distingue.

Piège

Une contrainte d’égalité non affine rend le problème non convexe, même si $f$ est convexe. Sur le cercle, la fonction linéaire $x + y$ a deux candidats, dont un maximum. Ne concluez jamais « c’est le minimum » sans l’un des trois arguments ci-dessus.

En pratique, les petits systèmes de Lagrange se résolvent très bien par calcul formel :

import sympy as sp

x, y, lam = sp.symbols("x y lambda", real=True)
f = (x**2 + y**2) + ((x - 4)**2 + y**2) + ((x - 2)**2 + (y - 6)**2)   # entrepôt
L = f + lam * (x + y - 2)                                              # rocade

candidats = sp.solve([sp.diff(L, v) for v in (x, y, lam)], [x, y, lam], dict=True)
print(candidats)   # un seul candidat : x = 1, y = 1, lambda = 6

En entretien

« À l’optimum sous une contrainte d’égalité, le gradient de l’objectif est colinéaire à celui de la contrainte : les lignes de niveau sont tangentes à la contrainte. Le multiplicateur de Lagrange mesure combien l’optimum gagnerait si l’on relâchait un peu la contrainte. »

En résumé

• Sous contrainte, le gradient de $f$ ne s’annule plus à l’optimum ; il devient colinéaire aux gradients des contraintes (condition de tangence).
• Le lagrangien $L = f + \sum_j \lambda_j h_j$ transforme le problème en recherche de ses points critiques : $\nabla_x L = 0$ et $h_j = 0$.
• Le théorème exige la qualification : gradients des contraintes linéairement indépendants à l’optimum.
• Le multiplicateur est une sensibilité : $dV/db = -\lambda$, comme un prix dual en programmation linéaire.
• Les conditions sont nécessaires : on conclut par la convexité ($f$ convexe, contraintes affines), par compacité et comparaison des candidats, ou par le second ordre.

Exercices

Exercice · La canette la plus économe

facile

Une canette cylindrique de rayon $r$ et de hauteur $h$ doit contenir $V = 330$ cm³. On veut minimiser la surface de métal $S = 2\pi r^2 + 2\pi r h$. Montrez avec Lagrange que la hauteur optimale est égale au diamètre, puis calculez les dimensions.

Voir la solution

La contrainte est $\pi r^2 h - V = 0$. Le lagrangien $L = 2\pi r^2 + 2\pi r h + \lambda(\pi r^2 h - V)$ donne :

• $\partial L / \partial r = 4\pi r + 2\pi h + 2\lambda \pi r h = 0$ ;
• $\partial L / \partial h = 2\pi r + \lambda \pi r^2 = 0$, d’où $\lambda = -2/r$.

En reportant dans la première : $4\pi r + 2\pi h - 4\pi h = 0$, soit $h = 2r$. La hauteur est égale au diamètre.

Alors $V = 2\pi r^3$, donc $r = (330 / 2\pi)^{1/3} \approx 3{,}74$ cm et $h \approx 7{,}49$ cm, pour une surface d’environ 264 cm². Une vraie canette (rayon 3,3 cm, donc hauteur d’environ 9,6 cm pour le même volume) est plus élancée : sa surface totale serait d’environ 268 cm², soit 1,5 % de plus seulement, un prix raisonnable pour une canette qui tient bien en main.

En code

Python

import numpy as np
from scipy.optimize import minimize_scalar

V = 330
surface = lambda r, h: 2 * np.pi * r**2 + 2 * np.pi * r * h

r = (V / (2 * np.pi)) ** (1 / 3)              # solution de Lagrange : h = 2r
print(r, 2 * r, surface(r, 2 * r))            # 3.745 7.49 264.4

# Contrôle : on élimine h = V / (π r²) et on minimise en r seul
res = minimize_scalar(lambda r: surface(r, V / (np.pi * r**2)), bounds=(1, 10), method="bounded")
print(res.x, res.fun)                         # 3.745 264.4

h_reel = V / (np.pi * 3.3**2)                 # vraie canette de rayon 3,3 cm
print(h_reel, surface(3.3, h_reel) / res.fun - 1)   # 9.65 0.015 : 1,5 % de métal en plus

R

V <- 330
surface <- function(r, h) 2 * pi * r^2 + 2 * pi * r * h

r <- (V / (2 * pi))^(1 / 3)                   # solution de Lagrange : h = 2r
c(r, 2 * r, surface(r, 2 * r))                # 3.745 7.490 264.4

# Contrôle : on élimine h = V / (π r²) et on minimise en r seul
res <- optimize(function(r) surface(r, V / (pi * r^2)), c(1, 10))
res$minimum; res$objective                    # 3.745 ; 264.4

h_reel <- V / (pi * 3.3^2)                    # vraie canette de rayon 3,3 cm
h_reel; surface(3.3, h_reel) / res$objective - 1   # 9.65 ; 0.015 : 1,5 % de plus

Exercice · Un enclos contre un mur

moyen

On veut construire un enclos rectangulaire contre un long mur, avec 8 mètres de grillage pour les trois autres côtés : un côté de longueur $x$ parallèle au mur, et deux côtés de longueur $y$. Quelles dimensions maximisent l’aire ? Que vaut le multiplicateur, et que signifie-t-il ?

Voir la solution

On maximise $xy$ sous $x + 2y = 8$, soit on minimise $f = -xy$ sous $h = x + 2y - 8 = 0$. Le lagrangien $L = -xy + \lambda(x + 2y - 8)$ donne $-y + \lambda = 0$ et $-x + 2\lambda = 0$, donc $y = \lambda$ et $x = 2\lambda$. La contrainte impose $4\lambda = 8$, d’où $\lambda = 2$, $x = 4$ m et $y = 2$ m, pour une aire de 8 m².

C’est bien un maximum : sur le segment réalisable ($0 \leq y \leq 4$), l’aire vaut $(8 - 2y)y$, une parabole tournée vers le bas qui s’annule aux extrémités.

Interprétation : avec la contrainte $x + 2y = b$, l’aire optimale vaut $b^2/8$, de dérivée $b/4 = 2$ pour $b = 8$. Chaque mètre de grillage supplémentaire rapporte environ 2 m² d’aire : c’est $\lambda$ (le signe vient de ce qu’on a minimisé $-xy$, dont la valeur optimale $-b^2/8$ a pour dérivée $-\lambda$).

En code

Python

import numpy as np

# Conditions de Lagrange : -y + λ = 0, -x + 2λ = 0, x + 2y = b (inconnues x, y, λ)
def enclos(b):
    M = np.array([[0, -1, 1], [-1, 0, 2], [1, 2, 0]], dtype=float)
    return np.linalg.solve(M, [0, 0, b])

x, y, lam = enclos(8)
print(x, y, lam, x * y)                         # 4.0 2.0 2.0 8.0

# Sensibilité : aire optimale pour 8,01 m de grillage
x2, y2, _ = enclos(8.01)
print((x2 * y2 - x * y) / 0.01)                 # 2.00125 : environ λ = 2 m² par mètre

R

# Conditions de Lagrange : -y + λ = 0, -x + 2λ = 0, x + 2y = b (inconnues x, y, λ)
enclos <- function(b) solve(rbind(c(0, -1, 1), c(-1, 0, 2), c(1, 2, 0)), c(0, 0, b))

s <- enclos(8)
s; s[1] * s[2]                                  # x = 4, y = 2, λ = 2 ; aire 8

# Sensibilité : aire optimale pour 8,01 m de grillage
s2 <- enclos(8.01)
(s2[1] * s2[2] - s[1] * s[2]) / 0.01            # 2.00125 : environ λ = 2 m² par mètre

Exercice · Deux contraintes à la fois

difficile

Trouvez le point le plus proche de l’origine sur la droite de l’espace définie par $x + y + z = 3$ et $x - y = 1$, c’est-à-dire minimisez $x^2 + y^2 + z^2$ sous ces deux contraintes. Donnez les multiplicateurs.

Voir la solution

Le lagrangien est $L = x^2 + y^2 + z^2 + \lambda_1(x + y + z - 3) + \lambda_2(x - y - 1)$. Les gradients des contraintes, $(1, 1, 1)$ et $(1, -1, 0)$, sont linéairement indépendants : le problème est qualifié. Les conditions :

$$2x + \lambda_1 + \lambda_2 = 0, \quad 2y + \lambda_1 - \lambda_2 = 0, \quad 2z + \lambda_1 = 0, \quad x + y + z = 3, \quad x - y = 1$$

Des contraintes, $y = x - 1$ et $z = 4 - 2x$. En ajoutant les deux premières équations : $2(x + y) + 2\lambda_1 = 0$, et la troisième donne $\lambda_1 = -2z$. Donc $x + y = 2z$, soit $2x - 1 = 2(4 - 2x)$, d’où $x = 1{,}5$, puis $y = 0{,}5$ et $z = 1$.

Les multiplicateurs valent $\lambda_1 = -2z = -2$ et $\lambda_2 = -2x - \lambda_1 = -1$ (vérification : $2y + \lambda_1 - \lambda_2 = 1 - 2 + 1 = 0$). La distance minimale au carré vaut $2{,}25 + 0{,}25 + 1 = 3{,}5$. L’objectif est convexe et les contraintes affines : c’est le minimum global.

En code

Python

import numpy as np

# Inconnues (x, y, z, λ1, λ2) : stationnarité (3 équations) puis contraintes (2)
M = np.array([[2, 0, 0, 1,  1],
              [0, 2, 0, 1, -1],
              [0, 0, 2, 1,  0],
              [1, 1, 1, 0,  0],
              [1, -1, 0, 0, 0]], dtype=float)
x, y, z, l1, l2 = np.linalg.solve(M, [0, 0, 0, 3, 1])
print(x, y, z, l1, l2)          # 1.5 0.5 1.0 -2.0 -1.0
print(x**2 + y**2 + z**2)       # 3.5

R

# Inconnues (x, y, z, λ1, λ2) : stationnarité (3 équations) puis contraintes (2)
M <- rbind(c(2, 0, 0, 1, 1),
           c(0, 2, 0, 1, -1),
           c(0, 0, 2, 1, 0),
           c(1, 1, 1, 0, 0),
           c(1, -1, 0, 0, 0))
s <- solve(M, c(0, 0, 0, 3, 1))
s                               # 1.5 0.5 1.0 -2.0 -1.0
sum(s[1:3]^2)                   # 3.5