Optimisation sous contraintes

3 Optimisation avec contraintes d’égalité11 4 Optimisation avec contraintes d’inégalité26 Chapitre 3 Programmation convexe35 1 En guise d’introduction : la moyenne arithmético-géométrique35 2 Parties convexes37 3 Fonctions convexes38 4 Convexité et régularité44 5 Fonctions quasi-convexes51 6 Programmation convexe57

Clément Rau Laboratoire de Mathématiques de Toulouse

Optimisation sans contraintes Optimisation sous contraintes Exemple 2a Un individu consomme deux biens X et Y en quantités x et y aux prix respectifs de 2 unités monétaire et 1 unité monétaire Sa satisfaction est exprimée par sa fonction d’utilité Cette dernière dépend des quantités consommées des deux biens Elle est de la forme

Optimisation linéaire - EPFL

Optimisation linéaire Il est toujours possible d’écrire le problème sous la forme suivante : min x∈Rn cTx sous contraintes Ax = b, x ≥ 0 • c ∈ Rn, n > 0 • A ∈ Rm×n, b ∈ Rm, m ≥ 0

M´ethodes d’Optimisation

La programmation math´ematique recouvre un ensemble de techniques d’optimisation sous contraintes qui permettent de d´eterminer dans quelles conditions on peut rendre maximum ou minimum une fonction objectif Z(X j) de nvariables X j li´ees par mrelations ou contraintes H i(X j) ≤0

Optimisation sous contrainte de fiabilité d une coque imparfaite

Optimisation sous contrainte de abilit e d une coque IFMA, EA 3867, Laboratoire de Mécanique et Ingénieries, BP 10448, F cgsont des contraintes déterministes ne mettant pas en jeu l

Introduction à la dualité - EPFL

Exemple d’optimisation min x∈R2 2x1 +x2 sous contraintes 1−x1 −x2 = 0 x1 ≥ 0 x2 ≥ 0 Solution optimale : (0,1) Coût optimal : 1 Relaxons la contrainte 1−x1 −x2 =0 Introduction a la dualit` e – p 7/40´

[PDF] OPTIMISATION CONTRAINTE

[PDF] OPTIMISATION SOUS CONTRAINTES

[PDF] Optimisation sous contraintes - Laboratoire de Mathématiques Jean

[PDF] Séquence 13 Optimisation de la gestion et de l 'utilisation de l 'énergie

[PDF] Les concepts normatifs : surplus et optimalité de Pareto

[PDF] 04 - LA METHODE DU COÛT MARGINAL Objectif(s - IUT en Ligne

[PDF] Annexe 7 guide des épreuves facultatives 2017 - Ministère de l

[PDF] Annexe 7 guide des épreuves facultatives 2017 - Ministère de l

[PDF] Les options arts plastiques au lycée Saint-Exupéry de Saint - sepia

[PDF] Annexe 7 guide des épreuves facultatives 2017 - Ministère de l

[PDF] Création et innovation technologiques - Educationgouv - Ministère

[PDF] Annexe 7 guide des épreuves facultatives 2017 - Ministère de l

[PDF] Les SES et la filière ES

[PDF] Annexe 7 guide des épreuves facultatives 2017 - Ministère de l

[PDF] bac musique option facultative a propos de l 'epreuve vocale - Lyon

Licence de mathématiques/Licence d"économie

Parcours Math-Éco

2015-2016

Optimisation sous contrainte

Laurent Guillopé

Laboratoire de mathématiques Jean Leray

Département de mathématiques, UFR Sciences et techniques

Université de Nantes

www.math.sciences.univ-nantes.fr/˜guillope/l3-oscVersion: 2 mars 2020 1

Table des matières

Chapitre 1. Prologue

Chapitre 2. Optimisation différentiable

1. Fonctions différentiables et différentielles

2. Optimisation sans contrainte

3. Optimisation avec contraintes d"égalité

4. Optimisation avec contraintes d"inégalité

Chapitre 3. Programmation convexe

1. En guise d"introduction : la moyenne arithmético-géométrique

2. Parties convexes

3. Fonctions convexes

4. Convexité et régularité

5. Fonctions quasi-convexes

6. Programmation convexe

Chapitre 4. Optimisation vectorielle

1. Ordres de Pareto et optima

2. Scalarisation

Annexe A. Formes quadratiques

1. Matrices symétriques et formes quadratiques

2. Formes définies et hyperboliques

3. Formes quadratiques sous contraintes

Annexe. Bibliographie

Table des figures

Annexe. Index

Index général

Index des noms

78
2

Table des matières 1

Chapitre 1

Prologue

Étant donnée une fonctionJ, ditefonction d"objectifs,fonction de coûts,fonction d"utilitéou encorefonction de production, à valeurs numériques, l"optimisation consiste en la recherche des valeursminimumou demaximum, soit de manière indifférenciée d"extremum, (1)minx2EJ(x);maxx2EJ(x): ainsi que le ou les points

1où la fonctionJatteint ces extrema

argmin x2EJ(x) =fy2E;J(y) = minx2E(J(x))g;argmaxx2EJ(x) = argminx2E(J(x)): SIJest à valeurs vectorielles,i. e.dansRp;p1, le problème1 garde un sens dès

qu"un ordre (processus de comparaison entre vecteurs) a été choisi. Ce thème, associé à

l"économiste Pareto, sera abordé à la fin du cous. La variablexest appelée parfoisvariable de choix, au pluriel sixest considéré comme unn-upletx= (x1;:::;xn)2ERnoù en généralEest un domaine (par- tie ouverte connexe), une adhérence d"un domaine à bord régulier ou des domaines de courbes, surfaces ou hypersurfaces

2. 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ères premières, unités de travail, capital, charges sociales,... Le domaine de définition de la fonctionJest souvent une partie du quadrantf(x1;:::;xn);xi= 0;i= 1;:::;ngdans les applications économiques. L"é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"oeuvre sont affines,programmation convexepour des fonctions, ou leurs opposées, convexes,...3. Remarquons tout de suite que la recherche d"un minimum pourJest équivalente à la recherche d"un maximum pour la fonction opposéeJ min

x2EJ(x) =maxx2E(J(x));maxx2EJ(x) =minx2E(J(x)):1. Les fonctionsargminetargmaxsont des fonctions à valeur dans l"ensemble des parties du domaine

de définition de la fonction d"objectifs.

2. Les exemples rencontrés suffiront à expliquer ces termes : la partieEne sera jamais un ensemble

discret, en bijection dans une partie deZn, ce cours ne s"occupant pas de programmation discrète.

3. Le termeprogrammationne réfère pas à la programmation informatique, bien que les ordinateurs

soient largement utilisés de nos jours pour résoudre desprogrammes mathématiques: il vient de l"usage

du motprogrammedans les années 1940 par les forces armées américaines pour établir des horaires de

formation et des choix logistiques, que Dantzig, le créateur de l"algorithme du simplexe en program-

mation linéaire étudiait à l"époque. L"emploi du termeprogrammationavait également un intérêt pour

débloquer des crédits en une époque où la planification devenait une priorité des gouvernements,cf.

1. PROLOGUE 3

Beaucoup d"énoncés ne seront formulés que pour la recherche de minimum. La recherche de bornesinfx2EJ(x);supx2EJ(x)est différente du problème (1) puisque les bornes ne sont 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 ou de coercivité. .Exemples1.1. 1.1 .1 La fonction (x;y;z)!x7+sinhy+sin(z3+x2)admet un minimum sur la boule ferméefk(x;y;z)(1;3;)k 3g. 1.1 .2 La fonction (x;y)2R27!x2+ 3y2+ sin2(x+y3)tend vers+1lorsque k(x;y)k !+1: elle est coercive. Elle admet un minimum surR2. 1.1 .3 Soit Jdéfinie surE= [0;1)parJ(x) = 1=xsix2[1;1)etJ(x) = 1sinon. Alors min x2EJ(x) = 0;maxx2EJ(x) = 1;argmaxJ= [0;1];argminJ=;:/

Rappelons quelques définitions

Définition1.1:SoitJdéfinie surEà valeurs réelles. (i) L ep ointx0est unminimum strictdeJsiJ(x0)< J(x)pourx2En fx0g. (ii) L ep ointx0est unminimum globaldeJsiJ(x0)J(x)pourx2E. (iii) L ep ointx0est unminimum local(resp.local strict) deJs"il existe un voisinage Vdex0tel queJ(x0)J(x)pourx2V(resp.J(x0)< J(x)pourx2Vnfx0g). Définition1.2:SoientJ;g1;:::;gn;h1;:::;hpdéfinies surEà valeurs numériques. Le problème d"optimisation avec les contraintes d"égalitégi(x) = 0;i= 1;:::;net les contraintes d"inégalitéhj(x)0;j= 1;:::;pest la recherche du minimum (2)minfJ(x) :x2E;gi(x) = 0;i= 1;:::;n;hj(x)0;j= 1;:::;pg:

4Remarque1.1.La contrainte d"égalitég(x) = 0peut s"exprimer comme une double

contrainte 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 introduction de la variable de choix supplémentaire, ditevariable d"écart,ssoumise à la contrainte s0. Les contraintes (2) peuvent s"exprimer comme une seule contrainte numérique

G(x) = 0avec

G(x) =nX

i=1jgi(x)j+pX j=1jhj(x)s2jj qui a l"inconvénient d"utiliser une fonction non différentiable sur l"ensemble des points admissiblesG= 0ou

G(x) =nX

i=1g i(x)2+pX j=1(hj(x)s2j)2 qui a celui d"une différentielle non régulière surG= 0(oùdGs"annule).5 Ces notes sont consacrées donc à étudier la recherche de minimum (valeur ou point l"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 :

4 1. PROLOGUE

siJ:E(R2)!Rest une fonction de deux variables, on peut considérer (cf.Figure I.1 des lignes de niv eau

4Lv=fJ(x;y) =v;(x;y)2Egpour un ensemble de valeurs

1;:::;vN,

le graphe GJ=f(x;y;J(x;y))2R3;(x;y)2Egde la fonction qui est une surface dansR3,

sur lesquels on peut repérer des extrema, points selle, voire les points critiques.Figure I.1.Les courbes de niveau de la fonction d"objectifsJ(x;y) =

3+y36xysur le carré[1;3]2et la surface de son graphe.

Le logicielsagepermet aisément de faire certains tracés ou des calculs algébriques formels (par ex. le déterminant ( 18 )); le logicielR(qu"on peut appeler d"ailleurs à partir desage) est d"un usage aisé, avec un ensemble riche de bibliothèques en calcul statistique et numérique. Ces deux outils, développés par la communauté scientifique, sont librement utilisables, avec des versions sur les différents systèmes communs (linux,windows,MacOs

notamment) : à utiliser sans modération!4. Les courbes de niveau d"une fonction de production sont appeléesisoquantes, celles d"une fonction

d"utilitécourbes d"indifférences

Chapitre 2

Optimisation différentiable

1. Fonctions différentiables et différentielles

Dans ce chapitre, les fonctions sont toujours supposées différentiables à tout ordre. Si fest définie surURnet à valeurs réelles, sa différentielle enx2Uest l"application linéaire notéedfx1 f(x+h) =f(x) +dfx(h) +khk"(h): Cette différentielle est représentée par le vecteur gradient 2 rfx=rf(x) = (@x1f(x);:::;@xnf(x)) avec 3 df x(h) =dfx(h1;:::;hn) =@x1f(x)h1+:::+@xnf(x)hn=hrf(x);hiRn Le produit scalaireh;iRnest le produit canonique surRn, qui sera le plus souvent noté simplementh;i. En termes matriciels, l"expressiondfx(h)s"obtient comme le produit matriciel du vecteur ligne(@x1f(x);:::;@xnf(x))des coordonnées de la formedxfdans la base(dx1;:::;dxn), alors que l"expressionhrxf;hiest le produit scalaireXTYdes deux vecteurs colonneX;Ydes coordonnées des vecteursrxfethresp. Définition2.1:Soitf:x2U(Rn7!f(x)2Rdifférentiable de classeC2. La matrice hessienne

4Hess(f)xdefau pointxest la matrice5

Hess xf=@2ijf(x)=0

211f(x)::: @21nf(x)......

2n1f(x)::: @2nnf(x)1

A des dérivées partielles secondes. Il lui est associée

6la forme quadratique

h= (h1;:::;hn)2Rn7!Hess(f)x[h] =nX i;j=1@

2ijf(x)hihj

.Exemples2.1.1. ... oudxf,df(x),f0(x);dxf(x0),Jf(x): les notations varient, parfois sans raison véritable autre

que certaines habitudes, parfois en insistant sur la variable de dérivation ou sur l"évaluation de la différen-

tielle en un point. Les mêmes variations ont lieu pour la hessienne :Hessxf,Hessf(x),...

2. En statistique, le gradient de la log-vraisemblance est appelé lescore.

3.@xfdénote la dérivée partielle@f@x

4. On ne confondra pas la matrice hessienne d"une fonctionf:2URn!Rde la jacobienne

JF(x)d"une transformationF:x2URn7!F(x) = (F1(x);:::;Fp(x))2Rpdéfinie parJF(x) =@xjFi(x): c"est la matrice de la différentielledF(x)relativement aux bases canoniques deRnetRp

resp.. SiF=rf, alorsdFs"identifie à la matrice (symétrique)Hessf.

5. En statistique, l"opposée de la hessienne de la log-vraisemblance est appeléeinformation observée.

6. À la matriceA= (aij)carrée d"ordrenet symétrique correspond la forme quadratiqueqA:x2

R n7! hAx;xi 2R. Cette correspondance est bijective vu2aij=qA(ei+ej)qA(ei)qA(ej)où la famille (ei)est la base canonique deRn. 5

6 2. OPTIMISATION DIFFÉRENTIABLE

2.1 .1 La hessienne de la fonction p olynomialeP(x;y) =ax2+2bxy+cy2+dx+ey+f est la matrice (indépendante dex;y)

Hess(f)(x;y)= 2a b

b c 2.1 .2 Soit `vla forme linéaire représentée par le vecteurvsuivant`v(x) =hv;xiet q Ala forme quadratique associée à la matrice symétriqueA. r`v(x) =v;Hess`v(x) = 0;rqA(x) =Ax;HessqA(x) = 2A: On établit ces formules soit en prenant des coordonnées et effectuant le calcul de dérivées partielles, soit en identifiant les termes développements de`v(x+h)et q A(x+h)à ceux du développement de Taylor (3) rappelé ci-dessous./

Rappelons la formule de Taylor à l"ordre 2 :

Proposition2.1:Soitx2Rn,Uxun ouvert contenantxetf:Ux7!Rdifféren- tiable. Alors (3)f(x+h) =f(x) +hrfx;hi+Hessfx[h]2 +khk2"(h); x+h2Ux avec"(h)!0lorsqueh!0. SoitH:R!Rstrictement croissante et :V(Rn)!Rnune bijection deV surU= (V). SieJ=HJ, les deux programmesminv2VeJ(v)etminu2UJ(u) sont équivalents, avecminu2UJ(u) = minv2VeJ(v)etargminJ= (argmineJ). Comme exemple, on peut citer diverses fonctions dérivées de la fonction de Cobb-Douglas :Q iuii,P iiloguietP iivi. Le lemme suivant sert à établir l"équivalence de certains critères d"optimisation vis a vis de ces compositions de fonctions.

Lemme2.1:SoitH:R!R, :V(Rm)!Rn,J:U(Rn)!R,eJ=HJ,

ep2Vetp= (ep). Alors d epeJ=H0(J(p))dpJdep r eJ(ep) =H0(J(p))T0(ep)[rJ(p)]; Hess epeJ=H00(J(p))(dpJdep)2+H0(J(p))HesspJ[dep] +J0(p)(d00ep[ev]): En particulier, sip= (ep)est un point critique deJ,epest aussi un point critique deeJ avec relation entre les hessiennes Hess epeJ[ev] =H0(J(p))HesspJ[dep(ev)];ev2Rn de telle sorte que siH;sont des applications inversibles au voisinage deej=J(p);ep resp., alors les hessiennesSign(H0(J(p))HessepeJetHesspJont même indice. Démonstration.La matrice hessienne et le gradient sont déterminés par le développe- ment de Taylor à l"ordre 2. Ainsi (ep+ev) = (ep) +dep(ev) +d00ep[ev]2 +o(kevk2)

2. OPTIMISATION SANS CONTRAINTE 7

puis (J)(ep+ev) =J (ep) +dep(ev) +d00ep[ev]2 +o(kevk2) =J((ep)) +J0((ep)) d ep(ev) +d00ep[ev]2 +HesspJ[dep(ev)]2 +o(kevk2) et donc e

J(ep+ev) =h(J(ep+ev))

J((ep)) +J0((ep))

d ep(ev) +d00ep[ev]2 +HesspJ[dep(ev)]2 +o(kevk2) eJ(ep) +h0(J(p)) J 0(p) d ep(ev) +d00ep[ev]2 +HesspJ[dep(ev)]2 h00(J(p))[J0(p)[dep(ev)]]22 +o(kevk2) eJ(ep) +h0(J(p))J0(p)(dep(ev)) h0(J(p))J0(p)d00ep[ev] + HesspJ[dep(ev)]+h00(J(p))[J0(p)(dep(ev))22 +o(kevk2) et donc les formules sur le gradient et le hessien de la fonction eJ.

2. Optimisation sans contrainte

Un problème d"optimisation sans contrainteconsidéré ici est du type inf x2 J(x) où est un ouvert7d"un espace vectoriel, en général de dimension finie, etJune fonction (au moins continue, de classeC1en général). Définition2.2:SoitJ:U(Rn)7!Rdifférentiable. Le pointx2Uest unpoint critiquedeJsidJx= 0ou de manière équivalenterJ(x) = 0. Théorème2.1 (Euler-Fermat):SiJ:U(Rn)!Rest minimum enx2U, alorsx est point critique deJ. Démonstration.Sixest minimum deJ, alors, pourh2RNett >0avecthassez petit

J(x+th)J(x)t

0; d"où dJ x(h) +khk"(th)0 et doncdJx(h)0en faisantt!0. S"ensuit aussidJx(h) =dJx(h)0et donc dJ x(h) = 0pour tout vecteurh, soit la nullité de la différentielledJx. .Exemples2.2.7. L"ouvert peut être défini par une fonctionJsous la forme =fF >0g: cette inégalité,

" ouverte », n"est pas considérée comme une contrainte, au contraire des inégalités larges des sections

suivantes.

8 2. OPTIMISATION DIFFÉRENTIABLE

2.2 .1 La fonction Jdéfinie parJ(x;y) =x2y2a0comme point critique : l"origine

0est un minimum global strict deJ+, alors queJn"a ni minimum, ni maximum

(local ou global). 2.2 .2 La fonction J(x;y) = cosx+y2a comme gradientrJ(x;y) = (sinx;2y): ses

points critiques sont les(k;0)pourk2Z.Figure II.1.Les courbes de niveau de la fonction d"objectifsJ(x;y) =

cosx+y2.

Théorème2.2:SoitJ:U(Rn)!Rcritique enx.

(i) Sixest un minimum (maximum resp.) local deJ, la hessienneHess(J)xest une forme quadratique positive

8(négative resp.).

(ii) Si la hessienneHess(J)xest une forme quadratique définie positive (négative resp.) etxpoint critique deJ, alorsxest un minimum (maximum resp.) local deJ. .Exemples2.3. 2.3 .1 Soit la fonction d"ob jectifJdéfinie parJ(x;y) =x2y4: avec (unique) point critiquex= (0;0)la fonctionJa au pointx= (0;0)a comme hessienne

HessJ(x) =1 0

01 , définie positive pourJ+et de signature(1;1)pourJ. Le pointxest minimum global deJ+, point selle pourJ. 2.3 .2 Reprenan tla fonction J(x;y) = cosx+y2de l"exemple précédent, on a au voisinage demk= (k;0)aveck2Z,

J(k+u;y) =y2+ (1)kcosu= (1)k+y2(1)ku22

+ (u2+y2)"(juj+jyj): Sikest impair, le pointmkest un minimum local strict, alors que sikest pair, c"est un point de minimum local le long de la verticalef(k;y);y2("1;"1)g et de maximum local le long de l"horizontalef(k+u;0);u2("2;"2)g,i. e.quotesdbs_dbs18.pdfusesText_24