L’optimisation en mathématiques

Thèmes abordés

optimisation, mathématiques, optimisation sans contrainte, optimisation avec contraintes, dualité, programme mathématique

Résumé du document

L'optimisation, c'est-à-dire les techniques permettant de chercher les minima ou les maxima de fonctions ou de fonctionnelles intervient dans pratiquement tous les processus de modélisation actuels. Qu'il s'agisse de problèmes directs (ajustement de données, contrôle optimal, résolution des systèmes linéaires par moindres carrés, etc) ou inverses (identification de paramètres), il est rare qu'un problème d'optimisation plus ou moins complexe n'intervienne pas à un stade donné de la modélisation et/ou de la simulation.

Extraits

[...] x Pour tout d D ; f ´tant concave et minor´e sur l'ensemble = x + td : t on a e e inf + = f x x En effet, raisonons par l'absurde, sinon il existerait t > 0 tel que f + td) t on a f + td) f x x f + td) f x x t t et donc f + td) si t ce qui est impossible car α > x Il s'ensuit que inf + = f P. x x x Par suite inf f = inf f Comme P est un polytope donc compact, le minimum est atteint et il l'est en un des points extremaux du polytope. On a le r´sultat sur l'unicit´ de la solution optimale. e e Th´or`me Si C est convexe et f fortement quasi convexe sur C alors ) admet au plus e e une solution optimale. La d´monstration est imm´diate. [...]

[...] e Preuve : Soit x C : on sait que T : 0 i = x). x x Il reste donc ` montrer l'inclusion inverse, c'est-`-dire que T x). a a Posons K = : gi = gi gi x x x x x (car les fonctions gi sont convexes et diff´rentiables) : donc x x K. e Soit d K. [...]

[...] pour cela, soit k compris entre 0 et n 2 ; e e on suppose que les directions d d , dk sont mutuellement conjugu´es. On a alors pour k + 1 : e , Adk+1 = , k+1 + βk dk = , Ag k+1 + βk , Adk = 0 d'apr`s le choix de βk e 13 Pour i [...]

[...] On sait que la condition est satisfaite. Il reste ` montrer la condition 2). Par d´finition du minimum local, il existe un voisinage V de dans a e n R tel que f f ) pour tout x V . Soit h Rn . En utilisant le developpement de Taylor au voisinage de , ` l'ordre deux et la a condition on a : pour t suffisamment petit, f + th) = f ) + t f + t2 ε(t) avec ε continue et limt→0 ε(t) = 0. [...]

[...] Si alors d = est une direction e de descente pour f en x. Le principe des m´thode ` directions de descente est le suivant : e a Choix d'un initial x0 Rn ; ee Initialisation : k 0 ; Arrˆt de l'algorithme si test d'arrˆt v´rifi´ ; e e e e Choix d'une direction de descente dk ; D´termination d'un pas de d´placement λk > 0 le long de dk de mani`re ` ”faire d´croˆ f e e e a e ıtre suffisamment” ; xk+1 = xk + λk dk , k k + 1 et aller en 1. [...]