Transcription of Optimisation sous contraintes
1 Licence de math matiques/Licence d conomieParcours Math- co2015-2016 Optimisation sous contrainteLaurent Guillop Laboratoire de math matiques Jean LerayD partement de math matiques, UFR Sciences et techniquesUniversit de guillope/l3-oscVersion: 2 mars 20201 Table des mati resChapitre 1. Prologue2 Chapitre 2. Optimisation diff rentiable51. Fonctions diff rentiables et diff rentielles52. Optimisation sans contrainte73. Optimisation avec contraintes d galit 114. Optimisation avec contraintes d in galit 26 Chapitre 3. Programmation convexe351. En guise d introduction : la moyenne arithm tico-g om trique352. Parties convexes373. Fonctions convexes384. Convexit et r gularit 445. Fonctions quasi-convexes516. Programmation convexe57 Chapitre 4. Optimisation vectorielle621. Ordres de Pareto et optima622. Scalarisation65 Annexe A. Formes quadratiques681.
2 Matrices sym triques et formes quadratiques682. Formes d finies et hyperboliques693. Formes quadratiques sous contraintes71 Annexe. Bibliographie75 Table des figures76 Annexe. Index77 Index g n ral77 Index des noms782 Table des mati res1 Chapitre 1 Prologue tant donn e une fonctionJ, ditefonction d objectifs,fonction de co ts,fonctiond utilit ou encorefonction de production, valeurs num riques, l Optimisation consisteen la recherche des valeursminimumou demaximum, soit de mani re indiff renci ed extremum,(1)minx EJ(x),maxx EJ(x).ainsi que le ou les points1o la fonctionJatteint ces extremaargminx EJ(x) ={y E,J(y) = minx E(J(x))},argmaxx EJ(x) = argminx E( J(x)).SIJest valeurs vectorielles,i. ,p 1, le probl me 1 garde un sens d squ un ordre (processus de comparaison entre vecteurs) a t choisi. Ce th me, associ l conomiste Pareto, sera abord la fin du variablexest appel e parfoisvariable de choix, au pluriel sixest consid r comme unn-upletx= (x1.)
3 ,xn) E Rno en g n ralEest un domaine (par-tie ouverte connexe), une adh rence d un domaine bord r gulier ou des domaines decourbes, surfaces ou hypersurfaces2. La fonctionsJexprime le r sultat d une production,de charges, de profit, d utilit ,.. Elle est d finie sur un ensembleEdont les l ments,ditsr alisablesouadmissiblesmod lisent desintrants: produits manufactur s, mati respremi res, unit s de travail, capital, charges sociales,.. Le domaine de d finition de lafonctionJest souvent une partie du quadrant{(x1,..,xn),xi = 0,i= 1,..,n}dansles applications tude d un probl me d Optimisation est appel programme, la d nomination depro-grammation tant diversement qualifi e pour signifier un cadre sp cifique, avec ses condi-tions et m thodes particuli res :programmation lin airequand les fonctions l uvresont affines,programmation convexepour des fonctions, ou leurs oppos es, convexes.
4 Tout de suite que la recherche d un minimum pourJest quivalente la recherche d un maximum pour la fonction oppos e Jminx EJ(x) = maxx E( J(x)),maxx EJ(x) = minx E( J(x)).1. Les fonctionsargminetargmaxsont des fonctions valeur dans l ensemble des parties du domainede d finition de la fonction d Les exemples rencontr s suffiront expliquer ces termes : la partieEne sera jamais un ensemblediscret, en bijection dans une partie deZn, ce cours ne s occupant pas de programmation discr Le termeprogrammationne r f re pas la programmation informatique, bien que les ordinateurssoient largement utilis s de nos jours pour r soudre desprogrammes math matiques: il vient de l usagedu motprogrammedans les ann es 1940 par les forces arm es am ricaines pour tablir des horaires deformation et des choix logistiques, que Dantzig, le cr ateur de l algorithme du simplexe en program-mation lin aire tudiait l poque.
5 L emploi du termeprogrammationavait galement un int r t pourd bloquer des cr dits en une poque o la planification devenait une priorit des gouvernements, (math matiques).21. PROLOGUE3 Beaucoup d nonc s ne seront formul s que pour la recherche de minimum. La recherchede bornesinfx EJ(x),supx EJ(x)est diff rente du probl me (1) puisque les bornes nesont pas n cessairement atteintes. Ce cours ne s interrogera pas sur l existence de op-tima : celle-ci provient parfois d un argument de compacit la Bolzano-Weierstrass oude coercivit .. La fonction(x,y,z) x7+ sinhy+ sin(z3+x2)admet un minimum sur la bouleferm e{ (x,y,z) (1,3, ) 3}. La fonction(x,y) R27 x2+ 3y2+ sin2(x+y3)tend vers+ lorsque (x,y) + : elle est coercive. Elle admet un minimum SoitJd finie surE= [0, )parJ(x) = 1/xsix [1, )etJ(x) = EJ(x) = 0,maxx EJ(x) = 1,argmaxJ= [0,1],argminJ= ./Rappelons quelques d finitionsD :SoitJd finie surE valeurs r elles.]]
6 (i) Le pointx0est unminimum strictdeJsiJ(x0)< J(x)pourx E\{x0}.(ii) Le pointx0est unminimum globaldeJsiJ(x0) J(x)pourx E.(iii) Le pointx0est unminimum local( strict) deJs il existe un voisinageVdex0tel queJ(x0) J(x)pourx V( (x0)< J(x)pourx V\{x0}).D :SoientJ,g1,..,gn,h1,..,hpd finies surE valeurs num probl me d Optimisation avec les contraintes d galit gi(x) = 0,i= 1,..,net lescontraintes d in galit hj(x) 0,j= 1,..,pest la recherche du minimum(2)min{J(x) :x E,gi(x) = 0,i= 1,..,n,hj(x) 0,j= 1,..,p}. contrainte d galit g(x) = 0peut s exprimer comme une doublecontrainte d in galit g(x) 0, g(x) 0. Inversement, une contrainte d in galit h(x) 0peut s exprimer comme la contrainte d galit h(x) s= 0apr s introductionde la variable de choix suppl mentaire, ditevariable d cart,ssoumise la contraintes 0. Les contraintes (2) peuvent s exprimer comme une seule contrainte num riqueG(x) = 0avecG(x) =n i=1|gi(x)|+p j=1|hj(x) s2j|qui a l inconv nient d utiliser une fonction non diff rentiable sur l ensemble des pointsadmissiblesG= 0ouG(x) =n i=1gi(x)2+p j=1(hj(x) s2j)2qui a celui d une diff rentielle non r guli re surG= 0(o dGs annule).
7 5 Ces notes sont consacr es donc tudier la recherche de minimum (valeur ou pointl atteignant) telle que pos e de mani re g n rale dans (2) et dont seuls quelques cas par-ticuliers seront abord s : programmes sans ou avec contraintes , fonctionJdiff rentiable,convexe,..L illustration graphique en basse dimension (une ou deux variables de d cision) per-met de pr ciser ou d anticiper certains r sultats analytiques, heuristiques ou approch s :41. PROLOGUEsiJ:E( R2) Rest une fonction de deux variables, on peut consid rer ( ) des lignes de niveau4Lv={J(x,y) =v,(x,y) E}pour un ensemble de valeursv1,..,vN, le grapheGJ={(x,y,J(x,y)) R3,(x,y) E}de la fonction qui est une surfacedansR3,sur lesquels on peut rep rer des extrema, points selle, voire les points courbes de niveau de la fonction d objectifsJ(x,y) =x3+y3 6xysur le carr [ 1,3]2et la surface de son logicielsagepermet ais ment de faire certains trac s ou des calculs alg briquesformels (par ex.)
8 Le d terminant (18)) ; le logicielR(qu on peut appeler d ailleurs partirdesage) est d un usage ais , avec un ensemble riche de biblioth ques en calcul statistiqueet num rique. Ces deux outils, d velopp s par la communaut scientifique, sont librementutilisables, avec des versions sur les diff rents syst mes communs (linux,windows,MacOsnotamment) : utiliser sans mod ration !4. Les courbes de niveau d une fonction de production sont appel esisoquantes, celles d une fonctiond utilit courbes d indiff rencesChapitre 2 Optimisation diff rentiable1. Fonctions diff rentiables et diff rentiellesDans ce chapitre, les fonctions sont toujours suppos es diff rentiables tout ordre. Sifest d finie surU Rnet valeurs r elles, sa diff rentielle enx Uest l applicationlin aire not edfx1f(x+h) =f(x) +dfx(h) + h (h).Cette diff rentielle est repr sent e par le vecteur gradient2 fx= f(x) = ( x1f(x).
9 , xnf(x))avec3dfx(h) =dfx(h1,..,hn) = x1f(x)h1+..+ xnf(x)hn= f(x),h RnLe produit scalaire , Rnest le produit canonique surRn, qui sera le plus souvent not simplement , . En termes matriciels, l expressiondfx(h)s obtient comme le produitmatriciel du vecteur ligne( x1f(x),.., xnf(x))des coordonn es de la formedxfdansla base(dx1,..,dxn), alors que l expression xf,h est le produit scalaireXTYdesdeux vecteurs colonneX,Ydes coordonn es des vecteurs :Soitf:x U( Rn7 f(x) Rdiff rentiable de classeC2. Lamatrice hessienne4 Hess(f)xdefau pointxest la matrice5 Hessxf=( 2ijf(x))= 211f(x).. 21nf(x).. 2n1f(x).. 2nnf(x) des d riv es partielles secondes. Il lui est associ e6la forme quadratiqueh= (h1,..,hn) Rn7 Hess(f)x[h] =n i,j=1 2ijf(x) .. oudxf,df(x),f (x),dxf(x0),Jf(x): les notations varient, parfois sans raison v ritable autreque certaines habitudes, parfois en insistant sur la variable de d rivation ou sur l valuation de la diff ren-tielle en un point.
10 Les m mes variations ont lieu pour la hessienne :Hessxf,Hessf(x),..2. En statistique, le gradient de la log-vraisemblance est appel xfd note la d riv e partielle f On ne confondra pas la matrice hessienne d une fonctionf: U Rn Rde la jacobienneJF(x)d une transformationF:x U Rn7 F(x) = (F1(x),..,Fp(x)) Rpd finie parJF(x) =( xjFi(x)): c est la matrice de la diff rentielledF(x)relativement aux bases canoniques SiF= f, alorsdFs identifie la matrice (sym trique) En statistique, l oppos e de la hessienne de la log-vraisemblance est appel einformation observ la matriceA= (aij)carr e d ordrenet sym trique correspond la forme quadratiqueqA:x Rn7 Ax,x R. Cette correspondance est bijective vu2aij=qA(ei+ej) qA(ei) qA(ej)o la famille(ei)est la base canonique Optimisation DIFF La hessienne de la fonction polynomialeP(x,y) =ax2+ 2bxy+cy2+dx+ey+fest la matrice (ind pendante dex,y)Hess(f)(x,y)= 2(a bb c) Soit`vla forme lin aire repr sent e par le vecteurvsuivant`v(x) = v,x etqAla forme quadratique associ e la matrice sym triqueA.
