La lecture à portée de main
Découvre YouScribe en t'inscrivant gratuitement
Je m'inscrisDécouvre YouScribe en t'inscrivant gratuitement
Je m'inscrisDescription
Sujets
Informations
Publié par | profil-feym-2012 |
Nombre de lectures | 26 |
Poids de l'ouvrage | 2 Mo |
Extrait
oN d’ordre: 2184 Ann´ee 2004
`THESE
pr´esent´ee pour obtenir le titre de
DOCTEUR DE L’INSTITUT NATIONAL
POLYTECHNIQUE DE TOULOUSE
´Ecole Doctorale : Informatique & T´el´ecommunications
Sp´ecialit´e : Math´ematiques Appliqu´ees
par
Dorin PREDA
´INTEGRATION D’UNE CONTRAINTE LOGIQUE
` ˆDANS LES PROBLEMES DE CONTROLE OPTIMAL
´ET RESOLUTION PAR LA PROGRAMMATION MIXTE
Soutenue publiquement le 14 D´ecembre 2004 devant le jury compos´e de:
MM. P. Hansen Rapporteurs
Ph. Toint
MM. J. Bernussou Examinateurs
R. Epenoy
P. Legendre
MM. J.-B. Caillau Invit´es
J. Gergaud
M. J. Noailles Directeur de th`eseiiTable des mati`eres
Introduction v
1 Position du probl`eme 1
1.1 Probl`eme de controleˆ optimal avec contraintes logiques . . . . 1
1.2 Discr´etisation . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.3 Contraintes logiques . . . . . . . . . . . . . . . . . . . . . . . 7
1.4 Probl`emes mixtes . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.5 Probl`eme en variables mixtes associ´e a` une dynamique lin´eaire 11
1.6 Probl`eme en variables associ´es a` une dynamique non-
lineai´ re. Transfert orbital . . . . . . . . . . . . . . . . . . . . 12
2 Contraintes logiques 15
2.1 Espace de recherche. Contraintes (C ) . . . . . . . . . . . . . 15Δ
2.2 Notion de solution satur´ee . . . . . . . . . . . . . . . . . . . . 16
2.3 R´eduction de l’espace de recherche . . . . . . . . . . . . . . . 18
2.4 Elimination d’une solution d´ej`a analys´ee . . . . . . . . . . . . 21
2.5 Matrice totalement unimodulaire . . . . . . . . . . . . . . . . 22
2.6 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3 MINLP associ´e `a une dynamique lin´eaire 25
3.1 Rappels relatifs `a la programmation mixte . . . . . . . . . . . 26
3.2 Mod`ele MIQP. Algorithmes et r´esultats . . . . . . . . . . . . 30
3.3 Mod`ele MINLP. Algorithme et r´esultats . . . . . . . . . . . 36
3.4 Exemples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
3.5 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
4 Optimisation globale et transfert orbital 53
4.1 La d´emarche Branch and Reduce . . . . . . . . . . . . . . . . 53
4.2 Transfert orbital 2D `a masse constante . . . . . . . . . . . . . 65
4.3 Convexification . . . . . . . . . . . . . . . . . . . . . . . . . . 68
4.4 La r´eduction du domaine . . . . . . . . . . . . . . . . . . . . 98
4.5 R´esultats . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
4.6 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
iiiConclusion 105
Bibliographie 107
ivIntroduction
Contexte. Dans le cadre de cette ´etude on se propose d’int´egrer un type
particulierdecontraintelogiquedanslesprobl`emesdecontrˆoleoptimal.Plus
pr´ecis´ement on consid`ere un syst`eme dont l’´evolution au cours du temps est
d´ecrite par des ´equations diff´erentielles et qu’on veut ramener d’un ´etat
initial donn´e en un ´etat final donn´e, dans un temps fix´e, en minimisant
l’´energie d´epens´ee le long du processus. Ce type de probl`eme est un cas
important de probl`eme de contrˆole optimal et diff´erentes approches pour le
r´esoudre existent. La question a` laquelle on essaye de r´epondre dans cette
´etude est de trouver la solution optimale du probl`eme obtenu a` partir du
pr´ec´edent en ajoutant une contrainte logique limitant la dur´ee de contrˆole.
Ce dernier type de probl`eme s’inscrit dans un cadre plus g´en´eral, celui de
l’optimisation globale. Plus sp´ecifiquement encore, on mod´elise notre sys-
t`eme comme un probl`eme MINLP (Mixed Integer Non Linear Problem),
probl`eme en variables mixtes, contenant `a la fois des variables continues
et des variables contraintes `a prendre des valeurs enti`eres. Il s’agit la` de
la classe la plus g´en´erale des probl`emes d’optimisation et deux facteurs
rendent ce type de probl`eme tr`es difficile `a r´esoudre: d’une part il n’existe
pas de conditions n´ecessaires et suffisantes d’optimalit´e, ce qui oblige les
algorithmes a` trouver d’autres m´ethodes pour v´erifier l’optimalit´e d’une so-
lution; d’autre part, cette classe de probl`emes est NP-difficile, ce qui signifie
que la solution ne peut pas ˆetre trouv´ee en temps polynˆomial. Dans ces
conditions, les algorithmes existants ne sont pas g´en´eraux, se limitant sou-
vent `a traiter des cas particuliers du domaine mixte (contraintes lin´eaires,
probl`eme convexes, etc). C’est la d´emarche qu’on va suivre nous aussi tout
au long de ce travail consistant `a adapter et prendre en compte au mieux
la forme particuli`ere du probl`eme `a r´esoudre, d’une part, et les sp´ecificit´es
des contraintes logiques, d’autre part. Quant au probl`emes de contrˆole opti-
maltrait´es,deuxcasrepr´esentatifssontanalys´es:leprobl`emeLQR(objectif
quadratiques´eparableetdynamiquelin´eaireparrapportauxvariablesconti-
nues)etlecasdutransfertorbital2D`amasseconstante(exemplesignificatif
d’une dynamique fortement non lin´eaire).
Organisation du document. Ce manuscrit est divis´e en quatre cha-
pitres. La premier chapitre a pour but de poser le probl`eme, en partant
vd’un probl`eme de contrˆole optimal et en exprimant les contraintes logiques
qui nous int´eressent. On donne ici les concepts utilis´es pour obtenir une
mod´elisation mixte: la discr´etisation par collocation directe et les diff´erentes
fa¸con qui s’offrent a` nous pour int´egrer les contraintes logiques. On propose
aussi la formulation g´en´erale du probl`eme dans deux cas int´eressants qui
m´eritent d’ˆetre distingu´es et analys´es de fa¸con ind´ependante: le cas ou` le
syst`eme de d´epart a une dynamique lin´eaire et celui d’un syst`eme gouvern´e
parunedynamique non-lin´eaire(illustr´e surleprobl`eme dutransfertorbital
2D a` masse constante).
Le deuxi`eme chapitre s’int´eresse aux contraintes logiques; il s’agit d’une
´etude pouvant s’appliquer aux deux cas (dynamique lin´eaire et dynamique
non lin´eaire). L’id´ee directrice du chapitre est de r´eduire l’espace de re-
cherche induit par les contraintes logiques, mais aussi de caract´eriser au
mieux les solutions parmis lesquelles se trouve l’optimum global. Plusieurs
propri´et´es int´eressantes sont ennonc´ees et d´emontr´ees dans cette partie et
leur rˆole dans l’acc´el´eration d’un algorithme mixte est mis en valeur.
Le trois`eme chapitre s’int´eresse de plus pr`es au mod`ele quadratique; il
faut pr´eciser qu’il s’agit du cas ou` le probl`eme de d´epart (avant l’int´egration
descontrainteslogiques)estquadratique,c’est`adiregouvern´epardes´equa-
tionsdiff´erentielleslin´eairesetunobjectifquadratique.Onpr´esenteicilesal-
gorithmesdudomainemixteetleuradaptationpourlesdeuxmod`elesmixtes
d´ecrits auparavant. La derni`ere partie du chapitre est consacr´ee `a l’analyse
des diff´erents r´esultats num´eriques obtenus en appliquant les algorithmes
existants, mais aussi celui qu’on a d´evelopp´e nous-mˆeme. Le cas de l’oscil-
lateur harmonique est analys´e plus en d´etail, comme exemple repr´esentatif
de la classe des probl`emes a` dynamique lin´eaire int´egrant les contraintes
logiques.
Au cœur du quatri`eme chapitre se trouve le cas non lin´eaire, le plus dif-
ficile a` traiter; apr`es avoir pr´esent´e la m´ethode qu’on utilise sur un exemple
plus simple ayant un nombre petit de termes non convexes, on s’int´eresse
au cas du transfert orbital 2D `a masse constante. Le cadre g´en´eral ´etant
celui de l’algorithme de Branch and Bound, le principal apport de ce cha-
pitre ´etant dans les diff´erentes fa¸cons d’obtenir une relaxation convexe du
probl`eme non convexe. En effet, la relaxation convexe joue un rˆole tr`es im-
portant dans l’algorithme de Branch and Bound/Reduce, en fournissant un
minorant de l’optimum global du probl`eme non convexe. Un autre apport
important constitue l’int´egration de l’analyse d’intervalle dans l’algorithme
afin de r´eduire le domaine de recherche. On pr´esente les diff´erents r´esultats
num´eriques obtenus et on conclut ce chapitre par une discussion concernant
les limitations de la m´ethode propos´ee.
Motivation. Les contraintes logiques se mod´elisent naturellement en uti-
lisant les variables bool´eennes, ce qui rend le probl`eme de d´epart mixte
vi(variables continues et enti`eres). C’est de cette fa¸con qu’on a ´et´e amen´e
`a s’int´eresser aux probl`emes MINLP. D’autre part, la contrainte logique
qu’on consid`ere apparaˆıt souvent dans le cas d’un engin dont le moteur
est soumis a` des limitations d’utilisation; ce sont les contraintes cumula-
tives sur la dur´ee du contrˆole. Une autre application possible est la prise en