No d'ordre Annee

Dorin Preda

Description

Niveau: Supérieur, Doctorat, Bac+8
No d'ordre : 2184 Annee 2004 THESE presentee pour obtenir le titre de DOCTEUR DE L'INSTITUT NATIONAL POLYTECHNIQUE DE TOULOUSE Ecole Doctorale : Informatique & Telecommunications Specialite : Mathematiques Appliquees par Dorin PREDA INTEGRATION D'UNE CONTRAINTE LOGIQUE DANS LES PROBLEMES DE CONTROLE OPTIMAL ET RESOLUTION PAR LA PROGRAMMATION MIXTE Soutenue publiquement le 14 Decembre 2004 devant le jury compose de : MM. P. Hansen Rapporteurs Ph. Toint MM. J. Bernussou Examinateurs R. Epenoy P. Legendre MM. J.-B. Caillau Invites J. Gergaud M. J. Noailles Directeur de these

• probleme en variables mixtes


• contrainte logique limitant la duree de controle


• contraintes logiques


• fois des variables continues et des variables contraintes


• probleme de controle optimal avec contraintes logiques


• problemes d'optimisation

Sujets

• Institut national polytechnique de Toulouse

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