Optimisation Quadratique Optimisation quadratique avec contraintes Méthodes On veut optimiser une fonction sous des contraintes • Si à l'optimum aucune Cette méthode marche très bien pour des contraintes linéaires • Peut résoudre
Previous PDF | Next PDF |
[PDF] Optimisation sous contraintes - Le laboratoire de Mathématiques
Optimisation sous contrainte Formes quadratiques sous contraintes tions et méthodes particulières : programmation linéaire quand les fonctions à l'œuvre
[PDF] eriques pour loptimisation avec contraintes
Optimisation Quadratique Optimisation quadratique avec contraintes Méthodes On veut optimiser une fonction sous des contraintes • Si à l'optimum aucune Cette méthode marche très bien pour des contraintes linéaires • Peut résoudre
[PDF] Optimisation linéaire & convexité
I 1 5 Un problème d'optimisation linéaire en dimension supérieure II 3 4 Minimisation d'une fonction quadratique généralisée sans contrainte 52 On récrit le sous-système des contraintes d'égalité sous la forme (on choisit l'ordre des
[PDF] Introduction `a loptimisation
optimisation linéaire quadratique f est une fonction convexe quadratique: f(x) = 1 2 On cherche donc `a maximiser la fonction abc sous la contrainte 2(ab+
[PDF] Techniques doptimisation
Programmation quadratique : coût quadratique et contraintes linéaires (QP) x* ∈X int intérieur à la contrainte → contrainte inactive 0*x 1x sous 1xmin 2 Rx
[PDF] COURS OPTIMISATION Cours en Master M1 SITN Ionel Sorin
3 1 2 Cas particulier des fonctions quadratiques 27 4 2 Optimisation sous contraintes d'inégalités 41 Dans la cas particulier m = 1 une fonction linéaire générale peut être écrite sous la forme f(x) =
[PDF] Optimisation non linéaire: Applications - GERAD
Optimisation quadratique ▷ Cas particulier de l'optimisation non linéaire sous contraintes linéaires ▷ Contraintes linéaires ▷ Objectif : Fonction quadratique
[PDF] 34 Optimisation sous contraintes
linéaire" Ces problèmes sont souvent résolus numériquement à l'aide de l' algorithme de Dantzig, inventé vers 1950 — Programmation quadratique Avec le
[PDF] Optimisation
3 2 4 Méthode de relaxation comme récurrence linéaire 4 3 1 Minimisation d' une fonction quadratique convexe sous des contraintes linéaires 75
[PDF] optimisation convexe pdf
[PDF] fonction convexe plusieurs variables
[PDF] modélisation et simulation d'un moteur ? courant continu matlab
[PDF] modélisation mcc
[PDF] simulation mcc simulink
[PDF] asservissement et regulation de vitesse d'un moteur a courant continu
[PDF] modélisation d'un moteur ? courant continu
[PDF] equation differentielle moteur courant continu
[PDF] schéma bloc moteur ? courant continu
[PDF] commande pid d'un moteur ? courant continu pdf
[PDF] modélisation machine asynchrone simulink
[PDF] onduleur triphasé matlab
[PDF] cours de modélisation financière sous excel
[PDF] modélisation financière pdf
![[PDF] eriques pour loptimisation avec contraintes [PDF] eriques pour loptimisation avec contraintes](https://pdfprof.com/Listes/18/9646-18oq3.pdf.pdf.jpg)
Master MIMSE - Année 2
Optimisation Quadratique
Optimisation quadratique avec contraintes
Méthodes numériques
DRAFT -- DRAFT -- DRAFT -- DRAFT -- DRAFT -- 2Algorithmes "extérieurs"
•On veut optimiser une fonction sous des contraintes. •Si à l'optimum aucune contrainte n'est active, la solution au- rait pu être trouvée au moyen d'une méthode d'optimisation sans contrainte. •Sinon, à l'optimum une ou plusieurs contraintes sont actives. •PL : identifier les contraintes actives mène à l'optimum. •en général "dans un coin" ou facette optimale. •PNL : optimum dans un coin, sur toute une "facette" ou aumilieu d'une facette. •Algos "extérieurs" qui "se baladent" le long de la frontièredu domaine, •qui "jonglent" avec l'ensemble actif (des contraintes actives)J(x) ={j|gj(x) = 0}.
DRAFT -- DRAFT -- DRAFT -- DRAFT -- DRAFT -- 3Gradient projeté
•Cette méthode est une méthode qui combine deux idées : -une direction de descente (plus forte pente) -une direction tangentielle (rester à la frontière). •Soit un pointxet?gjles gradients des fonctions des con- traintesactivesenx. •On cherche une direction de descente orthogonale aux?gj, •Projection de-?fsur l'orthogonal deS=V ect{?gj}. DRAFT -- DRAFT -- DRAFT -- DRAFT -- DRAFT -- 4Formule de projection
•En un pointxsur la frontière, •une directionsdansSest de la forme s=? j?J(x)μ j?gj(x) =Nμ, avec N=((γ1...γl
où les j=?gj(x) ||?gj(x)||. •Soitg=?f(x) •g=r+savecs?Setr?O(S). •On utilisera-rcomme direction. DRAFT -- DRAFT -- DRAFT -- DRAFT -- DRAFT -- 5Projection 2
•On ag=r+Nμ •doncNTg=NTr+NTNμ •On suppose que lesγsont linéairement indépendants •(sinon on aurait sélectionné une base deS) •alorsNTNest inversible ! •doncμ= (NTN)-1NTg •d'où r= (I-N(NTN)-1NT)g. •rest tangente (dansO(S)) •direction de descente. •Sir= 0? •Point de KKT DRAFT -- DRAFT -- DRAFT -- DRAFT -- DRAFT -- 6Algorithme
1. (Initialisation)X1un point faisable,
2. (Itération k) Calculerg=?f(Xk)
3. Calculerdkla projection surO(Sk)(si pas de contraintes ac-
tives, on garde le gradient)4. Sidk= 0une relation de KKT est vérifiée
(a) Si lesμisatisfont KKT : fini, (b) Sinon prendre unμide mauvais signe, enleverideJ(x) et réitérer.5. Maximiser le long de la direction, tout en restant faisable,
6.Xk+1
7. Réitérer
8. Sion sortdudomainefaisable,calculerunedirectionderetour
(a)wvecteur du viol des contraintes, (b) direction de retours=N(NTN)-1w DRAFT -- DRAFT -- DRAFT -- DRAFT -- DRAFT -- 7Remarques
•Cette méthode marche très bien pour des contraintes linéaires. •Peut résoudre un PL de façon analogue au simplexe. •Mais peut aussi trouver l'optimum pour une fonction objectif non linéaire. •Appliquée à des contraintes quadratiques, marche encore as- sez bien •mais est pénalisée par les "sauts de faisabilité" •en fait "linéarise" par morceaux la frontière •Le calcul de(NTN)-1à chaque itération, est une faiblesse de la méthode, •en fait on ajoute ou on retranchedes hyperplans de l'ensemble actif •Il existe des relations de récurrence pourmettre à jourla ma- trice plutôt que de la recalculer. •Autres directions à projeter que-?f? DRAFT -- DRAFT -- DRAFT -- DRAFT -- DRAFT -- 8Quasi-Newton avec contraintes d'égalité
•On peut incorporer les contraintes d'égalité linéaires dans une méthode DFP •Contraintes d'inégalité actives↔égalités •Contraintes d'inégalité non actives↔ignorées •Si on n'a qu'une contrainte d'égalitéaTx=b•En l'absence de contraintes, on a trouvé une directiondk=-Hkgkpar DFP, DFP complémentaire ou gradients
conjugués. •La "vraie" direction de recherche devient d k1=-Hk1gk avec H k1=Hk-HkaaTHk aTHka •Cette direction permet de vérifier la contrainte tout le longde la recherche linéaire : aT(Xk+ρdk1) =aTXk-ρaT?
H k-HkaaTHk aTHka? =b-ρ? aTHk-aTHkaaTHk
aTHka? =b. •Les directionsdk1ont encore la propriété d'êtremutuellement conjuguées, •donc sifest quadratique, termine enn-1itérations. DRAFT -- DRAFT -- DRAFT -- DRAFT -- DRAFT -- 9 mcontraintes d'égalité d'une matriceAtelle que : A Tx=b. •La direction de recherche est donnée par une formule ana-logue : d km=-Hkmgk avec H km=Hk-HkA(ATHkA)-1ATHk •Cette direction permet de vérifier la contrainte tout le longde la recherche linéaire : AT(Xk+ρdkm) =ATXk
-ρAT(Hk-HkA(ATHkA)-1ATHk) =b-ρATHk +ρATHkA(ATHkA)-1ATHk =b. •Encore une fois, terminaison quadratique car directions con- juguées. •On peut calculerHkmen calculant desHk1mfois, les uns à la suite des autres (poura1puisa2puisa3etc.) •Evite de calculer(ATHkA)-1. DRAFT -- DRAFT -- DRAFT -- DRAFT -- DRAFT -- 10Inégalités linéaires
•AXkinégalités actives traitées comme des égalités •inégalités non actives ignorées. •SiXk+ρ?dkviole une inégalité non active enXkon doit calculerXk+1intersection de la droite de recherche et de la contrainte. •Il faut alors incorporer cette nouvelle contrainte active dans le calcul deHk+1,m+1.•De même, on peut être amené à relâcher une contrainte pourchercher dans une direction où elle est non active ("change-ment de direction dans un coin") :
H k=Hk1+aaT aTa a rparmiqformant la matriceA: H k,q-1=Hk,q+Pq-1araTrPq-1 aTrPq-1ar avec P q-1=I-Aq-1(ATq-1Aq-1)-1ATq-1 oùAq-1est la matriceAprivée de larème colonnear.•Plusieurs contraintes à enlever en même temps : on peut fairel'opération successivement pour chaque contrainte.
DRAFT -- DRAFT -- DRAFT -- DRAFT -- DRAFT -- 11Revoilà Lagrange...
•Quand enlever une contrainte et laquelle ? •A chaque point, calculer les coefficients de Lagrange g k=Aλ doncλ= (ATA)-1ATgk
pour les contraintes actives. •Si (pour unmin) desλsont négatifs, •on relâche la contrainte correspondant auλle plus négatif. •Cette méthode revient à jongler avec les contraintes actives comme le gradient projeté. •On traite des contraintes non linéaires en les approchant lo- calement par un hyperplan tangent et avec des directions de retour. DRAFT -- DRAFT -- DRAFT -- DRAFT -- DRAFT -- 12Algorithmes de points intérieurs
•Jusqu'ici, on se balade sur la frontière du domaine. •Par contraste, les algorithmes de points intérieurs restent à l'intérieur du domaine des contraintes d'inégalité, •et s'approchent de la frontière sans jamais l'atteindre (fonc- tions barrière) •donc, pas de relaxation •ou sont dissuadés de sortir trop du domaine faisable (pénalités simples) •donc, relaxation. •On supposera que DRAFT -- DRAFT -- DRAFT -- DRAFT -- DRAFT -- 13Fonctions de pénalité
•Idée : trouver une fonctionP(x) telle que l'optimum de soit proche de l'optimum de minf(x) +P(x). •Ne pas perturberfquand on est à la frontière, •Pénaliser fortement quand on viole une contrainte. •Le lagrangien f(x) +?λ kgk(x) est une formetrèsparticulière de pénalité. DRAFT -- DRAFT -- DRAFT -- DRAFT -- DRAFT -- 14Exemples de fonctions de pénalité usuelles
•Pour confiner une variablexdans[-X,X]: -P(x) =k?x X?2Maveck >0etMentier non nul.
-P(x) =-kln?-cosπx X? •Pour confinerxdans[X1,X2]: -P(x) =k?2x-(X1+X2)X2-X1?
2Maveck >0etMentier
non nul. -P(x) =-kln? -cosπ[2x-(X1+X2)]X2-X1?
•Inégalitésgi(x)≥0 -P(x) =? iki[gi(x)]2avecki>0 -P(x) =? iki[gi(x)]2Mavecki>0 la somme étant prise sur les contraintes actives •Egalitésgi(x) = 0 -idemque les inégalités -P(x) =? iki|gi(x)|avecki>0 DRAFT -- DRAFT -- DRAFT -- DRAFT -- DRAFT -- 15Remarques
•Méthode simple, •assez efficace, •attention : on peut perturber fortement dans l'intérieur donc rester proche de la frontière •de même perturbations parfois chaotiques "loin" à l'extérieur •faire des petits pas ? sans contrainte. •Mais fortement non linéaire, parfois même pas quadratique. •Une contrainte est remplacée par une "crevasse" •doncattentionla méthode de plus forte pente risque de mal marcher. •Efficacité dépend beaucoup des ajustements deski(qui peu- vent varier d'une itération à l'autre). DRAFT -- DRAFT -- DRAFT -- DRAFT -- DRAFT -- 16Ajustement des paramètres
•En posantZ(x) =f(x) +?
ik igi(x)2 (contraintes d'égalité ou inégalités actives) •on cherchera, quand on s'approche de l'optimum, à vérifier j? ∂f ∂xj+ 2? ik igi∂g i∂xj? ∂g r∂xj= 0. •on résout ce système pour trouver leski. •Onpeutaussiutiliserk?i=|gi|εikiavecεiunecertainetolérance.
•En principe,kiaugmente à chaque itération •gi→0quandki→+∞. •Coûteux d'évaluerki? Tâtonnements ! DRAFT -- DRAFT -- DRAFT -- DRAFT -- DRAFT -- 17Fonctions barrières
•Ajouter une pénalité qui empêche même d'atteindre la fron-tière. •On part d'un point strictement faisable, •on résout le problème perturbé sans contrainte, •on a le nouveau point courant, •on change les paramètres pour s'autoriser à approcher de lafrontière •on réitère. -Fonctions inverses :1 g(x), -Fonctions logarithmiques :log|g(x)|.•A chaque itération on doit rester faisable donc si on sort dudomaine, on réajuste le pas.
DRAFT -- DRAFT -- DRAFT -- DRAFT -- DRAFT -- 18