Optimisation sans contrainte
Optimisation différentiable

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

) est notée || · ||₂ .

L'inégalité

(resp. u < v ) entre deux vecteurs v et w signifie que

(resp. v_i < w_i ) pour tout indice i.

On note

et

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

(resp.

).

L'ensemble des matrices symétriques d'ordre n est noté

et

.

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 :