UFR DE MATHEMATIQUES ET INFORMATIQUE

Georges Koepfler

Description

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 ≤ √

Sujets

• Cours magistral
• Modèle
• Loisir

Informations

• Publié par: thieg
• Nombre de lectures: 104
• Langue: Français

Extrait

´UFR DE MATHEMATIQUES ET INFORMATIQUE
Licence MIA, L3
Notes de cours
Optimisation
Georges Koepfler 2006-2010 - georges.koepfl[e-mail] des mati`eres
1 Introduction 1
2 Espace vectoriels norm´es 3
3 Espaces vectoriels norm´es de dimension finie 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, diff´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 diff´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´efinition 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’infimum est atteint dans K? c.`a.d. est-ce qu’il existe x ∈ K v´erifiant
∗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´erifie (P), alors x v´erifie la propri´et´e N(x)
et/ou trouver des conditions suffisantes pour ˆetre un point optimal :
si x v´erifie la propri´et´e S(x), alors x v´erifie (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 finie ou infinie, ...
- les propri´et´es de K ⊂E : ferm´e, born´e, convexe, ...
- les propri´et´es de J : E−→R : continuit´e, diff´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´erifier 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 ) .