Introduction à l’Optimisation ^{1}

B. Rousselet ^{2} 27 avril 1998

Une version plus a jour peut etre cherchée sur ma page:http://math.unice.fr/membres/br.html

1réalisé par l’auteur avec l’aide technique de A. Omrane et le support financier du P.E.C. Tempus No 07 228-94 "Shape optimal design, application to structures and environment"

2Laboratoire J. A. Dieudonné, Parc Valrose, F 06108 Nice, Cédex 2, email : br@math.unice.fr

2

Table des matières

1 Introduction  7
1.1 Présentation générale . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.2 Introduction et notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.3 Résultats de base . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.4 Projection sur un sous -espace paramétré . . . . . . . . . . . . . . . . . . . . . . . 11
1.4.1 Introduction - Notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.4.2 Résolution au sens des moindres carrés . . . . . . . . . . . . . . . . . . . . . 12
1.4.3 Projection et résolubilité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.5 Minimisation dans IR^{n} . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.5.2 Rappel de calcul différentiel . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.5.3 Résultats de base . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
1.6 Algorithmes pour l’optimisation sans contraintes... . . . . . . . . . . . . . . . . . . 20
1.6.1 Algorithme du gradient . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2 Minimisation avec contraintes  23
2.1 Minimisation avec contraintes d’égalités linéaires . . . . . . . . . . . . . . . . . . . 23
2.2 Fonction quadratique avec contraintes d’égalités linéaires . . . . . . . . . . . . . . . 28
2.2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.2.2 Elimination . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.2.3 Algorithmes d’élimination généralisée . . . . . . . . . . . . . . . . . . . . . 29
2.2.4 Triangulation par des matrices orthogonales . . . . . . . . . . . . . . . . . . 31
2.2.5 Programmation quadratique . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
2.3 Minimisation avec contraintes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
2.3.1 Condition d’optimalité avec contraintes d’égalité . . . . . . . . . . . . . . . 34
2.3.2 Minimisation avec contraintes d’inégalités . . . . . . . . . . . . . . . . . . . 39
2.4 Devoir : optimisation en présence d’inégalités simples . . . . . . . . . . . . . . . . 46
2.5 Esquisse de solution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
2.6 Examen : Eléments finis et optimisation . . . . . . . . . . . . . . . . . . . . . . . . 52
2.7 Une présentation de la programmation quadratique séquentielle . . . . . . . . . . . 54
2.7.1 Introduction, l’algorithme de Newton sans contraintes . . . . . . . . . . . . 54

2.7.2 Programmation quadratique séquentielle . . . . . . . . . . . . . . . . . . . . 55
2.7.3 Devoir : convergence de l’algorithme . . . . . . . . . . . . . . . . . . . . . . 56
3 Exemples d’optimisation d’origine mécanique  63
3.1 Introduction ; exemple sans contraintes . . . . . . . . . . . . . . . . . . . . . . . . . 63
3.2 Exemples avec contraintes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
3.2.1 Cas d’une liaison (avec deux ressorts) \underline{bilatérale} . . . . . . . . . . . . . . . . 66
3.2.2 Liaisons Unilatérales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
3.3 Analyse en grands déplacements . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
4 Optimisation dans des espaces fonctionnels  73
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
4.2 Automatique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
4.3 Deux théorèmes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
4.3.1 Contraintes d’égalité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
4.3.2 Application à la conception de systèmes . . . . . . . . . . . . . . . . . . . . 75
4.3.3 Contraintes d’inégalités . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79

Table des figures

1.1 Projection orthogonale de f ∈ E . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.2 Lissage par une droite : droite des moindres carrés . . . . . . . . . . . . . . . . . . 14
1.3 Distance (Pythagore) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.4 fonctions avec f′′(0) = 0 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.5 fonction avec plusieurs minimums locaux . . . . . . . . . . . . . . . . . . . . . . . . 17
1.6 fonction f vérifiant l’hypothèse H_{1} . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.1 Projection sur un sous espace ^{t}bv − c = 0 . . . . . . . . . . . . . . . . . . . . . . . 26
2.2 Cas où ^{t}B B = IIR^{m} . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.3 La C.N.O. à partir des courbes de niveau . . . . . . . . . . . . . . . . . . . . . . . 27
2.4 Cas où ^{t}s_{j} z = 0 ; j = 1, 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
2.5 symétrie orthogonale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
2.6 Courbe tangente . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
2.7 Exercice 2.8, minimisation d’une fonction J . . . . . . . . . . . . . . . . . . . . . . 38
2.8 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
2.9 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
2.10 En 1 variable . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
2.11 Projection en 2 variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
2.12 La solution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
2.13 Un pas de gradient projeté . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
3.1 Equilibre des forces. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
3.2 Une liaison bilatérale ; schématisation d’un rail . . . . . . . . . . . . . . . . . . . . 66
4.1 Barre chargée verticalement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
4.2 Aires optimales. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80

6  TABLE DES FIGURES

Chapitre 1

Introduction

1.1 Présentation générale

On considère l’optimisation d’abord sans contraintes en dimension finie ; puis nous passons au cas avec contraintes d’égalités et inégalités ; nous établissons les conditions d’optimalité avec des multiplicateurs de Lagrange et considérons l’approximation numérique de l’optimum ; une présentation de la programmation mécanique séquentielle est fournie. Ces méthodes sont utilisées pour des problèmes de statique de structures élastiques en présence de liaisons unilatérales et en grands déplacements. L’optimisation dans des espaces de dimension infinie est enfin esquissée.

1.2 Introduction et notations

Nous considérons dans ce chapitre la minimisation de fonctions en dimension finie (ce qui signifie dans notre cas un espace vectoriel E de dimension finie sur IR ; on l’identifiera le plus souvent à IR^{n}). Nous considérons d’abord le cas significatif des fonctions quadratiques ; ceci par souci de simplicité mais aussi parceque au voisinage d’un minimum, une fonction peut être approchée par une fonction quadratique (écrire une formule de Taylor). Nous verrons dans les chapitres suivants que cela intervient tant du point de vue théorique qu’ algorithmique : une condition suffisante pour un optimum local est que le Hessien soit défini positif ; l’algorithme de Newton pour minimiser une fonction consiste à l’approcher par une fonction quadratique ; les méthodes dites de quasi-Newton reposent sur une variante de cette idée et constituent une classe très importante d’algorithmes ; voir aussi les algorithmes d’optimisation avec contraintes. \underline{Notations} :

• E Espace vectoriel de dimension finie n • a : E × E ⟶ IR forme bilinéaire symétrique.

• ℓ : E ⟶ IR forme linéaire.

Rappelons qu’en dimension \underline{finie} les formes linéaires et bilinéaires sont continues ; le produit scalaire dans E est noté (\underline{x}, \underline{y}), ∥\underline{x}∥ désigne la norme associée.

Après choix d’une base (\underline{e}_{i})_{1≤i≤n}, \underline{x} = ∑_{j=1}^{n} x_{i} \underline{e}_{i} \underline{y} = ∑_{i=1}^{n} y_{j} \underline{e}_{j}

ℓ(\underline{x}) = ^{t}F x a(\underline{x}, \underline{y}) = ^{t}y A x où x = ( x_{1} ; ⋮ ; x_{n} ) y = ( y_{1} ; ⋮ ; y_{n} ) avec A_{i j} = a(e_{i}, e_{j})

l’expression de droite est un produit matriciel, ^{t}y désigne le transposé de y : ^{t}y = [y_{1}, ..., y_{n}] ; noter la différence de position de \underline{y} et de y a(\underline{x}, \underline{y}) = ^{t}y A x; comme a est symétrique, A est une matrice

symétrique ; quand la base est \underline{orthonormée} (\underline{x}, \underline{y}) = ∑_{i=1}^{n} x_{i}ȳ_{i} = ^{t}y x, ∥\underline{x}∥^{2} = ^{t}x x = ∥x∥^{2} . Notons

que A est aussi matrice de l’application linéaire A associée à la forme bilinéaire a : a(\underline{x}, \underline{y}) = (A\underline{x}, \underline{y}) Indiquons que le cas de fonctions en dimension finie est souvent une approximation de \underline{fonctionnelles} définie sur des espaces de fonctions de dimension infinie ; c’est le cas classique de la méthode de Galerkine et en particulier de la méthode des éléments finis si répandue en calcul de structures élastiques. L’élasticité linéaire fournit de très nombreux exemples de minimisation de fonctionelles quadratiques : l’énergie potentielle totale d’un système élastique (en élasticité linéaire) est une forme quadratique : la position d’équilibre est atteinte au minimum.

Rappel de calcul différentiel : Dérivée directionnelle (ou de Gateau) J : E ⟶ IR admet au point \underline{x} une dérivée dans la direction \underline{y} si et seulement si

lim_{t→0} \frac{J(x + ty) − J(x)}{t} existe ; on la note J′(x, y).

Différentielle (ou dérivée au sens de Fréchet) J : E ⟶ IR est dérivable en \underline{x} si et seulement si il existe une forme linéaire notée J′(\underline{x}) telle que

pour tout \underline{y} ∈ E |J(\underline{x} + \underline{y}) − J(\underline{x}) − J′(\underline{x}) \underline{y}| = o(∥\underline{y}∥) quand y → 0 ou lim_{∥y∥→0} \frac{|J(\underline{x} + \underline{y}) − J(\underline{x}) − J′(\underline{x}) \underline{y}|}{∥y∥} = 0

L’existence de la dérivée au sens de Gateau est un peu plus forte que l’existence de dérivées partielles pour lesquelles la limite du quotient différentiel n’existe que pour y = a_{i} une base de E; remarquer la notation : J′(x, a_{i}) = \frac{∂J}{∂x_{i}}. On donne dans les cours élémentaires des contre exemples variés de fonctions dérivables au sens de Gateau qui ne le sont pas au sens de Fréchet mais on montrera facilement que les fonctions dérivables au sens de Fréchet le sont au sens de Gateau ; la non équivalence résulte de situations plutôt pathologiques ! Attention à la notion de gradient très utile en optimisation.

Définition 1.1 Le gradient associé à la forme linéaire de la dérivee est défini par la formule :

∀y J′(x, y) = (gradJ, y) ou (gradJ, a_{i}) = J′(x, a_{i}) = \frac{∂J}{∂x_{i}}

Mais les composantes de gradJ ne sont pas (gradJ, a_{i}) sauf si la base est orthonormée.

Exercice 1.1 Dans le cas où la base a_{i} n’est pas orthonormée, écrire un système linéaire qui fournit les composantes d’un vecteur associé à une forme linéaire (et donc celle du gradient à partir des dérivées partielles).

suggestion : la matrice M est donnée par M_{i,j} = (a_{i}, a_{j}) ; cette matrice porte le nom de Gramm.

Exercice 1.2 Montrer que J(\underline{x}) = \frac{1}{2}a(\underline{x}, \underline{x}) − ℓ(\underline{x}) est Fréchet dérivable et de dérivée J′(\underline{x}, \underline{y}) = a(\underline{x}, \underline{y}) − ℓ(\underline{y}) = ^{t}y A x −^{t}F y.

Exercice 1.3 Montrer qu’une fonction dérivable au sens de Fréchet l’est au sens de Gateau.

1.3 Résultats de base

Proposition 1.1 Soit E espace vectoriel de dimension n a : E × E ⟶ IR une forme bilinéaire symétrique b : E ⟶ IR une forme linéaire

et J : E ⟶ IR J(\underline{x}) = \frac{1}{2}a(\underline{x}, \underline{x}) − ℓ(\underline{x}) = \frac{1}{2}^{t}x A x − ^{t}x F ;

abus de notations J(\underline{x}) = J(x)

(i) si J atteint un minimum relatif ou local en un point \underline{x}_{∗} ∈ E alors ∀\underline{y} ∈ E J′(\underline{x}_{∗}, \underline{y}) = 0 ou Ax_{∗} = F (condition nécessaire d’optimalité ou C.N.O.) (ii) Si de plus la forme bilinéaire est définie positive : ∃γ > 0 , ∀\underline{x} ∈ E a(\underline{x}, \underline{x}) ≥ γ∥\underline{x}∥^{2} ( ou tx A x ≥ γ ∥x∥^{2}) la C.N.O. admet une unique solution x_{∗} et cette solution réalise le minimum absolu (ou global) de J sur E.) elle est donc aussi C.S.O. (condition suffisante d’optimalité)^{1}

\underline{La démonstration} est simple et ses méthodes s’étendent à des situations plus compliquées (voir §1.3)

(i) soit x_{∗} un minimum relatif de J, alors pour tout y ∈ E et t ∈ IR petit J(\underline{x_{∗}} + t\underline{y}) ≥ J(\underline{x_{∗}})

donc pour t > 0 \frac{J(\underline{x_{∗}} + t\underline{y}) − J(\underline{x∗})}{t} ≥ 0

et pour t < 0 \frac{J(\underline{x_{∗}} + t\underline{y}) − J(\underline{x∗})}{t} ≤ 0 .

D’où en faisant tendre t ⟶ 0 par valeurs positives J′(\underline{x_{∗}}, \underline{y}) ≥ 0 puis par valeurs négatives J′(\underline{x_{∗}}, \underline{y}) ≤ 0 et donc J′(\underline{x_{∗}}, \underline{y}) = 0 ce qui se traduit par ∀y ∈ IR^{n} ^{t} (A x_{∗} − F) = 0 d’où A x_{∗} − F = 0.

1Si besoin de clarifier son vocabulaire logique : il faut, condition nécessaire ; il suffit, condition suffisante !

(ii)

Lemme 1.1 : Sous l’hypothèse (ii), soit A l’application linéaire associée à a : a(\underline{x}, \underline{y}) = (A \underline{x}, \underline{y}), A est bijective ; la matrice associée est inversible.

En effet : si A \underline{x} = 0 alors a(\underline{x}, \underline{x}) = 0 et donc avec l’hypothèse \underline{x} = 0, A est injective et donc bijective puisque nous sommes en dimension finie.

Conséquence : la C.N.O. admet une unique solution ; de plus un calcul facile donne :

J(x + y) = J(x) + ^{t}y A x − ^{t}y F + \frac{1}{2} ^{t}y A y

quand x = x_{∗} , la C.N.O. fournit :

J(x_{∗} + y) = J(x_{∗}) + \frac{1}{2} ^{t}y A y

on a donc bien ∀y ∈ IR^{n} J(x_{∗} + y) ≥ J(x_{∗}) ce qui montre que x_{∗} est bien un minimum absolu (ou global) et non pas relatif (ou local).

Exercice 1.4 (rappel)

• a définie positive si et seulement si toutes les valeurs propres de A (ou de A) sont strictement positives.

• a est définie positive si et seulement si : ∀x ∈ E a(x, x) > 0 (avec E de dimension finie).

Exercice 1.5 a) exprimer J dans une base de valeurs propres de A, determiner ainsi le minimum de J.

b) En dimension 2 ou 3 , \underline{former les courbes de niveau} de J.

c) Cette méthode est elle interéssante numériquement dans le cas où A est une matrice 1000 × 1000 ? (Consulter éventuellement un cours d’analyse numérique matricielle)

Exercice 1.6 a) Reformuler la proposition si A est définie négative.

b) Que peut -on dire si les valeurs propres de A sont positives ou nulles ? (courbes de niveau).

c) Mêmes questions si les valeurs propres sont de signe quelconque mais non nulles ? (courbes de niveau).

Exercice 1.7 (élémentaire) Soit f(x_{1}, x_{2}) = ax_{1}^{2} + bx_{1} x_{2} + cx_{2}^{2} + dx_{1} + ex_{2}

a) Calculer la dérivée de f

b) en déduire une écriture matricielle de f.

Exercice 1.8 1. Soit B matrice à n lignes et m colonnes indépendantes avec n ≥ m, montrer

que A = ^{t}B B est une matrice m × m symétrique et définie positive.

2. Donner des exemples issus de la mécanique des structures.

1.4 Projection sur un sous -espace paramétré

1.4.1 Introduction - Notations

Pour une bonne compréhension de l’optimisation , il me parait indispensable de maîtriser d’une part l’algèbre linéaire et le calcul matriciel et d’autre part la géométrie affine euclidienne ; nous rappelons ici quelques principes utiles dans ce paragraphe ; se reporter à un manuel de base. Soit donc E un espace vectoriel euclidien (muni d’un produit scalaire) de dimension n et soient (b_{j})_{1≤j≤m} un système \underline{libre} vecteurs de E; le sous -espace vectoriel engendré

F = \{\underline{y} ∈ E, ∃ (x_{j})_{1≤j≤m} ∈ IR^{m} y = ∑_{i=1}^{m} x_{j} \underline{b}_{j}\}  (1.1)

F est un sous- espace paramétré ; les x_{j} sont les paramètres ;

Fig. 1.1 – Projection orthogonale de f ∈ E

il est bien connu en géométrie euclidienne que si \underline{f} ∈ E, il existe une unique projection orthogonale P \underline{f} ∈ F, il existe donc des paramètres λ_{j∗} tels que P \underline{f} = ∑ λ_{j}_{∗} \underline{b}_{j} vérifient pour k = 1, ..., m.

(\underline{f} − ∑_{i=1}^{m} λ_{i}_{∗} \underline{b}_{i} , \underline{b}_{k} ) = 0  (1.2)

Nous allons écrire matriciellement cette relation et la retrouver à l’aide du résultat du §1.1.

Après le choix d’une base (\underline{e}_{i})_{i=1,...,n} comme dans l’introduction, \underline{b}_{j} = ∑_{i=1}^{n} b_{i j} e_{i}, posons b_{j} = [ b_{1 j} ; ⋮ ; b_{n j} ] et B matrice de coefficients b_{i j} ; il sera commode parfois de considèrer B par blocs : B = [b_{1}, ..., b_{m}] où les b_{i} désignent donc les blocs des colonnes de B; dans ces conditions si x ∈ IR^{m} on peut effectuer le produit par blocs : B x = ∑ b_{j} x_{j} = ∑ x_{j} b_{j} et il convient de remarquer que ∑ x_{j} b_{j} sont les composantes du vecteur ∑ x_{j} \underline{b}_{j} ; noter que dans l’usage des espaces vectoriels on écrit les scalaires à gauche des vecteurs mais quand on veut

representer ∑ x_{j} \underline{b}_{j} par un produit matriciel par blocs Bx = [b_{1}, ..., b_{m}] [ x_{1} ; ⋮ ; x_{m} ] les scalaires ap-

paraissent à droite du vecteur.

Exercice 1.9 Interpreter par blocs le produit ^{t}y B; caractériser le noyau de ^{t}B; comparer avec ImB.

Exercice 1.10 Utiliser une représentation graphique des matrices rectangulaires B ; interpreter

ainsi B x, ^{t}B B, B^{t}B; ^{t}y ^{t}B....

Nous pouvons donc écrire matriciellement (1.2) en supposant que \underline{e}_{i} est une base \underline{orthonormale} :

(\underline{e}_{i}, \underline{e}_{j}) = ^{t}\underline{e}_{i} \underline{e}_{j} = δ_{ij} ^{t} (f − B x_{∗}) b_{k} = 0 et donc ^{t} (f − B x_{∗}) B = 0  (1.3)

C’est cette dernière équation que nous allons retrouver.

1.4.2 Résolution au sens des moindres carrés

Dans la pratique il est fréquent que l’on ait à résoudre un système linéaire B x = f avec B matrice à n lignes et m colonnes (indépendantes), avec n ≥ m. Nous verrons au §3. que ce système peut admettre des solutions mais le cas le plus fréquent est qu’il n’admette pas de solutions quand n > m : " il y a trop d’équations, le système est surdeterminé". Quand on a besoin d’une "solution " on utilise souvent la notion de " solution au sens des moindres carrés ". Résoudre au sens des moindres carrés signifie chercher le x_{∗} ∈ IR^{m} qui minimise J(x) = ∥B x − \underline{f} ∥_{2}^{2} C’est à dire le carré de la distance de f au sous- espace F défini en (1.2) où ∥\underline{y}∥_{2}^{2} = (y, y) = ^{t}y y est le produit scalaire de E.

Dorénavant nous omettrons l’indice 2 pour la norme : ∥\underline{y}∥^{2} = (y, y) .

Proposition 1.2 : Soit B une matrice à n lignes et m colonnes indépendantes, il existe un x^{∗} unique qui minimise J(x) = ∥Bx − f∥^{2} ; il satisfait la condition nécessaire et suffisante ^{t}e^{∗} B = 0 avec e^{∗} = f − B x^{∗}. Ceci définit x^{∗} solution de ^{t}B B x^{∗} −^{t}B f = 0.

\underline{Interprétation géométrique} : B x^{∗} n’est autre que le vecteur colonne de la projection orthogonale P f sur F ; en effet ^{t}e^{∗} B = 0 n’est autre que (1.3), une écriture matricielle de (1.2) ; cette proposition n’est donc rien d’autre que : " la perpendiculaire est plus courte que toute oblique ". (comme disait l’un de mes professeurs de Lycée) ; mais on peut dire aussi dans ce contexte que l’erreur e_{∗} est orthogonale aux colonnes de B. La \underline{Démonstration} peut se faire simplement avec le résultat de base du §1.1 D’abord en dévelopant le produit matriciel : J(x) = ^{t} (B x − f) (B x − f) on trouve J(x) = ^{t}x^{t}B B x − 2^{t}x ^{t}B f + ^{t}f f qui est donc de la forme du J de la proposition ?? avec A = 2^{t}B B F = 2^{t}B f E = IR^{m} et avec un terme constant ^{t}f f qui n’intervient pas dans la détermination de x; enfin avec l’exercice 5, A = ^{t}B B est définie positive ; la proposition 2 indique donc l’existence, et l’unicité du minimum x_{∗}, elle fournit de plus la C.N.S.O. A x_{∗} − F = 0 soit ici ^{t}B B x_{∗} − ^{t}B f = 0 ou ^{t}B (B x_{∗} − f) = 0

Utilisation pratique : pour déterminer la "solution au sens des moindres carrés " on résout les équations dites "normales "

tB B x_{∗} = ^{t}B f

elles ne sont autres qu’une autre écriture de ^{t}B e^{∗} = 0. Si vous avez fait l’exercice 1.8, vous savez que ^{t}B B est une matrice carrée m × m; il est donc numériquement facile de résoudre au sens des moindres carrés si vous avez peu d’inconnues même avec beaucoups d’équations !

Exercice 1.11 ( lissage par une droite, droite des moindres carrés) on dispose de points (ξ_{i}, η_{i}) et l’on souhaite trouver une droite qui passe au mieux par les points (ξ_{i}, eta_{i})

(pensez à des points de mesure de 2 quantités ξ et η supposées reliées par une loi linéaire η = c+dξ de coefficient c et d inconnu) ; on va chercher cette droite au sens des moindres carrés i.e. résoudre au sens des moindres carrés :

c + ξ_{i} d  =  η_{i}  i = 1, ..., n

les inconnues sont ici c et d.

a) écrire un système linéaire B x = f avec B n lignes, 2 colones

Fig. 1.2 – Lissage par une droite : droite des moindres carrés

x 2 lignes f n lignes.

b) trouver x_{∗} au sens des moindres carrés (les coefficients c et d).

c) vérifier que c + ξ̄d = η̄ avec ξ̄ et η̄ moyennes de (ξ̄_{i}) et (η̄_{i}).

d) d peut s’interpreter comme une covariance si l’on considère ξ_{i} et η_{i} comme des variables aléatoires équiprobables ; comment s’appelle cette droite en probabilités- statistiques ?

1.4.3 Projection et résolubilité

Reprenons les notations du paragraphe précédent, en se rappelant que B x_{∗} est la projection orthogonale de f sur F P f = B x_{∗} avec

tB B x_{∗} = ^{t}B f

On a donc :

Proposition 1.3 i) La projection P : E ⟶ F = {B x, x ∈ IR^{m}} est donnée par P f = B(^{t}BB)^{−1} ^{t}Bf la matrice de P est B(^{t}BB)^{−1} ^{t}B on a (^{t}f − P f) P f = 0 ii) On vérifie P^{2} = P et ^{t}P = P donc P est aussi orthogonale.

\underline{Attention} : On a vu (exercice 1.8) que comme les colonnes de B sont indépendantes ^{t}B B est définie positive donc inversible ; (^{t}B B)^{−1} a bien un sens ; mais B n’est pas inversible : cela n’a pas de sens car c’est une matrice rectangulaire !

\underline{Cas particulier fondamental} : projection sur une droite parametrée ; soit b ∈ IR^{n} D = {y ∈ IR^{n}/∃x ∈ IR, y = xb}

tB B = ^{t}b b ∈ IR , P f = \frac{b^{t}b f}{^{t}b b}

noter que cette projection est invariante quand on multiplie b par un scalaire, on a donc avec

u = \frac{b}{(^{t}b b)^{1/2}} , P f = u^{t}u f

géométriquement ^{t}u f = ∥f∥ cos θ avec θ angle entre u et f si bien que P f = cos θ ∥f∥ u est la formule bien connue de la projection sur une droite de vecteur unitaire u. On retrouve aussi que d(f, D) = ^{t}(f − P f)(f − P f) comme ^{t}(f − P f)P f = 0 on a :

d(f, D) = ^{t}(f − P f)f = ^{t}(f − u^{t}u f)f
= ^{t}f f −^{t}f u^{t}u f
= ^{t}f f −^{t}(P f) P f

ceci n’est autre que le théorème de Pythagore !

Fig. 1.3 – Distance (Pythagore)

Corollaire 1.1 : IR^{n} se décompose en une somme directe \underline{orthogonale} de F = Im B = Im P et de Ker B = Ker P ; en pratique si f ∈ IR^{n}

f = Bx_{∗} + (f − Bx_{∗}) avec \{ \begin{matrix}f − Bx_{∗} ∈ Ker^{t}B ou \\ ^{t}B Bx_{∗} −^{t}B f = 0 \end{matrix}

Bx_{∗} et f − Bx_{∗} sont orthogonaux et cette écriture est unique : si f = b + n avec b ∈ Im B et n ∈ Ker^{t}B, alors b = Bx_{∗} avec ^{t}B Bx_{∗} −^{t}B f = 0 et n = f − Bx_{∗}.

\underline{En effet} avec la proposition 1.2. f−Bx_{∗} ∈ Ker^{t}B; d’autre part si y ∈ Im B et z ∈ Ker^{t}B : y = Bx et^{t}y z = ^{t}x^{t}B z = 0 ce qui montre l’orthogonalité ; il reste juste à vérifier que Im B ∩ Ker^{t}B = {0} en effet si y = Bx et ^{t}B y = 0 alors ^{t}y y = ^{t}x B y = 0 Ce corollaire est très important en pratique sous la forme suivante.

Proposition 1.4 Soit le système linéaire surdéterminé Bx = f avec B à n lignes et m colonnes indépendantes avec n ≥ m, f ∈ IR^{n} et x ∈ IR^{m}; ce système est soluble si et seulement si : ∀ y ^{t} y B = 0 ⟹ ^{t} y f = 0 (ce qui signifie f ∈ (Ker ^{t}B)^{⊥}) en d’autres termes : le système est soluble (ou f ∈ Im B) si et seulement si f ∈ (Ker ^{t}B)^{⊥} ou encore Im B = (Ker ^{t}B)^{⊥}

\underline{Cas particulier} : B = A_{λ} = A − λI avec A matrice carée ; quand λ est valeur propre de A , la condition ^{t}y A_{λ} = 0 signifie y vecteur propre à gauche de A_{λ} ou vecteur propre de ^{t} A_{λ}, on a donc :

Corollaire 1.2 Soit A matrice inversible, λ valeur propre de A (A − λ I)x = f ce système est soluble si et seulement si b est orthogonal au sous- espace propre de ^{t}A − λ I.

Remarque 1.1 En dimension infinie, ce résultat est connu sous le nom d’alternative de Fredholm .

1.5 Minimisation dans IR^{n}

1.5.1 Introduction .

Ce paragraphe vise à étendre le résultat de base de la proposition 1.1. à des fonctions plus générales ; cela n’est pas aisé ; tant que l’on ne s’intéresse qu’à un résultat d’existence, l’hypothèse suivante est commode :

H 1 lim_{∥x∥→+∞} J(x) = + ∞ parfois appelée coercitivité

de J car la fonctionelle quadratique a cette proprièté quand la forme bilinéaire est coercitive. L’obtention d’une condition nécessaire d’optimalité demande seulement que la fonction soit différentiable. Cela se complique beaucoup si l’on souhaite une condition nécessaire et suffisante : en effet le Hesien positif est une C.N.O. mais pas vraiment suffisante ; le Hessien défini positif est suffisant mais pas nécessaire ; il est facile de le voir en une variable. La fonction f(x) = x^{3} satisfait f′(0) = 0 f′′(0) = 0 a-t-on envie de dire que zéro est un minimum local ?

Minimisation dans IR^{n}  17

Fig. 1.4 – fonctions avec f′′(0) = 0

f(x) = x^{4} Dans le cas f′(0) = 0 f′′(0) = 0 et zéro est un minimum absolu bien que f′′(0) ne soit pas strictement positif.

Mais le pire n’est pas là, considérons cette fonction g avec plusieurs minimums locaux, en tous

Fig. 1.5 – fonction avec plusieurs minimums locaux

ces minimums f′(x_{i∗}) = 0 x_{i∗} et f′′(x_{i∗}) > 0 et l’on voudrait bien caractériser le meilleur minimum absolu et disposer d’algorithmes de calcul. Ces questions ne sont pas passées inaperçues dès les débuts des algorithmes d’optimisation (années 60) mais ne se sont vraiment développées que dans les années 80 ; les applications à l’art de l’ingénieur démarrent et sont prometeuses (Arora et al [?] (1995)) ; pourquoi ce changement de perspectives : on commence à disposer de moyens de calculs suffisants pour analyser à faible coût de grands systèmes ; or la détermination numérique d’un minimum demande d’analyser de très nombreuses fois le système à optimiser.

1.5.2 Rappel de calcul différentiel

Nous allons avoir besoin de dérivée seconde de fonctions de plusieurs variables ; c’est une fonction de 2 variables vectorielles Définition 1.2 J est dite deux fois dérivable au sens de Gateau si la

lim_{t→0} \frac{J′(x + tz, y) − J′(x, y)}{t}

existe et on la note J′′(x; y, z).

Définition 1.3 Elle est dite deux fois dérivable au sens de Fréchet s’il existe une forme bilinéaire (y, z) ⟼ J′′(x)(y, z) telle que

lim_{∥z∥→0} \frac{∥J′(x + z)y − J′(x)y − J′′(x)(y, z)∥}{∥z∥} = 0

cette forme bilinéaire s’appelle souvent le Hessien et en notation matricielle J′′(x)(y, z) = ^{t}z H(x) y

Proposition 1.5 : Formule de Taylor à l’ordre 2 (suffisante pour nos applications)

1) J(x + y) = J(x) + J′(x)y + \frac{1}{2}J′′(x; y, y) + o(∥y∥^{2})

2) J(x + y) = J(x) + J′(x)y + ∫_{0}^{1}(1 − t)J′′(x + ty; y, y)dt

\underline{Démonstration} 1) La première formule n’est qu’un cas particulier très utile du 2) obtenu en approchant J′′(x + ty) par J′′(x) et ∫_{0}^{1}(1 − t)dt = \frac{1}{2} !

2) la formule 2) se déduit de la formule de Taylor en une variable en posant f(t) = J(x + ty) f(1) = f(0) + f′(0) + ∫_{0}^{1}(1 − t)f′′(t)dt (cette dernière formule résulte de 2 intégrations par parties)

1.5.3 Résultats de base

Définition 1.4 Soit J une fonction à minimiser, I = Inf J(x) (éventuellement −∞) ; (x_{k})_{k∈IN} est dite minimisante quand J(x_{k}) ⟶ I

\underline{Attention} : I peut n’être pas atteint : par exemple I = 0 pour f = e^{−x^{2}/2} mais la valeur 0 n’est atteinte pour aucune valeur de x ∈ IR. Remarquons que par définition d’une borne inférieure, l’existence de suites minimisantes est banale ; considérons le cas où I est fini, alors pour tout ε > 0, il existe x tel que I ≤ f(x) ≤ I + ε

Fig. 1.6 – fonction f vérifiant l’hypothèse H_{1}

il suffit de considèrer une suite ε_{n} ⟶ 0 pour disposer d’une suite x_{n} telleque f(x_{n}) ⟶ I.

Toutefois, le comportement de la suite x_{n} \underline{n’est pas évident} ; voici deux exemples.

a . f(x) = e^{−x^{2}/2} I = 0 ; si (x_{n}) est une suite minimisante |x_{n}| → +∞; le minimum n’est pas atteint ; mais f ne vérifie pas H1.

b . f(x) = sin x I = −1 ; si x_{n} est une suite minimisante, elle peut osciller au voisinage des points \frac{3π}{2} + 2kπ k ∈ Z; dans cet exemple il y a beaucoup de minimums absolus ; l’hypothèse H1 n’est pas vérifiée.

c.

Lemme 1.2 Sous l’hypothèse H 1 , une suite minimisante (x_{k}) est bornée.

Ce résultat très simple déroute souvent les étudiants, pourtant il suffit de raisonner par la contraposée : si la suite (x_{k}) n’est pas bornée on peut en extraire une sous- suite x_{k′} telle que ∥x_{k′}∥ ⟶ +∞ mais H 1 entraîne J(x_{k′}) ⟶ +∞; ceci est la négation de l’hypothèse J(x_{k′}) ⟶ I (sauf bien sûr si J était toujours égale à +∞, situation pathologique exclue de facto)

Proposition 1.6 Soit J : IR^{n} ⟶ IR, continue

i) Si J satisfait l’hypothèse H 1 alors J atteint son minimum en au moins un point x_{∗}. ii) Si J est différentiable, x_{∗} vérifie J′(x_{∗}) = 0 iii) Si J est deux fois différentiable, x_{∗} vérifie de plus ∀y ∈ IR^{n} ^{t}y H(x_{∗}) y ≥ 0 où H est le Hessien de J. iv) Si J′(x_{0}) = 0 et H(x_{0}) est défini positif, alors x_{0} est un minimum local isolé.

\underline{Démonstration} i) Je vais illustrer pour ce point, l’utilisation de la technique de la suite minimisante. Soit I = Inf_{x∈IR^{n}}J(x) ce nombre peut être −∞ et n’est peut être pas atteint !

Par définition d’une borne inférieure, il existe une suite x_{k} tel que J(x_{k}) ⟶ I; quitte à en extraire une sous- suite on pourrait supposer que la suite J(x_{k}) est décroissante d’où le nom de la technique. Avec le lemme 1.2, la suite est bornée.

Pour achever la démonstration du i) il suffit d’utiliser le résultat classique : " De toute suite bornée (x_{k}) de IR^{n} on peut extraire une sous- suite convergente (x_{k′}) " . Ceci n’est qu’une formulation commode de la compacité des parties fermées, bornées de IR^{n}.

Par suite x_{k′} ⟶ x_{∗} et comme J est continue J(x_{k′}) ⟶ J(x_{∗}) qui est donc égale à I = lim J(x_{n}) ; le minimum est donc bien atteint au point x_{∗}.

Noter que sans hypothèse supplémentaire la suite (x_{k}) peut ne pas converger ainsi qu’on le voit sur la figure.

ii) La démonstration est analogue au i) de la proposition 1.1. iii) la formule de Taylor donne comme J′(x_{∗}) = 0

J(x_{∗} + ρy) − J(x_{∗}) = \frac{1}{2}ρ^{2} ^{t}y H(x_{∗}) y + o(ρ^{2})

et donc comme J(x_{∗} + ρy) ≥ J(x_{∗}) en faisant tendre ρ → 0, on trouve pour tout y ∈ IR^{n} ^{t}y H(x_{∗}) y ≥ 0 iv) La formule de Taylor donne encore avec J′(x_{0}) = 0

J(x_{0} + y) − J(x_{0}) = \frac{1}{2} ^{t}y H(x_{0}) y + o(∥y∥^{2})

et donc comme ^{t}y H(x_{∗}) y ≥ α ∥y∥^{2} J(x_{0} + y) − J(x_{0}) > 0 pour y assez petit ce qui montre que x_{0} est un minimum local isolé (la fonction ne peut pas présenter de "plateau " au voisinage de x_{0}).

1.6 Algorithmes pour l’optimisation sans contraintes...

Notons que pour le cas quadratique, un algorithme de résolution de systèmes linéaires convient : par exemple Choleski ou une méthode de relaxation ; le gradient conjugué est bien adapté aux grandes matrices creuses issues des éléments finis.

Pour une fonctionnelle non quadratique, l’algorithme du gradient a l’avantage de la simplicité et l’inconvénient de la lenteur ; l’algorithme de Newton (voir propriétés dans la section sur la programmation quadratique séquentielle ) demande peu d’itérations mais demande le calcul de dérivées secondes ; la mise en oeuvre de ce calcul peut être bien simplifiée par l’utilisation de calcul symbolique (par exemple, Maple) ou de différentiation automatique de programme fortran (exemple Odysee, Adifor). Un algorithme de quasi-newton peut être un compromis car il utilise seulement des dérivées premières.

1.6.1 Algorithme du gradient

Encore appelé algorithme de la plus grande pente pour minimiser une fonction J : IR^{n} ⟶ IR, x^{k+1} = x^{k} − ρ^{k}gradJ(x^{k}) où ρ ∈ IR est à choisir par un algorithme de minimisation dans IR.

Pour simplifier l’analyse, supposons que ρ^{k} réalise le minimum de

j(ρ) = J(x^{k} − ρgradJ(x^{k}))

; pour insister sur ce choix considérons

j(ρ) = J(x^{k} − ρw^{k})

Lemme 1 1. Pour x^{k+1} = x^{k} − ρw^{k} si ρ est optimal (réalise le minimum de j(ρ), on a

(gradJ(x^{k+1}, gradj(x^{k})) = 0 ;

2. si w^{k} = gradJ(x^{k}) on a (gradJ(x^{k+1}, x^{k+1} − x^{k}) = 0

3. ∥gradJ(x^{k})∥ ≤ ∥gradJ(x^{k}) − gradJ(x^{k+1})∥

Exercice 1.12 Dessiner une itération de l’algorithme à l’aide de courbes de niveaux pour minimiser une fonction de 2 variables.

Proposition 1.7 Soit J : IR^{n} ⟶ IR avec J elliptique et J′ uniformément continue sur les compacts , la méthode du gradient à pas optimal converge et on a :

∥x^{k} − x^{∗}∥ ≤ α∥gradJ(x^{k})∥

La démonstration peut de faire en plusieurs étapes. étape1 : Comme J est elliptique son minimum est atteint ; par suite J(x^{k}) est minorée et décrois-

sante donc convergente. étape2 : avec ellipticité :

J(x^{k}) − J(x^{k+1}) ≥ (gradJ(x^{k+1}, x^{k+1} − x^{k}) + α∥x^{k} − x^{k+1}∥^{2}

avec le lemme le premier terme de droite est nul et donc ∥x^{k} − x^{k+1}∥ ⟶ 0 étape3 : comme J(x^{k}) est décroissante et J coercitive (car elliptique x^{k} reste dans un borné

(lemme ...) et avec uniforme continuité de J′ : ∥gradJ(x^{k}) − gradJ(x^{k+1})∥ ⟶ 0 et donc

∥gradJ(x^{k})∥ ⟶ 0 avec le lemme.

étape4 : l’ellipticité fournit encore :

(gradJ(x^{k}) − gradJ(x^{∗}), x^{k} − x^{∗}) ≥ α∥x^{k} − x^{∗}∥^{2} d’où la majoration du lemme.

Remarque 1.2 1. Il suffit de supposer que J est 2 fois continument différentiable pour avoir l’uniforme continuité de J′ sur les bornés.

2. En pratique, on ne peut avoir précisement le pas optimal

Proposition 1.8 Soit J : IR^{n} ⟶ IR avec J elliptique et avec

∥gradJ(x) − gradJ(y)∥ ≤ M∥x − y∥, alors pour 0 < a ≤ ρ^{k} ≤ b < \frac{2α}{M^{2}} , l’algorithme du gradient converge géométriquement : ∥x^{k+1} − x^{∗}∥ ≤ β∥x^{k} − x^{∗}∥ avec β < 1

Exercice 1.13 Démontrer la proposition

Exercice 1.14 Dans le cas où J est quadratique 1. Préciser l’algorithme du gradient.

2. Ecrire l’algorithme dans la base de vecteurs propres de A.

3. pour A définie positive en déduire que le meilleur choix de ρ est ρ^{∗} = \frac{2}{λ_{n}+λ_{1}} et que le taux de convergence τ = \frac{λ_{n}−λ_{1}}{λ_{n}+λ_{1}}

4. Dans quel cas l’algorithme est très lent ?

5. Ce choix est tout à fait théorique pourquoi ?

Exercice 1.15 Faire un changement de variable x = Cξ; que devient l’algorithme du gradient ? Cas quadratique. Interet du changement ?

cette idée très simple est très efficace si l’on sait construire une matrice telle que les valeurs propresles plus petites et les plus grandes soient plus proches : on parle de preconditionement

Minimisation avec contraintes

2.1 Minimisation avec contraintes d’égalités linéaires

Comme dans le cas sans contraintes, nous considérons d’abord le cas le plus simple : les contraintes sont de la forme ^{t}b_{j} v = c_{j} où b_{j} ∈ IR^{n} j = 1, ⋯, m , c_{j} ∈ IR. D’une part l’obtention des conditions d’optimalité avec multiplicateur de Lagrange est facile à partir de la proposition 1.3 (de la page p.13) ; d’autre part cette situation peut être considérée comme un intermédiaire algorithmique : la minimisation d’une fonction quadratique avec contraintes d’égalités linéaires peut servir à minimiser la même fonction avec des contraintes d’inégalités linéaires ; ce dernier problème pouvant être utilisé séquentiellement pour approcher un problème général de programmation mathématique : programmation quadratique séquentielle (voir §2.4). Le mot contraintes est fréquent en optimisation ; en analyse mathématique c’est la situation de minimisation dans une partie K d’un espace vectoriel. Il convient de ne pas confondre le sens du mot contrainte en optimisation avec les contraintes mécaniques ; dans ce dernier sens les Belges parlent de tension ; en anglais on parle de "constraint" en optimisation et de "stress " en mécanique. Nous considérons donc le problème : (C.L.E) Minimiser J : IR^{n} ⟶ IR dans l’ensemble K = {v|^{t}b_{j} v = c_{j} j = 1, ⋯, m} où b_{j} ∈ IR^{n} c_{j} ∈ IR. ou encore K = {v|^{t}B v = c} où les colonnes de la matrice B sont les vecteurs b_{j} :

B = [b_{1} | b_{2} ⋯ | b_{m}] c = [ c_{1} ; ⋮ ; c_{m} ].

Le théorème ci-dessous étend le (i) et (ii) de la proposition 1.6, au cas avec contraintes linéaires ; cette condition n’est pas suffisante (voir plus loin).

Théorème 2.1 : Soit le problème (C.L.E) avec J continue, et les b_{j} sont supposés linéairement indépendants.

(i) Si J tend vers l’infini quand ∥v∥ ⟶ +∞ dans K fermé ou si K est fermé, borné alors J atteint son minimum (ou maximum) en au moins un point v^{∗} ∈ K. (ii) Si J est différentiable et si J atteint son minimum en v^{∗} ∈ K, alors il existe λ_{j}^{∗} ∈ IR , j = 1, ⋯, m (des multiplicateurs de Lagrange) tels que on ait la C.N.O.(condition nécessaire d’optimalité)

grad J(v^{∗}) + ∑ λ_{j}^{∗} b_{j} = 0 ou de façon équivalente

grad J(v^{∗}) + B λ^{∗} = 0 avec λ^{∗} = [ λ_{1}^{∗} ; ⋮ ; λ_{m}^{∗} ] B = [b_{1}|b_{2} ⋯ |b_{m}]

ou encore J′(v^{∗}) + ^{t}λ^{∗} ^{t}B = 0

En pratique, il est commode d’introduire le Lagrangien L(v, λ) = J(v) + ^{t}λ(^{t}B v − C) la C.N.O. s’écrit alors \frac{∂ L}{∂ v}(v^{∗}, λ^{∗}) = 0 \underline{sans oublier} la contrainte ^{t}B v − C = 0 qui n’est autre que

\frac{∂L}{∂λ}(v^{∗}, λ^{∗}) = 0 .

Démonstration

(i) Comme dans le cas sans contrainte de la proposition 1.6 avec la technique de la suite minimisante, et en utilisant la compacité des fermés, bornés de IR^{n} : v^{∗} ∈ K puisque K est fermé. (ii) Pour obtenir la C.N.O. , comme dans le cas sans contrainte on part de J(v^{∗} + ρ w) − J(v^{∗}) ≥ 0 mais ici on doit avoir v^{∗} ∈ K et v^{∗} + ρ w ∈ K i.e. tb_{j}(v^{∗} + ρ w) = c_{j} et donc ^{t}b_{j} w = 0. Posons donc K_{T} = {w ∈ IR^{n} / ^{t}b_{j} w = 0} (C’est le sous- espace vectoriel tangent à K d’où la notation !) ; comme K_{T} est un sous- espace vectoriel nous pouvons faire tendre ρ → 0 par valeurs positives ou négatives et donc :

\frac{J(v^{∗} + p w) − J(v^{∗})}{ρ} ≥ 0 pour ρ ≥ 0 donne

J′(v^{∗}, w) ≥ 0 tandis que ρ ≤ 0 donne J′(v^{∗}, w) ≤ 0 et donc J′(v^{∗}, w) = 0. Mais à la différence du cas sans contraintes, J′(v^{∗}, w) n’est nul que pour w ∈ K_{T} ! Remarquons que K_{T} = Ker^{t}B et donc : ∀w ∈ Ker^{t}B ^{t}w grad J(v^{∗}) = 0 ; avec la proposition 1.4 cela montre que le système B λ = − grad J(v^{∗}) est soluble, d’où l’existence de λ^{∗} énoncé dans le théorème.

\underline{Cas Particulier} : J quadratique

J = \frac{1}{2} ^{t}v A v − ^{t}v F

grad J = A v − F et la C.N.O. devient :

\{ \begin{matrix}A v + B λ  = F  avec la contrainte \\ ^{t} B v  =  c \end{matrix}  (2.1)

Lemme 2.1 Si il existe α > 0 , ∀w ∈ K_{T} ^{t}w A w ≥ α ∥w∥^{2}, le système (2.1) admet une solution unique.

Noter que A n’est pas nécessairement inversible mais que sa restriction à K_{T} est inversible. Dans ce cas particulier on peut donner une démonstration directe. En effet, il suffit de vérifier

\{ \begin{matrix}A v + B λ = 0 donne une solution nulle \\ ^{t} B v = 0 \end{matrix}  (2.2)

or la première équation donne ^{t}v A v + ^{t}v B λ = 0 et avec la dernière équation il reste ^{t}v A v = 0 d’où v = 0 et λ = 0 en reportant dans la première équation.

\underline{Remarques} sur le système (2.1)

(1) Dans le cas où A est \underline{inversible}, on a v = −A^{−1} B λ − A^{−1} F et la deuxième équation donne −^{t}B A^{−1} B λ = c + A^{−1} F ; ce système permet de trouver λ. Cette méthode n’est pas conseillée numériquement mais est commode dans les petits exemples.

(2) De plus dans le cas A = I : v = −Bλ + F et +^{t}B B λ = −c + ^{t}B F donc v = −B(^{t}B B)^{−1}(−c + ^{t}B F) + F .

Remarque 2.1 A noter que la situation du cas particulier est tres fréquente dans l’analyse par éléments finis de systèmes elliptiques d’équations aux dérivées partielles, en particulier en mécanique des structures élastiques.

Exercice 2.1 J(v) = \frac{1}{2}∥v − F ∥^{2} avec la contrainte v ∈ K = \{^{t}Bv − c = 0\}

a) trouver explicitement v et λ.

b) comparer avec la projection sur un sous- espace paramétré.

c) cas où B a une seule colonne.

d) cas où B a des colonnes orthonormées.

\underline{Solution}

a) J(v) = ^{t}v v −^{t}v F +^{t}F F c’est à dire A = I; on a donc la formule du 2) ci- dessus : v = −B (^{t}B B)^{−1} ^{t}B F + B (^{t}B B)^{−1}c + F

b) le premier terme B (^{t}B B)^{−1} ^{t}B F n’est autre que la projection de F sur le sous- espace {v/ v = B x x ∈ IR^{m}} qui est orthogonal à K_{T} (voir proposition 1.3), le deuxième terme tient compte du fait que K ne passe pas par l’origine ; si l’on connait un v_{0} ∈ K c = ^{t}B v_{0}) on peut écrire : v = −B (^{t}B B)^{−1} ^{t}B (F − v_{0}) + F

c) Quand B = b a une seule colonne K = {v/^{t}b v = c} est un hyperplan affine ;

Fig. 2.1 – Projection sur un sous espace ^{t}bv − c = 0

−\frac{b^{t}b}{^{t}b b}(F − v_{0}) est la projection de −(F − v_{0}) sur la droite portée par b; ajouté à F cela ramène dans K (voir figure 2.1).

d) Dans le cas où ^{t}B B = IIR^{m} on a : v = −B^{t}B(F − v_{0}) + F attention B^{t}B ≠ IIR^{m}

Remarque 2.2 Il convient de réaliser intuitivement la C.N.O. à partir des courbes de niveau de J ; visualisons pour une fonction de deux variables x, y.

La figure 2.3 représente les courbes de niveau de (x, y) ⟼ J(x, y) ; en l’abscence de contraintes, J atteint son minimum au point m autour duquel tournent les courbes de niveau comme sur une carte géographique ; plus les ellipses sont grandes, plus grande est J(x, y) ; on constate que lorsqu’on s’éloigne du point v_{∗} = (x_{∗}, y_{∗}) où D est tangent à une courbe de niveau, la fonction augmente ; c’est donc que (x_{∗}, y_{∗}) est un minimum local de J sur la droite D! Or la normale à la courbe de niveau est ∇J(x_{∗}, y_{∗}) ; ce vecteur est donc colinéaire au vecteur b orthogonal à la droite tb v − c = 0 ; ou ∇J(x_{∗}, y_{∗}) + λb = 0 ce qui n’est autre que la C.N.O. du théorème 2.1 avec une seule contrainte.

Fig. 2.2 – Cas où ^{t}B B = IIR^{m}

Fig. 2.3 – La C.N.O. à partir des courbes de niveau Voici quelques exercices pour lesquels on peut obtenir une solution explicite assez facilement ; le seul but est de manipuler la C.N.O. ; on dessinera les contraintes et les courbes de niveau.

Exercice 2.2 Soit J(x, y) = x^{2} + y^{2} et K = {(x, y) | 2x + y = 2} . Déterminer le minimum et le multiplicateur de Lagrange.

Exercice 2.3 Même question pour x ∈ IR^{n} J(x, y) = \frac{∥x∥^{2}}{2} et K = \{x |^{t}b x − c = 0\}

Exercice 2.4 J(x, y) = \frac{1}{2}(x_{1}^{2} + x_{2}^{2} + x_{3}^{2}) et K = \{x | x_{1} − x_{2} − 1 = 0 , x_{2} − x_{3} − 2 = 0\}

Exercice 2.5 Projection de β = [ \begin{matrix}6 \\ 0 \\ 0 \end{matrix} ] sur K = \{x |^{t}B x = 0\} avec B = [ \begin{matrix}1 1 \\ 1 2 \\ 1 3 \end{matrix} ]; distance

de f à K.

2.2 Fonction quadratique avec contraintes d’égalités linéaires

2.2.1 Introduction

Soit donc pour v ∈ IR^{n} J(v) = \frac{1}{2}^{t}v A v − ^{t}v f avec la contrainte

tB v − c = 0 où B ; m n est une matrice à n lignes et m colonnes avec m < n, et la C.N.O.

\{ \begin{matrix}A v + B λ = f \\ ^{t} B v  = c \end{matrix}

on a vu dans les petits exemples qu’il est commode de tirer v en fonction de λ de la première équation et de reporter cette expression dans la dernière équation, ce qui fournit un système pour déterminer λ : v = A^{−1}Bλ + A^{−1}f d’où −^{t}BA^{−1}Bλ = c −^{t}BA^{−1}f ce qui permet de déterminer λ que l’on reporte ensuite pour trouver v. Cette méthode peut être transformée en un algorithme numérique sous réserve que \underline{A soit inversible} avec une décomposition de Cholesky de A puis de ^{t}BA^{−1}B.

2.2.2 Elimination

Nous allons présenter une autre méthode qui s’applique même si A n’est pas inversible ; rappelons que cela n’empêche pas le système d’avoir une unique solution ; le problème de minimisation a également une solution dès que A est définie positive sur l’espace tangent aux contraintes (Lemme 2.1). Il s’agit essentiellement d’une méthode d’élimination ; voyons cela d’abord avec une seule contrainte : tb v = c si b_{i} ≠ 0 on peut tirer

v_{1} = \frac{1}{b_{1}} [ − ∑_{i=2}^{n} b_{i} v_{i} + c ]

et reporter cela dans la 1ère équation ; il est alors possible d’éliminer λ_{1} : une façon indirecte de s’en convaincre est que l’on a paramétré les contraintes, on a donc un problème de minimisation sans contraintes ; avec une seule contrainte, la seule précaution est de vérifier que b n’est pas trop petit, sinon prendre un autre coefficient ; dans le cas de plusieurs contraintes il faut chercher une sous- matrice m × m dont le déterminant n’est pas trop petit. Remarquons toutefois que cette transformation peut s’écrire :

v = s c + Z v^{♭} avec s = [ \frac{1}{b_{1}} ; 0 ; ⋮ ; 0 ] v^{♭} = [ v_{2} ; ⋮ ; v_{n} ]

et Z = [ \begin{matrix}−\frac{b_{2}}{b_{1}} ⋯ − \frac{b_{m}}{b_{1}} \\ 1 ⋯ 0 \\ . & . & . \\ 0 ⋯ 1 \end{matrix} ]

Notons que l’on a banalement ^{t} s b = 1 et que ^{t}b Z = 0 c’est à dire que les colonnes de Z constituent une base de l’hyperplan ^{t}b w = 0 pour w ∈ IR^{n}. L’algorithme ci-dessous est une généralisation de cette remarque.

2.2.3 Algorithmes d’élimination généralisée

En suivant Fletcher, 1981 [?] avec une présentation légérement différente, nous supposons que nous disposons de deux matrices S et Z

n S  Z n telles que la matrice [S|Z]

m n − m soit inversible et que ^{t}B S = IIR^{m} ^{t}B Z = 0

Nous verrons au §2.2.4. une méthode possible pour construire S et Z.

Comme dans le cas d’un hyperplan, la deuxième condition, jointe à l’inversibilité de [S|Z], signifie que les colonnes de Z constituent une base du sous- espace vectoriel ^{t}B w = 0 avec w ∈ IR^{n}. Quand à la première condition, elle s’explicite en ^{t}b_{i} s_{j} = δ_{ij} avec B = [b_{1}| ⋯ |b_{m}] S = [s_{1}| ⋯ |s_{m}]. Cette condition rappelle celle de base duale du sous- espace vectoriel engendré par les b_{i}; toutefois cela n’est le cas que si ^{t}s_{j} Z = 0, ce qui n’est pas nécessairement le cas ; toutefois voir le §2.4. où nous verrons aussi comment construire pratiquement ces matrices. L’idée est très simple tout comme au §2.2.2., ces matrices permettent de paramétrer les contraintes :

v = S c + Z y avec y ∈ IR^{n−m} si et seulement si ^{t}B v = c  (2.3)

Nous avons dessiné, sur la figure 2.4 , le cas où ^{t}s_{j} z = 0 j = 1, 2 avec n = 3 , m = 2 dans

Fig. 2.4 – Cas où ^{t}s_{j} z = 0 ; j = 1, 2

ce cas Z se réduit à un seul vecteur ; S c est alors l’intersection de la droite ^{t}B v = c et du plan tZ w = 0 w ∈ IR^{n}. Il suffit donc de considérer A v + B λ = f qui s’écrit : A Z y + A S c + B λ = f et en multipliant par ^{t}Z on élimine λ : tZ A Z y = ^{t}Zf − ^{t}Z A S c Ce système est soluble en y puisque A est définie positive sur le sous espace vectoriel {w ∈ IR^{n}/^{t}B w = 0} et ce sous espace vectoriel est engendré par les colonnes de Z! on peut donc utiliser l’algorithme de Cholesky pour calculer y. On en déduit v avec (2.3) puis λ en multipliant A v + B λ = f par ^{t}S : λ = ^{t}S f − ^{t}S A v.

2.2.4 Triangulation par des matrices orthogonales

Nous indiquons ici une méthode numériquement stable pour construire les matrices S et Z du paragraphe précédent. Pour cela nous supposons savoir construire une matrice Q \underline{orthogonale} n × n et une matrice R triangulaire supérieure m × m :

Q = \begin{aligned}[ & | ; Q_{1} | Q_{2} ; | & ] \\ & m n − m \end{aligned} n telles que B = Q [ \begin{matrix}R \\ 0 \end{matrix} ] = [Q_{1} Q_{2}] [ \begin{matrix}R \\ 0 \end{matrix} ] = Q_{1} R

Avec ces matrices si on suppose S = Q_{1}^{t}R^{−1} on a bien ^{t}B S = I et Z = Q_{2} satisfait ^{t}B Z = 0 puisque ^{t}B Z = ^{t}R^{t}Q_{1} Q_{2} et ce dernier produit est nul car comme Q est orthogonale, ses colonnes sont orthogonales entre elles ! Dans ce cas la matrice S satisfait de plus :

t S Z = 0

En effet ^{t}S Z = R^{−1}^{t}Q_{1} Q_{2} = 0. Nous voyons que dans ce cas s_{1}, ⋯, s_{m} constitue la base duale de b_{1}, ⋯, b_{m} (dans le sous- espace vectoriel ∑ λ_{i} b_{i}). La figure 2.4 correspond donc à cette situation.

A noter que pour orthogonaliser on peut être tenter d’utiliser la méthode de Gramm- Schmidt : elle est à éviter car elle n’est pas stable numériquement. Une bonne méthode numérique consiste à utiliser les opérateurs de Householder :

S(h) v = v − 2\frac{h^{t}h v}{^{t}h h}  v, h ∈ IR^{n}.  (2.4)

On reconnaît en \frac{h^{t}h v}{^{t}h h} la projection de v sur la droite engendrée par h; voir figure 2.5

Exercice 2.6 i) Pour h ≠ 0 montrer que S(λ h) = S(h) avec λ ∈ IR, λ ≠ 0 montrer que S(h) est l’opérateur de symétrie orthogonale par rapport à l’hyperplan ^{t}h w = 0. ii) montrer que S(h) est un opérateur symétrique ^{t}S = S et orthogonal S ^{t}S = ^{t}S S = I ce qui avec la symétrie se réduit à S^{2} = I. iii) Si ∥v∥ = ∥w∥, montrer qu’il existe h ∈ IR^{n} telque w = S(h) v.

\underline{Solution} : i) S(λ h) = S(h) est immédiat avec λ ≠ 0. Ceci revient à dire que la projection de v et de S(h) v sur h sont opposées et ont même projection sur {w,^{t}h w = 0}; prenons ∥h∥ = 1 or S(h) v = v − 2h^{t}h v th S(h) v = ^{t}h v − 2^{t}h v = −^{t}h v donc la projection de S(h) v sur h est −h^{t}h v est bien opposée à la projection de v. D’autre part : la projection de v sur l’hyperplan ^{t}h w = 0 P v = v − h^{t}h v P S(h) v = S(h) v − h^{t}h S(h) v = v − 2h^{t}h v + h^{t}h v = v − h^{t}h v = P v ii) simple calcul matriciel. iii) l’interprétation avec la symétrie amène à prendre h = w − v; il faut alors calculer

w − S(h) v = w − v + 2\frac{h^{t}h v}{^{t}h h} = \frac{h^{t}h h + 2h^{t}h v}{^{t}h h} = \frac{h^{t}h (h + 2v)}{^{t}h h}

or h + 2v = w + v donc ^{t}h(h + 2v) = ^{t}(w − v)(w + v) = ^{t}w w −^{t}v v

A partir de ces propriétés il est facile de transformer un vecteur v en ∥v∥e_{1} où e_{1} = [ 1 0 ⋮ 0 ] soit h_{1}

telque ∥v∥e_{1} = S(h_{1}) v

si v est la première colonne de A : S(h_{1}) A = A_{1} a pour première colonne [ ∥v∥ ; 0 ; ⋮ ; 0 ] et donc

A = S(h_{1}) A_{1} d’où la possibilité de triangulariser à l’aide de matrices orthogonales. A noter que cette idée est à l’origine d’un bon algorithme de calcul de valeurs et de vecteur propres : la méthode Q R; voir par exemple Schatzman [?].

Fig. 2.5 – symétrie orthogonale

2.2.5 Programmation quadratique

Dans le cas d’une fonctionnelle quadratique avec des inégalités linéaires, on peut utiliser itérativement la minimisation de la fonctionnelle avec des contraintes d’égalité. considérons la minimisation de J(v) = \frac{1}{2}^{t}vAv −^{t} vf avec les contraintes ^{t}Bv − c ≤ 0. Remarquons que

J(v + d) = q(d) + J(v)

avec

q(d) = \frac{1}{2}^{t}dAd^{t}vAd −^{t} df

Algorithme : A partir d’un point admissible v^{0}, Minimiser q(d) avec _{j}^{B}d = 0 pour j ∈ sat(v^{k}) ; soit d^{k} le minimum et posons : ṽ^{k+1} = v^{k} + d^{k} Si d^{k} = 0 et si les multiplicateurs du problème avec égalités sont ≥ 0 on s’arrête ; si des multiplicateurs sont négatifs, on retire le plus négatif. Si d^{k} ≠ 0, on distingue 2 cas :

cas 1 Si ṽ^{k+1} satisfait les autres contraintes, J a diminué et on le prend comme nouveau point de

départ v^{k+1} = ṽ^{k+1}. cas 2 Dans ce cas, on cherche ρ tel que le point v + ρd^{k} soit admissible ; on doit donc avoir

tB_{j}(v + ρd^{k}) − c_{j} ≤ 0 ; on trouve que

ρ ≤ ρ^{∗} = Min\{\frac{c_{j} −^{t} B_{j}v}{^{t}B_{j}d} / j ∉ sat(v^{k}),^{t} B_{j}d > 0\}

On prend v_{k+1} = v + ρ^{∗}d^{k} et on rajoute dans les contraintes saturées celle que l’on vient d’atteindre avec le pas ρ^{∗}; et on recommence.

2.3 Minimisation avec contraintes

2.3.1 Condition d’optimalité avec contraintes d’égalité

On souhaite obtenir une condition analogue à celle obtenue au théorème 2.1 dans lequel les contraintes sont supposées linéaires ^{t}b_{j} v = c_{j} ; si l’on reprend la démonstration de ce théorème on voit qu’un des ingrédients est que si v^{∗} est minimum local v^{∗} + ρw satisfait les contraintes si et seulement si ^{t}b_{j} w = 0 ; cette caractérisation simple des directions admissibles w vient naturellement du caractère linéaire des contraintes. Une façon d’adapter cette approche au cas de contraintes non linéaires F_{j}(v) = 0 est de considérer des w^{k} tels que il existe ρ^{k} avec v^{∗} + ρ^{k}w^{k} admissible et de considérer les w qui sont limite de w^{k} quand ρ^{k} ⟶ 0 ; cette approche s’étend au cas avec contraintes d’inégalités et se trouve par exemple dans Fletcher [?] (1981).

Du point de vue géométrique cela rappelle la définition d’une tangente à une surface comme limite de sécantes.

Il nous paraît plus commode de caractériser les w admissibles comme les vecteurs tangents en v^{∗}, aux courbes passant par v^{∗} et satisfaisant les contraintes.

K = {v ∈ IR^{n} / F_{j}(v) = 0; j = 1, ⋯, n} ≡ {v ∈ IR^{n} / F(v) = 0} où

\begin{matrix}F : IR^{n} ⟶ IR^{m} \\ v ⟼ ( F_{1}(v) ; ⋮ ; F_{m}(v) ) \end{matrix}

Définition 2.1 L’espace tangent en v^{∗} ∈ K est

K_{T} (v^{∗}) = \{w = \frac{dv}{dt} |_{t=0} ∈ IR^{n} /v(0) = v^{∗}, ∃ ε > 0 , v ∈ C^{1}(−ε, ε) , v(t) ∈ K\}

On pourrait démontrer qu’il s’agit bien d’un sous-espace vectoriel mais ce qui nous interésse ici est d’en donner une caractérisation à l’aide de la dérivée de F ; pour cela nous avons besoin d’une condition dite de régularité.

Définition 2.2 v^{∗} ∈ K est dit régulier pour K si les Fj^{′}(v^{∗}) sont des formes linéaires indépendantes (ou grad F_{j}(v) = ^{t}Fj^{′}(v^{∗}) sont des vecteurs indépendants).

Cette terminologie habituelle en optimisation correspond à ce que les géomètres appelent une submersion (voir par exemple Berger-Gostiaux [?] (1972), F. Pham [?] ) ; le résultat suivant est classique.

Théorème 2.2 En un point régulier v^{∗} ∈ K, on a K_{T} (v^{∗}) = K_{G}(v^{∗}) avec

K_{G}(v^{∗}) = {w ∈ IR^{n} , F′(v^{∗}) w = 0}

ou de façon équivalente

K_{G}(v^{∗}) = {w ∈ IR^{n} , F′_{j}(v^{∗}) w = 0 ; j = 1, ..., m} ≡ ⋂_{j=1,...m} Ker F′_{j}(v^{∗}) .

\underline{Démonstration} : Nous montrons d’abord que K_{T} (v^{∗}) ⊂ K_{G}(v^{∗}) ; soit w ∈ K_{T} (v^{∗}), il existe donc une courbe de K \{t ⟼ v(t)\} telle que v(0) = v^{∗} et \frac{dv}{dt} |_{t=0} ;

comme F(v(t)) = 0 on en déduit par la dérivation de fonctions composées que : F′(v(t) \frac{dv}{dt} = 0 et donc en t = 0 F′(v^{∗}) w = 0.

Réciproquement, si w ∈ K_{G}(v^{∗}) nous devons construire une courbe située sur K au voisinage de v^{∗}; en s’appuyant sur l’intuition géométrique (voir figure 2.6) il est naturel de chercher cette courbe dans le sous-espace affine v^{∗} + αw + ∑_{j=1}^{m} u_{j} grad F_{j}(v^{∗})

Fig. 2.6 – Courbe tangente

nous allons montrer que l’on peut trouver des fonctions α ⟶ u_{j}(α) telles que au voisinage de α = 0 celle courbe soit tangente à w; nous cherchons donc α ⟶ u(α) telque

F(v^{∗} + αw +^{t}F′(v^{∗})u(α)) = 0 ;

nous sommes dans une situation de fonction implicite pour f(α, u) = F(v^{∗} + αw +^{t}F′(v^{∗})u), on a

\frac{∂f}{∂α}|_{α=0 ,u=0} = F′(v^{∗}) w = 0 (car w ∈ K_{G}(v^{∗}))

\frac{∂f}{∂u} |_{α=0 ,u=0} = F′(v^{∗}) ^{t}F′(v^{∗})

Comme v^{∗} est régulier les colonnes de F′(v^{∗}) sont linéairement indépendantes, F′(v^{∗}) ^{t}F′(v^{∗}) est définie positive (exercice 1.8 du §1.1.) donc inversible ; le théorème des fonctions implicites (Pham [?]) assure donc l’existence au voisinage de zéro, d’une fonction α ⟼ u(α) telle que

f(α, u(α)) = 0 ou F(v^{∗} + αw +^{t}F′(v^{∗})u(α)) = 0

et l’on a \frac{∂f}{∂u} \frac{d u}{d α} = − \frac{∂f}{∂α} en particulier en α = 0

F′(v^{∗}) ^{t}F′(v^{∗}) \frac{d u}{d α}|_{α=0} = −F′(v^{∗}) w = 0 car w ∈ K_{G}(v^{∗}) ;

finalement la courbe α ⟼ v^{∗} + αw +^{t}F′(v^{∗}) u(α) est tangente à w, situé sur K et passe par v^{∗} .

Cette caractérisation de l’espace tangent va nous permettre d’obtenir une condition nécessaire d’optimalité du 1er ordre ; comme pour le théorème 2.1 cette condition n’est pas suffisante et pour un problème de maximisation, nous aurions la même condition.

Nous considérons le problème (avec contraintes d’égalités) : (C.E.) Minimiser J : IR^{n} ⟶ IR dans l’ensemble S = {v ∈ IR^{n} / F(v) = 0} avec F : IR^{n} ⟶ IR^{m}.

Nous avons le théorème suivant qui généralise le théorème 2.1 .

Théorème 2.3 Soit le problème (C.E.) avec J et F continues.

(i) Si J tend vers l’infini quand ∥v∥ ⟶ +∞ ou si K est (fermé), borné alors J atteint son minimum (ou maximum) en au moins un point v^{∗} . (ii) Si J et F sont différentiables et si J atteint un minimum (ou maximum) local en v^{∗} (point régulier pour S), alors il existe λ_{j}^{∗} ∈ IR , j = 1, ⋯, m (les multiplicateurs de Lagrange) tels que on ait la C.N.O. :

∀w ∈ IR^{n} J′(v^{∗}) w + ^{t}λ F′(v^{∗}) w = 0

ou grad J(v^{∗}) + ^{t}F′(v^{∗}) λ = 0 .

Remarque 2.3 En pratique, il est commode d’introduire le Lagrangien L(v, λ) = J +^{t}λ F la C.N.O. s’écrit : \frac{∂L}{∂v}(v^{∗}, λ^{∗}) = 0 sans oublier la contrainte sous la forme :

\frac{∂L}{∂λ}(v^{∗}, λ^{∗}) = 0 .

Démonstration

(i) Comme dans le cas sans contraintes avec une suite minimisante ; comme les F sont continues, S est fermé et les limites de sous-suites sont bien dans S; dans le cas où S est fermé, borné, on utilise la compacité des fermés, bornés de IR^{n}.

(ii) Nous pouvons d’abord dégager le

Lemme 2.2 Sous les hypothèses du théorème, ∀w ∈ K_{T} (v^{∗}) J′(v^{∗}) w = 0 .

La démonstration de ce lemme est très simple et utilise la même idée que dans le cas sans contraintes : on utilise les variations de v^{∗}; on les prend ici, sous la forme d’une courbe de S passant par v^{∗} : t ⟼ v(t) ; on a donc

J(v^{∗}) ≤ J(v(t)) et donc \frac{J(v(t)) − J(v^{∗})}{t} ≥ 0

pour tout t > 0 ; en faisant tendre t ⟶ 0^{+} on obtient J′(v^{∗}) \frac{dv}{dt} |_{t=0} ≥ 0

avec t < 0 et t → 0^{−}, on obtient J′(v^{∗}) \frac{dv}{dt} |_{t=0} ≤ 0 et donc

J′(v^{∗}) \frac{dv}{dt} |_{t=0} = 0 ou par définition de l’espace tangent : ∀w ∈ K_{T} (v^{∗}) J′(v^{∗}) w = 0

Pour la démonstration du (ii) du théorème, on utilise ce lemme et la caractérisation

K_{T} (v^{∗}) = K_{G}(v^{∗}) (théorème 2.2)

et on conclut comme dans le cas avec contraintes linéaires avec la proposition 1.4 qui fournit l’existence des λ.

Voici quelques exercices d’application directe de ce théorème.

Exercice 2.7 Soit m ∈ IR^{n}, trouver la distance de m à l’hyperplan {x ∈ IR^{n} / ∑ a_{i}x_{i} − b = 0} .

\underline{Solution} La fonctionnelle à minimiser n’est pas précisée ; si J(x) = \frac{1}{p} ∑ |x_{i} − m_{i}|^{p}, le Lagrangien est

L(x, λ) = J(x) + λ (∑ a_{i}x_{i} − b) et la C.N.O.

\frac{∂L}{∂x_{i}} = 0 donne |x_{i} − m_{i}|^{p−1} sgn |x_{i} − F_{i}| + λa_{i} = 0

avec ∑ a_{i}x_{i} − b = 0

pour un calcul effectif, on essaye de tirer x_{i} de la 1ère équation en fonction de λ et de reporter dans la contrainte ; pour simplifier prenons p = 2 ;

λ = \frac{b − ∑ a_{i}x_{i}}{∑ a_{i}^{2}} x_{i} = m_{i} − λa_{i}

et \frac{1}{2} \frac{|b − ∑ a_{i}m_{i}|^{2}}{∑ a_{i}^{2}} carré de la distance euclidienne à un hyperplan ; formule élémentaire connue.

Cet exemple pouvait se traiter avec le théorème 2.1 ; mais voici une situation "duale " qui relève du théorème précédent.

Exercice 2.8 Minimiser J(x) = ∑ a_{i}x_{i} avec la contrainte ∑ |x_{i}|^{p} − 1 = 0

Fig. 2.7 – Exercice 2.8, minimisation d’une fonction J

\underline{solution} L = J + λF avec F(x) = ∑ |x_{i}|^{p} − 1

C.N.O. a_{i} + λ p |x_{i}|^{p−1} sgn x_{i} = 0 avec ∑ |x_{i}|^{p} − 1 = 0 dans le cas p = 2 x_{i} = \frac{a_{i}}{2λ}

et \frac{1}{4λ^{2}} ∑ a_{i}^{2} − 1 = 0 donne λ^{2} = \frac{∑ a_{i}^{2}}{4}

x_{i}^{∗}^{±} = \frac{± a_{i}}{(∑ a_{i}^{2})^{1/2}} J(x_{i}^{∗}^{±}) = ±(∑ a_{i}^{2})^{1/2}

La C.N.O. fournit 2 solutions dont l’interprétation géométrique est évidente ; pour les départager il faut une condition de 2ième ordre (voir ...)

Exercice 2.9 soit a = (1, 0), trouver la distance de a à la parabole d’équation y^{2} = 4 x; ceci par 3 méthodes :

i) tirer x en fonction de y ii) tirer y en fonction de x iii) utiliser les multiplicateurs de Lagrange

Comparer et commenter les résultats trouvés.

Exercice 2.10 Soit F(x) = x_{1}^{2} + x_{2}^{2} + x_{3}^{2} − R^{2} et S = {x ∈ IR^{3} / F(x) = 0}

a) Soit G orthogonal à F′(x), construire une courbe tangente à G. b) Ecrire une C.N.O. avec le plan tangent en x^{∗} minimum de J(x) = x_{1} + x_{2} + x_{3} sur S; trouver x^{∗} .

c) Comparer avec la C.N.O. avec multiplicateurs de Lagrange ; trouver x^{∗}.

d) Vérifier la C.S.O. du 2nd ordre.

2.3.2 Minimisation avec contraintes d’inégalités

Introduction

On a vu lors de la démonstration de la C.N.O. du 1^{er} ordre avec contraintes d’égalités linéaires que l’on utilisait un résultat d’équivalence entre la résolubilité d’un système surdéterminé BΛ = g et le fait que g soit orthogonal au noyau de ^{t}B (proposition 1.4) ; dans le cas d’égalités linéaires Ker ^{t}B = {w ∈ IR^{n} / ^{t}b_{j} w = 0} (b_{j} sont les colonnes de B) est un ensemble de directions admissibles.

En présence de contraintes d’inégalités, les directions admissibles sont maintenant définies par des inégalités comme le montre l’exemple ci-dessous ;

Considérons l’exemple très simple suivant : minimiser la fonction J(x) avec la contrainte (b_{1}, x) ≤ c_{1} ; soit x^{∗} le minimum ; si (b_{1}, x^{∗}) = c_{1}, on a donc J(x^{∗} +ρy)−J(x^{∗}) ≥ 0 pour (b_{1}, y) ≤ 0 et donc en divisant par ρ et en faisant tendre ρ > 0 vers zéro J′(x^{∗}, y) ≥ 0 pour (b_{1}, y) ≤ 0 ; si (b_{1}, x^{∗}) < c_{1}, on trouve J′(x^{∗}, y) = 0

Fig. 2.8 –

40  Minimisation avec contraintes

Comme grad J(x_{∗}) doit avoir un produit scalaire positif avec tous les y qui vérifient (b_{1}, y) ≤ 0, on voit intuitivement que grad J(x_{∗}) doit être de la forme grad J(x_{∗}) = −λ_{1} b_{1} avec λ_{1} ≥ 0.

Exercice 2.11 montrer l’existence de λ_{1} ≥ 0 dans l’exemple ci-dessus.

Exercice 2.12 Pour la fonction J(x) = J(x^{1}, x^{2}) = \frac{1}{2} [(x^{1} − 1)^{2} + (x^{2} − 1)^{2}] on cherche à minimiser avec 2 contraintes (b_{1}, x) ≤ 0 et (b_{2}, x) ≤ 0

a) à l’aide d’un dessin, distinguer dans quels cas le minimum est atteint en tx_{m} = (1, 1).

\underline{Indications.} Le minimum x_{m} de J sans contraintes est x_{m}^{1} = 1, x_{m}^{2} = 1 ; suivant la position de la droite

Fig. 2.9 –

d’équation (b_{1}.x) = 0 par rapport à ce minimum nous avons deux situations très différentes.

1er Cas. Si (b_{1} . x_{m}) < 0 alors pour ρ assez petit x = x_{m} + ρy vérifie encore la contrainte pour tout y ∈ IR^{2} ; toutes les directions sont admissibles et J′(x_{m}, y) = 0 pour tout y ∈ IR^{2} comme en l’absence de contraintes ; en fait dans ce cas cette contrainte est inutile et n’influe pas sur la minimisation de J.

2ième Cas. Si au contraire (b_{1} . x_{m}) > 0 comme sur la figure 2.9, on constate en regardant les courbes de niveau que le minimum x_{∗} ≠ x_{m} se trouve sur la droite (b_{1}. x) = 0 mais alors x = x_{∗} + ρy ne vérifie la contrainte que si (b_{1}. y) ≤ 0. Il reste à discuter la contrainte (b_{2}, x_{m}) < 0

Exercice 2.13 Reprendre dese exercices de projection sur sous espaces affines ; remplacer les e’galités par des inégalités et essayer de trouver directement le minimum ; utiliser aussi le théorème ci dessous.

Exercice 2.14 Voir les exercices de barres avec blocages du chapitre sur les exemples me’caniques.

Conditions d’optimalité du premier ordre

Nous considérons le problème (avec Contraintes d’Inégalités) (C.I.) Minimiser J : IR^{n} ⟶ IR dans l’ensemble K = {v ∈ IR^{n}/E(v) = 0 et F(v) ≤ 0} avec E : IR^{n} ⟶ IR^{m} m ≤ n

F : IR^{n} ⟶ IR^{p}

Comme nous l’avons vu dans l’exemple en un point v^{0} donné on peut avoir F_{i}(v^{0}) < 0 ou F_{i}(v^{0}) = 0 suivant les indices considérés.

Définition 2.3 Une contrainte d’inégalité F_{i}(v) ≤ 0 est dite saturée au point v^{0} si en ce point F_{i}(v^{0}) = 0 ; si F_{i}(v^{0}) < 0 elle est dite non saturée ; par convention une contrainte d’égalité est saturée en ce point ; on note sat(v_{0}) les indices de contraintes saturées en v_{0}.

Ainsi une contrainte non saturée en un point v^{0} ne restreint pas le domaine admissible au voisinage de v^{0} ; il faut donc s’attendre que les conditions d’optimalités locales ne fassent intervenir que les contraintes saturées au minimum local.

Comme dans le cas de contraintes d’égalités et pour simplifier, nous faisons une hypothèse de régularité.

Définition 2.4 v^{0} ∈ K défini en (C.I.) est dit régulier pour K, si les E′_{j}(v^{0}) j = 1, ⋯, m et les F′_{k}(v^{0}) pour k = 1, ⋯, p, et k ∈ sat(v^{0}) = {indices de contrainte saturée en v^{0}} sont des formes linéaires indépendantes.

Voici le théorème qui exprime la condition d’optimalité locale du premier ordre ; la seule mais importante nouvauté réside dans le bfsigne des multiplicateurs de Lagrange ; le résultat suivant est connu comme condition de Karush-Kuhn-Tucker. Attention comme il y a 2 façons d’écrire une inégalité et que l’on peur écrire le Lagrangien avec + ou − devant le multiplicateur de Lagrange les conditions de signe du théorème ci dessous dépendent de la convention choisie.

Théorème 2.4 Soit le problème (C.I.) avec J , E et F continues.

(i) Si J tend vers l’infini quand ∥v∥ → +∞ (Hypothèse H1 du §1.3.1) ou si K est (fermé), borné, alors J atteint son minimum (ou maximum) en au moins un point v^{∗} ∈ K

(ii) Si J , E et F sont différentiables et si J atteint un minimum (ou maximum) local en v^{∗}, point régulier pour K, alors il existe λ ∈ IR^{m} , μ ∈ IR^{p} tels que

\frac{∂L}{∂v}(v^{∗}, λ^{∗}, μ^{∗}) = 0

μ^{∗} ≥ 0 , ^{t}μ^{∗} F(v^{∗}) = 0

et \frac{∂L}{∂λ}(v^{∗}, λ^{∗}, μ^{∗}) = 0  \frac{∂L}{∂μ}(v^{∗}, λ^{∗}, μ^{∗}) ≤ 0

avec L(v, λ, μ) = J (v) +^{t}λ E(v) +^{t}μ F(v)

Remarque 2.4 la condition \frac{∂L}{∂v} = 0 peut s’expliciter en J′(v^{∗}) +^{t}λ^{∗} E′(v^{∗}) +^{t}μ^{∗} F′(v^{∗}) = 0 ou gradJ(v^{∗}) +^{t}E′(v^{∗}) λ^{∗} +^{t}F′(v^{∗}) μ^{∗} = 0 ; les conditions \frac{∂L}{∂λ} = 0 \frac{∂L}{∂μ} ≤ 0 ne font que redire les contraintes : E = 0 et F ≤ 0 ; la condition μ^{∗} ≥ 0 est typique des contraintes d’inégalités ; si l’on avait pris des contraintes F(v) ≥ 0, μ^{∗} serait alors négatif ; enfin comme μ_{k}^{∗} ≥ 0 et F_{k}(v^{∗}) ≤ 0 la condition ^{t}μ^{∗}F(v^{∗}) = 0 donne simplement μ_{k}^{∗}F_{k}(v^{∗}) = 0, k = 1, ⋯, p; l’interprétation est que μ_{k}^{∗} = 0 si F_{k}(v^{∗}) < 0 (c’est à dire si contraintes non saturées)

Démonstration.

(i) Pour l’existence, cela est encore analogue au cas sans contraintes ; remarquons d’abord que comme E et F sont continues, les contraintes sont un ensemble K fermé ; soit I = inf_{v∈K} J(v) et (v^{k}) une suite minimisante : J(v^{k}) ⟶ I; si K est borné la suite l’est aussi ; dans le cas contraire, l’hypothèse H1 du § 1.3.1. et le lemme 1.2 assurent que cette suite est bornée ; on peut donc extraire une sous-suite convergente : v^{k} → v^{∗}; comme K est fermé, v^{∗} ∈ K; la continuité de J donne de plus J(v^{k′}) ⟶ J(v^{∗}) on a donc I = J(v^{∗}) et le minimum est atteint en v^{∗}.

(ii) Considérons l’ensemble S_{v_{∗}} = {v ∈ IR^{n}/ E(v) = 0 et F_{sat}(v) = 0} il est défini à l’aide des mêmes égalités E(v) = 0 que K et l’on a remplacé les inégalités F(v) ≤ 0 par les égalités F_{sat(v_{∗})}(v) = 0 où F_{sat(v_{∗})} désigne [F_{i}]_{i∈sat(v^{∗})} (sat(v^{∗}) sont les indices tels que F_{i}(v) ≤ 0 soit saturée en v = v^{∗}) ; comme S_{v^{∗}} ⊂ K, la fonction J atteint donc son minimum au point v_{∗}, le théorème 2.3 assure que le Lagrangien

L(v, λ, μ) = J (v) +^{t}λ E(v) +^{t}μ_{sat(v_{∗})} F_{sat(v_{∗})}(v)

vérifie en (v^{∗}, λ^{∗}, μ_{sat(v_{∗})}^{∗})

\begin{matrix}\frac{∂L}{∂v}(v^{∗}, λ^{∗}, μ_{sat(v_{∗})}^{∗}) = 0 et \\ \frac{∂L}{∂λ^{∗}} (v^{∗}, λ^{∗}, μ_{sat(v^{∗})}^{∗}) = 0 & \frac{∂L}{∂μ^{∗}} (v^{∗}, λ^{∗}, μ_{sat(v^{∗})}^{∗}) = 0 \end{matrix}

Mais comme v^{∗} réalise un minimum local sur K qui contient S_{v^{∗}}, nous avons des conditions supplémentaires sur le signe des μ_{i}^{∗} pour i indice de contrainte d’inégalité saturée.

Comme v^{∗} est régulier le noyau de ^{t}B = [^{t}E′(v^{∗}) , ^{t}F′_{sat(v^{∗})}(v^{∗})] est réduit à zéro :

tB [ \begin{matrix}λ \\ μ_{sat(v^{∗})} \end{matrix} ] = ^{t}E′(v^{∗}) λ + ^{t}F′(v^{∗}) μ_{sat(v^{∗})} = 0

entraine λ = 0 et μ_{sat(v^{∗})} = 0 ; avec la proposition 1.4, l’opérateur B est donc surjectif ; soit donc k_{0} un indice de contrainte d’inégalité saturée ; on peut trouver w telque

E′(v^{∗}) w = 0 F′_{i}(v^{∗}) w = 0 pour i ≠ k_{0} et i ∈ sat(v^{∗}) F′_{k^{0}}(v^{∗}) w < 0 soit alors,

S_{v^{∗}}^{k^{0}} = {v/E(v) = 0 et F_{i}(v) = 0 i ∈ sat(v^{∗}) − {k^{0}}}

et soit t ⟼ v(t) ∈ S_{v^{∗}}^{k^{0}} telle que \frac{dv}{dt} |_{t=0} = w; comme v^{∗} est régulier, le théorème 2.2 (si w est orthogonal au gradient des contraintes, il est tangent à une courbe tracée sur la surface) assure que pour tout t petit, v(t) existe ;

comme F_{k_{0}}(v(t)) < 0 donc v(t) ∈ K pour tout t petit ; la condition d’optimalité \frac{∂L}{∂v}(v^{∗}, λ^{∗}, μ_{sat(v^{∗})}^{∗}) = 0 donne J′(v^{∗}) w + 0 + μ_{k_{0}} ^{t}F′_{k^{0}}(v^{∗}) w = 0

par suite comme F′_{k^{0}}(v^{∗}) w < 0, μ_{k_{0}} et J′(v^{∗})w sont de même signe ; d’autre part pour t petit v(t) est dans K, donc J (v(t)) ≥ J (v^{∗}) donne J′(v^{∗}) \frac{dv}{dt} |_{t=0} ≥ 0 par suite μ_{k_{0}} ≥ 0.

Finalement nous avons obtenu toutes les conditions en posant μ_{j}^{∗} = 0 pour les indices de contraintes non saturées ; dans ce cas

\begin{matrix}si F_{j}(v^{∗}) < 0  μ_{j}^{∗} = 0 et \\ si F_{i}(v^{∗}) = 0  μ_{i}^{∗} ≥ 0 \end{matrix}

on a donc bien μ^{∗} ≥ 0 et ^{t}μ^{∗} F(v^{∗}) = 0.

Conditions d’optimalité du deuxième ordre

De même que sans contraintes, l’annulation de la dérivée est une condition nécessaire et non suffisante d’optimalité, la situation est analogue en présence de contraintes : il convient d’utiliser les dérivées secondes du Lagrangien. La encore comme dans le cas sans contraintes on n’a pas de conditions nécessaires et suffisantes. Nous utilisons les mêmes notations que pour les conditions du premier ordre. Pour obtenir une condition suffisante assez générale, il est commode d’utiliser des vecteurs obtenus comme limites de sécantes ; on peut donner un contre-exemple où il n’existe pas de courbe qui satisfait F(x(t)) = 0 au voisinage d’un extremum.

Définition 2.5

K_{G} = {w ∈ IR^{n} : E′(v∗)w = 0, F′_{sat(v^{∗})}w ≤ 0};  (2.5)
K_{T} = {w|x^{∗} + α^{k}w^{k} ∈ K and w^{k} → w}

et l’on a le lemme :

Lemme 2 Si v^{∗} est régulier K_{T} = K_{G}

Pour les conditions du deuxième ordre, il faut considérer des ensembles un peu plus petit.

Théorème 2.5 (conditions nécessaires du deuxième ordre) Soit v^{∗} un point régulier de K où J atteint son minimum ; avec le théorème précédent, il satisfait les conditions du premier ordre. Soit

K_{G_{2}} = {w ∈ IR^{n} : E′(v∗)w = 0, F′_{sat^{+}(v^{∗})}w = 0, F′_{sat^{0}(v^{∗})}w ≤ 0};  (2.6)

où sat^{+}(v^{∗}) désigne les indices de contraintes saturées de multiplicateur strictement positif et sat^{0}(v^{∗}) désigne les indices de contraintes saturées de multiplicateur nul ; on a :

∀w ∈ K_{G_{2}} \frac{∂^{2}L^{∗}}{∂v^{2}} (w, w) ≥ 0  (2.7)

La démonstration utilise un lemme

Lemme 3 Si v^{∗} est régulier

K_{G_{2}} = \overline{K_{T_{2}}}

où

K_{T_{2}} = {w|x^{∗} + α^{k}w^{k} ∈ K_{2} and w^{k} → w}
K_{2} = {v|E(v) = 0 F_{sat^{+}(v^{∗})}(v) = 0} ∩ K

où sat^{+}(v^{∗}) désigne les contraintes saturées de multiplicateur strictement positif.

Théorème 2.6 Conditions suffisantes du deuxième ordre Si v^{∗} satisfait les conditions du premier ordre et si

∀w ∈ K_{G_{2}} \frac{∂^{2}L^{∗}}{∂v^{2}} (w, w) > 0  (2.8)

alors v^{∗} est un minimum local isolé.

Démonstration Soit la suite v^{k} = v^{∗} + δ^{k}w^{k} ∈ K avec ∥ w^{k} ∥= 1 avec x^{k} ∈ K; on extrait une sous-suite telle que w^{k′} → w ∈ K_{G}. cas 1 : w ∉ K_{G_{2}}. Dans ce cas, il existe i ∈ sat^{+}(v^{∗}) tel que F′_{i}w < 0 La condition du premier

ordre donne :

J′(v^{∗})w +^{t}λ^{∗} E′(v^{∗})w +^{t}μ^{∗} F′(v^{∗})w = 0

comme w ∈ K_{G} mais w ∉ K_{G_{2}} on en deduit que J′(v^{∗})w > 0 donc pour k′ grand J′(v^{∗})w^{k′} > 0 et donc J(v^{k′}) > J(v^{∗}). Notons que la condition du deuxième ordre n’a pas encore servi. C’est donc pour cela qu’il n’y a aucune condition à vérifier pour les w ∉ K_{G_{2}}.

cas2 :w ∈ K_{G_{2}}. Alors comme v^{k′} ∈ K donc

J(v^{k′}) ≥ L(v^{k′}, λ^{∗})

or la formule de Taylor fournit :

L(v^{k′}, λ^{∗}) = L^{∗}(v^{∗}, λ^{∗}) + δ^{k′} \frac{∂L}{∂x}(w^{k′}) + \frac{(δ^{k′})^{2}}{2} \frac{∂^{2}L^{∗}}{∂v^{2}} (w^{k′}, w^{k′}) + o((δ^{k′})^{2})

ce qui se simplifie avec la condition du premier ordre :

L(v^{k′}, λ^{∗}) = L(v^{∗}, λ^{∗}) + \frac{(δ^{k′})^{2}}{2} \frac{∂^{2}L^{∗}}{∂v^{2}} (w^{k′}, w^{k′}) + o((δ^{k′})^{2})

ou (comme L(v^{∗}, λ^{∗}) = J(v^{∗}))

J(v^{k′}) ≥ J(v^{∗}) + \frac{(δ^{k′})^{2}}{2} \frac{∂^{2}L^{∗}}{∂v^{2}} (w^{k′}, w^{k′}) + o((δ^{k′})^{2})

Ce qui donne avec la condition du deuxième ordre :

J(v^{k′}) > J(v^{∗})

Exercice 2.15 Soit J(x) = ∑_{i=1}^{n}(x_{i} − a_{i})^{2} avec les contraintes v_{i} ≤ c_{i} , i = 1, m ≤ n. En distingant, a_{i} < c_{i} , a_{i} = c_{i} , a_{i} > c_{i} préciser K_{G} , K_{G_{2}}.

Exercice 2.16 Soit j(x, y) = \frac{σx^{2}}{2} + \frac{y}{2} + x à minimiser avec x ≥ 0 ; discuter suivant σ.

Exercice 2.17 Soit A une matrice symétrique et J =^{t} xAx.

1. Soit la contrainte ^{t}xx = 1 ; préciser le min de J (discuter suivant les valeurs propres de A).

Ce résultat est souvent attribué à Lord Rayleigh

2. Soit la contrainte ^{t}xx ≥ 1 ; préciser le min de J.

3. Soit la contrainte ^{t}xx ≤ 1 ; préciser le min de J. On trouve un résultat un peu surprenant : x

vecteur propre associé à valeur propre simple négative, les autres étant positives ; considérer le cas n = 2, A de valeurs propres 1 et -1 ; tracer les courbes de niveau de J)

4. Avec A, définie positive, soit la contrainte ^{t}xx = 1 et ^{t}xx_{1} = 0 avec x_{1} vecteur propre associé à plus petite valeur propre ; préciser le min de J (discuter suivant les valeurs propres de A).

2.4 Devoir : optimisation en présence d’inégalités simples

MIM Partiel optimisation avril 1998 Rousselet

Exercice 1 On considère la minimisation de J : IR^{n} ⟶ IR dans K = {v ∈ IR^{n} :^{t} Bv − c ≤ 0}. 1. Avec quelles hypothèses a-t-on existence d’un minimum de J avec v ∈ K?

2. Avec quelles hypothèses peut-on écrire des conditions nécessaires d’optimalité avec des multiplicateurs de Lagrange ? Les écrire.

3. Dans le cas où

B = [e_{1}, ..., e_{m}]

avec e_{i} vecteurs de la base canonique deIR^{n} et m ≤ n, particulariser les conditions d’optimalité. Cas où n = m = 1 ; dessin.

4. Cas

J = \frac{1}{2}^{t}vAv −^{t} vF , B = [e_{1}, ..., e_{m}]

(A symétrique) particulariser les conditions d’optimalité. Résoudre avec n = m = 1 puis 2.

5. Autre cas

J = \frac{1}{2}^{t}(v − a)(v − a) , B = [e_{1}, ..., e_{m}]

particulariser les conditions d’optimalité. On note vP_{a} le point où le minimum est atteint (vecteur projection de a sur K)

6. Solution explicite des conditions d’optimalité précédentes ; dessin pour n = m = 2.

7. On utilise vP_{a} défini plus haut ; montrer

∥ vP_{a} − vP_{b} ∥_{2}≤∥ a − b ∥_{2}

Dessin avec n = m = 2.

Exercice 2 On considère la minimisation de J : L^{2}(Ω) ⟶ IR avec J(v) = \frac{1}{2} ∫_{Ω}(v − ϕ)^{2}dx; cette

fonctionnelle est à minimiser dans K = {v ∈ L^{2}(Ω) : v ≤ γ p.p.}

1. Préciser des conditions d’optimalité avec multiplicateur de Lagrange ; solution explicite ; comparer avec 1.6.

2. En approchant l’intégrale avec une formule d’intégration numérique (par exemple en dimension 1, les trapèzes avec Ω =]a, b[), écrire une fonctionnelle approchée définie dans IR^{n} avec n points de quadrature ; comparer avec 1.6.

Exercice3 On considère la minimisation de J : IR^{n} ⟶ IR avec J elliptique (constante α ) avec

de plus : ∥gradJ(x) − gradJ(y)∥ ≤ M∥x − y∥ 1. Existence unicité du minimum dans IR^{n}.

2. On considère l’algorthme du gradient ; on note v^{k} le k^{ieme} itéré et v^{∗} le minimum. En exprimant v^{k+1} − v^{∗} à l’aide de v^{k} et v^{∗}, monter que avec un choix convenable de ρ on a ∥v^{k+1} − v^{∗}∥ ≤ β∥v^{k} − v^{∗}∥ avec β < 1 3. Pour minimiser J dans K = {v ∈ IR^{n} :^{t} Bv − c ≤ 0} avec B = [e_{1}, ..., e_{m}], on considère

l’algorithme ṽ^{k+1} = vP_{v^{k+1}} où v^{k+1} se déduit de ṽ^{k} par un pas de l’algorithme du gradient et vP_{a} est défini dans l’exercice précédent (projection de a sur K) ; dessiner 2 itéres successifs avec n = 2, m = 1.

4. Avec le même choix de ρ que precédement, montrer que l’on a encore avec v^{∗} minimum

dans K :

∥ṽ^{k+1} − ṽ^{∗}∥ ≤ β∥ṽ^{k} − ṽ^{∗}∥

5. Conclusion pour cet algorithme.

2.5 Esquisse de solution

Exercice 1 1. Il suffit d’utiliser un théorème du cours. On suppose J continue et

limJ(v) = +∞ , ∥ v ∥→ +∞

K est manifestement fermé ; dans le cas où K est borné, la continuité de J est naturellement suffisante.

2. On applique le même théorème avec J différentiable et F(v) =^{t} Bv−c; comme F_{k}(v) =^{t} B_{k}, v est un point régukier des que les B_{k} sont linéairement indépendants pour k ∈ sat(v). Attention cela ne demande pas que tous les vecteurs B_{k} soient linéairement indépendants : penser au cas où K est un cube !

L(v, λ, μ) = J (v) + +^{t}μ F(v)

\frac{∂L^{∗}}{∂v} = \frac{∂J^{∗}}{∂v} +^{t} μ^{∗}^{t}B = 0

μ^{∗} ≥ 0 ;^{t} μ^{∗}F^{∗} = 0 ;^{t} Bv − c

3. Si B = [e_{1}, ..., e_{m}], la condition \frac{∂L}{∂v} = 0 se particularise en :

\frac{∂J^{∗}}{∂v_{1}} = −μ_{1}  (2.9)
⋮
\frac{∂J^{∗}}{∂v_{i}} = −μ_{i}  (2.10)
⋮
\frac{∂J^{∗}}{∂v_{m}} = −μ_{m}  (2.11)
⋮
\frac{∂J^{∗}}{∂v_{i}} = 0  (2.12)
⋮
\frac{∂J^{∗}}{∂v_{n}} = 0  (2.13)

Fig. 2.10 – En 1 variable

4. La condition \frac{∂L}{∂v} = 0 devient :

(Av − F)_{1} = −μ_{1}  (2.14)
⋮
(Av − F)_{i} = −μ_{i}  (2.15)
⋮
(Av − F)_{m} = −μ_{m}  (2.16)
⋮
(Av − F)_{i} = 0  (2.17)
⋮
(Av − F)_{n} = 0  (2.18)

Dans le cas n = m = 1 cas 1 Si F/a ≤ c alors v^{∗} = F/a cas2 Si F/a ≥ c alors v^{∗} = c = (F − μ^{∗})/a La dernière égalité détermine μ^{∗} Dans le cas m = n = 2 la discussion est analogue mais il faut distinguer 4 cas : [v_{1} < c_{1} v_{2} < c_{2}] [v_{1} < c_{1} v_{2} = c_{2}] [v_{1} = c_{1} v_{2} < c_{2}] [v_{1} = c_{1} v_{2} = c_{2}]

5. Maintenant, la fonction à minimiser est la distance de v au point a; l’ensemble des

conditions :

v_{i} = a_{i} − μ_{i} i=1, ..., m v_{i} = a_{i} mboxi = m + 1, ..., n
μ_{i} ≥ 0 v_{i} − c_{i} ≤ 0 μ_{i}(v_{i} − c_{i}) = 0 i=1, ..., m

6. Le minimum est donc atteint en (vP_{a})_{i} = v_{i}^{∗} = min(a_{i}, c_{i}) (vP_{a}) est la projection de a sur K.

Fig. 2.11 – Projection en 2 variables

7. (vP_{a})_{i} − (vP_{b})_{i} = min(a_{i}, c_{i}) − min(b_{i}, c_{i}) ce qui vaut suivant le cas a_{i} − b_{i} ou c_{i} − b_{i}

ou a_{i} − c_{i}. d’où l’on déduit facilement ∥ (vP_{a}) − (vP_{b}) ∥≤∥ a − b ∥

Exercice 2 1. La situation est analogue au premier problème mais dans un espace de Hilbert ; on utilise le théorème du chapitre Optimisation dans des espaces fonctionnels. La régularité est banale à vérifier ; comme l’espace est de Hilbert ; son dual est identifié à lui même, le multiplicateur est pris dans L^{2}(Ω).

L(v, p) = J(v) + ∫_{Ω} p(v − γ)

Les conditions d’optimalité :

∀h ∈ L^{2}(Ω) ∫_{Ω}(v − ϕ)h + ∫_{Ω} ph = 0

ce qui donne

v − ϕ + p = 0

d’autre part :

v − ϕ ≤ 0 ; ∫_{Ω} p(v − γ) = 0 ; p ≥ 0

On a donc si ϕleqγ v = ϕ ; p = 0 et si ϕ > γ on a v = γ.

2. En discrétisant :

J_{h} = \frac{1}{2} ∑_{i} ω_{i}(v_{i} − ϕ_{i})^{2}

et la contrainte v_{i} ≤ γ_{i} c’est donc un problème du type projection considéré dans le premier problème.

Fig. 2.12 – La solution

Exercice 3 Dans le cas où la fonctionnelle est plus compliquée qu’une distance, il est en général impossible de calculer explicitement la solution ; un algorithme possible est de projeter le gradient ; cet algorithme ne peut etre utilisé que si l’on sait effectivement projeter ; on se limite donc dans ce problème au cas simple v ≤ c.

1. Comme J est elliptique on a existence et unicité du minimum.

2. On a comme gradJ(v^{∗}) = 0

v^{k+1} − v^{∗} = v^{k} − ρgradJ(v^{k}) − v^{∗} − gradJ(v^{∗})

en prenant le produit scalaire :

∥v^{k+1}−v^{∗}∥^{2} = ∥v^{k}−v^{∗}∥^{2}−2ρ(v^{k}−v^{∗}, gradJ(v^{k})−gradJ(v^{∗}))+ρ^{2}∥gradJ(v^{k})−gradJ(v^{∗})∥

d’où avec l’ellipticité et le caratère Lipschitz du gradient :

∥v^{k+1} − v^{∗}∥ ≤ (1 − 2ρα + ρ^{2}M)∥v^{k} − v^{∗}∥^{2}

il est facile de trouver un intervalle pour ρ tel que l’on ait la majoration demandée.

3. Avec la solution de la question 6 du premier problème.

ṽ_{i}^{k+1} = (vP_{v^{k+1}})_{i} = min(v_{i}^{k+1}, c_{i})

Dessin facile. 4.

∥ṽ^{k+1} − ṽ^{∗}∥ = ∥vP_{v^{k+1}}) − vPṽ^{∗}∥ ≤ ∥ṽ^{k} − ρgradJ(ṽ^{k}) − ṽ^{∗} − gradJ(ṽ^{∗})∥

la première égalité car ṽ^{∗}, le minimum dans K est sa propre projection. On conclut avec une majoration analogue à celle du gradient sans contrainte.

Fig. 2.13 – Un pas de gradient projeté

2.6 Examen : Eléments finis et optimisation

MIM juin 1998 (B. Rousselet)

Exercice 1 On considère la fonctionnelle

J : V ⟶ IR  (2.19)
θ ⟼ ∫_{0}^{ℓ} \frac{k}{2} θ^{′2}ds − ∫_{0}^{ℓ} mθds  (2.20)

1. Donner un espace de Hilbert dans lequel la minimisation de J est bien définie. Existence et unicité du minimum.

2. On considère la minimisation de J dans

K_{1} = {θ ∈ V / ∫_{0}^{ℓ} sinθ ds = 0}  (2.21)

Ecrire puis justifier une condition nécessaire d’optimalité du 1premier ordre.

3. On considère la minimisation de J dans

K_{2} = {θ ∈ V / − c ≤ ∫_{0}^{ℓ} sinθ ds ≤ c}  (2.22)

Ecrire puis justifier une condition nécessaire d’optimalité du premier ordre.

4. Proposez une discrétisation de ce problème de minimisation : on ne demande pas de détailler le calcul explicite des fonctionnelles approchées.

5. Proposer un algorithme pour résoudre le problème d’optimisation discrétisé ; proposez un logiciel corespondant ?

6. Interprétation mécanique : flexion d’une tige inextensible au repos le long de l’axe des

x

x′(s) = cosθ y′(s) = sinθ

Donner une interprétation des contraintes K_{1} et K_{2} ainsi que du multiplicateur de Lagrange.

Exercice2 On considère la fonction :

J : IR^{3}  ⟶ IR  (2.23)
(θ_{0}, θ_{1}, θ_{2}) ⟼ \frac{k}{2} (θ_{0} − θ_{1})^{2} + \frac{k_{2}}{2} (θ_{2} − θ_{1})^{2} − m_{1}θ_{1} − m_{2}θ_{2}  (2.24)

1. (a) Expliciter une condition nécessaire du premier ordre pour la minimisation de J ; (b) etudier une condition suffisante du deuxième ordre.

(c) Que se passe-t-il si J ne dépend que de θ_{1}, θ_{2} ; (on fait θ_{0} = 0).

On fait cette hypothèse dans la suite

2. On minimise maintenant J : IR^{2} ⟶ IR avec la contrainte :

K_{1} = {(θ_{1}, θ_{2}) ∈ IR^{2} /ℓ(sinθ_{1} + sinθ_{2}) = 0}

Examen : Eléments finis et optimisation  53

(a) Expliciter une condition nécessaire du premier ordre pour la minimisation de J ; solution explicite.

(b) Etudier une condition suffisante du deuxième ordre.

(c) Interprétation mécanique du problème (en particulier K_{1} et le multiplicateur).

(d) On appelle θ_{α} le point où est atteint le minimum avec la contrainte perturbée :

K_{1,α} = {(θ_{1}, θ_{2}) ∈ IR^{2} /ℓ(sinθ_{1} + sinθ_{2}) = α}

Calculer la dérivée de α ⟼ J(θ_{α}).

3. On minimise maintenant J : IR^{2} ⟶ IR avec la contrainte :

K_{2} = {(θ_{1}, θ_{2}) ∈ IR^{2} / − c ≤ ℓ(sinθ_{1} + sinθ_{2}) ≤ c}

(a) Expliciter une condition nécessaire du premier ordre pour la minimisation de J ; discussion et solution explicite pour θ_{1}, θ_{2}, c petits.

(b) Etudier une condition suffisante du deuxième ordre.

(c) Interprétation mécanique du problème (en particulier K_{2} et le multiplicateur).

(d) On appelle θ_{α} le point où est atteint le minimum avec la contrainte perturbée :

K_{2,α} = {(θ_{1}, θ_{2}) ∈ IR^{2} / − c + α ≤ ℓ(sinθ_{1} + sinθ_{2}) ≤ c + α}

Calculer la dérivée de α ⟼ J(θ_{α}).

2.7 Une présentation de la programmation quadratique sé-

quentielle

2.7.1 Introduction, l’algorithme de Newton sans contraintes

L’idée de cette famille de méthodes est d’utiliser un algorithme du type Newton pour résoudre les conditions d’optimalité

\{ \begin{matrix}\frac{∂ L}{∂ x}(x, λ) = 0 \\ \frac{∂ L}{∂ λ}(x, λ) = 0 \end{matrix}

où L est un Lagrangien associé au problème. En fait cela revient plutôt à minimiser successivement les approximations quadratiques du Lagrangien. Voyons d’abord cela sans contraintes pour une fonction J : IR^{n} ⟶ IR ; la formule Taylor fournit :

J(x^{k} + δ) = J(x^{k}) + J′(x^{k}) δ + \frac{1}{2}J′′(x^{k})(δ, δ) + o(∥δ∥^{2})

on considère alors la minimisation de

q(δ) = J(x^{k}) + J′(x^{k}) δ + \frac{1}{2}J′′(x^{k})(δ, δ)

Cette fonction admet un unique minimum dès que J′′(x^{k}) est défini positif et c’est la solution de J′′(x^{k}) δ = −J′(x^{k}) on pose ensuite x^{k+1} = x^{k} + δ et l’on itère le processus. Si l’on pose g(x^{k}) = J′(x^{k}) cela donne g′(x^{k}) δ = −g(x^{k}) et l’on reconnaiit la méthode de Newton-Raphson pour résoudre g(x) = 0 ; cette dernière équation n’est autre que la condition nécessaire d’optimalité pour la minimisation de J (suffisante si J′′(x) est défini positif). Voici un résultat simple sur la convergence de la méthode de Newton

Proposition 2.1 Soit g = ^{t}J′(x) si g′(x) = J′′(x) est définie positive (dans un voisinage du minimum x_{∗}) :

∃ α > 0 α∥h∥^{2} ≤ ^{t}h g′(x) h ;

si g′ est lipschitzienne (au voisinage de x_{∗}) :

∃ M > 0 ∥g′(x) − g′(y)∥ ≤ M∥x − y∥

alors la méthode de Newton converge quadratiquement :

∥x^{k+1} − x^{∗}∥ ≤ \frac{M}{α} ∥x^{k} − x^{∗}∥^{2}

Démonstration L’itération g′(x^{k}) δ^{k} = −g(x^{k}) peut s’écrire avec h^{k} = x^{k} − x_{∗} δ^{k} = x^{k+1} − x^{k} = h^{k+1} − h^{k} g′(x^{k}) h^{k+1} = g′(x^{k}) h^{k} − g(x^{k}) or la formule de Taylor fournit : g(x^{k}) = g(x_{∗}) + g′(x_{∗}) h^{k} + o(h^{k}) comme au minimum g(x_{∗}) = 0 on obtient g′(x^{k}) h^{k+1} = (g′(x^{k}) − g′(x_{∗}))h^{k} + o(h^{k})

d’où avec l’uniforme ellipticité de g′(x) au voisinage de x_{∗} :

α ∥h^{k+1}∥^{2} ≤ ^{t} h^{k+1} (g′(x^{k}) − g′(x_{∗})) h^{k}

puis comme g′ est lipschitzien : α ∥h^{k+1}∥^{2} ≤ M ∥h^{k}∥^{2} ∥h^{k+1}∥ ou bien

α ∥h^{k+1}∥ ≤ M ∥h^{k}∥^{2}

ce qui montre que h^{k} → 0 et que la convergence est quadratique.

2.7.2 Programmation quadratique séquentielle

Soit la minimisation de J : IR^{n} ⟶ IR avec les contraintes d’égalité

c(x) = 0 avec c : IR^{n} → IR^{m} .

Le lagrangien associé : L(x, λ) = J(x) +^{t}λ c(x) ; dévellopons à l’ordre 2 au voisinage de (x^{k}, λ^{k}) avec la notation :

L^{k} = L(x^{k}, λ^{k}) , F^{k} = F(x^{k}) g^{k} = ^{t} J′(x^{k})

L(x^{k} + δ, λ^{k} + μ) = L^{k} + \frac{∂ L^{k}}{∂ x} δ +^{t}μ F^{k} + \frac{1}{2} \frac{∂^{2} L^{k}}{∂ x^{2}} (δ, δ) +^{t}μ\frac{∂ F^{k}}{∂ x} δ + o(|μ| + |δ|)^{2}

= J^{k} +^{t}λ^{k} F^{k} +^{t}g^{k}δ +^{t}λ^{k} \frac{∂ F^{k}}{∂ x} δ + \frac{1}{2} \frac{∂^{2} L^{k}}{∂ x^{2}} (δ, δ) +^{t}μF^{k} +^{t}μ\frac{∂ F^{k}}{∂ x} δ + o(|μ| + |δ|)^{2} .

Ou :

L(x^{k} + δ, λ^{k} + μ) = J^{k} +^{t}g^{k}δ + \frac{1}{2} \frac{∂^{2} L^{k}}{∂ x^{2}} (δ, δ) +^{t}(λ^{k} + μ) (F^{k} + \frac{∂ F^{k}}{∂ x} δ) + o(|μ| + |δ|)^{2}

En posant λ^{k+1} = λ^{k} + μ, on constate donc que la partie quadratique de ce developpement est constituée de deux termes :

q^{k}(δ) = J^{k} +^{t}g^{k}δ + \frac{1}{2} \frac{∂^{2} L^{k}}{∂ x^{2}} (δ, δ) et de ^{t}λ^{k+1} ^{t}ℓ^{k}(δ) = ^{t}λ^{k+1} (F^{k} + \frac{∂ F^{k}}{∂ x} δ)

La minimisation de q^{k} avec la contrainte ℓ^{k}(δ) = 0 a pour C.N.O. :

tg^{k} + \frac{1}{2} \frac{∂^{2} L^{k}}{∂ x^{2}} δ +^{t}ν (\frac{∂ c^{k}}{∂ x} ) = 0

Comme \frac{∂^{2} L^{k}}{∂ x^{2}} δ est proche de \frac{∂ L}{∂ x}(x^{k} + δ, λ^{k}) ceci est une C.N.O. approchée de notre problème initial D’où l’algorithme : Soit x^{1} , λ^{1} approximation initiale de (x_{∗}, λ_{∗}),

Faire pour k de 2 à k max |||||||||||||

Minimiser q^{(k)}(δ) avec ℓ^{k}(δ) = 0 ; soit

δ^{k} qui réalise le minimum

λ^{k+1} est le multiplicateur de Lagrange associé x^{k+1} = x^{k} + δ^{k} Vérifier un critère d’arrêt (par exple C.N.O.)

fin faire

Extension à des contraintes d’inégalités F(x) ≤ 0 ; on utilise le même algorithme en remplaçant ℓ^{k}(δ) = 0 par ℓ^{k}(δ) ≤ 0.

Commentaires :

1) Pour résoudre la minimisation du problème quadratique on peut utiliser l’algorithme du §2.3.1. pour les contraintes d’égalité ou du §2.3.2. pour les contraintes d’inégalité. On peut démontrer que si l’on part assez près du minimum, l’algorithme converge quadratiquement, la situation est donc analogue à celle de Newton. Du reste Fletcher [?] (1981) l’appelle méthode de Lagrange-Newton.

2) Les mises en oeuvre de cet algorithme utilisent souvent une méthode de quasi-Newton au lieu d’une méthode de Newton pour construire le problème quadratique approché ; c’est le cas dans le programme VF13 de Harwell HSL12.

2.7.3 Devoir : convergence de l’algorithme

Exercice 2.18 : Minimum \frac{1}{2}(x^{2} + y^{2}) avec y − x^{2} − 1 = 0.

1) Ecrire la C.N.O. ; résoudre et interpreter graphiquement.

2) En partant d’un point (x^{1}, y^{1}, λ^{1}) proche de (x_{∗}, y_{∗}, λ_{∗}) calculer (x^{2}, y^{2}, λ^{2}) avec l’algorithme cidessus et montrer que cette nouvelle solution donne une amélioration quadratique !

Exercice 2.19 Si (d’après Fletcher (1981)) la condition suffisante d’optimalité du deuxième ordre

est satisfaite en un point x^{∗} régulier pour les contraintes alors la matrice [ \begin{matrix}H_{L}^{∗} & G^{∗} \\ ^{t}G^{∗} & 0 \end{matrix} ] est inversible

au voisinage de x^{∗}, avec les notations H_{L}^{∗} matrice hessienne du Lagrangien L(x, λ) = J(x) +^{t}λ F(x) ; à noter cette matrice intervient dans l’algorithme de programmation quadratique séquentielle (voir §2.4.2. et l’exercice 2.20 ).

\underline{Solution} : La C.S.O. du 2nd ordre utilise l’ensemble G_{2}^{∗} = {y ∈ IR^{n} / ^{t}G_{i}^{∗} y = 0 i ∈ S − S_{0} , ^{t}G_{i}^{∗} y ≤ 0 i ∈ S_{0}} où S désigne les indices des contraintes saturées en x^{∗} et S_{0} les indices de S pour lesquels le multiplicateur est nul ; la C.S.O. du 2nd ordre : ∀y ∈ G_{r}^{∗} − {0} ^{t}y H_{L}^{∗} y > 0

On va montrer que le noyau de la matrice [ \begin{matrix}H_{L}^{∗} & G^{∗} \\ ^{t}G^{∗} & 0 \end{matrix} ] est réduit à zéro, ce qui assurera l’inver-

sibilité ; soit (y, μ) solution de

\{ \begin{matrix}H_{L}^{∗} y + G^{∗} μ & = 0 \\ ^{t}G^{∗} y & = 0 \end{matrix}

La deuxième équation signifie ^{t}G_{i}^{∗}y = 0 pour toutes les contraintes, donc y ∈ G_{2}^{∗}; d’autre part en multipliant la première équation on a : ty H_{L}^{∗} y +^{t}y G^{∗} μ = 0 et avec la C.S.O. ^{t}y G^{∗} μ < 0 pour y ∈ G_{r}^{∗} − {0}

Comme ^{t}G^{∗} y = 0 cela est impossible et entraîne que y = 0 ; finalement dans la première équation il reste G^{∗} μ = 0 ; la condition de régularité entraîne que μ = 0.

Exercice 2.20 Examen éléments finis et Optimisation ; Maîtrise M.I.M 1996/97- Partiel d’optimisation (avril 97)

On considère la minimisation de J_{0} : IR^{p} ⟶ IR avec les contraintes d’égalité F_{i}(x) = 0 , F_{i} : IR^{p} ⟶ IR; i = 1, ..., m

(On pose F = ( F_{1} ; ⋮ ; F_{m} )) et le cas particulier où p = 2 \underline{( C. P.)},

J_{0}(x) = \frac{1}{2} ^{t}xAx avec la contrainte x_{2} − x_{1}^{2} − 1 = 0.

1) Rappeler la C.N.O. du 1er ordre ; \underline{C. P.} : expliciter.

2) Rappeler la C.S.O. du 2ème ordre ; \underline{C. P.} : expliciter.

⟶ Utiliser les notations : g_{0} = \frac{^{t}∂J_{0}}{∂x} G = \frac{^{t}∂F}{∂x} ,

H_{0} matrice Hessienne de J_{0} : ^{t}yH_{0}z = \frac{∂^{2}J_{0}}{∂x^{2}} [y, z]

H Hessien de F : H_{ijl} = \frac{∂^{2}F_{i}}{∂x_{j} ∂x_{ℓ}} ; H_{L} matrice Hessienne du Lagrangien ;

tλH = ∑ λ_{i}H_{i} avec H_{i} matrice Hessienne de F_{i};

g_{0}^{∗} désigne g_{0} calculé en x^{∗} ,

58  Minimisation avec contraintes

g_{0}^{k} désigne g_{0} calculé en x^{k}, etc ..

3) Rappeler l’algorithme de programmation quadratique séquentiel ; \underline{C. P.} : expliciter.

4) En développant à l’odre 1, au voisinage de x^{∗} avec x^{k} = x^{∗} + h^{k}, λ^{k} = λ^{∗} + α^{k} : g^{k}, G^{k}, F^{k} , montrer que la C.N.O. du 1er ordre peut s’écrire :

\{ \begin{matrix}g_{0}^{k} + G^{k}λ^{∗} − H_{L}^{k} h^{k} +^{t}α^{k} H^{k} h^{k} & = O(∥h^{k}∥^{2}) \\ ^{t}G h^{k} & = O(∥h^{k}∥^{2}) \end{matrix}

\underline{C. P.} : préciser la formule et la retrouver directement.

5) En déduire que l’algorithme de programmation quadratique séquentiel peut s’écrire :

\{ \begin{matrix}H_{L}^{k} h^{k+1} + G^{k} α^{k+1} & = − ^{t}α^{k} H^{k} h^{k} + O(∥h^{k}∥^{2}) \\ ^{t}G^{k} h^{k+1} & = O(∥h^{k}∥^{2}) \end{matrix}

\underline{C. P.} : expliciter.

6) Avec quelles hypothèses peut - on en déduire :

max (∥h^{k+1}∥ , ∥α^{k+1}∥) ≤ c ∥h^{k}∥ max (∥h^{k}∥ , ∥α^{k}∥)

7) Convergence de l’algorithme ; nature de la convergence. \underline{Solution}

1) Le Lagrangien du problème est :

L(x, λ) = J_{0} +^{t} F avec λ ∈ IR^{m}

et dans le \underline{C.P.}

L(x, λ) = \frac{1}{2} ^{t}x A x + λ (x_{2} − x_{1}^{2} − 1) avec λ ∈ IR

La C.N.O. du 1er ordre s’écrit :

\{ \begin{matrix}\frac{∂L}{∂x} & = 0 \\ \frac{∂L}{∂λ} & = 0 \end{matrix}  soit  \{ \begin{matrix}g_{0}^{∗} + G^{∗} λ^{∗} & = 0 \\ F^{∗} & = 0 \end{matrix}

et dans le \underline{C.P.} : \{ \begin{matrix}A x^{∗} + λ^{∗} ( \begin{matrix}−2x_{1}^{∗} \\ 1 \end{matrix} ) & = 0 \\ x_{2}^{∗} − x_{1}^{∗}^{2} − 1 & = 0 \end{matrix}

2) Comme il s’agit d’un problème de minimisation avec contraintes d’égalité, l’ensemble G_{2}^{∗} utile pour la C.S.O. est simplement (voir § 2.3.1.) {p ∈ IR^{n} , ^{t}G_{i}^{∗} p = 0} et la C.S.O. est : ∀p ∈ G_{2}^{∗} − {0} ^{t}p H_{L} p > 0 où H_{L} est la matrice hessienne du Lagrangien :

H_{L} = H_{0} + ^{t}λ H = H_{0} + ∑ λ_{i} H_{i}

avec les notations de l’énoncé.

\underline{C.P.} H_{L} = A + λ ( \begin{matrix}−2 & 0 \\ 0 & 0 \end{matrix} ) G_{2}^{∗} = \{p, −2x_{1}^{∗} p_{1} + p_{2} = 0\}

et la \underline{C.S.O.} est : ∀p ∈ G_{2}^{∗} − {0} ^{t}p A p − 2λ p_{1}^{2} > 0

3) L’algorithme de programmation quadratique séquentielle (voir § 2.4.2.) peut s’écrire : Minimiser q^{k}(δ) avec la contrainte ℓ^{k}(δ) = 0 λ^{k+1} est le multiplicateur de Lagrange associé au problème quadratique et x^{k+1} = x^{k} + δ^{k} avec δ^{k} minimum du problème quadratique. Nous écrivons les conditions d’optimalité du problème quadratique où (voir §2.4.2.) q^{k}(δ) = J^{k} +^{t}g_{0}^{k} δ +^{t}δ H_{L}^{k} δ ℓ^{k}(δ) = F^{k} +^{t}G^{k} δ

Le Lagrangien associé est

L^{k}(δ, ν) = q^{k}(δ) +^{t}ν ℓ^{k}(δ) et la

C.N.O. s’écrit

\{ \begin{matrix}\frac{∂L^{k}}{∂δ} & = 0 \\ \frac{∂L^{k}}{∂ν} & = 0 \end{matrix}  ou \{ \begin{matrix}g_{0}^{k} + H_{L}^{k} δ + G^{k} ν & = 0 \\ F^{k} +^{t}G^{k} δ & = 0 \end{matrix}

la solution (δ, ν) de ce système

\{ \begin{matrix}H_{L}^{k} δ + G^{k} ν & = −g_{0}^{k} \\ ^{t}G^{k} δ & = F^{k} \end{matrix}

est notée (δ^{k}, λ^{k+1}) et x^{k+1} = x^{k} + δ^{k} est utilisé pour définir le problème quadratique approché à l’itération (k + 1) ; dans le C.P. le système est :

\{ \begin{matrix}A δ + λ^{k} ( \begin{matrix}−2 & 0 \\ 0 & 0 \end{matrix} ) δ + ( \begin{matrix}−2x_{1}^{k} \\ 1 \end{matrix} ) v & = − Ax^{k} \\ (−2x_{1}^{k} 1) δ^{k} & = − (x_{2}^{k} − (x_{1}^{k})^{2} − 1) \end{matrix}

4) Développons à l’ordre 1 avec x^{∗} = x^{k} − h^{k}

tg_{0}^{∗} = ^{t}g_{0}^{k} − ^{t}h^{k} H_{0}^{k} + O(|h^{k}|^{2})
tG^{∗} = ^{t}G^{k} − ^{t}h^{k} H^{k} + O(|h^{k}|^{2})
F^{∗} = F^{k} − ^{t}G^{k} h^{k} + O(|h^{k}|^{2})

et la C.N.O. du 1er ordre

\{ \begin{matrix}g_{0}^{∗} + G^{∗} λ^{∗} & = 0 \\ F^{∗} & = 0 \end{matrix} s’écrit avec λ^{∗} = λ^{k} − α^{k}

\{ \begin{matrix}g_{0}^{k} − H_{0}^{k} h^{k} + G^{k} λ^{∗} − ^{t}(λ^{k} − α^{k}) H^{k} h^{k} & = O(|h^{k}|^{2}) \\ ^{t} G^{k} h^{k} & = −F^{k} + O(|h^{k}|^{2}) \end{matrix}

La première équation peut se transformer en remarquant que

H_{L} = H_{0} +^{t}λ H et la deuxième avec F^{∗} = 0
\{ \begin{matrix}g_{0}^{k} + G^{k} λ^{∗} − H_{L}^{k} h^{k} + ^{t}α^{k} H^{k} h^{k} & = O(|h^{k}|^{2}) \\ ^{t} G^{k} h^{k} & = −F^{k} + O(|h^{k}|^{2}) . \end{matrix}

Pour le \underline{C.P.} :

\{ \begin{matrix}+A x^{k} + ( \begin{matrix}−2x_{1}^{k} \\ 1 \end{matrix} ) λ^{∗} − [A h^{k} + λ^{k} ( \begin{matrix}−2 & 0 \\ 0 & 0 \end{matrix} ) δ ] + ^{t}α^{k} [ \begin{matrix}−2 & 0 \\ 0 & 0 \end{matrix} ] h^{k} & = O(|h^{k}|^{2}) \\ (−2x_{1}^{k} 1) h^{k}  =  −(x_{2}^{k} − (x_{1}^{k})^{2} − 1) + O(|h^{k}|^{2}) \end{matrix}

5) Reprenons les itérations et utilisons le développement de la C.N.O. obtenu à la question précédente en notant que δ^{k} = x^{k+1} − x^{k} = h^{k+1} − h^{k} et λ^{k+1} = λ^{∗} + α^{k+1}

La première relation H_{L}^{k} δ^{k} + G^{k} λ^{k+1} = −g_{0}^{k} s’écrit H_{L}^{k} (h^{k+1} − h^{k}) + G^{k}(λ^{∗} + α^{k+1}) + g_{0}^{k} = 0

et avec la C.N.O. développée

H_{L}^{k} h^{k+1} + G^{k} α^{k} = −^{t}α^{k} H^{k} h^{k} + O(|h^{k}|^{2})

La deuxième relation

\begin{aligned}^{t} G^{k} δ^{k} & = −F^{k} s’écrit \\ ^{t} G^{k} h^{k+1} & = ^{t} G^{k} h^{k} − F^{k} = O(|h^{k}|^{2}) \end{aligned}

la deuxième égalité vient de la C.N.O. développée ; nous avons bien obtenu

\{ \begin{matrix}H_{L}^{k} h^{k+1} + G^{k} α^{k+1} & = − ^{t}α^{k} H^{k} h^{k} + O(|h^{k}|^{2}) \\ ^{t} G^{k} h^{k+1} & = O(|h^{k}|^{2}) \end{matrix}

Et pour le \underline{C.P.} :

\{ \begin{matrix}A h^{k+1} + λ^{k} ( \begin{matrix}−2 & 0 \\ 0 & 0 \end{matrix} ) h^{k+1} + ( \begin{matrix}−2x_{1}^{k} \\ 1 \end{matrix} ) α^{k+1} & = ^{t}α^{k} ( \begin{matrix}−2 & 0 \\ 0 & 0 \end{matrix} ) h^{k} + O(|h^{k}|^{2}) \\ (−2x_{1}^{k} 1) h^{k+1} & = + O(|h^{k}|^{2}) \end{matrix}

6) Le but des développements de la question précédente est d’obtenir une estimation de (h^{k+1}, α^{k+1}) à partir de (h^{k}, α^{k}) comme c’est habituel dans l’analyse de la convergence d’un algorithme. Insistons d’abord sur la méthode car la plupart des étuduants font le \underline{raisonnement} suivant qui est \underline{faux} ! Pour déduire de Bx = f une majoration de x, les étudiants essayent curieusement de majorer ∥B∥ par une constante c et en déduisent idiotement que ∥x∥ ≤ \frac{1}{c}∥f∥!

Il y a deux erreurs : d’abord en dimension finie ∥B∥ est toujours majorée par une constante et ensuite cela permet d’écrire ∥f∥ ≤ ∥B∥ ∥x∥ et donc on peut seulement minorer ∥x∥. Le bon raisonnement consiste simplement à écrire x = B^{−1} f d’où : ∥x∥ ≤ ∥B^{−1}∥ ∥f∥; il convient donc de majorer ∥B^{−1}∥ ou encore de savoir que B est inversible, uniformément si il dépend de paramètres comme c’est le cas ici.

On va utiliser cette démarche avec

B = [ \begin{matrix}H_{L}^{k} & G^{k} \\ ^{t}G^{k} & 0 \end{matrix} ]  x = [ \begin{matrix}h^{k+1} \\ α^{k+1} \end{matrix} ]  f = [ \begin{matrix}−^{t}α^{k} H^{k} h^{k} + O(|h^{k}|^{2}) \\ O(|h^{k}|^{2}) \end{matrix} ]

L’uniforme inversibilité de B au voisinage de (x^{∗}, λ^{∗}) fait l’objet de l’exercice 2.19 ; en prenant comme norme max(∥h∥; ∥α∥) on a donc :

max(∥h^{k+1}∥, ∥α^{k+1}∥) ≤ c max(∥α^{k}∥ ∥h^{k}∥ , ∥h^{k}∥^{2})

7) Pour en déduire la convergence de l’algorithme, posons e^{k} = max(∥h^{k}∥, ∥α^{k}∥) ; l’estimation ci-dessus s’écrit :

e^{k+1} ≤ c ∥h^{k}∥ e^{k} ≤ c (e^{k})^{2}

ce qui donnera la convergence \underline{quadratique} de l’algorithme dès que l’on saura que lim_{k→+∞} e^{k} = 0 ; pour cela on va montrer que c e^{k} ≤ β < 1 ce qui donnera

e^{k+1} ≤ β e^{k} et la convergence vers zéro de e^{k}. Pour cela nous raisonnons par récurrence en montrant d’abord c e^{2} ≤ β < 1 ; pour cela, nous distingons deux cas : \underline{1er cas} : Si ∥h^{1}∥ ≤ |α^{1}| alors

e^{2} ≤ c∥h^{1}∥e^{1} ≤ β < 1 dès que ∥h^{1}∥ ≤ \frac{β}{c e^{1}} = \frac{β}{c∥α^{1}∥}

donc dans ce cas on prendra :

∥h^{1}∥ ≤ ∥α^{1}∥ et ∥h^{1}∥ ≤ \frac{β}{c∥α^{1}∥}

(si ∥α^{1}∥ grand on doit prendre ∥h^{1}∥ petit)

\underline{2ème cas} : si ∥α^{1}∥ ≤ ∥h^{1}∥ alors e^{2} ≤ c∥h^{1}∥ e^{1} = c ∥h^{1}∥^{2} ≤ β c

dès que ∥h^{1}∥^{2} ≤ \frac{β}{c}

dans ce cas on prendra

∥α^{1}∥ ≤ ∥h^{1}∥ ≤ \sqrt{\frac{β}{c}}

La \underline{récurrence} est ensuite aisée : hypothèse de récurrence c e^{k} ≤ β < 1 on a e^{k+1} ≤ c (e^{k})^{2} ≤ β e^{k}

et d’autre part c e^{k+1} ≤ c β e^{k} ≤ β^{2} < β d’où c e^{k+1} ≤ β < 1 ce qui achève la récurrence et la solution du problème.

Exemples d’optimisation d’origine

mécanique

Nous donnons dans ce chapitre des exemples de problèmes d’optimisation d’origine mécanique avec ou sans contraintes. La discussion des conditions aux limites se fait avec des arguments mécaniques ; à titre d’\underline{exercice} on justifiera tout ça avec les conditions d’optimalité du chapitre 3

3.1 Introduction ; exemple sans contraintes

Dans ce chapitre on décrit un exemple très simple issu de la mécanique des structures : il s’agit d’un assemblage de barres munies de rotules avec ressort de rappel. Nous considérons le cas de petites rotations qui donne lieu à la minimisation d’une énergie potentielle totale sans contraintes si le mouvement de rotation des barres ne peut rencontrer aucun obstacle ; en présence d’obstacles (liaisons unilatérales) l’équilibre des barres s’obtient par minimisation de l’énergie potentielle avec les contraites sur les déplacements. La position d’équilibre peut donc être obtenue avec un algorithme de programmation quadratique §2.3.2 ; ceci peut être réalisé avec un autre algorithme, le programme V E17 dû à Powell et qui se trouve dans la bibliothèque HSL12 de HARWELL.

Le cas à un ressort

- \underline{équilibre des forces} : ici équilibre des moments en O où est située une rotule sans frottements :

Fig. 3.1 – Equilibre des forces.

M_{0} = F ℓ

- \underline{loi du ressort} : M_{0} = k θ (relation contraintes-déformations en élasticité linéaire).

- d’où l’\underline{équation} : k θ = F ℓ En fait, on a écrit l’équilibre des moments sur la configuration au repos : approximation correcte, seulement pour θ petit : en fait le moment en O de la force appliquée est M_{0} = F ℓ cos θ et l’équation est alors :

k θ = F ℓ cos θ (équation exacte)

L’approximation ci-dessus est correcte si θ^{2} est négligeable devant 1.

Dans les deux cas :

- énergie élastique : w(θ) = \frac{1}{2} kθ^{2}

- travail des forces extérieures : \{ \begin{matrix}cas approché : F ℓ θ \\ cas exact : F ℓ sin θ \end{matrix}

- énergie potentielle totale :

Π = \frac{1}{2} k θ^{2} − F ℓ sin θ exact

Π ≃ \frac{1}{2} k θ^{2} − F ℓ θ approché

Principe de stationarité de l’énergie potentielle totale : (valable seulement en \underline{élasticité}). L’équilibre a lieu en θ qui annule Π′ (θ) : Π′ (θ) = 0 redonne les équations obtenues par équilibre des forces ; l’équilibre est \underline{stable} quand c’est un minimum de Π (voir par exemple Bamberger [?] (1981), Corradi [?]). Remarque dans le cas exacte Π′′ = k + F ℓ sin θ

Exercice 3.1 Vérifier la stabilité de l’équilibre (Π′′ > 0 à l’équilibre).

\underline{Cas à deux ressorts} (petits déplacements)

Le deuxième ressort tourne de θ_{2} − θ_{1} par rapport au premier. Nous étudions toujours l’équilibre avec l’énergie potentielle totale (Cf par exemple Bamberger [?] (1981)).

- énergie de déformation élastique.

w(θ_{1}, θ_{2}) = \frac{1}{2}k_{1}θ_{1}^{2} + \frac{1}{2}k_{2}(θ_{2} − θ_{1})^{2}

- travail des forces extérieures (\underline{cas approché} : θ_{i}^{2} << 1) : T = F_{1}ℓ_{1}θ_{1} + F_{2}(ℓ_{2}θ_{2} + ℓ_{1}θ_{1})

- énergie potentielle totale : Π = w − T

- \underline{Equilibre} :

\{ \begin{matrix}\frac{∂ Π_{1}}{∂ θ_{1}} = k_{1} θ_{1} − k_{2}(θ_{2} − θ_{1}) − F_{1} ℓ_{1} − F_{2} ℓ_{1} \\ \frac{∂ Π_{2}}{∂ θ_{2}} =  + k_{2}(θ_{2} − θ_{1}) − F_{2} ℓ_{2} \end{matrix}

- \underline{Stabilité} :

\begin{matrix}\frac{∂^{2} Π}{∂ θ_{1}^{2}} = k_{1} + k_{2} \\ \frac{∂^{2} Π}{∂ θ_{1} ∂ θ_{2}} = − k_{2} \frac{∂^{2} Π}{∂ θ_{2}^{2}} = k_{2} \end{matrix}

le Hessien est donc H = [ \begin{matrix}k_{1} + k_{2} − k_{2} \\ −k_{2} k_{2} \end{matrix} ]

\underline{définie positive :} si et seulement si tous les mineurs principaux sont ≥ 0 k_{1} + k_{2} > 0 det H = (k_{1} + k_{2})k_{2} − k_{2}^{2} = k_{1}k_{2} > 0 réalisé par exemple quand k_{1} > 0, k_{2} > 0 ce qui est naturel : ressorts de rappel.

3.2 Exemples avec contraintes

3.2.1 Cas d’une liaison (avec deux ressorts) \underline{bilatérale}

Fig. 3.2 – Une liaison bilatérale ; schématisation d’un rail

On suppose que l’extrémité se déplace sans frottement sur une droite ; (x_{0}, y_{0}) position de l’extrémité au repos, (x, y) position après chargement ; équation de la droite :

a x + b y + c = 0 d’autre part puisque l’extrémité (x_{0}, y_{0}) se trouve sur la droite D a x_{0} + b y_{0} + c = 0 le déplacement de l’extrémité est relié au déplacement

\begin{matrix}u_{1} + u_{2} = x − x_{0} \\ v_{1} + v_{2} = y − y_{0} \end{matrix}

et vérifie : a (u_{1} + u_{2}) + b (v_{1} + v_{2}) = 0

Le principe de stationarité s’applique aux systèmes avec liaisons : la position d’équilibre annule la dérivée du Lagrangien :

L(u, v, λ) = Π(u, v) + λ (a(u_{1} + u_{2}) + b(v_{1} + v_{2}))

pour l’utiliser, il faut tout exprimer à l’aide des mêmes variables ; on peut exprimer l’angle à partir du déplacement :

v_{i} = ℓ_{i} sin θ_{i} ≃ ℓ_{i} θ_{i} θ_{i} ≃ \frac{v_{i}}{ℓ_{i}} (θ_{i}^{2} négligé devant 1) Le Lagrangien s’écrit :

L(u_{1}, u_{2}, v_{1}, v_{2}; λ) = \frac{1}{2}k_{1} (\frac{v_{1}}{ℓ_{1}} )^{2} + \frac{1}{2}k_{2} (\frac{v_{2}}{ℓ_{2}} − \frac{v_{1}}{ℓ_{1}} )^{2} − F_{1}v_{1} − F_{2}(v_{1} + v_{2})

− G_{1}u_{1} − G_{2}(u_{1} + u_{2}) + λ (a (u_{1} + u_{2}) + b (v_{1} + v_{2}))

\underline{Equilibre} : \frac{∂Π}{∂u_{i}} = 0 \frac{∂Π}{∂v_{i}} = 0

\frac{∂L}{∂u_{1}} = −G_{1} − G_{2} + λ a

\frac{∂L}{∂u_{2}} = −G_{2} + λ a

\frac{∂L}{∂v_{1}} = \frac{k_{1}}{ℓ_{1}^{2}} v_{1} − \frac{k_{2}}{ℓ_{1}} (\frac{v_{2}}{ℓ_{2}} − \frac{v_{1}}{ℓ_{1}} ) − F_{1} − F_{2} + λ b = 0

\frac{∂L}{∂v_{2}} = −\frac{k_{2}}{ℓ_{2}} (\frac{v_{2}}{ℓ_{2}} − \frac{v_{1}}{ℓ_{1}} ) − F_{2} + λ b = 0

les deux premières conditions nous donnent G_{1} = 0 et G_{2} = λ a; ceci est particulier : avec notre approximation, l’énergie potentielle ne contient pas u_{1}, il est donc normal que l’on ne puisse pas prendre en compte une force horizontale^{1} .

Pour simplifier on supposera G_{2} = 0 et a = 0 alors la liaison se réduit à : v_{1} + v_{2} = 0 ;

\underline{Analyse aux dimensions} : b (v_{1} + v_{2}) = 0 v_{i} est une longueur, b sans dimension, F_{i} est une force, \frac{k_{2}v_{1}}{ℓ_{1}ℓ_{2}} aussi ; λ a donc la dimension d’une force ! c’est la force de réaction exercée par le support pour que l’extrémité reste sur le support.

\underline{Autre situation} : supposons qu’une rotule est bloquée par exemple θ_{2} − θ_{1} = 0 on peut bien sûr voir directement que w = \frac{1}{2}k_{1}θ_{1}^{2} ; retrouvons le avec un multiplicateur

1ce cas n’est pas considéré dans le cours sur les C.N.O.

L = W − T + λ (\frac{v_{2}}{ℓ_{2}} − \frac{v_{1}}{ℓ_{1}} )

Equilibre

\frac{∂L}{∂v_{1}} = \frac{k_{1}}{ℓ_{1}^{2}} v_{1} − \frac{k_{2}}{ℓ_{1}} (\frac{v_{2}}{ℓ_{2}} − \frac{v_{1}}{ℓ_{1}} ) − F_{1} − F_{2} − \frac{λ}{ℓ_{1}}

\frac{∂L}{∂v_{2}} = −\frac{k_{2}}{ℓ_{2}} (\frac{v_{2}}{ℓ_{2}} − \frac{v_{1}}{ℓ_{1}} ) − F_{2} + \frac{λ}{ℓ_{2}}

\frac{v_{2}}{ℓ_{2}} − \frac{v_{1}}{ℓ_{1}} = 0 fournit :

\{ \begin{matrix}\frac{k_{1}}{ℓ_{1}^{2}} v_{1} − F_{1} − F_{2} − \frac{λ}{ℓ_{1}} = 0 \\ −F_{2} + \frac{λ}{ℓ_{2}} = 0 \end{matrix}

λ = F_{2}ℓ_{2} est le produit d’une force par une distance, c’est un moment, le moment qui permet le blocage de la rotule.

3.2.2 Liaisons Unilatérales

Exemple 0 Une rotule à blocage

Π(θ) = \frac{1}{2}kθ^{2} − F lsinθ avec θ ≤ \overline{θ}

Le Lagrangien :

L(θ, λ) = Π(θ) + λ(θ − \overline{θ})

es conditions d’optimalité :

kθ − F lcosθ + l = 0  (3.1)
λ(θ − \overline{θ}) = 0 ; λ ≥ 0 ; θ − \overline{θ} ≤ 0  (3.2)

cas 1 : λ = 0 alors kθ − F lcosθ = 0 ; il y a une solution dans [0, \frac{π}{2} ] mais elle ne convient que si

θ − \overline{θ} ≤ 0 ; quand on approche le cosinus par 1, ca donne \frac{F l}{k} ≤ \overline{θ}. cas 2 : θ − \overline{θ} = 0 dans ce cas θ est connu mais cela n’est possible que si λ ≥ 0 on doit donc avoir :

k\overline{θ} − F lcos\overline{θ} ≤ 0 ; dans le cas contraire, cela voudrait dire que le blocage agit dans le même sens que la force ce qui ne corespond pas aux conditions de l’expérience ; noter que λ est l’opposé de la réaction !

Exemple 1 Les rotules n’autorisent pas une trop grande rotation :

θ_{1} ≤ θ̄_{1} ou \frac{v_{1}}{ℓ_{1}} ≤ θ̄_{1}

θ_{2} − θ_{1} ≤ θ̄_{21} ou \frac{v_{2}}{ℓ_{2}} − \frac{v_{1}}{ℓ_{1}} ≤ θ̄_{21}

L(v, λ) = W − T + λ_{1} (\frac{v_{1}}{ℓ_{1}} − θ̄_{1}) + λ_{2} (\frac{v_{2}}{ℓ_{2}} − \frac{v_{1}}{ℓ_{1}} − θ̄_{21})

\{ \begin{matrix}\frac{∂L}{∂v_{1}} = \frac{k_{1}}{ℓ_{1}^{2}} v_{1} − \frac{k_{2}}{ℓ_{1}} (\frac{v_{2}}{ℓ_{2}} − \frac{v_{1}}{ℓ_{1}} ) − F_{1} − F_{2} + \frac{λ_{1}}{ℓ_{1}} − \frac{λ_{2}}{ℓ_{2}} \\ \frac{∂L}{∂v_{2}} =  −\frac{k_{2}}{ℓ_{2}} (\frac{v_{2}}{ℓ_{2}} − \frac{v_{1}}{ℓ_{1}} ) − F_{2} + \frac{λ_{2}}{ℓ_{2}} \end{matrix}

\{ \begin{matrix}−\frac{v_{1}}{ℓ_{1}} − θ_{1} ≤ 0 \\ \frac{v_{2}}{ℓ_{2}} − \frac{v_{1}}{ℓ_{1}} − θ̄_{2_{1}} ≤ 0 \end{matrix}

- si les inégalités sont saturées c’est à dire si \frac{v_{1}}{ℓ_{1}} − θ_{1} = 0 et si

\frac{v_{2}}{ℓ_{2}} − \frac{v_{1}}{ℓ_{1}} − θ̄_{2_{1}} = 0,

les équations d’équilibre donnent λ_{1} et λ_{2} (moments qui autorisent le blocage)

λ_{2} = F_{2} ℓ_{2} − k_{2} θ̄_{21}

pour θ̄_{21} petit,λ_{2} a le même signe que F_{2} ℓ_{2} ; λ_{2} + k_{2} θ̄_{21} = F_{2}ℓ_{2} : le blocage et le ressort équilibrent F_{2}ℓ_{2}.

- si θ̄_{21} est plus grand on peut avoir λ_{2} = F_{2} ℓ_{2} − k_{2} θ̄_{21} < 0 dans ce cas λ_{2} < 0, et F_{2} ℓ_{2} = λ_{2} + θ̄_{21} < λ_{2} le blocage s’oppose à l’action du ressort ; mécaniquement idiot ; on est donc amené à considérer que λ_{i} > 0

D’autre part quand \{ \begin{matrix}\frac{v_{1}}{ℓ_{1}} − θ_{1} < 0 \\ \frac{v_{2}}{ℓ_{2}} − \frac{v_{1}}{ℓ_{1}} < θ̄_{21} \end{matrix}

les blocages ne sont pas actifs, mécaniquement on est amené à considérer λ_{1} = 0 et λ_{2} = 0 ; si une liaison est saturée le multiplicateur est positif ; si une liaison n’est pas saturée, ce multiplicateur est nul.

Exercice 3.2 1. retrouver cela en utilisant la C.N.O. du §2.3.1 2. si nécessaire reprendre et discuter le même problème avec une seule barre avec θ ≤ θ̄.

Exemple 2 un obstacle empêche chaque rotule de trop descendre

∑_{j≤i} v_{j} ≤ v̄_{i}

L(v, λ) = W − T + λ_{1} (v_{1} − v̄_{1}) + λ_{2} (v_{1} + v_{2} − v̄_{2})

\{ \begin{matrix}\frac{∂L}{∂v_{1}} = \frac{k_{1}}{ℓ_{1}^{2}} v_{1} − \frac{k_{2}}{ℓ_{1}} (\frac{v_{2}}{ℓ_{2}} − \frac{v_{1}}{ℓ_{1}} ) − F_{1} − F_{2} + λ_{1} + λ_{2} \\ \frac{∂L}{∂v_{2}} =  −\frac{k_{2}}{ℓ_{2}} (\frac{v_{2}}{ℓ_{2}} − \frac{v_{1}}{ℓ_{1}} ) − F_{2} + λ_{2} \end{matrix}

si les inégalités sont saturées \{ \begin{matrix}v_{1} = v̄_{1} \\ v_{1} + v_{2} = v̄_{2} \end{matrix} −\frac{k_{2}}{ℓ_{1}} (\frac{v̄_{2}}{ℓ_{2}} − \frac{v̄_{1}}{ℓ_{1}} ) + λ_{2} = F_{2}

si −\frac{k_{2}}{ℓ_{1}} (\frac{v_{2}}{ℓ_{2}} − \frac{v_{1}}{ℓ_{1}} ) + λ_{2} < F_{2} on a λ_{2} < 0

les ressorts et l’obstacle n’agissent pas dans le même sens : contact idiot ; au contraire si v_{1} < v̄_{1} pas de contact pas de réaction d’où λ_{1} = 0.

Cas d’un grand nombre de ressorts

W = \frac{1}{2}k_{1} θ_{1}^{2} + \frac{1}{2} ∑_{i=2}^{nr} k_{i}(θ_{i} − θ_{i−1}) n r = nombre de ressorts ; θ_{i} = \frac{v_{i}}{ℓ_{i}}

T = ∑_{i} F_{i} (∑_{j≤i} v_{j}) = F_{1}v_{1} + F_{2}(v_{1} + v_{2}) + … + F_{7}(v_{1} + ⋯ + v_{7})
= (F_{1} + ⋯ + F_{7})v_{1} + (F_{2} + ⋯ + F_{7})v_{2} + ⋯ + F_{7}v_{7}

\underline{Liaison} : θ_{i+1} − θ_{i} ≤ θ̄_{i+1,i} \frac{v_{1}}{ℓ_{1}} ≤ θ̄_{1}

\frac{v_{i+1}}{ℓ_{i+1}} − \frac{v_{i}}{ℓ_{i}} ≤ θ̄_{i+1,i}  ∑_{j≤i} v_{j} ≤ v̄_{i}

Exercice 3.3 1) écrire matriciellement avec les variables v_{i} (ou bien θ_{i}) l’énergie potentielle et les contraintes.

2) Calculer la position d’équilibre avec le sous-programme Ve17ad de la bibliothèque Harwell HSL 12.

3.3 Analyse en grands déplacements

On étudie le cas de grands déplacements : on n’approche plus sinθ par θ et en présence d’obstacles. Pour prendre en compte les contraintes en déplacements (liaison unilatérale avec un obstacle) nous exprimons l’énergie potentielle en déplacement en posant

θ_{i} = Arc sin \frac{v_{i}}{ℓ_{i}}

mais dans ce cas il faut imposer comme contraintes l’inextensibilité des barres. On considère le même problème mécanique que précédement.

Exercice 3.4 1) Ecrire des sous-programmes qui calculent l’énergie potentielle totale et son gradient, les contraintes et leur gradient ;

2) utiliser le sous-programme Ve13ad de la bibliothèque Harwell HSL 12 pour trouver la position d’équilibre.

Optimisation dans des espaces

fonctionnels

4.1 Introduction

Ce chapitre considère des situations où le problème n’est pas naturellement posé dans R^{n}.

– Le cas sans contrainte est très classique : minimisation de l’énergie potentielle en élasticité, principe de Hamilton en dynamique.

– Le cas avec une contrainte s’intitule classiquement, problème isopérimétrique ; voici un exemple : Minimiser J(ϕ) = ∫_{a}^{b} ϕdx avec ∫_{a}^{b} \sqrt{1 + ϕ^{′2}}dx − l = 0 avec ϕ(a) = 0 = ϕ(b) nous avons ici une contrainte définie à l’aide d’une intégrale.

– Nous pouvons avoir aussi une "infinité" de contraintes comme en automatique (ou controle optimal). Voici une situation classique dite linéaire-quadratique : minimiser

J(x, u) =^{t} x(t_{f})Sx(t_{f})/2 + \frac{1}{2} ∫_{t_{0}}^{t_{f}} [^{t}xCx +^{t} uQu]dx

avec les contraintes

ẋ = Ax(t) + Bu(t) t ∈ [t_{0}, t_{f}] x(t_{0}) = x_{0}

4.2 Automatique

Nous détaillons l’exemple ci-dessus.

Exercice 4.1 1. Approcher le problème ci-dessus avec une formule d’intégration numérique pour la fonctionnelle et l’équation différentielle (le plus simple est les trapèzes et Euler explicite).

2. Ecrire un Lagrangien pour le problème discrétisé.

3. Ecrire les conditions d’optimalité.

4. Essayer de les résoudre (on pourra y revenir après l’etude du cas continu).

Dans l’exemple ci-dessus vous avez pris soin de prendre un multiplicateur associé à chaque noeud de discrétisation ; pour le cas continu, le multiplicateur devient une fonction p (et même une mesure μ comme nous verrons plus loin). Le Lagrangien s’écrit donc à l’aide d’une intégrale (ou plus géneralement à l’aide d’un crochet de dualité).

L(x, u, p) = J(x, u) + ∫_{t_{0}}^{t_{f}} [^{t}p(ẋ − Ax(t) − Bu(t))]dt  (4.1)

La premiére condition d’optimalité :

∀v \frac{∂L}{∂u}v = 0  (4.2)

donne :

Qu +^{t} Bp = 0  (4.3)

d’autre part :

∀y \frac{∂L}{∂x}y = 0  (4.4)

fournit :

ty(t_{f})Sx(t_{f}) + ∫_{t_{0}}^{t_{f}} [^{t}yCx]dt + ∫_{t_{0}}^{t_{f}} [^{t}p(ẏ − Ay)]dt  (4.5)

Par intégration par parties, nous trouvons :

− ṗ −^{t} Ap + Cx = 0 t ∈ [t_{0}, t_{f}]  (4.6)

avec

tp(t_{f}) + Sx(t_{f}) = 0  (4.7)

Cette équation est dite adjointe ; si x était connu, ce serait une équation analogue à l’équation d’état mais avec une matrice transposée et une condition initiale en t_{f} ; c’est un problème rétrograde ; la solution est dite état adjoint.

Exercice 4.2 Approcher les conditions d’optimalité avec Euler et la formule des trapèzes et comparer. (Vous pouvez trouver de petites variantes)

4.3 Deux théorèmes

Voici deux théorèmes qui permettent d’écrire des conditions d’optimalité locales pour des problèmes d’optimisation posés dans des espaces de Banach ; on pourra trouver des démonstrations dans [?].

4.3.1 Contraintes d’égalité

Définition 4.1 Soient X et Z deux espaces de Banach et E une application continuement Fréchet dérivable : E : X → Z et K = {x; E(x) = 0}; x_{0} est dit un point régulier de K si et seulement si l’application linéaire E′(x_{0}) : X → Z est surjective.

Théorème 4.1 Soit J : X → IR, continuement Fréchet dérivable ; si x_{∗} réalise un minimum local de J dans K et est un point régulier de K, alors il existe z′_{∗} ∈ Z′ tel que le lagangien

L(x, z′) = J(x)+ < z′, E(x) >  (4.8)

vérifie :

∀h ∈ X \frac{∂L}{∂x}(x_{∗}, z′_{∗})h = 0  (4.9)

et \frac{∂L}{∂z′_{∗}} = 0 (ce qui redonne la contrainte).

La démonstration peut se faire en utilisant un théorème de la fonction inverse généralisée dû à Liusternik.

Ce théorème permet de justifier l’écriture de conditions d’optimalité pour des problèmes de type isopérimétrique ou d’automatique avec des contraintes d’égalités.

Exercice 4.3 1. On considère la fonctionnelle

\frac{1}{2} ∫_{a}^{b}[y^{′2} − fy]dx;  (4.10)

minimiser avec y(a) = α y(b) = β; introduire des espaces adéquat et écrire des conditions d’optimalité.

2. Interpréter les multiplicateurs de Lagrange ; cas particulier α = 0 = β.

3. Considérer la même fonctionnelle avec les contraintes y(a) = α y(b) = β y(x_{0}) = y_{0} avec a < x_{0} < b

4. Extension en plusieurs variables.

4.3.2 Application à la conception de systèmes

Nous considérons ici, sous formes d’application, un exemple très simple pour illustrer la conception de systèmes. Cette démarche est en fait au coeur de l’application industrielle des mathématiques. Pourquoi résout-on des équations ? Tout simplement pour prévoir le comportement de systèmes complexes avant leur fabrication ; le comportement d’un système dépend de nombreux paramètres que l’on cherche toujours à optimiser au mieux. Cette étude peut se placer au niveau de l’avant projet ou plus tard au niveau de la mise au point des détails du projet. L’exemple suivant est présenté d’un autre point de vue dans le document d’optimisation de structures (barre peusante d’élongation minimum).

Système à analyser

Cet exemple est présenté par Verma et Keller [?] (la présentation de la solution est légèrement différente). L’origine mécanique est la suivante : comme dans l’interprétation donnée à la fin du §2, il s’agit d’une barre chargée le long de son axe : u désigne le déplacement longitudinal, l’allongement relatif est γ = u′(x) et l’effort normal n = EAu′(x) avec A(x) aire de la section droite ; cette barre est fixée à une extrémité x = 0, elle est soumise à une force concentrée à son autre extrémité x = ℓ et à son poids propre : force répartie de densité linéique ρgA(x) avec ρ masse volumique du matériaux, g accélération de la pesanteur.

Fig. 4.1 – Barre chargée verticalement

Le principe des travaux virtuels (ou principe variationnel), s’écrit donc :

\{ \begin{matrix}trouver u_{A} nul en x = 0 telque pour v nul en x = 0 \\ ∫_{0}^{ℓ} EAu′(x) v′(x) dx = ∫_{0}^{ℓ} ρ g A v dx + P v(ℓ) . \end{matrix}  (4.11)

Le problème d’optimisation

Minimiser J(u, A) = u avec les contraintes : Équation 4.11 et ∫_{0}^{ℓ} A(x) dx − V = 0. L’espace dans lequel l’équation est bien posée est par exemple X = {v ∈ H^{1}(0, ℓ)/v(0) = 0} qui est un espace de Hilbert ; le multilplicateur peut donc être pris dans le même espace ; nous préciserons cela plus loin. On peut donc écrire le Lagrangien :

L(u, A, p, λ) = u(l) + ∫_{0}^{ℓ} EAu′(x) p′(x) dx − ∫_{0}^{ℓ} ρ g A p dx − P p(ℓ)  (4.12)

Pour appliquer le théorème, il convient de vérifier que la fonctionnelle et les contraintes sont continument Fréchet dérivable et la regularité par rapport aux contraintes. Les conditions d’optimalité s’écrivent d’abord formellement :

∀w ∈ X \frac{∂L}{∂u}w = 0 ; ∀B ∈ L^{∞}(0, l) \frac{∂L}{∂A}B = 0  (4.13)
∀z ∈ X \frac{∂L}{∂p}z = 0 ; ∀μ ∈ IR \frac{∂L}{∂λ}μ = 0  (4.14)

Ce qui fournit :

∀w ∈ X w(l) + ∫_{0}^{ℓ} EAw′(x) p′(x) dx = o  (4.15)
∀B ∈ L^{∞}(0, l) ∫_{0}^{ℓ} EBu′(x) p′(x) dx − ∫_{0}^{ℓ} ρ g B p dx + λ ∫_{0}^{ℓ} Bdx = 0  (4.16)
∀z ∈ X ∫_{0}^{ℓ} EAu′(x) z′(x) dx − ∫_{0}^{ℓ} ρ g A z dx − P z(ℓ) = 0  (4.17)
∀μ ∈ IR μ[∫_{0}^{ℓ} A(x) dx − V] = 0  (4.18)

La première equation 4.15 est souvent appelée état adjoint comme en automatique ; elle est définie à l’aide de la même forme bilinéaire que l’équation du système 4.17 ; en général on trouve un opérateur adjoint linéarisé. L’équation 4.16 peut se simplifier en mettant B en facteur ; comme l’égalité est vraie pour tout B, on obtient

∀x ∈ (0, ℓ) Eu′(x) p′(x) − ρgp(x) = −λ  (4.19)

Ce qui signifie que la fonction de gauche est en fait constante dans l’intervalle. Pour justifier cette démarche, nous pouvons utiliser un cadre abstrait ; soit la forme bilinéaire qui dépend de A :

a_{A}(u, v) = ∫_{0}^{ℓ} EAu′(x) p′(x) dx  (4.20)

On montre facilement que cette forme est bilinéaire, symétrique, continue, coercitive dans X ; elle dépend de façon linéaire continue de A ∈ L^{∞}(0, l) ; le théorème de Lax-Milgram ([?]) permet de lui associer un opérateur A :

A_{A} : X ⟶ X  (4.21)
u ⟼ A_{A}u  (4.22)

tel que

(A_{A}u, v)_{X×X} = a_{A}(u, v)  (4.23)

Avec les notations du théorème, la contrainte peut alors se préciser à l’aide de la fonctionnelle :

E : X × L^{∞}(o, ℓ) ⟶ V × IR  (4.24)
(u, A) ⟼ E(u, A) = (A_{A}u − f, ∫_{0}^{ℓ} Adx − V)  (4.25)

où f ∈ V est donné par le théorème de Riesz :

(f, z)_{X×X} = ∫_{0}^{ℓ} ρ g A z dx − P z(ℓ)  (4.26)

Comme

∥Au∥_{X} = Sup_{∥v∥≤1}(A_{A}u, v) = Sup_{∥v∥≤1}a_{A}(u, v)

la Fréchet différentiabilité de E est facile à montrer et on a :

E′(u, A)(v, B) = (A_{B}u + A_{A}v, ∫_{0}^{ℓ} Bdx)  (4.27)

La surjectivité de cette dérivée est facile ; pour la deuxième composante à valeur dans IR c’est banal et il y a une infinité de solutions ; pour la première, remarquons que pour g ∈ X, nous devons résoudre en (v, B) :

A_{B}u + A_{A}v = g  (4.28)

Prenons B arbitraire qui satisfasse l’équation de la deuxième composante, il reste une équation en v avec l’opérateur A_{A} qui est inversible ; d’où la surjectivité et donc la régularité de tout point u qui satisfait les contraintes.

Solution explicite

Ce problème très simple peut être résolu explicitement ; voir poly d’optimisation de structures ; voici des solutions graphiques.

4.3.3 Contraintes d’inégalités

Comme dans le cas d’égalité, soient X et Z deux espaces de Banach et F une application Fréchet dérivable : F : X → Z et K = {x; F(x) ≤ 0}; pour que K soit bien défini, Z doit être ordonné ce qui peut se faire avec un cône P dit des éléments positifs ; nous supposerons que ce cône est d’intérieur non vide ; nous dirons ici que x_{0} est dit un point régulier de K si

∃h ∈ X F(x_{0}) + F′(x_{0})h < 0  (4.29)

Exercice 4.4 Vérifier que en dimension finie l’hypothèse de régularité donnée dans le chapitre correspondant implique la régularité ci dessus.

Théorème 4.2 Avec les hypothèses ci-dessus , soit une fonction J continuement Fréchet dérivable,

J : X → IR

si x_{∗} est un minimum local de J dans K et si x_{∗} est un point régulier de K, alors il existe

Fig. 4.2 – Aires optimales.

z′_{∗} ∈ Z′ z′_{∗} ≥ 0 tel que

L(x, z′) = J(x)+ < z′, F(x) >  (4.30)

vérifie

∀h ∈ X \frac{∂L}{∂x}(x_{∗}, z′_{∗})h = 0  (4.31)
\frac{∂L}{∂z′} (x_{∗}, z′_{∗}) ≤ 0  (4.32)

et

< z′_{∗}, F(x_{∗}) >= 0  (4.33)

Un exercice d’application directe est le suivant.

Exercice 4.5 1. On considère la fonctionnelle

\frac{1}{2} ∫_{a}^{b}[y^{′2} − fy]dx;  (4.34)

minimiser avec y(a) = 0 = y(b) y(x_{0}) − y_{0} ≤ 0 Ecrire des conditions d’optimalité.

2. Dans le cas où f est une masse de Dirac résoudre les conditions d’optimalité en discutant suivant la valeur de y_{0}.

3. Extension en plusieurs variables.