Theorie D'optimisation

En mathematiques, l'optimisation est l'etude des problemes qui sont de la forme :

Etant donne : une fonction d'un ensemble A dans l'ensemble des nombre

reels

Rechercher : un element x0 de A tel que pour tous les x en A

(<< maximisation >>) ou tel que pour tous les x en A (<< minimisation >>).

Une telle formulation est parfois appelee programme mathematique (terme non directement lie a

la programmation informatique). Plusieurs problemes theoriques et pratiques peuvent etre etudies dans cet

encadrement general.

Etant donne que la maximisation de f est equivalente a la minimisation de - f, une methode pour

trouver le minimum (ou le maximum) suffit a resoudre le probleme d'optimisation.

Il arrive frequemment que A soit un sous-ensemble donne de l'espace euclidien , souvent

specifie par un ensemble de contraintes, des egalites ou des inegalites que les elements de A doivent

satisfaire. Les elements de A sont appelees les solutions admissibles et la fonction f est appelee la fonction

objectif. Une solution possible qui maximise (ou minimise, si c'est le but) la fonction objectif est appelee

une solution optimale.

Un minimum local x * est defini comme un point tel qu'il existe un voisinage V de x * tel que pour

tout , ; c'est-a-dire que dans une voisinage de x * toutes les valeurs de la

fonction sont plus grandes que la valeur en ce point.

Lorsque A est un sous-ensemble de , ou plus generalement un espace vectoriel norme, cela

s'ecrit : pour un ? > 0 donne et tous les x tels que on a . Les

maximums locaux sont definis semblablement. En general, il est facile de trouver les minimums

(maximums) locaux, qui sont parfois nombreux. Pour verifier que la solution trouvee est un minimum

(maximum) global, il est necessaire de recourir a des connaissances additionnelles sur le probleme (par

exemple la convexite de la fonction objectif).

Il n'existe pas de methode connue assurant quel que soit le type de fonction que l'on trouvera un

extremum global.

Notation

Les problemes d'optimisation sont souvent exprimes avec une notation speciale. Voici quelques

exemples :

Ex. 1.

On cherche la valeur minimale pour l'expression x2 + 1, ou x s'etend sur les nombres reels . La

valeur minimale dans ce cas est 1, s'occasionnant a x = 0.

Ex. 2.

On cherche la valeur maximale pour l'expression 2x, ou x s'etend sur les reels. Dans ce cas, il n'y

a pas de tel maximum puisque l'expression n'est pas bornee, donc la reponse est << l'infini >> ou

<< indefini >>.

Ex.3.

On cherche la ou les valeurs de x dans l'intervalle qui minimise l'expression x2 + 1.

(La valeur minimale veritable de cette expression n'est pas importante.) Dans ce cas, la reponse est x = -

1.

Ex. 4.

On cherche la ou les paires (x,y) qui maximisent la valeur de l'expression xcos(y), avec la

contrainte ajoutee que x ne peut exceder 5. (A nouveau, la valeur maximale veritable de l'expression n'est

pas importante.) Dans ce cas, les solutions sont les paires de la forme (5,2k?) et ( - 5,(2k + 1)?), ou k

s'etend sur tous les entiers.

Methodes pour resoudre les problemes d'optimisation

Pour les fonctions derivables deux fois, des problemes sans contraintes peuvent etre resolus en

trouvant les lieux ou le gradient de la fonction est 0 (par exemple les points stationnaires) et en utilisant la

matrice hessienne pour classer le type de point. Si le hessien est defini positif, le point est un minimum

local ; s'il est un defini negatif, un maximum local et s'il est indefini c'est un << point-col >>.

Si la fonction est convexe sur l'ensemble des solutions admissibles (definies par les contraintes)

alors tout minimum local est aussi un minimum global. Des techniques numeriques robustes et rapides

existent pour optimiser des fonctions convexes doublement derivables. En dehors de ces fonctions, des

techniques moins efficaces doivent etre employees.

Les problemes a contraintes peuvent souvent etre transformes en des problemes sans contraintes a

l'aide du multiplicateur de Lagrange : cette methode revient en effet a introduire des penalites croissantes

a mesure qu'on se rapproche des contraintes..

Le procede pour chercher la solution d'un probleme d'optimisation parcourt les etapes:

1. la choix d'un point d'initialisation x0

2. la recherche du point optimal x* par l'effectuassions