Optimisation avec contraintes d'égalité et d'inégalité
Optimisation différentiable

AF1252 v1 Article de référence

Optimisation avec contraintes d'égalité et d'inégalité
Optimisation différentiable

Auteur(s) : Jean Charles GILBERT

Date de publication : 10 avr. 2008 | Read in English

Cet article est réservé aux abonnés

Pour explorer cet article plus en profondeur Consulter l'extrait gratuit

Déjà abonné ?Se connecter

Sommaire
Médias

Présentation

1 - Outils théoriques, concepts algorithmiques

1.1 - Problème à résoudre
1.2 - Conditions d'optimalité
1.3 - Prolégomènes à l'algorithmique

2 - Optimisation sans contrainte

2.1 - Techniques de globalisation

Figure 3 - Règle de Wolfe
2.2 - Méthodes rapidement convergentes
2.3 - Problèmes de moindres-carrés

3 - Optimisation avec contraintes d'égalité et d'inégalité

3.1 - Méthodes newtoniennes
3.2 - Méthodes de points intérieurs

Bibliographie & annexes

Présentation

RÉSUMÉ

Les problèmes d’optimisation différenciable se posent lorsque l’on cherche à déterminer la valeur optimale d’un nombre fini de paramètres, l’optimalité signifiant la minimalité d’un critère donné. Cet article décrit les principaux algorithmes de résolution de ces problèmes, en précisant leur motivation. Ces problèmes de résolution se présentent dans de nombreux domaines de l’ingénieur, mais aussi en science et en économie. Ils se posent parfois en dimension infinie, on cherche alors à déterminer une fonction optimale. Les méthodes numériques actuelles de l’optimisation sont la résultante d‘avancées qui ne cessent de se multiplier et de s’enrichir mutuellement.

Lire cet article issu d'une ressource documentaire complète, actualisée et validée par des comités scientifiques.

Lire l’article

Auteur(s)

Jean Charles GILBERT : Directeur de recherche à l'INRIA (Institut national de recherche en informatique et en automatique)

INTRODUCTION

Cette synthèse raisonnée décrit les principaux algorithmes de résolution des problèmes d'optimisation différentiable et en donne leur motivation. Ces problèmes se posent lorsque l'on cherche à déterminer la valeur optimale d'un nombre fini de paramètres. L'optimalité signifie ici la minimalité d'un critère donné. La différentiabilité supposée des fonctions qui définissent le problème écarte d'emblée de notre propos l'optimisation combinatoire (les paramètres à optimiser ne prennent que des valeurs entières ou discrètes, voir le dossier « Optimisation en nombres entiers » [AF 1 251]) et l'optimisation non lisse (les fonctions ont des irrégularités, voir le dossier « Optimisation et convexité » [AF 1 253]).

Les problèmes d'optimisation se présentent dans de nombreux domaines de l'ingénieur, ainsi qu'en science et en économie, souvent après avoir conduit à leur terme les étapes de simulation. Il arrive souvent que ces problèmes se posent en dimension infinie, c'est-à-dire que l'on cherche une fonction optimale plutôt qu'un nombre fini de paramètres optimaux. Il faut alors passer par une phase de discrétisation (en espace, en temps) pour retrouver le cadre qui est le nôtre et se ramener ainsi à un problème qui peut être résolu sur ordinateur. La transcription directe des problèmes de commande optimale suit une telle procédure de discrétisation. D'autres exemples sont décrits dans le dossier « Optimisation continue » [S 7 210].

Les méthodes numériques de l'optimisation ont principalement été développées après la seconde guerre mondiale, en parallèle avec l'amélioration des ordinateurs, et n'ont cessé depuis de s'enrichir. En optimisation non linéaire, on peut ainsi distinguer plusieurs vagues : méthodes de pénalisation, méthode du lagrangien augmenté (1958), méthodes de quasi-Newton (1959), méthodes newtoniennes ou SQP (1976), algorithmes de points intérieurs (1984). Une vague n'efface pas la précédente mais permet d'apporter de meilleures réponses à certaines classes de problèmes, comme ce fut le cas pour les méthodes de points intérieurs en optimisation semi-définie positive (SDP). Une attention particulière est portée aux algorithmes pouvant traiter les problèmes de grande taille, ceux qui se présentent dans les applications.

La norme euclidienne (ou $l_{2}$ ) est notée || · ||₂ .

L'inégalité $v \leq w$ (resp. u < v ) entre deux vecteurs v et w signifie que $v_{i} \leq w_{i}$ (resp. v_i < w_i ) pour tout indice i.

On note $R (M)$ et $N (M)$ l'image et le noyau d'une matrice M.

Pour indiquer qu'une matrice carrée M est symétrique semi-définie positive (resp. définie positive), on note $M ≽ 0$ (resp. $M ≻ 0$ ).

L'ensemble des matrices symétriques d'ordre n est noté $S^{n}, S_{+}^{n} := {M \in S^{n} : M ≽ 0}$ et $S_{+ +}^{n} := {M \in S^{n} : M ≻ 0}$ .

Une fonction f est dite de classe C ^m,α si elle est m fois différentiable et si sa dérivée m-ième vérifie pour une constante C et pour tout x et y :

‖ f^{(m)} (y) - f^{(m)} (x) ‖ \leq C {‖ y - x ‖}^{α} .

Cet article est réservé aux abonnés.
Il vous reste 95 % à découvrir.

Pour explorer cet article Consulter l'extrait gratuit

Déjà abonné ? Se connecter

DOI (Digital Object Identifier)

https://doi.org/10.51257/a-v1-af1252

Lecture en cours
Présentation

Page
suivante

Outils théoriques, concepts algorithmiques

Article inclus dans l'offre

"Mathématiques"

(170 articles)

Une base complète d’articles

Actualisée et enrichie d’articles validés par nos comités scientifiques.

Des contenus enrichis

Quiz, médias, tableaux, formules, vidéos, etc.

Des modules pratiques

Opérationnels et didactiques, pour garantir l'acquisition des compétences transverses.

Des avantages inclus

Un ensemble de services exclusifs en complément des ressources.

Voir l'offre

3. Optimisation avec contraintes d'égalité et d'inégalité

Nous présentons dans ce paragraphe deux classes d'algorithmes qui peuvent résoudre des problèmes avec contraintes, tels que :

(P_{EI}) {\begin{cases} \min f (x) \\ c_{i} (x) = 0, i \in E \\ c_{i} (x) \leq 0, i \in I . \end{cases}

Les notations ont été précisées dans le paragraphe 1.1 . Il s'agit d'une part des algorithmes newtoniens, qui s'attaquent directement aux conditions d'optimalité, et d'autre part des méthodes de points intérieurs, qui peuvent être vues comme des méthodes de pénalisation.

La difficulté principale de (P_E I ) ne réside pas tant dans la présence des contraintes d'égalité (on reste dans le domaine de l'analyse), mais dans celle des inégalités. Celles-ci introduisent un aspect combinatoire dans (P_E I ), qui rend le calcul de sa solution très difficile. En effet, on ne sait pas quelles sont les contraintes d'inégalité actives en la solution et il y a $2^{m_{I}}$ manières de réaliser cela (m _I :≥ | I |). Il se fait que les algorithmes éprouvent des difficultés...

Cet article est réservé aux abonnés.
Il vous reste 93 % à découvrir.