UFR DE MATHEMATIQUES ET INFORMATIQUE

pages

Français

Documents

Écrit par
Georges Koepfler

Publié par
thieg

Lire un extrait

Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus

Découvre YouScribe en t'inscrivant gratuitement

Je m'inscris

Découvre YouScribe en t'inscrivant gratuitement

Je m'inscris

pages

Français

Ebook

Lire un extrait

Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus

Publié par

thieg

Nombre de lectures

Langue

Français

Niveau: Supérieur, Licence, Bac+3

cours magistral

UFR DE MATHEMATIQUES ET INFORMATIQUE Licence MIA, L3 Notes de cours Optimisation Georges Koepfler 2006-2010 -

instants ti ?

probleme de maximisation en probleme de minimisation

x2 ≤

modele

optimisation - l3

point x?

temps libre

probleme sans contrainte

?f?1 ≤ √

Voir

Publié par

thieg

Nombre de lectures

Langue

Français

´UFR DE MATHEMATIQUES ET INFORMATIQUE
Licence MIA, L3
Notes de cours
Optimisation
Georges Koepﬂer 2006-2010 - georges.koepﬂer@mi.parisdescartes.frTable des mati`eres
1 Introduction 1
2 Espace vectoriels norm´es 3
3 Espaces vectoriels norm´es de dimension ﬁnie 4
4 Espaces euclidiens. Espaces de Hilbert 5
5 Th´eor`eme de projection 7
5.1 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
5.2 M´ethode des moindres carr´es . . . . . . . . . . . . . . . . . . . . . . . . . . 8
6 Adjoint d’un endomorphisme 10
7 D´eriv´ee directionnelle, d´eriv´ees partielles, diﬀ´erentiabilit´e 12
8 Caract´erisation des points optimaux 16
9 Fonctions convexes 17
10 Multiplicateurs de Lagrange 20
Avertissement : ces notes sont un support et compl´ement du cours magistral.
Leurcontenu n’estpas´equivalent aucoursenseign´e, en particulierlesexamens
et contrˆoles se r´ef`erent au cours enseign´e uniquement.
Bibliographie. Les r´ef´erences suivantes peuvent ˆetre utiles mais d´epassent le
niveau de ce cours.
• H. Cartan, Cours de calcul diﬀ´erentiel, Hermann 1997.
• J.E.Rombaldi,Analyse matricielle. Cours et exercices r´esolus,EDPSciences
1999.
• P.G. Ciarlet, Introduction a` l’analyse matricielle et a` l’optimisation, Mas-
son 1990.Georges KOEPFLER : Optimisation - L3 2009-2010 1
1 Introduction
Dans ce cours on va introduire des outils math´ematiques pour r´esoudre un probl`eme
d’optimisation dont la forme abstraite g´en´erale est la suivante :
Soit E un ensemble, K ⊂ E et une application J : E −→ R, on veut r´esoudre le
probl`eme (
⋆x ∈K
(P) ∗J(x ) = inf J(x)
x∈K
Onditque (P)est un probl`eme d’optimisationou probl`eme de minimisationdela fonction
J sous la contrainte x∈K.
Si K = E on a un probl`eme sans contrainte. La fonction J est appel´ee fonction couˆt,
fonction objectif, fonction ´economique.
En remplac¸ant J par −J on transforme un probl`eme de maximisation en probl`eme de
minimisation.
∗ ∗Un point x est un minimum local de J sur K s’il existe un voisinage V de x tel que
∗J(x )≤J(x) pour tout x∈K∩V.
∗ ∗Un point x est un minimum local strict de J sur K s’il existe un voisinage V de x tel
∗ ∗que J(x )<J(x) pour tout x∈K∩V, x =x .
Une suite (x ) de points de K est une suite minimisante si lim J(x ) = inf J(x).n n∈N n
n→+∞ x∈K
Une telle suite existe toujours, par d´eﬁnition de inf, par contre on ne sait rien au sujet de
sa convergence ´eventuelle.
Pour r´esoudre le probl`eme (P), il faut se poser les questions suivantes :
• Est-ce que inf J(x) existe? c.`a.d. est-ce que J est born´ee inf´erieurement?
x∈K
⋆• Est-ce que l’inﬁmum est atteint dans K? c.`a.d. est-ce qu’il existe x ∈ K v´eriﬁant
∗J(x ) = minJ(x)?
x∈K
⋆• Est-ce que x est unique? Sinon, quelle est la taille de l’ensemble des solutions?
⋆• Est-ce que l’on peut caract´eriser x ? c.`a.d. peut-on trouver des conditions n´ecessaires
pour caract´eriser un minimum : si x v´eriﬁe (P), alors x v´eriﬁe la propri´et´e N(x)
et/ou trouver des conditions suﬃsantes pour ˆetre un point optimal :
si x v´eriﬁe la propri´et´e S(x), alors x v´eriﬁe (P) .
• Trouver un algorithme d’optimisation pour d´eterminer la, resp. les, solutions de (P).
Pour r´epondre `a ces questions on est en particulier amen´e `a ´etudier
- la structure deE : espace vectoriel, muni d’une norme, d’un produit scalaire, de dimen-
sion ﬁnie ou inﬁnie, ...
- les propri´et´es de K ⊂E : ferm´e, born´e, convexe, ...
- les propri´et´es de J : E−→R : continuit´e, diﬀ´erentiabilit´e, convexit´e, ...
Dans les chapitres suivants on va donner des ´el´ements de r´eponse `a ces questions.

62 UFR de Math´ematiques et Informatique, Universit´e Paris Descartes
Exemples :
•Unbanquierexplique`asonclientquepourˆetrenonimposables,lesquantit´esx d’actionsi
du type A (i = 1,2) doivent v´eriﬁer 3x +x ≤ 3. Or le client voulait x = 4 et x = 1/3.i 1 2 1 2
Que peut lui proposer le banquier comme solution non imposable, mais la“plus proche”
de la r´epartition souhait´ee par le client?
2L’ensemble de contraintes est K ={(x ,x )∈R /x ≥ 0,x ≥ 0,3x +x ≤ 3}1 2 1 2 1 2
∗ ∗et on cherche (x ,x )∈K qui minimise la distance de (4,1/3) `a K.1 2
• Un dispositif exp´erimental fournit aux instants t ∈R les mesures y ∈R (1≤i≤m),i i
nX
or, pour le ph´enom`ene ´etudi´e, on a un mod`ele param´etrique m(t) = x w (t)j j
j=1
ou` les x ∈ R sont les param`etres et w : R → R des fonctions r´eelles, lin´eairementj j
ind´ependantes.
On veut adapter au mieux les param`etres du mod`ele aux donn´ees exp´erimentales, pour
ceci on compare la mesure y `a la valeur que donne le mod`ele m(t ) `a l’instant t et oni i i
minimise leur ´ecart. Sans hypoth`eses restrictives sur les param`etres x = (x ,...,x ), on1 n
a un probl`eme sans contraintes :
  2m n X X  min y − x w (t ) .