100% ont trouvé ce document utile (1 vote)

403 vues175 pages

Introduction à la Recherche Opérationnelle

Transféré par

Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.

Formats disponibles

Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

100% ont trouvé ce document utile (1 vote)

403 vues175 pages

Introduction à la Recherche Opérationnelle

Transféré par

Rémy Menoung

Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.

Formats disponibles

Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

Introduction à la Recherche Opérationnelle

Anatoli Iouditski, LJK

[email protected]

Lien vers le cours :

https://ljk.imag.fr/membres/Anatoli.Iouditski/ro-m1-ssd.htm

-1-
Objectifs de ce cours :

— s’initier à la modélisation et la résolution de problèmes “du monde réel” et de

problèmes d’optimisation surgissant en applications statistiques
— comprendre les qualités et les limites de différents modèles par rapport aux hypo-
thèses, à la complexité et à l’effort de résolution
— experimenter la résolution de problèmes à l’aide de modèles mathématiques en
utilisant les logiciels disponibles, et interpréter correctement les résultats

Évaluation : réalisation d’un projet en TP

-2-
Introduction
Recherche opérationnelle : comment organiser les operations (activités) d’une or-
ganisation (production, transport, construction, communication, planification financière,
santé, militaire...)
Recherche – en reference à une approche scientifique :
— analyse des besoins, collection des données, formulation du problème
— construction d’un modèle mathématique – abstraction et extraction des facteurs
essentiels – assez precis, pour que ces solutions soient valides pour le problème
“réel”
— résolution – conception d’un algorithme numérique pour calculer la solution
— validation – experimentation pour tester l’adequation du modèle et des solutions,
ajustements
Caractéristique importante : l’objectif est de proposer “la meilleure solution” = la
solution optimale (ou plutôt une solutions optimales)
Avertissement : Une approche par modèles à de la prise de décision aide à prendre de
bonnes décisions, mais ne peut garantir de bons résultats

-3-
De point de vue de statisticien
1. RO est le “consommateur final” des solutions statistiques – analyse statistique est
un étape de construction, d’identification et de test d’un modèle
2. Les outils mathématiques et numériques de RO – théorie et algorithmes d’opti-
misation sont utilisées en statistiques quand les règles de decisions statistiques
nécessitent une recherche de “meilleurs solutions”

Dans ce cours on présentera brièvement ces deux aspects de RO. Mais notre intérêt
s’orientera surtout vers le second – les outils mathématiques et numériques de resolution
de problèmes d’optimisation et leurs applications en statistique.

En termes de compétences les objectifs sont d’apprendre de modéliser un problème

comme un problème d’optimisation (ou encore, de programmation mathématique), et
d’utiliser les outils disponibles (e.g., CVXR, RMosek) pour le résoudre.

-4-
Formuler un modèle mathématique
Problème général de programmation mathématique
minimiser f (x) [fonction objective]
sous contraintes
hi(x) = 0, i = 1, ..., m [contraintes d’égalité] (MP)
gj (x) ≤ 0, j = 1, ..., k [contraintes d’inégalité]
x∈X [domaine du problème]
Un problème d’optimisation, comme tout modèle mathématique est une representation
idéalisée du problème “réel.” Le modèle
— doit être “adéquate” – modéliser “correctement” la structure des relations entre les
décisions et les résultats)
— peut être “nourri” par les données – on doit pouvoir identifier les différents para-
mètres
— peut être traité numériquement en temps raisonnable

-5-
Éléments d’un problème de programmation mathématique
— variables de décision, e.g., x = [x1; ...; xn] – décisions quantifiées
— une solution x ∈ Rn représente une decision possible
— fonction objective représente la mesure de performance (les pertes) à optimiser,
e.g.,
f (x1, ..., xn) = c1x1 + ... + cnxn
— contraintes du problème representent les restrictions sur les décisions admissibles,
définies par les inégalités ou égalités contenant les variables de decision, par
exemple,
x
x1 + 3x1x2 + 2x2 ≤ 10, x1 + x25 − x6 cos(x8) = 0, ...
— les coefficients et les seconds membres sont données ou paramètres du problème

-6-
minimiser f (x) [fonction objective]
sous contraintes
hi (x) = 0, i = 1, ..., m [contraintes d’égalité] (MP)
gj (x) ≤ 0, j = 1, ..., k [contraintes d’inégalité]
x∈X [domaine du problème]

Resoudre le problème (MP) veut dire trouver une solution optimale x∗, c.-à-d.,
une solution admissible (réalisable) (i.e., qui respecte les contraintes) avec la valeur de
l’objectif ≤ sa valeur sur toute autre solution admissible :
 
 hi(x∗) = 0 ∀i, gj (x∗) ≤ 0 ∀j, et x∗ ∈ X 
 h (x) = 0 ∀i, g (x) ≤ 0 ∀j, et x ∈ X 
i j

⇒ f (x∗) ≤ f (x)

-7-
Classification des problème de programmation mathématique
minimiser f (x) [fonction objective]
sous contraintes
hi (x) = 0, i = 1, ..., m [contraintes d’égalité] (MP)
gj (x) ≤ 0, j = 1, ..., k [contraintes d’inégalité]
x∈X [domaine du problème]

• En optimisation combinatoire (ou discrete), le domaine X est un ensemble discret

(e.g., ensemble des vecteurs avec des composantes entières ou 0/1.
• En optimisation continue on se concentre sur X qui est un “continuum” (e.g., Rn,
P
boite {x a ≤ x ≤ b}, ou simplex {x ≥ 0 : xj = 1}, etc.) ; l’objectif et les
j
contraintes sont des fonction (pour le moins !) continues sur X.
• En optimisation linéaire, X = Rn et l’objectif et les contraintes sont des fonctions
linéaires de x.
• Au contraire, en optimisation non-linéaire continue, (certaines fonctions parmi) l’ob-
jectif et les contraintes sont non-linéaires.

-8-
1ère partie : Optimisation linéaire
Exemples et définitions

Nous commençons ce cours par optimisation (programmation) linéaire (OL) –

la partie de la programmation mathématique la plus simple et la plus souvent utilisée en
applications.

Exemple
minimiser 350x1 + 300x2
sous contraintes x1 ≥ 0, x1 ≥ 0
9x1 + 6x2 ≤ 1566
12x1 + 16x2 ≤ 2880

-9-
Pourquoi c’est bien ?

• Les raisons de popularité de l’OL sont :

— “pouvoir d’expression” interessant – les dépendances linéaires sont souvent des
approximation satisfaisantes des dépendances actuelles non-linéaires.
— Modèles linéaires sont faciles à specifier – pour “remplir” une fonction linéaire
de 1000 variables on a besoin de définir 1000 coefficients ; pour spécifier une
fonction quadratique on a besoin de 501 500 coefficients ! Ainsi, il est possible de
construire des modèles avec beaucoup de variables et de contraintes
— existence d’une théorie complète et élégante
— dès le début, la méthodologie de OL était accompagnée par une technique de
résolution extrêmement puissant - algorithme de simplex qui a fait de OL un outil
de travail.
Les “moteurs d’optimisation” actuels sont capables de résoudre des problèmes OL
avec 104 ÷ 106 variables et contraintes

- 10 -
• Dans cette partie du cours on s’intéressera de

— Modélisation OL, y compris des exemples “instructifs” des modèles et leur “calcul”
– ensemble d’outils pour reconnaı̂tre la possibilité de formuler le problème comme
problème OL
— Théorie de l’OL – la géométrie des programmes linéaires, existence et caractéri-
sation des solutions optimales et dualité ;
— Applications de ces outils pour résoudre quelques problèmes d’optimisation linéaire
pertinentes en probabilité et statistique

- 11 -
Modèle d’optimisation linéaire
Programme OL (programme linéaire PL)
Pn
minimiser ci x i
Pi=1
n
sous contraintes ajixi ≤ bj , j = 1, ..., m
Pi=1
n
i=1 djixi = fj , j = 1, ..., p
avec
— n variables d’optimisation : x1, ..., xn (scalaires réels)
— donnees de problème (paramètres) : coefficients ci, aji, bj , dji, fj
P
— cixi est la fonction de coût ou fonction objective
P
— ajixi ≤ bj , j = 1, ..., m, contraintes d’inégalité (non-strictes)
P
— djixi = fj , j = 1, ..., p, contraintes d’égalité

- 12 -
Étapes de formulation de modèles d’OL

1. Comprendre le problème (souvent difficile dans la pratique)

2. Identifier les variables de décision
3. Formuler les contraintes comme des combinaisons linéaires du variables de décision
4. Poser la fonction objective comme une combinaison linéaire de les variables de
décision

- 13 -
Exemple : problème de transport
• Une compagnie possède n usines de production et m clients.
— Chaque usine a la capacité mensuelle ui, i = 1, ..., n de production, et chaque
client a la demande mensuelle dj , j = 1, ..., m.
— Soit xij la quantité de produits fournis par l’usine “i” vers le client “j.”
— L’objectif est de determiner un plan de transport qui minimise le coût total
P
i,j cij xij , ou cij et le coût de transport de “i” vers “j.”

Formulation OL
Pn Pm
minimiser j=1 cij xij [cout de transport à minimiser]
Pi=1
n
sous contraintes xij ≥ dj , j = 1, ..., m [satisfaire toutes les demandes]
Pi=1
m x ≤u,
j=1 ij i i = 1, ..., n [respecter les capacités de production]
xij ≥ 0, i = 1, ..., n, [contraintes de production
j = 1, ..., m non-négative]

- 14 -
Exemple : problème de régime optimal
• Il y a n types de produits et m types d’éléments nutritionnels.
— Une unité de produit #j contient pij grammes d’élément #i et coute cj .
— La consommation journalière de l’élément #i doit être entre les limites [bi, bi].
— On cherche un “régime” (mélange de produits) le moins cher qui procure les
quantités quotidiennes nécessaires d’éléments nutritionnels.
En notant xj la quantité du j ème produit dans le régime, le modèle OL dévient
Pn
min j=1 cj xj [cout à minimiser]
x
sous contraintes  
Pn 
pij xj ≥ bi 
 bornes inf et sup du contenu
Pnj=1 
 
j=1 pij xj ≤ bi 
 d’éléments nutritionnels 

 dans le régime
1≤i≤m
" #
quantité de chaque produit
xj ≥ 0, 1 ≤ j ≤ n
ne peut pas etre negatif

- 15 -
• Le régime optimal est systématiquement utilisé dans les élevages de volaille et de
bétail. La nourriture des humains ne peut pas être optimisée de la même façon à cause
des facteurs du goût, de diversité, etc, difficiles à prendre en compte.
• Quoi que... Voici le regime optimal pour un humain calculé par le “solveur”
http://www.neos-guide.org/content/diet-problem-solver
(le problème est formulé en utilisant 68 produits disponibles dans le logiciel) :

Food Serving Cost

Raw Carrots 0.12 cups shredded 0.02
Peanut Butter 7.20 Tbsp 0.25
Popcorn, Air-Popped 4.82 Oz 0.19
Potatoes, Baked 1.77 cups 0.21
Skim Milk 2.17 C 0.28

Coût journalier : $ 0.96

Exemple : problème du flux maximal (Max Flow)
• Étant donné un réseau avec 2 noeuds choisis – une source et un puits, trouver un flux
maximal de la source vers le puits.
Autrement dit, on veut trouver le plus grand s tel que une alimentation externe “s au
noeud source, −s au noeud puits, et 0 partout ailleurs” correspond à un flux réalisable
respectant les capacités des arcs.
Formulation OL :

flux total de la source vers
max s le puits à maximiser
f,s
sous contraintes


 s, si i est le noeud-source
P
γ Piγ fγ =  −s, si i est le noeud-puits
 0, pour toues les autres noeuds
[loi de concervation des flux]
fγ ≥ 0, γ ∈ Γ [flux dans les arcs sont ≥ 0]
fγ ≤ hγ , γ ∈ Γ [on doit respecter les capacités des arcs]
où Γ est l’ensemble des arcs du reseau, et Piγ = 1 si l’arc γ est connecté au noeud i
et Piγ = 0 sinon.
- 16 -
Exemple : problème d’affectation
• On veut trouver la correspondance entre N personnes et N taches de façon que
— toute personne est assignée à une seule tache ; toute tache est associée à une
seule personne
— le cout d’association de la personne i à la tache j est aij
Formulation combinatoire
PN
minimiser i,j=1 aij xij
PN
sous contraintes xij = 1, j = 1, ..., N
Pi=1
N x = 1, i = 1, ..., N
j=1 ij
xij ∈ {0, 1}, i, j = 1, ..., N
— variable xij = 1 si la personne i est assignée à la tache j ; xij = 0 sinon
— il y a N ! correspondances possibles – beaucoup trop pour les énumérer toutes

- 17 -
Exemple : problème d’affectation
Formulation OL
P
N
minimiser i,j=1 aij xij
PN
sous contraintes xij = 1, j = 1, ..., N
Pi=1
N x = 1, i = 1, ..., N
j=1 ij
0 ≤ xij ≤ 1, i, j = 1, ..., N
— nous avons relaxé les contraintes binaires xij ∈ {0, 1}
— on peut démontrer que dans ce cas tout point optimal satisfait xij ∈ {0, 1}
— ainsi, on peut résoudre ce problème combinatoire (très particulier) de façon effi-
cace (par OL ou des méthodes spécialisées)

- 18 -
Un peu d’histoire
— années 30-40 : Kantorovitch, Koopmans, von Neumann, Dantzig : fondations
motivées par des problèmes de l’économie et de logistique
— 1947 : (Dantzig) algorithme de simplexe
— 1948-1949 : application historique : organisation du pont aérien pour ravitaille-
ment de la zone occidentale de Berlin pendant le blocus de Berlin-ouest par les
soviétiques. Resolution numérique “à la main” (par algorithme de simplexe avec
des milliers de variables)
— 1950-1960 : des nombreuses applications dans les autres disciplines
— 1975 : prix Nobel d’économie pour Kantorovitch et Koopmans
— 1984 (Karmarkar) : premier “algorithme de point intérieur” – avènement de “l’op-
timisation moderne”
— depuis 1984 : algorithmes pour des problèmes de très grande taille, utilisation de
l’OL dans tous les domaines industriels...

- 19 -
Notations :  
x1
 
— n-vecteurs : x = [x1; ...; xn] = [x1, ..., xn]T =  ... .
xn
On note xi la i-ème composante de x
On note x = 0 si xi = 0, ∀i ; x = 1 si xi = 1, ∀i ; x = ei si xi = 1 et
xj = 0 pour j 6= i (i-ème vecteur de base canonique).
— Matrices m × n :
 
a11 ... a1n
 ... 
A =  ... 
am1 ... amn
avec elements aij (ou [A]ij ), [A]j la j-ème colonne de A (m-vecteurs =
matrices m × 1).
On note A = 0 (matrice nulle) si aij = 0 ∀i, j ; A = I (matrice identite) si
aii = 1 et aij = 0 ∀j 6= i.

- 20 -
Operations matricielles :

— matrice transposée AT
— multiplication par un scalaire αA
— addition A + B and soustraction A − B de matrices de même taille
— produit matrice-vecteur y = Ax et y T = xT AT (de tailles compatibles)
— produit C = AB de matrices de tailles compatibles (lesquelles ?)
— produit scalaire de 2 vecteurs de même taille :

hx, yi = xT y = x1y1 + ... + xnyn.

— produit scalaire de 2 matrices de même taille (m × n) :
n
X
hX, Y i = Trace(X T Y ) = [X T Y ]ii
i=1
m X
X n
= Trace(Y T X) = ... = xij yij .
i=1 j=1

- 21 -
Notations matricielles

— In extenso
 
Xn Pn 
aji x i ≤ b j , j = 1, ..., m
min ci x i : Pi=1
n
 i=1 djixi = fj , j = 1, ..., p 
i=1
— Notation vectorielle (par contrainte)
( T )
aj x ≤ bj , j = 1, ..., m
min cT x :
dT
j x = fj , j = 1, ..., p
avec les n-vecteurs c, ai et di :

c = [c1; ...; cn], aj = [aj1; ...; ajn], dj = [dj1; ...; djn].

n o
— Notation matricielle : min cT x : Ax ≤ b, Dx = f
où A est une matrice m×n avec des lignes aT j (elements aji), et D une matrice
p × n avec des lignes dT j (elements dji).
— L’inégalité a ≤ b entre les vecteurs est comprise “par composante,” dans le sens
ai ≤ bi pour tout i (de même pour “<, >, ≥”).
- 22 -

min cT x : Ax ≤ b, Dx = f

Terminologie :
— x1, ..., xn variables de décision du problème,
x = [x1; ...; xn] est vecteur de decision
— x solution réalisable (admissible) ssi elle satisfait les contraintes Ax ≤ b et
Dx = f
— domaine du problème (ensemble admissible) = ensemble des solutions réalisables
— x∗ est une solution optimale ssi elle est réalisable et cT x∗ ≤ cT x pour toute
solution réalisable x
— la valeur optimale du PL est la valeur Opt = cT x∗
— on dit que PL est non-borné intérieurement si Opt = −∞
— on dit que PL est irréalisable (inadmissible) si le domaine réalisable est vide ; dans
ce cas on pose Opt = +∞. n o
T
Pour un problème de maximisation, max c x : Ax ≤ b, Dx = f , la situation est
inversée : Opt = +∞ si le problème n’est pas borné, et Opt = −∞ s’il n’est pas
réalisable.

- 23 -
Forme canonique et forme standard
On remarque que
• toute égalité/inégalité linéaire peut être réécrite avec le second membre constant
(toutes les variables “à gauche”) : 2x1 ≥ 20 − x2 ⇔ 2x1 + x2 ≥ 20
• toute inégalité non-stricte peut être réécrite comme une inégalité avec “≤” :
2x1 + x2 ≥ 20 ⇔ −2x1 − x2 ≤ −20
• toute égalité peut être représentée par (une paire d’inégalités avec les signes opposés :
2x1 − x2 ≤ 5
2x1 − x2 = 5 ⇔
−2x1 + x2 ≤ −5
• toute inégalité avec ≤, en rajoutant une variable d’écart y, peut être réécrite comme
une égalité et une inégalité “simple” y ≥ 0 :
(
2x1 + x2 + y = 20
2x1 + x2 ≤ 20 ⇔
y ≥ 0
• minimiser la fonction linéaire cT x revient exactement à maximiser la fonction linéaire
−cT x.

- 24 -
• Tout programme OL est equivalent à un programme OL en forme canonique, dans
laquelle l’objectif doit être maximisé et les contraintes sont les inégalités avec “≤ :”
nP Pn o
n
Opt = max
x j=1 cj xj : j=1 aij xj ≤ bi , 1 ≤ i ≤ m
n [notation
o “in extenso”]
⇔ Opt = max cT x : aT
i x ≤ bi , 1 ≤ i ≤ m
x
n o [notation “par contrainte”]
⇔ Opt = max cT x : Ax ≤ b
x
[notation “matricielle”]
où

c = [c1; ...; cn], b = [b1; ...; bm], ai = [ai1; ...; ain], A = [aT T T
1 ; a2 ; ...; am ]
• Ensemble X ⊂ Rn défini par X = {x : Ax ≤ b} – l’ensemble de solutions d’un
système fini d’inegalites lineaires non-strictes aT n
i x ≤ bi , 1 ≤ i ≤ m en x ∈ R –
s’appel ensemble polyédrique, ou un polyèdre.

• Un programme OL en forme canonique consiste à maximiser un objectif linéaire sur un

ensemble polyédrique.
- 25 -
  

 
 −x1 + x2 ≤ 6 


 
 

3x1 + 2x2 ≤ 7
max x2 :
x 


 
7x1 − 3x2 ≤ 1 


  
−8x1 − 5x2 ≤ 100

[−1;5]

[1;2]

[−10;−4]

[−5;−12]

Programme OL et son domaine réalisable

- 26 -
• Un programme OL en forme standard consiste à maximiser une forme linéaire sur
l’intersection de l’orthant non-négatif Rn
+ = {x ∈ Rn : x ≥ 0} et d’un plan réalisable

{x : Ax = b} :
( Pn )
Opt = max
Pn
c x : j=1 aij xj = bi , 1 ≤ i ≤ m
x j=1 j j xj ≥ 0, j = 1, ..., n
( [notation
) “ in extenso”]
T aT
i x = bi , 1 ≤ i ≤ m
⇔ Opt = max c x :
x xj ≥ 0, 1 ≤ j ≤ n
n o[notation “par contrainte”]
⇔ Opt = max cT x : Ax = b, x ≥ 0
x
[notation “matricielle”]
où

c = [c1; ...; cn], b = [b1; ...; bm], ai = [ai1; ...; ain], A = [aT ;
1 2 aT ; ...; aT ]
m
• Dans le programme OL standard
— toute variables sont non-négatives
— toutes contraintes linéaires “generales” sont des égalités
- 27 -
Remarque : la forme standard de PL est universelle : tout programme linéaire est
equivalent à un PL en forme standard.
En effet, il suffit de convertir un PL en forme canonique max{cT x : Ax ≤ b}. Pour
x
le faire,
— on introduit des variables d’écart (une par inégalité), et on réécrit le problem
comme
max{cT x : Ax+s = b, s ≥ 0}
x,s
— ensuite, on représente x comme x = u − v, la difference de 2 vecteurs non-
négatifs, et on arrive à
n o
T T
max c u − c v : Au − Av + s = b, [u; v; s] ≥ 0 .
u,v,s

- 28 -
Illustration :
Opt = max[2x1 + 3x2 − x3]
x
s.c.
3x1 + 4x2 + 5x3 ≤ 6
7x1 + 8x2 + 9x3 ≤ 10
⇔ Opt = max[2x1 + 3x2 − x3]
x,s
s.c.
3x1 + 4x2 + 5x6 +s1 = 6
7x1 + 8x2 + 9x3 +s2 = 10
s1 ≥ 0, s2 ≥ 0
⇔ Opt = max[2[u1 − v1] + 3[u2 − v2] − [u3 − v3]]
u,v,s
s.c.
3[u1 − v1 ] + 4[u2 − v2 ] + 5[u3 − v3 ] +s1 = 6
7[u1 − v1 ] + 8[u2 − v2 ] + 9[u3 − v3 ] +s2 = 10
s1 ≥ 0, s2 ≥ 0, u1 ≥ 0, u2 ≥ 0, u3 ≥ 0,
v1 ≥ 0, v2 ≥ 0, v3 ≥ 0,

- 29 -
Interprétation géométrique

Normes dans Rn
qP p
• Norme euclidienne (`2) : kxk2 = n 2 T
i=1 xi = x x
• Normes `1 et `∞ :

kxk1 = |x1| + ... + |xn|, kxk∞ = max{|x1|, ...|xn|}

Propriétés :
— kxk ≥ 0, kxk = 0 ssi x = 0 (positivité)
— kx + yk ≤ kxk + kyk (inégalité triangulaire)
— ∀α ∈ R, kαxk = |α|kxk (homogénéité)
• Inégalité de Cauchy-Schwartz : |xT y| ≤ kxk2kyk2
— |xT y| = kxk2kyk2 ssi x et y sont proportionnels
— implique d’autres inégalités intéressantes, e.g.,

n n
X X √
x ≤ |x | ≤ nkxk2
i i
i=1 i=1
(pour quelle x cette inégalité devient- 30
une- égalité ?).
projection of x on the line defined by nonzero y: the vector t̂y with

Hyperplans et projections t̂ = argmin kx − tyk

t
• Projection de x sur la droite avec le vecteur-directeur y : vecteur t̂y ou

y

xT y
t̂y = yT y
y
t̂ = argmin kx
expression for −
t̂: tyk2
t
xT yx Tkxk2 cos θ
y kxk cos θ x
⇒ t̂ = t̂2== 2 =
kyk2 kyk kyk2kyk

Introductionest l’ensemble de solutions de l’équation linéaire aT x = b1–20

• Un hyperplan avec
vecteur normal a 6= 0
• Un demi-espace est l’ensemble de solutions de l’inégalité linéaire
aT x ≤ b
avec vecteur normal a 6= 0
- 31 -
Interpretation géométrique
Geometricalinterpretation
Geometrical interpretation

G= | a|TaTxT x
{x{x =b}b} H= {x || aaTTTxx ≤ b}
={x
G = {x : a x==
G=
b} H
H = {x : a x ≤ b}
a a a

2 2
u=
u=(b/kak
(b/kak)a)a u
xx
xx

GG
0 0 xx−−uu H
H
x−
x−uu

— vecteur u = b 2 a satisfait aT u = b
• the
• thevector
vectoru= ukak
=(b/kak
2(b/kak2 2
)a)asatisfies TT
satisfiesaa uu==bb
T
— x ∈ G si a (x − u) = 0 (i.e. x − u ⊥ a)
• x• isx in
is hyperplane
in hyperplane
T G Gif ifaTa(x
T − u) = 0 (x − u is orthogonal to a)
(x − u) = 0 (x − u is orthogonal
— x ∈ H si a (x − u) ≤ 0 (i.e. angle ∠(x − u, a) ≥ π/2)
• x•(⇔ isThalfspace
isx in
a ≤ aT uH=Hifb).
inx halfspace ifaTa(x
T − u) ≤ 0 (angle 6 6 (x − u, a) ≥ π/2)
(x − u) ≤ 0 (angle (x − u, a) ≥

- 32 -
Introduction
Introduction 1–22
1–22
Example
Exemple

x2 x2
aT x = 0 aT x = 10

a = (2, 1) a = (2, 1)

x1 x1

T T aT x ≤ 3
a x = −5 a x=5

- 33 -

Introduction 1–23
Polyhedron
Un polyèdre : ensemble de solutions d’un système fini d’inégalités linéaires :
solution set of a finite number of linear inequalities
aT1 x ≤ b 1 , a T x ≤ b , ..., aT x ≤ b
2 2 m m
T T T
a 1 x ≤ b1 , a 2 x ≤ b2 , ..., a m x ≤ bm

a1 a2

a3
a5

• intersection of a finite number of halfspaces

T
• in matrix
— intersection notation:
d’un nombreAxfini≤ bdeif demi-espaces
A is a matrix with rows ai
• canmatricielle
— notation include equalities:
: Ax ≤ g isAequivalent
F xb,=ou x ≤ les
to Favec
la matrice g, −F
lignes aT
x ≤ −g
i
T
— peut contenir les égalités ai x = bi
(avec les inégalités aT
Introduction
i x ≤ b i et −a T x ≤ −b )
i i
1–24

- 34 -
Example
Exemple

x1 + x2 ≥ 1, −2x1 + x2 ≤ 2, x1 ≥ 0, x2 ≥ 0

−2x1 + x2 = 2

x1
x1 + x2 = 1

Introduction - 35 - 1–25
Example
Exemple

0 ≤ x1 ≤ 2, 0 ≤ x2 ≤ 2, 0 ≤ x3 ≤ 2, x1 + x2 + x3 ≤ 5

(0, 0, 2) (0, 2, 2)

(1, 2, 2)

(2, 1, 2)
(2, 0, 2)

(0, 2, 0)x
2
(2, 2, 1)

(2, 0, 0) (2, 2, 0)

Introduction 1–26

- 36 -
Geometrical interpretation
Interprétation géométrique of LP
de PL

n minimizeo cT x n o
T
min c x : subject
Ax ≤ b to= Ax
− max T
≤ b −c x : Ax ≤ b
x x

−c

optimal solution
Ax ≤ b

dashed
ligneslines (hyperplanes)
(hyperplans) areéslevel
en pointill cT x = αdeforniveau
setsensembles
sont des {x : αcT x = α} de la
different
forme linéaire cT x pour les différents α
Introduction - 37 - 1–27
Exemple


Example 

 2x1 + x2 ≤ 3 

min −x 1 − x2 : −xx11−+
minimize x2 4x ≤ 5
2
 1 + x2 ≤ 3
 subject to 2xx 

1 ≥ 0, x2 ≥ 0
x1 + 4x2 ≤ 5
x1 ≥ 0, x2 ≥ 0
−x1 − x2 = −2 x2

−x1 − x2 = −1
−x1 − x2 = −5

−x1 − x2 = 0
−x1 − x2 = −4
x1

−x1 − x2 = −3
optimal solution is (1, 1)
solution optimale : x = [1; 1], cT x = −2
Introduction 1–28

- 38 -
Algorithme du simplexe

Soit un programme linéaire sous la forme spéciale :

 

 T
a1 x ≤ b1 

 

 
aT x ≤ b
max cT x : 2
T
2
x∈R2 

 a3 x ≤ b3 


 

x≥0
avec b1 ≥ 0, b2 ≥ 0, b3 ≥ 0.
x2
6 aT
2 x = b2

5 aT
3 x = b3

2 c aT
1 x = b1

O 1 2 3 4 5 6 7 x1

- 39 -
 
aT
1x ≤

 b1 



 
T aT
2x ≤ b2 
max c x : Tx ≤
x∈R2 

 a3 b3 



 

x≥0

On cherche une solution en parcourant les points extremes à partir de x(0) = 0.

x(1) : x1 = 0, aT
3 x = b3 .
x2
6

4
c
3

2
x(1)
1

cT x = cT x(1)
O 1 2 3 4 5 6 7 x1
 

 T
a1 x ≤ b1 

 

 
aT x ≤ b
max cT x : 2
T
2
x∈R2 

 a3 x ≤ b3 


 

x≥0

x(2) : aT
1 x = b 1 , a Tx = b .
3 3
x2
6

c
5

3
x(2)
2
x(1)
1
cT x = cT x(2)

O 1 2 3 4 5 6 7 x1
 
aT

1x ≤

 b1 



 
T aT
2x ≤ b2 
max c x : Tx ≤
x∈R2 

 a3 b3 



 

x≥0

x(3) : aT T
1 x = b 1 , a 2 x = b2 .
x2
6

5
c
4

3
x(2)
x(3)
2
x(1) cT x = cT x(3)
1

O 1 2 3 4 5 6 7 x1

Solution optimale : x(3)

- 40 -
Algorithme du simplexe – explication

Exemple : résoudre le problème

 

 2x1 + x2 ≤ 4, 
max x1 + x2 : x1 + 2x2 ≤ 3
x1 ,x2 
 
x1 ≥ 0, x2 ≥ 0 

1o. On convertit en forme standard :

 

 2x1 +x2 +s1 = 4, 

max x1 + x2 : x1 +2x2 +s2 =3
x1 ,x2 
 

x1 ≥ 0, x2 ≥ 0, s1 ≥ 0, s2 ≥ 0

2o. On pose z = x1 + x2, et on considère le système



 z − x1 −x2 =0

 2x1 +x2 +s1 = 4,

 x1 +2x2 +s2 =3


x1 ≥ 0, x2 ≥ 0, s1 ≥ 0, s2 ≥ 0

- 41 -
Notre objectif est de maximiser z.


 z − x1 −x2 =0

 2x1 +x2 +s1 =4

 x1 +2x2 +s2 =3


x1 ≥ 0, x2 ≥ 0, s1 ≥ 0, s2 ≥ 0
On dit que une variable est basique s’elle n’apparaı̂t que dans une seule equation.
On forme une solution basique en mettant à zero toute variable non basique.

• Base : s1, s2. Nous avons

x1 = x2 = 0, z = x1 + x2 = 0, s1 = 4, s2 = 3

Peut on accroı̂tre z ?

Règle I Si toutes les variables en 1ère ligne ont des coefficients non négatifs, la solution
basique est optimale. Sinon, on choisit une variable non basique dont le coefficient est
négatif et on l’augment tant que le système reste admissible.

- 42 -


 z − x1 −x2 =0

 2x1 +x2 +s1 =4

 x1 +2x2 +s2 =3


x1 ≥ 0, x2 ≥ 0, s1 ≥ 0, s2 ≥ 0
On choisit, par exemple, x1. Quel pivot d’algorithme de Gauss choisir ?

second membre
Règle II Choisir la ligne qui correspond au plus petit rapport coefficient de la variable
(on suppose que coefficient de la variable est strictement positif)

Puisque 4/2 < 3/1, on choisit la 2ème ligne :



 z − 12 x2 + 12 s1 =2

 x1 + 12 x2 + 12 s1 =2
3 1


 2
x2 − s
2 1
+s2 = 1

x1 ≥ 0, x2 ≥ 0, s1 ≥ 0, s2 ≥ 0
• Base : x1, s2. Nous avons

s1 = x2 = 0, x1 = 2, s2 = 3, z = 2

- 43 -


 z − 12 x2 + 12 s1 =2

 x1 + 12 x2 + 12 s1 =2
3



x
2 2
− 12 s1 +s2 = 1

x1 ≥ 0, x2 ≥ 0, s1 ≥ 0, s2 ≥ 0

On continue avec x2. Comme 2/ 21 > 1/ 23 , on choisit la 3ème ligne :



 z + 13 s1 + 13 s2 = 7


3
x1 + 23 s1 − 13 s2 = 5
3



x2 − 13 s1 + 23 s2 = 2
3

x1 ≥ 0, x2 ≥ 0, s1 ≥ 0, s2 ≥ 0

• Base : x1, x2. Nous avons

s1 = s2 = 0, x1 = 35 , x2 = 32 , z = 7
3

• D’après la Règle I, nous avons trouvé la solution optimale

- 44 -
On récapitule :


 z − x1 −x2 =0

 2x1 +x2 +s1 =4

 x1 +2x2 +s2 =3


x1 ≥ 0, x2 ≥ 0, s1 ≥ 0, s2 ≥ 0
On commence avec x(0) = [0; 0], contraintes “actives” :
x1 = 0, x2 = 0
⇓


 z − 21 x2 + 12 s1 =2

 x1 + 12 x2 + 12 s1 =2
3



x
2 2
− 12 s1 +s2 = 1

x1 ≥ 0, x2 ≥ 0, s1 ≥ 0, s2 ≥ 0
Solution actuelle x(1) = [2; 0], contraintes “actives” :
x2 = 0, 2x1 + |{z} x2 = 4
=0

- 45 -
⇓



 z + 13 s1 + 13 s2 = 7


3
x1 + 23 s1 − 13 s2 = 5
3



x2 − 13 s1 + 23 s2 = 2
3

x1 ≥ 0, x2 ≥ 0, s1 ≥ 0, s2 ≥ 0

Solution actuelle x(2) = [ 35 ; 23 ], contraintes “actives” :

2x1 + x2 = 4, x1 + 2x2 = 3
Nous avons trouvé une solution optimale

- 46 -
x2

4 2x1 + x2 = 4

2
c = [1; 1]
1
x(2)
x1 + 2x2 = 3
1 2 3 4 x1
Interprétation géométrique

- 47 -
• Écriture sous forme de tableau :

z x1 x2 s1 s2 RHS Solution basique

1 −1 −1 0 0 0 basique s1 = 4, s2 = 3
0 2 1 1 0 4 non basique x1 = x2 = 0
0 1 2 0 1 3 z=0
1 0 − 12 1
2
0 2 basique x1 = 2, s2 = 1
1 1
0 1 2 2
0 2 non basique x2 = s1 = 0
3 1
0 0 2
− 2
1 1 z=2
1 1 7
1 0 0 3 3 3
basique x1 = 53 , x2 = 32
2 1 5
0 1 0 3
− 3 3
non basique s1 = s2 = 0
0 0 1 − 13 2
3
2
3
z = 7
3

- 48 -
Cycles
• Soit
 

 2x1 + x2 ≤ 4, 
max x1 + 21 x2 : x1 + 2x2 ≤ 3
x1 ,x2 
 
x1 ≥ 0, x2 ≥ 0 

Le tableau d’algorithme du simplexe :

z x1 x2 s1 s2 RHS Solution basique
1 −1 − 12 0 0 0 basique s1 = 4, s2 = 3
0 2 1 1 0 4 non basique x1 = x2 = 0
0 1 2 0 1 3 z=0
1
1 0 0 2
0 2 basique x1 = 2, s2 = 1
1 1
0 1 2 2
0 2 non basique x2 = s1 = 0
3 1
0 0 2
− 2
1 1 z=2

Maintenant, Règle I implique que [x1; x2] = [2; 0] est une solution optimale.

- 49 -
Néanmoins, on peut essayer d’augmenter x2 pour obtenir une solution basique avec
x2 6= 0. Cela donne :
z x1 x2 s1 s2 RHS Solution basique
1
1 0 0 2
0 2 basique x1 = 53 , x2 = 32
2
0 1 0 3
− 13 5
3
non basique s1 = s2 = 0
0 0 1 − 13 2
3
2
3
z=2

On observe que le coefficient de s2 en 1ère ligne est 0. Si on choisi s2 et le pivot en

3ème ligne on obtient de nouveau
z x1 x2 s1 s2 RHS Solution basique
1
1 0 0 2
0 2 basique x1 = 2, s2 = 1
1 1
0 1 2 2
0 2 non basique x2 = s1 = 0
3 1
0 0 2
− 2
1 1 z=2
Ce sont exactement le tableau et la solution précédents !

- 50 -
Problème dégénéré
• On considère le programme
 

 3x1 + x2 ≤ 6, 

 
x1 − x2 ≤ 2 
max 2x1 + x2 :
x1 ,x2 


x2 ≤ 3  


x1 ≥ 0, x2 ≥ 0 
L’application de l’algorithme du simplex résulte en
z x1 x2 x3 s1 s2 RHS Solution basique
1 −2 −1 0 0 0 0 basique x3 = 6, s1 = 2, s2 = 3
0 3 1 1 0 0 6 non basique x1 = x2 = 0
0 1 −1 0 1 0 2 z=0
0 0 1 0 0 1 3
1 0 −3 0 2 0 4 basique x1 = 2, x3 = 0, s2 = 3
0 0 4 1 −3 0 0 non basique x2 = s1 = 0
0 1 −1 0 1 0 2 z=4
0 0 1 0 0 1 3
On note qu’une des variables basiques – x3 – est nulle.

- 51 -
Maintenant, Règle I suggère de choisir x2 comme nouvelle variable basique, et Règle II
implique le pivot de la 2ème ligne :
z x1 x2 x3 s1 s2 RHS Solution basique
3
1 0 0 4
− 14 0 4 basique x1 = 2, x2 = 0, s2 = 3
1
0 0 1 4
− 34 0 0 non basique x3 = s1 = 0
1 1
0 1 0 4 4
0 2 z=4
0 0 0 − 14 3
4
1 0

C’est la même solution, sauf que la variable basique dégénérée est x2. Si on continue
par s1, avec le pivot de la 4ème ligne,
z x1 x2 x3 s1 s2 RHS Solution basique
2 1
1 0 0 3
0 3
5 basique x1 = 1, x2 = 3, s1 = 4
0 0 1 0 0 1 3 non basique x3 = s2 = 0
1 1
0 1 0 3
0 − 3
1 z=5
0 0 0 − 13 1 4
3
4
La dégénérescence n’a pas empêchée la convergence vers la solution optimale, mais dans
certains cas elle peut conduire au cycles.

- 52 -
Problème non borné
• Exemple :
 

 −x1 + x2 ≤ 1, 
max 2x1 + x2 : x1 − 2x2 ≤ 2
x1 ,x2 
 
x1 ≥ 0, x2 ≥ 0 
La resolution par l’algorithme du simplex donne
z x1 x2 s1 s2 RHS Solution basique
1 −2 −1 0 0 0 basique s1 = 1, s2 = 2
0 −1 1 1 0 1 non basique x1 = x2 = 0
0 1 −2 0 1 2 z = 0
1 0 −5 0 2 4 basique x1 = 2, s1 = 3
0 0 −1 1 1 3 non basique x2 = s2 = 0
0 1 −2 0 1 2 z = 4
A ce stade Règle I choisit x2, mais il n’y a pas de pivot positif dans la colonne corres-
pondante.
⇒ En augmentant x2, on va jamais attendre une contrainte ⇒ Il n’y a pas de limite
pour la valeur du problème – problème non borné

- 53 -
Dualité linéaire
Dualité pour les systèmes d’inégalités linéaires
Comment repondre aux questions suivantes :
• Comment savoir si l’ensemble polyédrique
X = {x ∈ R : Ax ≤ b}
est/n’est pas vide ?
• Comment savoir si l’ensemble polyédrique
X = {x ∈ R : Ax ≤ b}
est/n’est pas bornée ?
• Comment comprendre si les deux polyèdres
X = {x ∈ R : Ax ≤ b}, X 0 = {x ∈ R : A0x ≤ b0}
coincident/ne coincident pas ?
• Comment savoir si le programme OL réalisable/irréalisable ?
Notre objectif actuel sera d’étudier les réponses donnés par le théorème de dualité en
programmation linéaire.
- 54 -
Théorème sur alternative linéaire
• Soit le système de m inégalités linéaires strictes et non-strictes en x ∈ Rn :
(
aT
i x< bi , i ∈ I (S)
aT
i x≤ bi , i ∈ I
où ai ∈ Rn, bi ∈ R, 1 ≤ i ≤ m, avec I ⊂ {1, ..., m}, et I = {1, ..., m}\I.
(S) est un système “universel” d’inégalités linéaires.
Questions importantes (opérationnelles) :
— Comment trouver une solution de (S) quand elle existe ?
— Comment comprendre que (S) est incompatible ?
Questions importantes (descriptives) :
— Comment certifier que (S) est soluble ?
— Comment certifier que (S) est incompatible ?

- 55 -

aTi x< bi , i ∈ I
(S)
aTi x≤ bi , i ∈ I
• Il est facile de certifier que le système est réalisable : il suffit de produire le certificat
– une solution candidate qui satisfait le système.
Exemple : Le vecteur x̄ = [10; 10; 10] est un certificat d’admissibilité du système
−x1 −x2 −x3 < −29
x1 +x2 ≤ 20
x2 +x3 ≤ 20
x1 +x3 ≤ 20
• Mais comment certifier que (S) n’a pas de solution ? E.g., comment prouver que le
système
−x1 −x2 −x3 < −30
x1 +x2 ≤ 20
x2 +x3 ≤ 20
x1 +x3 ≤ 20
est incompatible ?

- 56 -

aTi x< bi , i ∈ I
(S)
aTi x≤ bi , i ∈ I
• Une idée simple : si on fait une somme pondérée d’inégalités de (S) avec des
coefficients non-négatifs, on obtient une inégalité linéaire qui est une conséquence du
système – il est satisfaite sur toute solution de (S). Si cette inégalité n’a pas de solutions,
alors (S), non plus, n’a pas de solutions.
Exemple : Pour le système
2× −x1 −x2 −x3 < −30
1× x1 +x2 ≤ 20
1× x2 +x3 ≤ 20
1× x1 +x3 ≤ 20
il suffit de sommer les inégalités avec des poids en rouge pour obtenir l’inégalité contra-
dictoire
0 · x1 + 0 · x2 + 0 · x3 < 0.
⇒ le vecteur λ = [2; 1; 1; 1] certifie que ce système n’est pas réalisable.

- 57 -

aTi x< bi , i ∈ I
(S)
aTi x≤ bi , i ∈ I
• Pour certifier l’absence de solution, faire la somme d’inégalités avec des poids λi ≥ 0,
pour arriver à l’inégalité
P T x ? Pm λ b
[ m λ a
i=1 i i ] i=1 i i
" P # (!)
? = ” < ” quand i∈I λi > 0
P
? = ” ≤ ” quand i∈I λi = 0
• Si (!) n’a pas de solutions, (S) est inadmissible.
Remarque : inégalité ( !) n’a pas de solution ssi
m
X
λiai = 0
i=1
et, de plus,
Pm P
i=1 λi bi ≤0 quand i∈I λi > 0
Pm P
λ b
i=1 i i <0 quand i∈I λi = 0

- 58 -

aTi x< bi , i ∈ I
(S)
aTi x≤ bi , i ∈ I

Proposition. On 
associe avec (S) deux systèmes d’in
égalités linéaires en λ1, ..., λm :

 λi ≥ 0 ∀i 
 λi ≥ 0 ∀i

 P m λa =0 
 Pm λ a = 0
(I) : Pm i=1 i i , (II) : Pi=1 i i
 λ b ≤ 0  m λb <0

 i=1 i i 
 i=1 i i
 P 
i∈I λi > 0 λi = 0, i ∈ I
| {z } | {z }
0T x<0 0T x≤−1
Si un des systèmes (I), (II) a une solution, alors (S) n’a pas de solutions.

- 59 -

aTi x< bi , i ∈ I
(S)
aTi x≤ bi , i ∈ I
Nous avons le résultat bien plus fort :
Théorème sur alternative linéaire. On associe avec le système (S) deux systèmes
d’inégalités linéaires 
en λ1, ..., λm : 

 λi ≥ 0 ∀i 
 λi ≥ 0 ∀i

 P m λa =0 
 Pm λ a = 0
(I) : Pi=1 i i , (II) : Pi=1 i i
 m λibi ≤ 0  m


 P i=1 

 i=1 λi bi < 0
i∈I λi > 0 λi = 0, i ∈ I
Système (S) n’a pas de solutions si et seulement si un des systèmes (I), (II) a une
solution.
Remarque : une solution de (I) ou (II) peut être vue comme un certificat d’incompati-
bilité de (S) : (S) est irréalisable si et seulement si un tel certificat existe.
Remarque : les inegalites strictes de (S) ne participent pas dans (II) ⇒ (II) a une
solution ssi le sous-système “nonstricte”
aT
i x ≤ bi , i ∈ I
de (S) n’a pas de solution.
- 60 -
Le théorème peut être reformuler de façon suivante :
Un système fini d’inégalités linéaires n’a pas de solution ssi il est possible, en faisant
une somme d’inégalités de système avec des poids admissibles (i.e., compatibles avec
les operations de base avec des inégalités), obtenir une inégalité contradictoire – soit
l’inégalité 0T x ≤ −1, ou 0T x < 0.
L’avantage de cette formulation c’est que nous n’avons pas besoin de convertir le système
en forme canonique.
Exemple : le système
x1 +2x2 < 5
2x1 +3x2 ≥ 3
3x1 +4x2 = 1
n’a pas de solution – il suffit de faire la somme d’inégalités avec les poids [−1; 2; −1]
pour obtenir
0 · x1 + 0 · x2 > 0

- 61 -
Remarque : le théorème sur alternative est toujours vrais dans une direction – en
faisant les sommes d’inégalités d’un système (S), linéaire ou non linéaire, avec des
inégalités triviales (toujours vraies), on obtient toujours une conséquence de (S).
Cependant, “l’autre direction” dans le théorème sur alternative linéaire exploite fortement
le fait que les inégalités du système original et une conséquence que nous recherchons
sont linéaires.
Par exemple, l’inégalité quadratique

x2 ≤ 1 (!)
est une conséquence du système d’inégalités linéaires (et, donc, quadratiques aussi)

−1 ≤ x ≤ 1 (∗)
Par contre, ( !) ne peut pas être représenté comme une somme d’inégalités de (∗) et
d’inégalités linéaires et quadratiques triviales, telles que

0 · x ≤ 1, x2 ≥ 0, x2 − 2x + 1 ≥ 0, ...

- 62 -
Dualité en OL On considère le problème OL
n o
Opt(P ) = max cT x : Ax ≤ b (P )
x
Problème dual permet de borner supérieurement la valeur optimal du problème primal
(P). Pour le faire, on “agrège” le problème (P) :
— on attribue aux contraintes aT i x ≤ bi des coefficients non-négatifs λi (“multipli-
cateurs de Lagrange”) et on fait la somme des contraintes avec ces coefficients,
pour obtenir
[AT λ]T x ≤ bT λ (!)
Observation : par construction, cette inégalité est une conséquence du système
Ax ≤ b, et est ainsi satisfaite sur toute solution realisable de (P).
— Si AT λ = c, alors ( !) dit que that bT λ est une borne supérieure sur cT x sur
tout domaine realisable de (P), et donc

bT λ ≥ Opt(P ).

- 63 -
n o
Opt(P ) = max cT x : Ax ≤ b (P )
x

• Maintenant nous pouvons rechercher la meilleure – la plus petite – borne supérieure du

Opt(P ) qu’on puisse obtenir par cette construction. Ainsi on arrive au problème suivant

n o
T T
Opt(D) = min b λ : A λ = c, λ ≥ 0 , (D)
λ
appelé problème dual de (P).

- 64 -
Observation : la construction de la borne pour la valeur optimale peut être appliquée à
tout programme OL, quelque soit le format. Par exemple, en l’appliquant au programme
primal
 

 ≤ p
P x |{z} (`) 


 


 


 λ` 

 
≥ q
Qx |{z} (g)
Opt(P ) = max cT x : (P )
x 
 λg 


 


 Rx |{z}
= r (e) 


 

 
λe
on obtient le problème dual
(
Opt(D) = min pT λ` + q T λg + rT λe :
[λ` ;λg ,λe ] ) (D)
λ` ≥ 0, λg ≤ 0
P T λ` + QT λg + RT λe = c
• Attention aux notations : les types ≤, ≥, = des contraintes de (P) sont préservés par
les vecteurs de coefficients de Lagrange affectés λ`, λg , λe.

- 65 -
En résumé :

Primal “min” Primal “max”

Dual “max” Dual “min”
Contrainte primale Variable duale Variable duale
“≥” “≥” “≤”
“≤” “≤” “≥”
“=” sans contrainte sans contrainte
Variable primale Contrainte duale Contrainte duale
“≥” “≤” “≥”
“≤” “≥” “≤”
sans contrainte “=” “=”

- 66 -
T

Opt(P ) = max c x : P x ≤ p (`), Qx ≥ q (g), Rx = r (e) (P )
x

λ` ≥ 0, λg ≤ 0
Opt(D) = min pT λ` + q T λg + rT λe : (D)
[λ` ;λg ,λe ] P T λ` + QT λg + RT λe = c
Théorème de dualité en OL : soit (P) le problème OL primal avec sont dual (D).
Alors
[Symétrie primal-dual] Dualité est symétrique : (D) est un programme OL, est le dual de
(D) est (équivalent à) (P).
[Dualité faible] Nous avons toujours Opt(D) ≥ Opt(P ).
Attention : cette inégalité correspond au problème primal de maximisation. Plus géné-
ralement, dualité faible dit que dans le couple primal-dual, la valeur optimale du problème
de minimisation est ≥ la valeur optimal du problème de maximisation.
[Dualité forte] Les propriétés suivantes sont équivalentes :
— un des problèmes est réalisable et borné
— deux problèmes sont solubles
— deux problèmes sont réalisables
et quand une (et, donc, toutes) de ces propriétés a lieu, nous avons
Opt(P ) = Opt(D).

- 67 -

Opt(P ) = max cT x : P x ≤ p (`), Qx ≥ q (g), Rx = r (e) (P )
x

λ` ≥ 0, λg ≤ 0
Opt(D) = min pT λ` + q T λg + rT λe : (D)
[λ` ;λg ,λe ] P T λ` + QT λg + RT λe = c
Verification de la symétrie primal-dual. On réécrit (D) comme un problème de
maximisation :
( )
λg ≤ 0, λ` ≥ 0
−Opt(D) = max − pT λ` − q T λg − rT λe :
[λ` ;λg ,λe ] P T λ` + QT λg + RT λe = c
et, en appliquant les règles de construction de dual, on obtient
 

 P xe + xg = −p 

min cT xe : x` ≥ 0, xg ≤ 0, Qxe + x` = −q .

[x` ;xg ;xe ]  

Rxe = −r
En posant xe = −x et en éliminant xg et xe, le problème dual du (D) devient

n o
T
min −c x : P x ≤ p, Qx ≥ q, Rx = r ,
x
qui est équivalent à (P).
- 68 -

Opt(P ) = max cT x : P x ≤ p (`), Qx ≥ q (g), Rx = r (e) (P )
x

λ` ≥ 0, λg ≤ 0
Opt(D) = min pT λ` + q T λg + rT λe : (D)
[λ` ;λg ,λe ] P T λ` + QT λg + RT λe = c
Consequences immédiates.
— Théorème Si au moins un des problemes (P), (D) est réalisable, nous avons
Opt(P ) = Opt(D). [pourquoi ça ?]
— Conditions d’optimalité en OL Soit x et λ = [λ`; λg ; λe] une paire des
solutions réalisables de (P ) et (D). Elle est comprise des solutions optimales
• [saut de dualité nul] si et seulement si le saut de dualité (duality gap) évalué sur cette
paire de solutions, est nul :
DualityGap(x, λ) := [pT λ` + q T λg + rT λe] − cT x = 0
• [complémentarité] si et seulement si les produits de tous les multiplicateurs de Lagrange
λiet des résidus de la contrainte correspondante primale sont nuls :
∀i : [λ`]i[p − P x]i = 0 & ∀j : [λg ]j [q − Qx]j = 0.

- 69 -
Verification Nous sommes dans le cas quand les deux problemes sont réalisables et
donc solubles avec les mêmes valeurs optimales. Alors
h i
DualityGap(x, λ) := [pT λ` + q T λg + rT λe] − Opt(D)
h i
+ Opt(P ) − c xT

Pour toute paire de solutions primal-dual réalisables, les expressions entre les crochets
sont non-négatives ⇒ le saut de dualité, évalué sur une paire primal-dual realisable est
≥ 0 et est nul ssi les deux expressions sont nulles ⇔ ssi x est une solution primale
optimale et λ est duale optimale.
• On remarque que
DualityGap(x, λ) = [pT λ` + q T λg + rT λe] − cT x
= [pT λ` + q T λg + rT λe] − [P T λ` + QT λg + RT λe]T x
= λT [p − P x] + λT [q − Qx] + λT [r − Rx]
g e
P` P
= i [λ` ]i [p − P x]i + j [λg ]j [q − Qx]j
⇒ tous les termes dans la sommes sont non-négatifs
⇒ le saut de dualité est nul ssi la complémentarité a lieu.

- 70 -
Fonction de coût d’un programme linéaire I

n o
T
Opt(c) = max c x : Ax ≤ b . (P [c])
x
Maintenant on suppose que A, b sont fixes, et que c varie, et on s’intéresse aux propriétés
Opt(c) comme fonction de c.
Hypothèse : (P [·]) est realisable (ce fait est indépendant de la valeur de c).
Théorème Soit c̄ tel que Opt(c̄) < ∞, et soit x̄ une solution optimale de (P [c̄]).
Alors,
∀c : Opt(c) ≥ Opt(c̄) + x̄T [c − c̄]. (!)
En effet, nous avons

Opt(c) ≥ cT x̄ = c̄T x̄ + [c − c̄]T x̄ = Opt(c̄) + x̄T [c − c̄].

- 71 -
Fonction de coût d’un programme linéaire II

Soit le programme linéaire

n o
T
Opt(b) = max c x : Ax ≤ b . (P [b])
x
On suppose que A, c sont fixes, et b varie, et nous sommes intéressé par les proprietes
de la valeur optimale Opt(b) comme fonction de b.
Remarque : Quand b est tel que (P [b]) est réalisable, la propriété du problème
d’être/ne pas être borné ne dépend pas de la valeur de b.
En effet, le problème (P [b]) n’est pas borné ssi il existe d : Ad ≤ 0, cT d > 0, et
ceci est indépendant de la valeur de b.
Hypothèse : il existe b tel que P ([b]) est réalisable et borné
⇒ P ([b]) est borné s’il est réalisable.
Fonction Opt(b) est monotone en b :
b0 ≤ b00 ⇒ Opt(b0) ≤ Opt(b00).

- 72 -
n o
T
Opt(b) = max c x : Ax ≤ b . (P [b])
x
L’information supplémentaire sur Opt(b) peut être obtenue par dualité. Le problème
duale de (P [b]) est
n o
T T
min b λ : λ ≥ 0, A λ = c . (D[b])
λ
Par le théorème de dualité en OL, sous l’hypothèse, (D[b]) est realisable pour tout b,
et
n o
T T
Opt(b) = min b λ : λ ≥ 0, A λ = c . (∗)
λ
Observation : Soit b̄ tel que Opt(b̄) > −∞, et donc (D[b̄]) est soluble, et soit λ̄
une solution optimale de (D[b̄]). Alors nous avons

∀b : Opt(b) ≤ Opt(b̄) + λ̄T [b − b̄]. (!)

En effet, par (∗) nous avons Opt(b̄) = λ̄T b̄ et Opt(b) ≤ λ̄T b, donc,

Opt(b) ≤ λ̄T b̄ + λ̄T [b − b̄] = Opt(b̄) + λ̄T [b − b̄].

- 73 -
Loi de décroissance des rendement marginaux
On considère la fonction de β définie par
n o
Opt(β) = max cT x : P x ≤ p, q T x ≤ β (Pβ )
x
Interprétation : x est un plan de production, q T x est le prix des ressources utilisées
par x, β est l’investissement dans les ressources, Opt(β) est le retour maximal sur
l’investissement β.
Comme ci-dessus, pour β tel que (Pβ ) est réalisable, indépendamment de la valeur de β,
le problème est soit toujours borné, soit toujours non-borné. Supposons que le problème
est borne dans notre cas, alors
• Le domaine Dom Opt(·) de la fonction Opt(·) est un rayon non vide β ≤ β < ∞
avec β ≥ −∞, et
• Opt(β) est non-décroissante et concave. Monotonie et concavité impliquent que si
β ≤ β1 < β2 < β3,
alors
Opt(β2) − Opt(β1) Opt(β3) − Opt(β2)
≥ .
β2 − β1 β3 − β2

- 74 -
Autrement dit
le retour pour 1e d’investissement décroı̂t (ne change pas dans le meilleur
cas) quand l’investissement β grandit.
⇔ Loi de décroissance des rendements marginaux en économie.

Opt(β̄) + λ̄(β − β̄) Opt(β)

β̄ β

- 75 -
Autre interprétation : accroissement des prix marginaux
On considère la fonction de β définie par
n o
Opt(β) = min cT x : P x ≥ p, q T x ≥ β (Pβ0 )
x
Interprétation : x est un plan de production, q T x la quantité du produit fabriqué, β
est la demande en produit, Opt(β) est le coût de fabrication des produit pour satisfaire
la demande β.
• Comme dans le cas précèdent, le domaine Dom Opt(·) de la fonction Opt(·) est un
rayon non vide β ≥ β > −∞ avec β ≤ ∞, et
• Opt(β) est non-croissante et convexe. Ainsi, si
β1 < β2 < β3 ≤ β,
alors
Opt(β2) − Opt(β1) Opt(β3) − Opt(β2)
≤ .
β2 − β1 β3 − β2

- 76 -
Ce qui peut-être exprimée en PL
Exemple : problème d’ordonnancement
On doit planifier n taches sur la grappe de m serveurs de calcul homogènes. Chaque
tache a la durée fixe ti, i = 1, ..., n, et peut être traitée par tout serveur. On veut
distribuer des taches sur les serveurs de façon à minimiser la durée totale du traitement.
Formulation MinMax
P
minimiser max1≤j≤m n i ti xij
Pm
sous contraintes j=1 xij = 1, i = 1, ..., n
xij ∈ {0, 1}, i = 1, ..., n, j = 1, ..., m.
— variable xij = 1 si la tache i est traitée par le serveur j ; xij = 0 sinon –
problème combinatoire (difficile)
— l’objectif du programme n’est pas linéaire. La fonction non-linéaire “max” peut
être facilement réduite à un objectif avec des contraintes linéaires :
on pose les contraintes
n
X
z≥ tixij , j = 1, ..., m,
i
et le nouvel objectif : minimiser z.
- 77 -
Remarque : dans un programme linéaire, l’objectif est une fonction linéaire de la variable
de decision x et les contraintes sont les equations ou les inégalités linéaires non-strictes.
La propriété d’un problème PM d’etre un programme OL est une propriété de la repré-
sentation. Les programmes seront classifiés selon leur présentation, pas selon ce à quoi
ils sont equivalents/peuvent être réduits.
Ainsi, le problème de programmation mathématique
 

 x1 + x2 ≤ 20 

min x1 : x1 − x2 = 5 (1)
x 
 

x1 , x 2 ≥ 0
est un programme OL.
Mais le problème
 

 x1 + x2 ≤ 20 

min |x1 − 2x2| : x1 − x2 = 5 (10)
x 
 

x1 , x 2 ≥ 0
n’est pas un programme OL, car l’objectif de (10) est non-linéaire.

- 78 -
Optimisation “linéaire par morceaux”
• Fonction linéaire : une fonction f : Rn → R est linéairePiecewise-linear
si function
f (αx + βy) = αf (x) + βf (y) ∀x, y ∈ Rn, ∀α, β ∈ R
f : RTn → R is (convex)npiecewise-linear if it can be expressed
Caractérisation : f est linéaire ssi f = a x pour un a ∈ R .
• Fonction affine : une fonction f : Rn → R est affine si f(x) = max (aT x + b )
i i
i=1,...,m
f (αx + (1 − α)y) = αf (x) + (1 − α)f (y) ∀x, y ∈ Rn, ∀α ∈ R
f is parameterized by m n-vectors a and m scalars bi
Caractérisation : f est affine ssi f = aT x + b pour a ∈ Rn, b ∈ R. i
f (x)
• Fonction linéaire par morceau :
f : Rn → R est (convexe) linéaire par
morceau si
aTi x + bi
f (x) = max (aT
i x + bi ).
i=1,..,m
x
f est paramétrée par m n-vecteurs ai et m scalaires bi.
(the term piecewise-affine is more accurate but less common)
- 79 -

Piecewise-linear optimization
Minimisation linéaire par morceaux
( )
min f (x) = max aT
i x + bi
i=1,...,m
• Modèle OL équivalent avec la variable x et la variable auxiliaire t :

min{t : aT
i x + bi ≤ t ∀i}
• PL en forme canonique (notation matricielle) :

max{c̄T x̄ : Āx̄ ≤ b̄},

avec
   
" # " # a T −1 −b1
x 0  ..1 ...  , b̄ =  ... 
 
x̄ = , c̄ = , Ā =  . .
t −1
aTm −1 bm

- 80 -
Minimisation de la somme des fonctions linéaires par morceaux

min maxi=1,...,m (aTi x + bi ) +maxj=1,...,p (cTj x
+ dj ) ⇔
 

 

min max T
(ai + cj ) x + (bi + dj )

 i = 1, ..., m 

j = 1, ..., p

• PL équivalent avec m + p inégalités

n o
min t1 + t2 : aT T
i x + bi ≤ t1 ∀i, cj x + dj ≤ t2 ∀j
Remarque : pour un x fixe, le minimum en t est
t1 = max (aTi x + bi ), t2 = max (cTj x + dj ).
i=1,...,m j=1,...,p

• PL en forme canonique : max{c̄T x̄ : Āx̄ ≤ b̄}, avec

   
aT1 −1 0 −b1
    ... ... ...   ... 
x 0    
 aTm −1 0 
x̄ = t1 , c̄ = −1 , Ā = 
     , b̄ = 

−bm 
.
 cT1 0 −1   −d1 
t2 −1  ... ... ...   ... 
 
cTp 0 −1 −dp

- 81 -
Approximation de Tchebychev `∞ : min {kAx − bk∞} .
• PL équivalent après la discrétisation (avec la variable x et variable auxiliaire t) :

min{t : −t1 ≤ Ax − b ≤ t1}

• PL en notation matricielle : min{c̄T x̄ : Āx̄ ≤ b̄}, avec
" # " # " # " #
x 0 A −1 b
x̄ = , c̄ = , Ā = , b̄ = .
t 1 −A −1 −b
Minimisation de la norme `1 : min {kAx − bk1} .
• PL équivalent avec la variable x et vecteur auxiliaire u :
 
Xm 
min ui : −u ≤ Ax − b ≤ u
 
i=1

• PL en notation matricielle : min{c̃T x̃ : Ãx̃ ≤ b̃}, avec

" # " # " # " #
x 0 A −I b
x̃ = , c̃ = , Ã = , b̃ = .
u 1 −A −I −b

- 82 -
• Le même problème peu être formulé comme un PL different en introduisant des va-
riables auxiliaires
u ≥ 0, v ≥ 0, u − v = Ax − b.
On obtiens ainsi le programme
 
Xm 
min (ui + vi) : Ax − b = u − v, u ≥ 0, v ≥ 0
 
i=1

• PL en notation matricielle : min{c̃T x̃ : Ãx̃ ≤ b̃}, avec

       
x 0 A −I I b
       
x̃ =  u  , c̃ =  1  , Ã =  0 −I 0  , b̃ =  0  .
v 1 0 0 −I 0

- 83 -
Application statistique : régression robuste
Étant données les observations {xi ∈ Rn, yi ∈ R}m
i=1 dans le modèle

yi = θ∗T xi + ξi [ξi : bruit d’observation]

on cherche à retrouver le vecteur de paramètres θ∗.
Dans le cas m n, une approche classique pour estimer θ∗ consiste à se donner une
“fonction de perte” φ(u, v) et de choisir l’estimation θb de θ∗ qui minimise en θ l’erreur
de prediction

T T
φ [y1; ...; ym], [θ x1; ...; θ xm]

des sorties observées par les sorties du modèle z = θT x, appliqué aux régresseurs
observés x1, ..., xm.
• En notant X = [xT T T
1 ; x2 ; ...; xm ] la matrice de régresseurs, la procédure d’estimation
s’écrit
θb ∈ Argmin φ(y, Xθ) [y = [y1; ...; ym]]
θ
(notation Argminx f ⇔ ensemble de minimiseurs de f en x).

- 84 -
• Le choix de la perte φ(·, ·) dépend de la distribution de bruit ξ.
La perte couramment utilisées est la perte quadratique φ(u, v) = ku − vk2, corres-
pondant au cas du bruit blanc normal (ξi ∼ N (0, σ 2) sont indépendants) ou, plus
généralement, au cas e ξi i.i.d. avec la moyenne nulle et la variance finie
P
⇒ méthode de moindres carres min m i=1 (yi − x T θ)2 .
i
θ

Dans certains cas l’estimation se réduit au problème OL :

— régression `∞ : φ(u, v) = ku − vk∞ := max |ui − vi|, on doit résoudre

i
( )
min max |yi − xT T
i θ| ⇔ min τ : max |yi − xi θ| ≤ τ (`∞)
θ 1≤i≤m θ,τ 1≤i≤m

- 85 -
Comment ça Comparison
marche – comparaison avec les moindres
with least-squares carrés
solution
Soit A ∈ R200×80, b ∈ R200 matrices aléatoires, et soit
histograms of residuals Ax − b, with randomly generated A ∈ R200×80, for
x`s ∈ Argmin kAx − bk2, x`1 ∈ Argmin kAx − bk1.
x x
xls = argmin kAx − bk, xℓ1 = argmin kAx − bk1

0
1.5 1.0 0.5 0.0 0.5 1.0 1.5

(Axls − b)k
100

0
1.5 1.0 0.5 0.0 0.5 1.0 1.5

(Axℓ1 − b)k
ℓ1-norm distribution is wider with a high peak at zero
- 86 -
Piecewise-linear optimization 2–11
Comment ça marche – Robust curve
régression fitting
simple
• fit affine function f (t) = α + βt to m points (ti, yi)
—
• anmapproximation
observations bruit ées (t
problem Axi, y
≈i)b de la fonction affine f (t) = α + βt
with
— Problème à résoudre : min
 kAx − bk avec  
1 t1 y1
α 
A =  .. "..  ,# x = 1 ,t1 b =  "..  #
α β  y
x1=tm , A =  ... ...  , b =ym .. 1 .
β .ym
1 tm
25
20
15 • •dashed:
en pointillé : min
minimize x kAx
kAx − bk− bk2
10 • en continu : minx kAx − bk1
5 • solid: minimize kAx − bk1
f (t)

0 ⇒ régression `1 est plus robuste par rap-

5 ℓ1-norm approximation is more
port against
aux observation
outliers aberrantes

10 robust

20 10 5 0 5 10

Piecewise-linear optimization 2–12

- 87 -
Application statistique : acquisition compressée (Compressed Sensing)
Nous avons une observation m-dimensionnel
y = [y1; ...; ym] = Xθ∗ + ξ
[X ∈ Rm×n : matrice d’acquisition, ξ : bruit d’observation]
d’un “signal” inconnu θ∗ ∈ Rn avec m n, et on cherche à estimer θ∗.
On s’interesse ici au cas m n, quand le système soluble

Xθ = y
en variables θ possède l’infinité de solutions
⇒ Même sans bruit d’observation, on ne peut pas identifier θ∗ sans hypothèses supplé-
mentaires.
• En Compressed Sensing (acquisition compressée) on suppose que θ∗ est creux — ait
au plus s m coefficients non-nuls.

- 88 -
Remarque : soit ξ = 0, et soit toute sous-matrice m × 2s de X de rang 2s (ce
qui est souvent le cas quand m 2s). Alors θ∗ est la solution optimal du problème
d’optimisation

min {kθk0 : Xθ = y} [kθk0 = Card{j : θj 6= 0}] (`0)

θ
Mauvaise nouvelle : (`0) est un problème combinatoire difficile.
• Un remède partiel : on remplace l’objectif “difficile” kθk0 par un objective “facile :”
X
kθk1 = |θi|,
i
et on arrive au problème de minimisation de la norme `1 :

θb = argmin {kθk1 : Xθ = y}
θ  
X 
⇔ min zj : Xθ = y, −zj ≤ θj ≤ zj ∀j ≤ n .
θ,z  j 

- 89 -
Comment ça marche – acquisition compressée
Example
Example
• signal exacte x∗ ∈ R1000, 2

2
1
10 coefficients non-nuls
1000
exact •signal x̂ ∈ R
exact signal x̂ ∈ R1000
1

x̂k
0

x̂k
• matrice A ∈ R100×1000 aléatoire,
0

10 nonzero components
• 10 nonzero components −1 −1

cas sans bruit b = Ax∗ −2

−2
0 200 400 600 800 1000
0 200 k 400 600 800 1000
k
100×1000
least-norm solutions (randomly generated A ∈ R )
100×1000
ast-norm solutions (randomly generated A
minimum ℓ -norm solution
∈R
minimum ℓ -norm solution
)
2 1

2 2
minimum ℓ2-norm solution minimum ℓ1-norm solution
1 1
2 2
xk

xk
0 0

1 1
−1 −1
xk

xk
0 −2 −2 0

0 200 400 600 800 1000 0 200 400 600 800 1000
−1 k −1 k

−2
ℓ1-norm estimate is exact - 90 - −2

Piecewise-linear
0 200 optimization
400 600 800 1000 0 200 400 600 800 2–14 1000
k k
• Quand l’observation est bruitée, c.-à-d. que

y = Xθ∗ + ξ,
et on connaı̂t une borne δ de norme kξk du bruit, l’estimateur de θ∗ par minimisation
de la norme `1 devient

θb ∈ Argmin {kθk1 : kXθ − yk ≤ δ} .

θ
Un autre estimateur
n o
T
θ̂DS ∈ Argmin kθk1 : kX (Xθ − y)k∞ ≤ δ .
θ
par “Dantzig Selector” de θ∗, est la “composante θ” de solution optimale du programme
OL :
( )
X −δ ≤ [X T (Xθ − y)]i ≤ δ ∀i ≤ m
Argmin z :
j j
.
θ, z −zj ≤ θj ≤ zj , zj ≥ 0 ∀j ≤ n

- 91 -
Comment ça marche – Dantzig Selector
• matrice A ∈ R200×500 aléatoire, σ = 0.25

true x observation

1.0
0.8

0.5
0.0
x0

y
0.4

−0.5
0.0

0 100 200 300 400 500 0 50 100 150 200

j j

minimum l_2−norm solution minimum l_1−norm solution

1.2
0.1 0.2 0.3

0.8
x

0.4
0.0
−0.1

0 100 200 300 400 500 0 100 200 300 400 500

j j

- 92 -
Application statistique : classification linéaire
— Étant donné un ensemble de points v1, ..., vm avec les etiquettes si ∈ {−1, 1}
— trouver un hyperplan αT x + β tels que les points avec les etiquettes “+1” et “-1”
se trouvent dans les deux demi-espaces différents
3 αT vi + β > 0 si si = 1, αT vi + β < 0 si si = −1

3
2

2
X2

X2
1

1
0

0
−1

−1
−1 0 1 2 3 −1 0 1 2 3

X1 X1

Note : un plan de separation satisfait si(β + αT vi) > 0, ∀i.

- 93 -
Remarque : les inégalités sont homogènes en α, β, et donc équivalentes aux inégalités
linéaires (en α, β)
sT T
i (α vi + β) ≥ 1 ∀i.
Dans le cas de points “non séparables,” on peut chercher un classifieur qui minimise le
coût
 
Xm 
min max{0, 1 − si(αT vi + β)}
 
i=1
— la quantité
hi = max{0, 1 − si(αT vi + β)}
(hinge loss) peut être vue comme une pénalité pour la mauvaise classification
P
— hi est une borne supérieure pour le nombre de points “mal classés.”

- 94 -
• PL équivalent en variables α ∈ Rn, β ∈ R et variable auxiliaire u ∈ Rm :
 
Xm 
1 − si(viT α + β) ≤ ui i = 1, ..., m
min ui :
 0 ≤ ui, i = 1, ..., m 
i=1

• PL en notation matricielle : min{cT x : Ax ≤ b}, avec

 
−s1 v1T −s1 −1 0 ... 0  
−1
   
 −s2 v2T −s2 0 −1 ... 0  ...
 ... ... ... . . . ...   
α 0    
   −1 
x =  β , c =  0 , A =  −sm vm T −sm 0 0 ... −1 , b =  .
   0 
u 1  0 0 −1 0 ... 0   ... 
 ... ... ... . . . ... 
0
0 0 0 0 ... −1

- 95 -
Logiciels
Les logiciels d’optimisation peuvent être classés en 2 groupes :
• “Solveurs” – moteurs d’optimisation, commerciaux (Mosek, CPLEX, Gurobi, ...)
ou libres (GLPK, LP Solve, SDPT3, ...) – ce sont eux qui, proprement dit, résolvent
des problèmes d’optimisation.
Un solveur accepte en entrée un problème d’optimisation dans un format special (propre
à chaque solveur), pour rendre à la sortie une solution, si le problème en question est
soluble, ou décide que le problème n’est pas soluble et produit un certificat pour justifier
cette décision.

Certains moteurs d’optimisation sont interfacé avec R. Dans ce cours vous allez utiliser
RMosek – l’interface R du moteur Mosek (logiciel commercial, disponible gratuitement
pour les universitaires) https ://www.mosek.com/

- 96 -
• Outils de modélisation – “modeleurs”, dont le but est de simplifier la formulation et
analyse d’un problème d’optimisation. En ce qui concerne les problèmes équivalents aux
programmes OL, ces outils peuvent
— accepter le problème dans une forme standard simplifiée
(e.g., avec les max, k · k1, k · k∞, etc)
— reconnaı̂tre les problèmes qui peuvent être convertis en OL
— transformer le problème dans le format accepté par le moteur d’optimisation utilisé

Les outils de modélisations sont disponibles sous différentes formes et en différents lan-
gages de programmation :
— AMPL, GAMS (outils autonomes)
— CVX, YALMIP (MATLAB)
— CVXPY, CVXOpt, Pyomo (Python)
— CVXR (R)

- 97 -
CVXR exemple

min {kxk1 : kAx − bk∞ ≤ r, kxk∞ ≤ s} .

> library(mvtnorm)
> n=500; p=50; sig=0.01;epsn=0.01;s=2;
> r=qnorm(1-epsn/n)*sig;
> S=0.5^toeplitz(1:p)
> A=rmvnorm(n, sigma = S)
> b=apply(A[,1:5], 1, sum) + sig*rnorm(n)
# CVXR proprement dit
> library(CVXR)
> x=Variable(p)
> constraints=list(p_norm(x, Inf)<=s, p_norm(b-A%*%x, Inf)<=r)
> prob=Problem(Minimize(p_norm(x,1)), constraints)
> result=solve(prob)
> x=result$getValue(x)
> plot(x)

- 98 -
RMosek Moteur “commercial” (accès gratuit pour les etudiants)
• Format standard RMosek :
— variable x ∈ Rn,
— matrice de contraintes A ∈ Rm×n
— objectif c ∈ Rn,
— bornes inférieure `c et supérieure uc de contraintes
— bornes inférieure `x et supérieure ux de x

minimize cT x
subject to `c ≤ Ax ≤ uc,
`x ≤ x ≤ ux
Manuel d’utilisateur RMosek : http ://rmosek.r-forge.r-project.org/

- 99 -
Utilisation de RMosek

• Problème de régime McDonald’s optimal :

“En mots :” minimizer les calories

sous contraintes des nutriments


Xn
min cj x j :
x 
j=1
Pn 

j=1 pij xj ≥ bi , i = 1, ...m,
Pn


j=1 pij xj ≤ bi , i = 1, ...m, 


xj ≥ 0, 1 ≤ j ≤ n

Ou encore :
min{cT x : b ≤ Ax ≤ b, x ≥ 0},
ou A ∈ Rm×n est la matrice avec les éléments [A]ij = pij , 1 ≤ i ≤ m, 1 ≤ j ≤ n.

- 100 -
> foods=read.table("food.dat", header=T) #Lecture des donnees
> foods[1:4,]
Food Cal CalFat Fat SatFat Chol Sodium Carbo Protein Vi
1 1%_Low_Fat_Milk_Jug 1_carton_(236_ml) 100 20 2 1 10 125 12 8
2 Apple_Slices 1.2_oz_(34_g) 15 0 0 0 0 0 4 0
3 BBQ_Ranch_Burger 4.1_oz_(116_g) 350 140 16 6 45 680 37 16
4 Bacon,_Egg_&_Cheese_Bagel 7_oz_(199_g) 630 290 32 11 275 1490 57 30
>
> fnames=foods[,1]
> nutr.norm=read.table("nutr_ideal.dat", header=T)
> names(nutr.norm)
[1] "Cal" "CalFat" "Fat" "SatFat" "Chol" "Sodium" "Carbo" "Protein" "VitA"
[11] "Calcium" "Iron"
>
> diet1 = list() # creation du probleme
> diet1$sense = "min" # definir le sens d'optimisation
> diet1$c = as.matrix(foods[,2]) # definir l'objectif: la valeur calorique
> A = t(as.matrix(foods[,3:13])) # definir la matrice des contraintes
> diet1$A = Matrix(A,sparse=TRUE)
> b = as.matrix(nutr.norm[2:12]) # definir les bornes admissibles
> blc = 0.8*b; buc=1.2*b; # pour les nutriments
> diet1$bc = rbind(blc, buc);
> blx = rep(0,305); bux <- rep(Inf,305); # contraintes de non-negativite
> diet1$bx = rbind(blx, bux);
> r = mosek(diet1)

Computer
Platform : Windows/64-X86
Cores : 1

Problem
Name :
Objective sense : min
Type : LO (linear optimization problem)
Constraints : 11
Cones : 0
Scalar variables : 305
Matrix variables : 0
Integer variables : 0

Optimizer started.
Interior-point optimizer started.
Presolve started.
...

Factor - nonzeros before factor : 66 after factor : 66

Factor - dense dim. : 0 flops : 3.18e+004
ITE PFEAS DFEAS GFEAS PRSTATUS POBJ DOBJ MU TIME
0 2.4e+002 6.6e+000 6.5e+002 2.26e+000 1.372955304e+005 0.000000000e+000 2.3e+000 0.00
1 2.2e+002 8.2e+000 6.6e+002 0.00e+000 1.418094583e+005 1.664025593e+003 7.4e+000 0.00
2 1.3e+001 4.6e-001 3.7e+001 -8.43e-001 5.591419263e+004 2.518824208e+003 4.2e-001 0.00
3 4.2e+000 1.6e-001 1.3e+001 9.61e-001 1.568108462e+004 2.162233225e+003 1.4e-001 0.00
4 2.4e+000 8.9e-002 7.2e+000 2.87e+000 6.625715907e+003 2.275951097e+003 8.1e-002 0.00
5 1.4e+000 5.2e-002 4.2e+000 2.90e+000 3.387566741e+003 2.192592773e+003 4.7e-002 0.00
6 8.4e-001 3.1e-002 2.5e+000 2.10e+000 2.434783666e+003 1.883464080e+003 2.8e-002 0.00
7 4.5e-001 1.7e-002 1.3e+000 1.43e+000 1.899310800e+003 1.640642415e+003 1.5e-002 0.00
8 2.1e-001 7.8e-003 6.3e-001 1.15e+000 1.573381052e+003 1.455345733e+003 7.0e-003 0.00
9 2.7e-002 9.8e-004 7.9e-002 1.23e+000 1.366259235e+003 1.352122956e+003 8.9e-004 0.00
10 5.5e-004 2.0e-005 1.6e-003 9.99e-001 1.335288862e+003 1.334995770e+003 1.8e-005 0.00
11 8.6e-007 3.2e-008 2.5e-006 1.00e+000 1.334857456e+003 1.334857002e+003 2.8e-008 0.00
12 8.6e-011 3.2e-012 2.5e-010 1.00e+000 1.334856193e+003 1.334856193e+003 2.8e-012 0.00

Basis identification started.

...
Optimizer terminated. Time: 0.00

Interior-point solution summary

Problem status : PRIMAL_AND_DUAL_FEASIBLE
Solution status : OPTIMAL
Primal. obj: 1.3348561927e+003 Viol. con: 7e-008 var: 0e+000
Dual. obj: 1.3348561929e+003 Viol. con: 4e-010 var: 6e-010

...
> x=r$sol$itr$xx # extraire la solution x
> t(diet1$c)%*%r$sol$itr$xx #valeur optimale c^Tx --la valeur calorique du regime
[,1]
[1,] 1334.856
>
...
> mydiet # impression du contenu de regime
[1] "Chocolate_Chip_Cookie 1_cookie_(33_g): 0.699908803471238"
[2] "EQUAL_0_Calorie_Sweetener 1_pkg_(1.0_g): 84.2645722693934"
[3] "Fat_Free_Chocolate_Milk_Jug 1_carton_(236_ml): 0.898566545455502"
[4] "Hamburger 3.5_oz_(100_g): 2.14750840210163"
[5] "Sausage_Burrito 3.9_oz_(111_g): 1.35453792177156"
[6] "Side_Salad 3.1_oz_(87_g): 1.98962488832494"
>

On peut ajouter des contraintes pour rendre le menu “mangeable,” par exemple

> bux=rep(10,n); % quantite de tous les produits ne depasse pas 10

et ainsi de suite...
Definitions
Programmation en nombres entiers
integer linear program (ILP)
• Définitions
— (PLE) – programme linéaire en nombres entiers
T (Integer Linear program, ILP)
minimize c x
min{csubject to ≤Ax
T x : Ax ≤ ∈b Zn}
b, x
x
x ∈ Zn

— mixed
(PLEM)integer
– programme
linearlin éaire d’entiers
program: only mixte
some (Mixed Integer Linear
of the variables program) :
are integer
certaines variables (mais pas toutes) sont des entiers
— 0-1
(PLB)(Boolean)
– programme linear program:
lineaire booléenvariables take Linear
(0-1, Boolean values program)
0 or 1 : variables à
valeurs dans {0, 1}
Integer linear programming - 101 - 18–2
Exemples
• Probleme d’emplacement
— n emplacement possibles pour les installation industrielles avec coût d’emplace-
ment cj
— m clients
— dij le coût de service du client i de l’emplacement j

Variables yj , xij :
— yj = 1 si l’emplacement j est sélectionné et 0 sinon
— xij = 1 si l’emplacement j sert le client i et 0 sinon

Formulation booléenne :
 Pn 

Xn m X
X n j=1 xij = 1, i = 1, ..., m 

min cj yj + dij xij : xij ≤ yj , i = 1, ..., m, j = 1, ..., n

j=1 

i=1 j=1 xij , yj ∈ {0, 1}

- 102 -
• L’exemple le plus connu d’un problème difficile – problème du voyageur de commerce :
– étant donnés n sites, déterminer l’ordre dans lequel les visiter pour minimiser la distance
totale parcourue

Pour n cites il y a n! parcours possibles ( !)

n n! n4 2n

7 5040 2401 128

8 40320 4096 256
... ... ...
20 2.4329e+18 160 000 1048576
... ... ...
40 8.1592e+47 2 560 000 1.0995e+12

- 103 -
13509 villes aux États-Unis

(Applegate, Bixby, Chvatal & Cook, 1998), algorithme spécialisé

Voir article NY Times “Le probleme du politicien voyageur” pour Iowa (99 contés)
https ://campaignstops.blogs.nytimes.com/2011/12/21/the-problem-of-the-traveling-politician/

- 104 -
Relaxation par PL
Probleme general de programmation en nombres entiers :
Linear programming
T
relaxation
min{c x : Ax ≤ b, x est un entier}
x
⇒ (relaxation) n
relaxation: remove the constraints
T
x ∈ Z
min{c x : Ax ≤ b, x est un entier}
x
• provides a lower
— Permet bound
d’obtenir on the
une borne intéoptimal value
rieure sur la valeurof the integer
optimale du PLE LP
— Si la solution est en nombres entiers, c’est aussi la solution du PLE
• if solution of relaxation is integer, then it solves the integer LP
— Attention : on peut avoir des formulations relaxées différentes pour le même PLE

c c

- 105 -
equivalent ILP formulations can have different LP relaxations
minimize −2x1 − 3x2
subject to (x1, x2) ∈ P
Exemple
where
2 1 1
P = {x ∈ Z2+ | x1 + x2 ≤ 1, x1 +
9 4 7

x2 −c
 
 2x + 1x ≤ 1 

 9 1 4 2 


 1 1 

 
x1 + x2 ≤ 1
min −2x1 − 3x2 :
x 
 |7 3
{z } 
 optima

 x∈X 


 

x1, x2 ∈ Z+
x1

Optimal solution : [2; 2]

Integer linear programming

- 106 -
Methode de séparation
tree of subproblems and et d’évaluation
results progressive (Brunch and Bound)
of LP relaxations
x∗ Opt

x1 ≤ 2
P0
x1 ≥ 3
P0 [2.17x;⋆ 2.07] p⋆
-10.56
P1P0 (2.17,
[2.00 ;2.07)
2.14] −10.56
-10.43
P1 P2
P2P1 (2.00,
[3.00 ;2.14)
1.33] −10.43
-10.00
x2 ≤ 2 x2 ≥ 3 x2 ≤ 1 x2 ≥ 2 P3P2 (3.00,
[2.00 ;1.33)
2.00] −10.00
-10.00
−10.00
P3 P4 P5 P6 P4P3 (2.00, 2.00)
[0.00 ; 3.00] -9.00
P4 (0.00, 3.00) −9.00
x1 = 3 x1 ≥ 4
P5P [3.38 ; 1.00]
(3.38, 1.00)
-9.75
−9.75
5
P6P6 +∞
+∞
P7 P8
P7P7 [3.00 ;1.00)
(3.00, 1.00] -9.00
−9.00
x2 = 0 x2 = 1 P8P8 [4.00 ;0.44)
(4.00, 0.44] -9.33
−9.33
P9 P10 P9P9 (4.50,
[4.50 ;0.00)
0.00] −9.00
-9.00
x1 = 4 x1 ≥ 5
PP10
10 +∞
+∞
PP11
11 (4.00,
[4.00 ;0.00)
0.00] −8.00
-8.00
PP12 +∞
P11 P12 12
+∞

Integer linear programming 18–7

- 107 -
Séparation et évaluation
⇒ P2 : min cT x sous contrainte x ∈ X et x1 ≥ 3
valeur optimale ≥ −10.00
⇒ P3 : min cT x sous contrainte x ∈ X, x1 ≤ 2, et x2 ≤ 2
solution x = [2; 2], valeur optimale Opt = −10
...
⇒ P6 : min cT x sous contrainte x ∈ X, x1 ≥ 3, x2 ≥ 2
problème irréalisable
...

Apres avoir résolu les relaxations pour P0, P1, P2, P3, P4 on peut déduire que [2; 2]
est la solution optimale du PLE

- 108 -
Utilisation du solveur d’entiers mixte (MIP) de Mosek
• il suffit de déclarer pour RMosek des variables entières :
— le vecteur intsub doit contenir les indices des variables entières
— variables booléennes, x ∈ {0, 1}, doivent être déclarer comme entières et satis-
faisant la contrainte 0 ≤ x ≤ 1

Par exemple, dans le problème de regime McDonald’s, pour convertir les variables en
entiers, il suffit de faire

> diet4=diet3
> diet4$intsub=c(1:305)
> r = mosek(diet4)

Computer
Platform : Windows/64-X86
Cores : 1

Problem
Name :
Objective sense : min
Type : LO (linear optimization problem)
Constraints : 12
- 109 -
Cones : 0
Scalar variables : 305
Matrix variables : 0
Integer variables : 305

Optimizer started.
Mixed integer optimizer started.
Optimizer - threads : 1
0 1 0 NA 1.5106771305e+003 NA 0.0
0 2 0 NA 1.5222410122e+003 NA 0.0
...
405 366 10 1.5950000000e+003 1.5800000000e+003 0.94 0.2
415 371 0 1.5950000000e+003 1.5950000000e+003 0.00e+000 0.2
An optimal solution satisfying the absolute gap tolerance of 0.00e+000 has been located.
The absolute gap is 0.00e+000.

Objective of best integer solution : 1.595000000000e+003

Best objective bound : 1.595000000000e+003
Construct solution objective : Not employed
Construct solution # roundings : 0
User objective cut value : 0
Number of cuts generated : 5
Number of branches : 415
Number of relaxations solved : 371
Number of interior point iterations: 15
Number of simplex iterations : 999
Time spend presolving the root : 0.00
Time spend in the heuristic : 0.00
Time spend in the sub optimizers : 0.00
Time spend optimizing the root : 0.02
Mixed integer optimizer terminated. Time: 0.19

Optimizer terminated. Time: 0.19

Integer solution solution summary

Problem status : PRIMAL_FEASIBLE
Solution status : INTEGER_OPTIMAL
Primal. obj: 1.5950000000e+003 Viol. con: 0e+000 var: 0e+000 itg: 0e+000
Optimizer summary
...
Mixed integer - relaxations: 371 time: 0.19

...

> t(diet4$c)%*%r$sol$int$xx
[,1]
[1,] 1595
> mydiet
[1] "Chocolate_Chip_Cookie 1_cookie_(33_g): 4"
[2] "Coffee_(Large) 16_fl_oz_cup: 10"
[3] "Coffee_(Medium) 16_fl_oz_cup: 10"
[4] "Coffee_(Small) 12_fl_oz_cup: 10"
[5] "Diet_Coke_(Medium) 21_fl_oz_cup: 10"
[6] "EQUAL_0_Calorie_Sweetener 1_pkg_(1.0_g): 10"
[7] "Egg_McMuffin 4.8_oz_(135_g): 1"
[8] "Fat_Free_Chocolate_Milk_Jug 1_carton_(236_ml): 1"
[9] "Hamburger 3.5_oz_(100_g): 1"
[10] "Newman's_Own_Low_Fat_Balsamic_Vinaigrette 1.5_fl_oz_(44_ml): 1"
[11] "SPLENDA_No_Calorie_Sweetener 1_pkg_(1.0_g): 10"
[12] "Side_Salad 3.1_oz_(87_g): 2"
[13] "Strawberry_Banana_Smoothie_(Small) 12_fl_oz_cup: 1"
2ème partie : Optimisation non-linéaire

Programme mathématique générale

minimiser f (x) [fonction objective]
sous contraintes
hi(x) = 0, i = 1, ..., m [contraintes d’égalité] (PM)
gj (x) ≤ 0, j = 1, ..., k [contraintes d’inégalité]
x∈X [domaine du problème]
Remarque : les contraintes dans le système sont toujours liées par “et” – une solution
réalisable doit satisfaire toutes les contraintes :
 
 ≥ 
x = [x1; ...; xn] : gi(x) = bi pour tout i = 1, ..., m,
 ≤


- 110 -
• Ainsi, le problème
n o
min x1 + x2 : x
| 1 − {z
x2 − 3} ≤ 0 ou |sin(x
{z 1 )} ≤ 0
x=[x1 ;x2 ]
g1 (x) g2 (x)
n’est pas dans le format de programme mathématique.
• La forme éligible de ce problème serait, par exemple,
n o
min x1 + x2 : min[x
|
− 3, sin(x1)]} ≤ 0
1 − x2{z
x=[x1 ;x2 ]
g(x)
En effet, dire que
g1(x) ≤ b1 ou g2(x) ≤ b2 ou ... ou gm(x) ≤ bm
est exactement le même que de dire

g(x) := min [g1(x) − b1, g2(x) − b2, ..., gm(x) − bm] ≤0.
Par contre, dire
g1(x) ≤ b1 et g2(x) ≤ b2 et ... et gm(x) ≤ bm
est exactement le même que de dire

g(x) := max [g1(x) − b1, g2(x) − b2, ..., gm(x) − bm] ≤0.

- 111 -
Remarque : (Presque) tout problème en mathématique appliquée peut être exprimée
comme un problème de programmation mathématique. ⇒ De façon générale, un pro-
blème de programmation non-linéaire est difficile – on ne peut pas espérer de le résoudre
en un temps raisonnable.

Question : Alors comment peut-on traiter des problems avec des dizaines de milliers de
variables et de contraintes avec une grande precision ?
Réponse : L’idee serait d’utiliser la structure du problème. Une structure favorable
permet d’utiliser l’information local sur l’objectif et les contraintes pour inférer sur une
solution globalement optimale.
Une “structure favorable” standard est celle de convexité.

- 112 -
Optimisation convexe

Problème générale de programmation convexe

minimiser f (x) [fonction objective]
sous contraintes
(PC)
gj (x) ≤ 0, j = 1, ..., k [contraintes d’inégalité]
x∈X [domaine du problème]
où
— f, g1, ..., gm sont des fonctions convexes
— X ⊂ Rn est un ensemble convexe.

Remarque : il n’y a pas de contraintes d’égalité ( !)

Autrement dit, les seules contraintes d’égalité autorisées sont les contraintes linéaires
aT x − b = 0, facilement transformables en contraintes d’inégalité avec des fonctions
linéaires (donc convexes)

aT x − b ≤ 0, −aT x + b ≤ 0.

- 113 -
Ensembles convexes : définitions
Ensemble X ⊂ Rn est dit convexe si avec tout point x, y, il contient le segment entier
qui les joint :
x, y ∈ X, λ ∈ [0, 1] ⇒ (1 − λ)x + λy ∈ X.
Définition équivalente : X ∈ Rn est convexe, si X contient toute combinaison
convexe de ses éléments (i.e., combinaison linéaire avec des coefficients non-négatifs
dont la somme fait 1) :
k
X k
X
x1, ..., xk ∈ X ⇒ λixi ∈ X ∀λ ≥ 0 tel que λi = 1.
i=1 i=1
Exemple : un ensemble polyédrique X = {x ∈ Rn : Ax ≤ b} est convexe. ⇒
sous-espaces linéaires et affines sont des ensembles convexes.
En effet, x ∈ X, y ∈ X ⇔ Ax ≤ b, Ay ≤ b.
Alors pour tout 0 ≤ λ ≤ 1 et z = λx + (1 − λ)y,

Az = A[λx+(1−λ)y] = λAx+(1−λ)Ay ≤ λb+(1−λ)b = b ⇒ z ∈ X.

- 114 -
f : Rn → R is convex if dom f is a convex set and
Fonctions convexes : définitions
Fonction f : Rn →f (θx (1 −
R est+dite θ)y) ≤
convexe si θf (x)tout
pour x, y−et
+ (1 θ)f
λ (y)
∈ [0, 1],

for all x, y ∈ dom 0≤

f, −
f ((1 θ≤
λ)x + 1λy) ≤ (1 − λ)f (x) + f (λy).

(y, f (y))
(x, f (x))

f : Rn → R est dite concave si −f est convexe.

• f is concave if −f is convex
Exemples
• f is strictly convex if dom f is convex and
— fonction affine ax + b sur R est convexe (et concave)
— fonction affinefa(θx T x + b sur Rn est convexe (et concave)
+ (1 − θ)y) < θf (x) + (1 − θ)f (y)
ax
— fonction e est convexe pour tout a ∈ R
for
— x, y ∈ dom
fonction 6= y, 0 <
xlogxf ,estx convexe surθR<
+∗1
— fonction kxk2 est convexe sur Rn
— ...
Convex functions 3–2

- 115 -
sublevel sets of convex functions are
n convex (converse is false)
Épigraphe d’une fonction Soit f : R → R, l’ensemble
epigraph of f : Rn → R:
Epi f = {[x; τ ] ∈ Rn : f (x) ≤ τ }
epi f = {(x, t) ∈ Rn+1 | x ∈ dom f, f (x) ≤ t}
s’appelle épigraphe de f .
epi f

Définition équivalente
f is convex : Une
if and only fonction
if epi f (x) :setRn → R ∪ {+∞} est convexe,
f is a convex
si et seulement si son épigraphe Epi f est un ensemble convexe.
Convex functions 3–11

Exemple La fonction linéaire par morceaux


 max[aT x + b ], si P x ≤ p
i i
f (x) = i
 +∞, sinon
est convexe.
En effet, l’épigraphe de f ,

Epi f = {[x; t] ∈ Rn : P x ≤ p, t ≥ aT
i x + bi , ∀i}
est un ensemble polyédrique. - 116 -
Inégalité de Jensen
Convexité :
∀λ ∈ [0, 1], f ((1 − λ)x + λy) ≤ (1 − λ)f (x) + f (λy) (∗)
Généralisation : si f est convexe, alors pour tout x et λ1, ..., λm tels que
m
X
λi ≥ 0 ∀i, λi = 1,
i=1
nous avons
 
m
X m
X
f λixi ≤ λif (xi)
i=1 i=1
(verification en utilisant la caractérisation de convexité par épigraphe).
En particulier, soit f convexe, alors
f (E(Z)) ≤ E(f (Z))
pour tout vecteur aléatoire Z sur Rn.
L’inégalité (∗) “à 2 points” correspond à cas de la loi discrète telle que
Prob{Z = x} = λ, Prob{Z = y} = 1 − λ.
- 117 -
Rôle de la convexité
On considère le problème minx∈X f (x) de minimisation d’une fonction f différentiable
sur un domaine simple, e.g., une “boite” n-dimensionnelle
X = {x ∈ Rn : −1 ≤ xi ≤ 1, i = 1, ..., n}.
• Pour f différentiable, la convexité est définie comme la propriété de f de dominer ses
linéarisations :
f (y) ≥ f (x) + [∇f (x)]T (y − x)
P ∂f (x)
:= f (x) + n i=1 ∂x (yi − xi ) for all x, y
i
f(x)

x
a

- 118 -
Soit f : [−1, 1] → R.
• Si nous avons calculé f and f 0 en a ∈ [−1, 1], et f 0(a) < 0
⇒ à gauche de a, la linéarisation de f est > f (a)
⇒ a gauche de a, f elle-même est > f (a)
⇒ on peut réduire le domaine du problème en éliminant tous les points < a !
• Le schéma des“coupes”peut être généralisé aux problèmes convexes multi-dimensionnels
(i.e., avec l’objectif et les contraintes convexes).
Remarque : la convexité de f est cruciale dans ce cas. Par exemple, en cas de la fonc-
tion f non convexe
f(x)

b c

l’information locale autour de c ne dit rien sur la position du minimum global et ne

permet pas d’éliminer une partie “massive” du domaine.
- 119 -
Reconnaı̂tre fonctions convexes I
• Critère différentiel, fonctions d’une variable
— fonction differentiable f : R → R est convexe ssi sa dérivée f 0(x) est monotone
non-décroissante : x1 ≤ x2 ⇒ f 0(x1) ≤ f 0(x2)
— fonction 2 fois differentiable f : R → R est convexe ssi sa dérivée seconde
f 00(x) est non-négative : f 00(x) ≥ 0 ∀x ∈ R.

• Fonctions de n variables :
fonction f : Rn → R 2 fois differentiable est convexe ssi sa matrice
hessienne est semi-définie positive pour tout x : ∇2f (x) 0, ∀x ∈ Rn
(toutes les valeurs propres de ∇2f (x) sont non négatives).

- 120 -
∇f (x) = P x + q, ∇ f (x) = P

if P Exemples
0
2 T
squares• objective: (x)kAx
f (x)f=
Fonction quadratique = 12 x−
T Pbk
x+2 q x + r avec

T ∇f = P x + q,2 ∇2f = P,
∇f (x) = 2A (Ax − b), ∇ f (x) = 2AT A
est convexe sur Rn ssi P 0 (P est semi-définie positive)
(for any A)
• Fonction quadratique-sur-linéaire
atic-over-linear:f (x,
f (x,
y) =y)x= x2/y
2 /y,
2
" #

f (x, y)
(x, y)= 1 2xy
∇f T2 , 1
2 y y y −x
2
f (x, y) = 3 0
y −x " −x# " #T 0
2 y y 2 2
∇2f (x, y) = 3 0 1 0
y −x −x
for y > 0 y 0 −2 x
est convexe pour x ∈ R et y > 0
ctions 3–9

- 121 -
Reconnaı̂tre fonctions convexes II : opérations qui préservent la convexité
• multiplication par un réel non-négatif : si f est convexe, α ≥ 0, alors αf est convexe
• somme : si f1, f2 sont convexes, f1 + f2 est convexe (ainsi que α1f1 + α2f2 pour
α1, α2 ≥ 0)
• composition avec une fonction affine : si f est convexe, f (Ax + b) l’est aussi
Exemples
— fonction kAx + bk2
P
— fonction i exp(aT i x + bi )
— fonction “barrière”
m
X
f (x) = − log(bi − aT
i x)
i=1
définie sur Domf = {x ∈ Rn : Ax<b}
— ...

- 122 -
• Maximum “point par point :” si f1, ...fm sont convexes, alors la fonction
f¯(x) = max{f1(x), ..., fm(x)}
est convexe.
Exemples
— fonction linéaire par morceaux f (x) = maxi(aT i x + bi ), et donc la fonction
(valeur absolue) |x| = max{x, −x}
— la norme kxk∞ = maxi |xi|
P
— la norme kxk1 = n i=1 |xi |
• Supremum par point : si fα(x) est convexe en x pour tout α ∈ A, la fonction

f¯(x) = sup fα(x)

α∈A
est convexe.
Exemple : la plus grande valeur propre λmax(A) d’une matrice symétrique A,

λmax(A) = sup y T Ay
y: kyk2 =1

- 123 -
• Superposition convexe-monotone : Soit
— gi(x) : Rn → R fonctions convexes
— F (y) : Rm → R fonction convexe et monotone non-décroissante en tout
y1, ..., ym :
y 1 ≤ y 2 ⇒ F (y 1) ≤ F (y 2)
Alors, la fonction composée (la superposition de F et g1, ..., gm)

f (x) = F (g1(x), ..., gm(x))

est convexe.

• ...

- 124 -
Illustration : soit g1, ..., gm fonctions convexes non-négatives, et soit F (y1, ..., ym) =
Pm 2
i=1 yi . Pm
Fonction f (x) = F (g1(x), ..., gm(x)) = 2
i=1 gi (x) est-elle convexe ?
• La propriété de superposition n’est pas applicable directement, car F n’est pas mono-
tone.
• Néanmoins, sur l’orthant non-négatif Q = {y : y ≥ 0}, F est monotone, et comme
toutes les gi sont non-négatives, on peut appliquer ce résultat pour montrer que f est
convexe.
Remarque : la non-négativité des gi est importante. Le carré d’une fonction convexe
n’est pas forcement convexe.
3 9

2.5 8

7
2

6
1.5

5
1
4

0.5
3

0
2

−0.5 1

−1 0
−2 −1 0 1 2 −2 −1 0 1 2

à gauche : x2, à droite : (x2 − 1)2

- 125 -
D’habitude, le “calcul de convexité” avec le critère différentiel suffisent pour verifier la
convexité des fonctions multi-variées.
Exemple. Soit

f (x) = log exp(aT T
1 x + b1 ) + ... + exp(am x + bm )
1o. Fonction lisse g(y) = log(1 + ey ) : R → R+, est convexe, avec

0 ey 00 ey
g (x) = y
, g (y) = y 2
≥0
1+e (1 + e )
2o. Fonction

h(y1, y2) = log ey1 + ey2 = log(1 + ey1−y2 ) + y2 = g(y1 − y2) + y2
est convexe (transformation linéaire d’argument et somme de fonctions convexes) ⇒
fonction

`(y) = log ey1 + ... + eym : Rm → R+
est convexe
3o. Finalement, fonction f (x) = `(Ax + b) est convexe aussi (transformation affine
d’argument).
Et ainsi de suite...
- 126 -
Quiz : Lesquelles parmi les fonctions suivantes sont convexes ?

• ln(e2x+3y + 2ey−x)
2 2
• ln(ex + ey )
2 2
• ln(e−x + ey )
2 2
• ln(ex + 2e−3x )
2 2
• ln(ex + e−x )

- 127 -
• ln(e2x+3y + 2ey−x) – convexe avec ln(ex1 + ex2 ) (substitution affine d’ar-
gument)

2 2
• ln(ex + ey ) – convexe avec ln(ex1 + ex2 ) et x2, y 2 (superposition mono-
tone, notez que ln(ex1 + ex2 ) est non-décroissante en x1 et x2)

2 2
• ln(e−x + ey ) – non-convexe : regardez ce qui se passe quand y = 0 :
−x2
d
dx
f (x, 0) = − e2xe+1 , et la dérivée n’est pas non-décroissante en x
−x2

2 2
• ln(ex + 2e−3x ) – non-convexe : dx
−3x2 x2
−2e )
d
f (x) = − x(6e
e +ex2
, et la dérivée n’est
−3x2

pas non-décroissante autour de x = 0

2 2
• ln(ex + e−x ) – convexe car fonction ln(es + e−s) est convexe et non-
décroissante pour s ≥ 0, et x2 est convexe et non-négative

- 128 -
Minima des fonctions convexes
Soit X ensemble convexe dans Rn, et f une fonction convexe sur Rn. On considère le
problème d’optimisation
Opt = min f (x)
x∈X
• Tout minimiseur local x∗ de f sur X est un minimiseur global de f sur X :
— si x∗ ∈ X est tel que pour un r > 0, f (x) ≥ f (x∗) pour tout x ∈ X et
kx − x∗k2 ≤ r,
— alors f (x) ≥ f (x∗) pour tout x ∈ X.

Soit x∗ un minimiseur local de f sur X ; et soit x 6= x∗, x ∈ X. Dans ce

cas,
f (x∗ + λ[x − x∗]) − f (x∗) f (x) − f (x∗)
≤
λkx − x∗k2 kx − x∗k2
pour tout λ ∈ (0, 1). Comme x∗ est le minimiseur local de f , nous avons
f (x∗ + λ[x − x∗]) ≥ f (x∗) pour λ petit
⇒ le ratio à droite est non-négatif ⇒ f (x) ≥ f (x∗).

- 129 -
Optimality criterion for differentiable f0
Question
Soit X un ensemble convexe dans Rn, f fonction convexe, et soit x∗ ∈ X
is point
xun optimal
tel ifque
and onlyderivable
f est if it is feasible and est-ce que x∗ est un minimiseur
en x∗. Quand
global de f sur X ?
∇f0(x)T (y − x) ≥ 0 for all feasible y
Réponse : c’est le cas si et seulement si
∀(x ∈ X) : ∇f (x∗)T (x − x∗) ≥ 0

−∇f0(x)
x
X

Géométriquement : X appartient au demi-espace

H = {x ∈ n : ∇f (x )T x ≥ b := ∇f (x )T x }.
R
if nonzero, ∇f0(x) defines a supporting ∗ ∗
hyperplane to feasible ∗set X at x
Autrement dit, le hyperplan
Convex optimization problems
Π = {x ∈ Rn : ∇f (x∗)T x = b} 4–9
est “tangent” à X en x∗.
- 130 -
Nécessité (seulement si) : pour tout x ∈ X et 0 ≤ λ ≤ 1, nous devons avoir

g(λ) := f (x∗ + λ(x − x∗)) ≥ f (x∗) = g(0);

ainsi
0 ≤ g 0(0) = ∇f (x∗)T (x − x∗),
et ceci pour tout x ∈ X.
Suffisance (si) : nous savons que, f (x) ≥ f (x∗) + ∇f (x∗)T (x − x∗) pour tout x,
donc f (x) ≥ f (x∗) quand x∗ ∈ X et ∇f (x∗)T (x − x∗) ≥ 0 pour tout x ∈ X.
Remarque : Quand x∗ se trouve dans l’intérieur de X (c.-à-d. que pour un r > 0
toute la boule {x : kx − x∗k2 ≤ r} ⊂ X, la condition ci-dessus devient la règle de
Fermat : ∇f (x∗) = 0.

- 131 -
Fonction de Lagrange et dualité de Lagrange
On considère le problème de programmation mathématique
n o
Opt(P ) = min f (x) : gi(x) ≤ 0, i = 1, ..., m (P )
x∈X⊂Rn
• La fonction de Lagrange du problème (P ) est la fonction
m
X
L(x, λ) := f (x) + λigi(x) : X × Rm
+→R
i=1
Remarque : quand on parle de la fonction de Lagrange,
— variable x varie dans X
— variable λ varie dans Rm +
on veut que les multiplicateurs de Lagrange λ1, ..., λm soient non-négatives.
Plus généralement,
• si problème de minimisation
— contrainte g(x) ≤ 0 ⇒ λ correspondant est ≥ 0
— contrainte g(x) ≥ 0 ⇒ λ correspondant est ≤ 0
• si problème de maximisation,
— contrainte “≤” ⇒ λ correspondant est ≤ 0
— contrainte “≥” ⇒ λ correspondant est ≥ 0

Opt(P ) = minx∈X⊂RPn m f (x) : gi(x) ≤ 0, im= 1, ..., m (P )
L(x, λ) := f (x) + i=1 λi gi (x) : X × R+ → R
Remarque : Nous avons deja rencontré la fonction de Lagrange dans le cas OL, où
X = Rn, f est linéaire, et g1, ..., gm sont affines (dans le cas OL, il s’agissait d’un
programme de maximisation, tandis qu’ici on s’interesse au problème de minimisation).
Observation : pour tout λ ≥ 0, fonction de Lagrange sous-estime f (x) en tout x
realisable. Ainsi, pour tout λ ≥ 0, la function

L(λ) = inf L(x, λ) : Rm

+ → R ∪ {−∞}
x∈X
satisfait L(λ) ≤ Opt(P ).
• Le problème de programmation mathématique
Opt(D) = maxλ≥0 L(λ) (D)
= maxλ≥0 [inf x∈X L(x, λ)]
s’appelle problème dual de Lagrange de problème primal (P ).

- 132 -
Opt(P ) = min {f (x) : gi (x) ≤ 0, i = 1, ..., m} (P )
x∈X⊂Rn
P
m
L(x, λ) = f (x) + λi gi (x) : X × Rm+ → R
i=1
L(λ) = inf L(x, λ) : Rm
+ → R ∪ {−∞}
x∈X
Opt(D) = max L(λ), (D)
λ≥0
= max inf L(x, λ)
λ≥0 x∈X

[Dualité faible] : par construction,

Opt(D) ≤ Opt(P ).
Remarque : ici la convexité n’est pas importante.

• Sous hypothèses supplémentaires “peu contraignantes,” dans le cas convexe,

Opt(D) = Opt(P ).

- 133 -
Opt(P ) = min {f (x) : gi (x) ≤ 0, i = 1, ..., m} (P )
x∈X⊂Rn
P
m
L(x, λ) = f (x) + λi gi (x) : X × Rm+ → R
i=1
L(λ) = inf L(x, λ) : Rm
+ → R ∪ {−∞}
x∈X
Opt(D) = max L(λ), (D)
λ≥0
= max inf L(x, λ)
λ≥0 x∈X

Condition de Slater : (P ) admet une solution strictement réalisable x̄, c.-à-d. telle
que x̄ ∈ X and gi(x̄)< 0 pour tout i = 1, ..., m.
Condition de Slater relaxée : (P ) admet une solution réalisable x̄ dans l’intérieur
de X, telle que toutes contraintes non-affines sont satisfaites comme inégalités strictes
en x̄.
Pour (P ) convexe, condition de Slater relaxée est plus “légère” que la condition de Slater.

- 134 -
Opt(P ) = min {f (x) : gi (x) ≤ 0, i = 1, ..., m} (P )
x∈X⊂Rn
P
m
L(x, λ) = f (x) + λi gi (x) : X × Rm+ → R
i=1
L(λ) = inf L(x, λ) : Rm
+ → R ∪ {−∞}
x∈X
Opt(D) = max L(λ), (D)
λ≥0
= max inf L(x, λ)
λ≥0 x∈X

Théorème de dualité de Lagrange Sous la condition de convexité de (P) et la

condition relaxée de Slater, (D) est soluble, et

Opt(D) = Opt(P )
Remarque : le problème primal (P) peut être aussi obtenu à partir de la fonction de
Lagrange L(x, λ) : on remarque que
(
f (x), gi(x) ≤ 0 ∀i
L(x) = sup L(x, λ) =
λ≥0 +∞, sinon
n o
et (P) s’écrit de façon équivalente minx∈X L(x) = supλ≥0 L(x, λ) .

- 135 -
Opt(P ) = min {f (x) : gi (x) ≤ 0, i = 1, ..., m} (P )
x∈X⊂Rn
P
m
L(x, λ) = f (x) + λi gi (x) : X × Rm+ → R
i=1
L(λ) = inf L(x, λ) : Rm
+ → R ∪ {−∞}
x∈X
Opt(D) = max L(λ) = max inf L(x, λ) (D)
λ≥0 λ≥0 x∈X

Opt(P ) = min L(x) = min sup L(x, λ) (P 0 )
x∈X x∈X λ≥0

Illustration :
• Soit (P) le problème
n1 o
Opt(P ) = min f (x) = : g1(x) := 20 − x ≤ 0 . (P )
x∈X=[0,∞) 1+x
Ici Opt(P ) = inf x{ 1+x1 : x ≥ 20} = 0, mais (P ) est insoluble.
Néanmoins, le problème est convexe et satisfait la condition de Slater. Nous avons
(
1 0, λ = 0
L(λ) = inf + λ(20 − x) =
x≥0 1 + x −∞, λ > 0
et (D) est soluble avec solution optimale λ = 0 et valeur optimale Opt(D) = 0 =
Opt(P ).
- 136 -
• Toutes les hypothèses du théorème de dualité sont essentielles. Par exemple, le problème
n o
Opt(P ) = min 2 1
x : g1(x) := x ≤ 0 , (P )
2
x∈X=R
est convexe et soluble avec Opt(P ) = 0. Il ne satisfait pas la condition de Slater.
Nous avons
(
λ 2 −∞, λ = 0
L(x) = min x + x = 1, λ>0
x 2 − 2λ
Et nous avons (“par chance”) Opt(D) = 0 = Opt(P ), mais le problème dual n’a pas
de solution.

- 137 -
Conditions d’optimalité en optimisation convexe
On considère le problème
n o
Opt(P ) = minn f (x) : gj (x) ≤ 0, j = 1, ..., m (P )
x∈R
avec f, , g1, ..., gm convexes.
Théorème [conditions de Karush-Kuhn-Tucker] Soit x∗ une solution realisable du pro-
blème convexe (P ), et soit f, g1, ..., gm différentiables en x∗.
[i] Soit x∗ un point KKT de (P ), c.-à-d. que x∗ peut être augmenté par un λ∗ ≥ 0
pour satisfaire
• [complémentarité] λ∗j gj (x∗) = 0 ∀j
Pm
• [équation KKT] ∇f (x∗) + j=1 λ∗j ∇gj (x∗) = 0.
Alors, x∗ est une solution optimale de (P ) (et, au fait, λ∗ est une solution optimale de
(D)).
[ii] Supposons que, en plus, (P) satisfait la condition relaxée de Slater. Alors x∗ est une
solution de (P ) si et seulement si x∗ est un point KKT de (P).

- 138 -
Opt(P ) = min {f (x) : gi (x) ≤ 0, i = 1, ..., m} (P )
x∈X⊂Rn
P
m
L(x, λ) = f (x) + λi gi (x) : X × Rm
+ → R
i=1

Explication, [i] – si x∗ est un point KKT et λ∗ ≥ 0 est le vecteur de multiplicateurs de

Lagrange associé, alors
• x∗ est admissible pour (P ), et x∗, λ∗ satisfont la condition de complémentarité
⇒ la fonction L(x∗, λ) de λ atteint son maximum sur λ ≥ 0 en λ∗ (pourquoi ?) et
nous avons
L(x∗, λ∗) = f (x∗)
• La fonction
X
h(x) = f (x) + λ∗i gi(x)
i
est convexe et différentiable en x∗ et satisfait ∇h(x∗) = 0
⇒ la fonction h(x) = L(x, λ∗) de x atteint son minimum en x∗ et
h(x∗) = L(x∗, λ∗) = f (x∗).
Mais pour tout x réalisable, f (x) ≥ h(x) ≥ h(x∗) = f (x∗).
⇒ x∗ est une solution optimale de (P).
- 139 -
Explication, [ii] – on doit verifier que
“si (P) est convex et satisfait la condition de Slater relaxée, f, gi sont différen-
tiables en x∗, et x∗ est une solution optimale de (P ), alors x∗ est un point
KKT de (P ).”

Soit λ∗ ≥ 0 une solution optimale du problème dual. Par le théorème de dualité, nous
avons ∀x ∈ Rn, λ ≥ 0,
L(x, λ∗) ≥ inf x L(x, λ∗) = L(λ∗)
= Opt(D) = Opt(P ) = f (x∗)
= L(x∗) = supλ≥0 L(x∗, λ) ≥ L(x∗, λ).
• Nous avons L(x∗, λ∗) ≥ L(λ∗) = f (x∗), et, puisque x∗ est réalisable,

λ∗j gj (x∗) = 0 ∀j (complémentarité)

P
• La fonction L(x, λ∗) = f (x) + j λ∗j gj (x) est convexe and différentiable en
x∗ ∈ X et atteint en x∗ son minimum.
X
⇒ ∇xL(x, λ∗) = ∇f (x) + λ∗j ∇gj (x) = 0.
j

- 140 -
Exemples
• Dualité linéaire : soit

min{cT x : b − Ax ≤ 0} [réalisable, borné]

x
Fonction de Lagrange L(x, λ) = cT x + λT (b − Ax), mais
(
T T −∞ si c 6= AT λ
inf [c x + λ (b − Ax)] =
x bT λ si c = AT λ
n o
T T
⇒ problème dual : maxλ b λ : A λ = c, λ ≥ 0
• Système linéaire, moindres carrés : soit

min{ 21 xT x : Ax = b} [réalisable]
x
Fonction de Lagrange L(x, λ) = 12 xT x + λT (Ax − b),

∇xL(x, λ) = x + AT λ, ⇒ x(λ) = −AT λ

⇒ objectif dual L(λ) = L(AT λ, λ) = − 12 λT AAT λ − bT λ
⇒ problème dual maxλ − 12 λT AAT λ − bT λ

- 141 -
• Moindres carrés (à nouveau) : soit minx{kxk2 : Ax = b}.
Fonction de Lagrange L(x, λ) = kxk2 − λT (Ax − b), nous avons
(
bT λ si kAT λk2 ≤ 1
L(λ) = inf [kxk2 − λT (Ax − b)] =
x −∞ sinon
⇒ problème dual maxλ{bT λ : kAT λk2 ≤ 1}
• Optimisation quadratique : soit
n
min 1
2
xT P x + q T x : Ax ≤ b, Cx = d} [réalisable, avec P = P T 0]
x
Fonction de Lagrange L(x, λ) = 21 xT P x + q T x + λT (Ax − b) + ν T (d − Cx)),
∇xL(x, λ) = P x + q + AT λ − C T ν, x(λ) = P −1(C T ν − AT λ − q)
⇒ objectif dual
L(λ) = − 12 (AT λ − C T ν − q)T P −1(AT λ − C T ν − q) − bT λ + dT ν
⇒ problème dual
n o
max − 12 (AT λ − C T ν − q)T P −1(AT λ − C T ν − q) − bT λ + dT ν : λ ≥ 0
λ,ν
n o
1 T T T T T
ou encore max − 2 t P t − b λ + d ν : P t = A λ − C ν − q, λ ≥ 0
λ,ν,t
- 142 -
• Problème de répartition : soit
n o
T 2
Opt(P ) = min x W x : xi = 1, i = 1, ..., n
x
— problème non-convexe, ensemble réalisable contient 2n points {−1, 1}n
— interprétation : répartir les elements de l’ensemble {1, ..., n} en 2 sous-
ensembles, Wij étant le coût de mettre “i” et “j ” dans le même ensemble, avec
les coût −Wij de mettre “i” et “j ” dans les ensembles différents
P
T
Fonction de Lagrange L(x, λ) = x W x + i λi(x2
i − 1)
⇒ objectif dual
(
h i −1T λ si W + Diag(λ) 0
L(λ) = inf xT (W + Diag(λ))x − 1T λ =
x −∞ sinon
⇒ problème dual
n o
T
Opt(D) = max −1 λ : W + Diag(λ) 0
λ
Nous avons Opt(D)≤Opt(P ).

- 143 -
Applications statistiques : régression linéaire
On suppose que les observations (bi, ai) sont liées par un modèle de régression linéaire :

bi = aT
i x∗ + ξi , i = 1, ..., m
ici
— x∗ ∈ Rn est le paramètre vectoriel inconnu
— ξi ∈ R sont des bruits de mesure i.i.d., avec la densité pξ
— en écriture vectorielle, b = Ax∗ + ξ, où A est la matrice avec des lignes aT
i ,
i = 1, ..., m.
Estimateur de maximum de vraisemblance : on prend comme estimation de x∗
une solution optimale de
 
 m
X 
max `(x) = log pξ (bi − aT
i x)
x  
i=1

- 144 -
Exemples
2
−z2
• Loi normale N (0, σ 2) : pξ (z) = √ 1 e 2σ ,
2πσ
m
m 2 1 X T x − b )2 ,
`(x) = − log(2πσ ) − (a i
2 2σ 2 i=1 i
et l’estimateur de ML est celui de moindres carrés.
|z|
1 e− τ ,
• Loi de Laplace L(τ ) : pξ (z) = 2τ
m
1 X
`(x) = −mlog(2τ ) − |aT
i x − bi |,
τ i=1
et l’estimateur de ML minimise la norme `1 des résidus.
11
• Loi uniforme U [−τ, τ ] : pξ (z) = 2τ |z|≤τ ,
(
−mlog(2τ ) si |aT
i x − bi | ≤ τ , i = 1, ..., m
`(x) =
−∞ sinon
Pour trouver l’estimateur de ML on doit trouver x qui satisfait |aT
i x − bi | ≤ τ , i =
1, ..., m.
- 145 -
Problème des moindres carrés contraints
• Dans le cas du bruit normal, on cherche l’estimateur de x∗ qui satisfait la contrainte
Cx = d. On suppose que la matrice hessienne AT A est inversible. On doit résoudre le
problème
n o
min 1
2
(Ax − b)T (Ax − b) : Cx = d (P )
x
On remarque que le problème dual de (P) s’écrit

max − 12 (AT b + C T λ)T (AT A)−1(AT b + C T λ) + λT d + bT b, (D)

λ
et la solution optimale (unique) de (D) peut être calculée explicitement :

λ = (C(AT A)−1C T )−1(d − C(AT A)−1Ab).

Cela donne l’estimateur de moindres carrés sous contraintes

b CLS = (AT A)−1(AT b + C T λ)

x

T
= (A A) −1 T T T −1 T −1
A b + |C (C(A A) C ) {z (d − C(A A) Ab)} T −1
| {z }
bLS
x correction de contrainte

- 146 -
• Régression de “‘ridge” consiste à imposer la contrainte kxk2 ≤ r sur l’estimateur de
moindres carrés :
n o
min (Ax − b)T (Ax − b) : kxk2 ≤ r (C)
x
ou encore, considérer un estimateur pénalisé, la solution de

min(Ax − b)T (Ax − b) + κxT x (R)

x
L’estimateur pénalisé – la solution de (R) – s’écrit explicitement :

b R = (AT A + κI)−1AT b.
x
Par ailleurs, on remarque que la fonction de Lagrange du problème (C) s’écrit

L(x, λ) = (Ax − b)T (Ax − b) + λ(xT x − r), x ∈ Rn, λ ≥ 0,

avec

∇xL(x, λ) = 21 AT (Ax − b) + λxT x, x(λ) = (AT A + λI)−1AT b

- 147 -

min (Ax − b)T (Ax − b) : kxk2 ≤ r (C)
x

Maintenant il y a deux cas :

— soit λ∗ = 0 (la contrainte correspondante n’est pas “active”), et
x0 = (AT A)−1AT b satisfait kx0k2 ≤ r.
b = x0 coincide avec celui de moindres carrés
Dans ce cas l’estimateur contraint x
ordinaires :
b LS = (AT A)−1AT b
x
— soit kx0k2 > r, et on doit choisir λ∗ > 0 tel que kx(λ∗)k2 = r, avec
l’estimateur contraint

b C = (AT A + λ∗I)−1AT b
x
Estimateur de lasso [Hastie, Tibshirani, 1996]
 
Xn p
X 
x̂lasso ∈ Argmin (bi − aT
i x) 2 s. c. |xj | ≤ t
x  
i=1 j=1
ou encore,
 
Xn p
X 
x̂lasso ∈ Argmin (bi − aT 2
i x) + λ |xj |
x  
i=1 j=1
Pp
— par rapport au ridge : la pénalité kxk2 2
2 = P j=1 xj est remplacé par
p
kxk1 = j=1 |xj |
— estimateur x̂lasso est non-linéaire
— quand t → ∞ (λ → 0) x̂lasso → x̂ls, l’estimateur des moindres carrés
ordinaires
— si t → 0 (ou λ → ∞), alors x̂lasso → 0, mais petite valeur de t (ou grande
valeur de λ) cause certains des coefficients être exactement zéro
— Lasso est une (sorte de) procédure de sélection “continue” de support de x̂

- 148 -
Ridge, lasso, et sélection du support
• Régression ridge

x̂ridge = argmin kbi − Axk2

2 + λkxk2
2
x
• Lasso
x̂lasso ∈ Argmin kb − Axk2
2 + λkxk1
x
• Sélection du meilleur support
p
X
x̂sparse ∈ Argmin kb − Axk2
2+λ I{xj 6= 0}
j=1
| {z }
“norme” kxk0
Ridge et (surtout) lasso sont deux alternatives “à coup numérique raisonnable” à la pro-
cedure difficile numériquement de sélection du meilleur sous-ensemble de prédicteurs.

- 149 -
Ridge et LASSO dans un cas particulier
Soit n = m et A = I, une matrice identité, c.-à-d.

bi = xi + ξi, i = 1, ..., n.
P
• Estimateur de moindres carrés : x̂ls = argminx n
i=1 (b i − x i ) 2,

x̂ls
i = bi , i = 1, . . . , n.
P 2 + λ Pn
• Régression ridge : x̂ridge = argminx n (b
i=1 i − x i ) 2
i=1 xi ,
bi
x̂ridge
i = , i = 1, . . . , n.
1+λ
P 2 + λ Pn
• Lasso : x̂lasso ∈ Argminx n (b
i=1 i − x i ) i=1 |xi |,


 bi − λ/2, bi > λ/2,
x̂lasso
i = bi + λ/2, bi < −λ/2, i = 1, . . . , n.

 0, |bi| ≤ λ/2

- 150 -
• x̂ridge = ponderation(bi)
• x̂lasso
i = seuillage(bi)

1.5

1.5
Ridge Lasso
Coefficient Estimate

Coefficient Estimate
Least Squares Least Squares
0.5

0.5
−0.5

−0.5
−1.5

−1.5
−1.5 −0.5 0.0 0.5 1.0 1.5 −1.5 −0.5 0.0 0.5 1.0 1.5

yj yj

- 151 -
Modèle de régression logistique
Exemple Données de l’état de maladie coronarienne (CHD) et d’age : 100 sujets

réponse η - absence ou presence (0/1) de la CHD, prédicteur ζ - age.

1.0
0.8
0.6
CHD

0.4
0.2
0.0

20 30 40 50 60 70

AGE

- 152 -
— Régression linéaire n’est pas appropriée :

E(η|ζ = a) = P (η = 1|ζ = a) = x0 + x1a

doit être dans [0, 1], pour tout a.
— L’idee est de modéliser la relation entre p(a) = P (η = 1|ζ = a) et a en
utilisant la fonction de réponse logistique :
ex0+x1a p(a)
p(a) = x +x a
⇔ logit{p(a)} := log = x0 + x1a.
1+e 0 1 1 − p(a)

1.0
0.8
0.6
y

0.4
0.2
0.0

−100 −50 0 50 100

Fonction de réponse logistique

- 153 -
Interprétation
— Il s’agit d’un cas spécial d’un modèle linéaire généralisé (GLM) avec la fonction
de lien logit :
z
g(E(η|ζ = a)) = x0 + x1a, g(z) = log , 0 ≤ z < 1.
1−z
p(a)
— Pourquoi logit ? Pour un a fixé, evidence, ou échelle des chances 1−p(a) est na-
turellement logarithmique : d’habitude, on compte les chances comme ’10 contre
1’, ou ’2 contre 1’.
p(a) = 0.75 ⇒ chances d’avoir la CHD à l’age a sont 3 contre 1.
a=0⇒
p(0) p(0)
log = x0 ⇔ = ex0 .
1 − p(0) 1 − p(0)
Ainsi ex0 peut être interprété comme niveau de référence
(surtout si zéro est dans la plage des données de la variable prédictive) ζ.
En augmentant a de 1, on multiplie les chances par ex1 . Si x1 > 0 alors
ex1 > 1 et les chances augmentent ; si x1 < 0 alors les chances diminuent.

- 154 -
Fonction de vraisemblance
• Modèle et données : {(ηi, ai), i = 1, . . . , n}, ηi ∈ {0, 1}, i.i.d.

ex0+x1ai
πi = π(ai) = P (ηi = 1|ai) = E(ηi|ai) = x +x a
, i = 1, . . . , n.
1+e 0 1 i

• Vraisemblance et log–vraisemblance à maximiser par rapport à (x0, x1) :

n
Y η
L(x0, x1; Dn) = πi i (1 − πi)1−ηi
i=1
n η 1−η
Y ex0+x1ai i 1 i
= x0 +x1 ai
i=1 1 + e 1 + ex0+x1ai
n
Y e(x0+x1ai)ηi
= x0 +x1 ai
i=1 1 + e
n
X n
X
log{L(x0, x1; Dn)} = ηi(x0 + x1ai) − log 1 + ex0+x1ai .
i=1 i=1
Pas de solution analytique, mais une solution numérique comme solution d’un problème
d’optimisation
minx0,x1 log{L(x0, x1; Dn)}
- 155 -
Plus généralement on considère le problème de classification, dans lequel on observe
les couples (ai, ηi), ou ai ∈ Rn et ηi ∈ {0, 1}.
• On admet que les étiquettes (labels) ηi sont des realisations des v.a. indépendantes
de loi de Bernoulli B(pi) de paramètre pi qui depend de ai ∈ Rn (lien logistique) :

exp(aT
i x)
pi = Prob{ηi = 1} =
1 + exp(aTi x)
où x est le paramètre à estimer à partir des observations.
• Fonction log-vraisemblance (on admet que y1 = ... = yk = 1 et yk+1 = ... =
ym = 0)
 
k
Y
exp(aT x) m
Y
i 1
`(u, v) = log  T T

i=1 1 + exp(ai x) i=k+1 1 + exp(ai x)
k
X m
X
= aT
i x− log(1 + exp(aT
i x))
i=1 i=1
est concave en x.

- 156 -
Machine à vecteur de support
On considère un problème de classification (binaire) avec les données (ai, `i), i =
1, ..., m, où ai ∈ Rn et `i ∈ {−1, 1}.
• On dit que l’échantillon admet une séparation linéaire si il existe un hyperplan de
séparation f (a) := aT u + v = 0 tel que
v + aTi u ≥ 0 si ` i = 1, et v + aT u < 0 si ` = −1.
i i
Si f (a) = 0 est un plan de séparation alors un classifieur “naturel” est sign{f (a)}.
3

3
2

2
X2

X2
1

1
0

0
−1

−1

−1 0 1 2 3 −1 0 1 2 3

X1 X1

Remarque : un plan de separation satisfait `i(v + uT ai) ≥ 0, ∀i.

- 157 -
Classifieur à marge maximale

— Si l’ensemble de données admet une séparation linéaire, il est naturel de chercher

l’hyperplan de séparation à marge maximale, c.-à-d., l’hyperplan de séparation le
plus éloigné des observations.
— Problème d’optimisation :
n o
minu,v 1
uT u : `i(v + uT ai) ≥ 1, i = 1, . . . , m
n2 o (P0)
= minu,v 1 T
u u : Λ(1v + Au) ≥ 1
2

kuk−12 étant la marge de séparation, Λ = Diag(`i ), et A la matrice avec les

lignes aT
i .

• Le problème d’optimisation (P0) est convexe.

• On appelle également ce classifieur hard margin classifier (classifieur à marge dure)

- 158 -
Une reformulation
• On écrit le problème dual de (P0) (avec λ ≥ 0) :
L(u, v; λ) = 12 uT u − λT (Λ(1v + Au) − 1),
avec
∇uL(u, v; λ) = u − AT Λλ, ⇒ u(λ) = AT Λλ,
L0v (u, v; λ) = Λ1 := `, ⇒ `T λ = 0.
⇒ problème dual de (D0) :
n o
T 1 T T
maxλ − λ ΛAA Λλ + 1 λ : ` λ = 0, λ ≥ 0 T
( 2
Pm )
P T a − Pm λ : i=1 λi ì = 0,
= − minλ 21 m λ λ ` `
i,j=1 i j i j i ja i=1 i (D0)
λi ≥ 0, ∀i
Proposition Soit [u∗; v ∗] une solution optimale de (P0). Si λ∗ est une solution opti-
male duale, alors
m
X
u∗ = AT Λλ∗ = ìλ∗i ai,
i=1
et pour tout k tel que λk > 0
v ∗ = `k − aT u∗ = ` − Pm λ∗ ` aT a .
k k i=1 i i i k
- 159 -
Remarques
— solution duale creuse : la condition de complémentarité implique que λ∗ et
(u∗, v ∗) satisfont
n o
∗ T ∗ ∗
λi ì[ai u + v ] − 1 = 0, ∀i = 1, . . . , m.

Autrement dit, seuls les vecteurs ai pour lesquels aT u∗ +v ∗ = ` correspondent

i i
à λ∗i > 0, les autres λ∗i sont nulls.
On appelle ces ai vecteurs de support (support vectors)

3
2
X2
1
0
−1

−1 0 1 2 3

— sensibilité – une seule observation peut modifier significativement la solution.

— Et si l’hyperplan de separation n’existait pas ?
- 160 -
Classifieur “à marge douce”
— L’idée : admettre des individus mal classés – imposer une marge douce (soft
margin).
— Problème d’optimisation
( )
Pm T
`i(v + ai u) ≥ 1 − i,
minv,u, 1
uT u + C i=1 i :
n
2
i ≥ 0, i = 1, . . . , m o
= minv,u, 1
2
uT u + C 1T : Λ(v 1 + Au) ≥ 1 − , ≥ 0 (P1)
où = [1; . . . ; n] est vecteur des variables d’écart (slacks), et C ≥ 0 est
un paramètre d’ajustement.

— Variable d’écart (slack) i nous dit où se trouve la i-ème observation :

— i = 0 : i-ème observation est “de bon cote” de la marge
— i > 0 : i-ème observation viole la marge
— i > 1 : i-ème observation est “de mauvais coté” (mal classée).
— Paramètre C à choisir établit une pénalité pour la violation de la marge

- 161 -
Formulation duale
• On écrit le dual de (P1) (avec λ, ν ≥ 0) :

L(u, v, ; λ, ν) = 21 uT u + C 1T − λT (Λ(1v + Au) − 1 + ) − ν T ,

avec
∇uL(u, v, ; λ) = u − AT Λλ ⇒ u(λ) = AT Λλ,
L0v (u, v, ; λ) = Λ1 := ` ⇒ `T λ = 0,
∇L0v (u, v, ; λ) = C 1 − λ − ν ⇒ λ + ν = C 1.
⇒ problème dual :
n o
min T 1 T T T
− λ ΛAA Λλ + 1 λ : ` λ = 0, λ, ν ≥ 0, λ + ν = C 1 ,
2
λ
et, en éliminant ν, on arrive à
n o
− 21 λT ΛAAT Λλ + 1T λ : `T λ = 0, 0 ≤ λ ≤ C 1
minλ (D1)
( Pm )
P P i=1 λi `i = 0,
= − minλ 21 m λ λ ` ` aTa − m λ :
i,j=1 i j i j i j i=1 i 0 ≤ λi ≤ C, ∀i

- 162 -
— Avantage principal d’une fonction de pénalité linéaire est que les variables de slack
disparaissent du problème dual ;
— Si λ∗ est une solution optimale duale, alors la solution optimale primal u∗ est
Pn
donnée par u = A Λλ = i=1 `iλ∗i ai, avec λ∗i > 0 seulement pour les
∗ T ∗

observations i t.q.
`i(aT u∗ + v ∗) = 1 − ≤ 1
i i

Les ai correspondants sont les vecteurs de support dans le cas d’un classifieur à
marge douce.
Les solutions duales 0 < λ∗i < C correspondent aux vecteurs de support ai sur
les “bords de la marge” (avec i = 0) ; si ai viole la marge (i > 0), nous avons
λ∗i = C.
— Le classifieur
X
n
g(a) = sign{aT u∗ + v ∗} = sign `iλ∗i aT
i a + v ∗ .
i=1
ne nécessite pas de calcule explicite de u∗, seule les produits aT
i a sont utilisés
⇒ on peut faire les calculs pour un n “très grand” (l’idee du “Kernel trick”).

- 163 -

Vous aimerez peut-être aussi

Dualité
Pas encore d'évaluation
Dualité
30 pages
Cours de Recherche Opérationnelle
Pas encore d'évaluation
Cours de Recherche Opérationnelle
53 pages
Cours de Programmation Linéaire 2022/2023
Pas encore d'évaluation
Cours de Programmation Linéaire 2022/2023
60 pages
Prog Lin
Pas encore d'évaluation
Prog Lin
127 pages
Programmation Linéaire et Modélisation en Recherche Opérationnelle
Pas encore d'évaluation
Programmation Linéaire et Modélisation en Recherche Opérationnelle
17 pages
Recherche Opérationnelle Master I
Pas encore d'évaluation
Recherche Opérationnelle Master I
59 pages
Recherche Opérationnelle et Programmation Linéaire
Pas encore d'évaluation
Recherche Opérationnelle et Programmation Linéaire
23 pages
Introduction à la recherche opérationnelle
Pas encore d'évaluation
Introduction à la recherche opérationnelle
17 pages
Cours Ci Gi s7!23!24
Pas encore d'évaluation
Cours Ci Gi s7!23!24
109 pages
01 Intro RO
Pas encore d'évaluation
01 Intro RO
18 pages
Recherche opérationnelle et optimisation
100% (1)
Recherche opérationnelle et optimisation
53 pages
Méthode Graphique en Recherche Opérationnelle
Pas encore d'évaluation
Méthode Graphique en Recherche Opérationnelle
5 pages
Programmation Mathématique et Optimisation
100% (1)
Programmation Mathématique et Optimisation
45 pages
Introduction à la recherche opérationnelle
Pas encore d'évaluation
Introduction à la recherche opérationnelle
102 pages
Introduction à l'Optimisation Linéaire
Pas encore d'évaluation
Introduction à l'Optimisation Linéaire
121 pages
Introduction à la programmation linéaire
Pas encore d'évaluation
Introduction à la programmation linéaire
60 pages
Introduction à la Recherche Opérationnelle
Pas encore d'évaluation
Introduction à la Recherche Opérationnelle
25 pages
Chapitre 1
Pas encore d'évaluation
Chapitre 1
27 pages
Cours de Programmation Linéaire
100% (1)
Cours de Programmation Linéaire
49 pages
Programmation Linéaire Mulapu Kapend
Pas encore d'évaluation
Programmation Linéaire Mulapu Kapend
133 pages
SOSI1
Pas encore d'évaluation
SOSI1
62 pages
Recherche Opérationnelle 1 À 4
Pas encore d'évaluation
Recherche Opérationnelle 1 À 4
10 pages
Rercherche Operationnelle Textile
Pas encore d'évaluation
Rercherche Operationnelle Textile
26 pages
Modélisation Mathématique et Études de Cas
Pas encore d'évaluation
Modélisation Mathématique et Études de Cas
11 pages
Introduction à la Recherche Opérationnelle
Pas encore d'évaluation
Introduction à la Recherche Opérationnelle
41 pages
Introduction à l'optimisation mathématique
Pas encore d'évaluation
Introduction à l'optimisation mathématique
47 pages
Sbihi
Pas encore d'évaluation
Sbihi
118 pages
Introduction à la Programmation Linéaire
Pas encore d'évaluation
Introduction à la Programmation Linéaire
16 pages
Optimisation de Régime Alimentaire par PL
Pas encore d'évaluation
Optimisation de Régime Alimentaire par PL
76 pages
Prise de Décision et Optimisation
Pas encore d'évaluation
Prise de Décision et Optimisation
135 pages
Cours
Pas encore d'évaluation
Cours
37 pages
Optimisation Numérique pour Ingénieurs
Pas encore d'évaluation
Optimisation Numérique pour Ingénieurs
32 pages
Cours de Programmation Linéaire en Mathématiques
Pas encore d'évaluation
Cours de Programmation Linéaire en Mathématiques
29 pages
Recherche Opérationnelle
Pas encore d'évaluation
Recherche Opérationnelle
21 pages
Introduction à la recherche opérationnelle
Pas encore d'évaluation
Introduction à la recherche opérationnelle
35 pages
Introduction à la programmation linéaire
Pas encore d'évaluation
Introduction à la programmation linéaire
50 pages
Introduction à l'optimisation mathématique
Pas encore d'évaluation
Introduction à l'optimisation mathématique
11 pages
Introduction à la Recherche Opérationnelle
Pas encore d'évaluation
Introduction à la Recherche Opérationnelle
23 pages
Introduction à la Programmation Mathématique
Pas encore d'évaluation
Introduction à la Programmation Mathématique
211 pages
Introduction à l'optimisation mathématique
100% (1)
Introduction à l'optimisation mathématique
100 pages
Cours de Programmation Linéaire en Génie Civil
Pas encore d'évaluation
Cours de Programmation Linéaire en Génie Civil
35 pages
Cours de Recherche Opérationnelle INF 316
Pas encore d'évaluation
Cours de Recherche Opérationnelle INF 316
33 pages
Polyao 101
Pas encore d'évaluation
Polyao 101
109 pages
Recherche Operationnelle Et Management Des Projets by Falloul Moulay El Mehdi
Pas encore d'évaluation
Recherche Operationnelle Et Management Des Projets by Falloul Moulay El Mehdi
88 pages
Méthodes Quantitatives de Gestion
100% (2)
Méthodes Quantitatives de Gestion
93 pages
Optimisation Linéaire par Madani Bezoui
Pas encore d'évaluation
Optimisation Linéaire par Madani Bezoui
29 pages
Prog Mathematic
Pas encore d'évaluation
Prog Mathematic
87 pages
Optimisation : Techniques et Applications
Pas encore d'évaluation
Optimisation : Techniques et Applications
63 pages
1.3. Recherche Operationnelle-Cours
Pas encore d'évaluation
1.3. Recherche Operationnelle-Cours
58 pages
Ordonnancement de tâches en temps réel
Pas encore d'évaluation
Ordonnancement de tâches en temps réel
3 pages
Planification de forage : Méthodes RO2MIR
Pas encore d'évaluation
Planification de forage : Méthodes RO2MIR
65 pages
Méthode du Grand M en Programmation Linéaire
Pas encore d'évaluation
Méthode du Grand M en Programmation Linéaire
6 pages
Cours R o Epcci 2021
100% (2)
Cours R o Epcci 2021
58 pages
Simplexe
Pas encore d'évaluation
Simplexe
94 pages
Profil d'El Bachir Rhamati
Pas encore d'évaluation
Profil d'El Bachir Rhamati
1 page
Calcul des temps d'attente en ordonnancement
Pas encore d'évaluation
Calcul des temps d'attente en ordonnancement
7 pages
Chap1 INTRODUCTION A LA PROGRAMMATION LINEAIRE 1
Pas encore d'évaluation
Chap1 INTRODUCTION A LA PROGRAMMATION LINEAIRE 1
9 pages
Exercices - Diagramme de PERT
Pas encore d'évaluation
Exercices - Diagramme de PERT
13 pages
Optimisation avec R : Recherche Opérationnelle
Pas encore d'évaluation
Optimisation avec R : Recherche Opérationnelle
34 pages
Cours Ro 2022 2023
Pas encore d'évaluation
Cours Ro 2022 2023
109 pages
Cours de Recherche Opérationnelle L3
Pas encore d'évaluation
Cours de Recherche Opérationnelle L3
51 pages
Série 1
Pas encore d'évaluation
Série 1
1 page
Introduction à la Recherche Opérationnelle
Pas encore d'évaluation
Introduction à la Recherche Opérationnelle
10 pages
Chapitre 1: Pr. Mohamed DHIB
Pas encore d'évaluation
Chapitre 1: Pr. Mohamed DHIB
22 pages
Gestion de La Production L1
Pas encore d'évaluation
Gestion de La Production L1
160 pages
BTS CG P5.1!03!02 Castand C
Pas encore d'évaluation
BTS CG P5.1!03!02 Castand C
6 pages
MP - Bac - Et - L1 - 2023 - 2024
Pas encore d'évaluation
MP - Bac - Et - L1 - 2023 - 2024
147 pages
Optimisation des profits en production
Pas encore d'évaluation
Optimisation des profits en production
4 pages
Introduction à l'optimisation combinatoire
Pas encore d'évaluation
Introduction à l'optimisation combinatoire
16 pages
Outils d'aide à la décision en gestion
Pas encore d'évaluation
Outils d'aide à la décision en gestion
22 pages
SMED Method - Wikipedia
Pas encore d'évaluation
SMED Method - Wikipedia
4 pages
Cycle Ingénieur: Génie Industriel & Logistique
Pas encore d'évaluation
Cycle Ingénieur: Génie Industriel & Logistique
1 page
Metaheuristiques
Pas encore d'évaluation
Metaheuristiques
139 pages
COURS
Pas encore d'évaluation
COURS
40 pages
Recherche Operationnelle
100% (1)
Recherche Operationnelle
58 pages
Liste Des Sujets Et Groupes
Pas encore d'évaluation
Liste Des Sujets Et Groupes
9 pages
Cours de Recherche Opérationnelle S6
0% (1)
Cours de Recherche Opérationnelle S6
26 pages
Méthodes d'aide à la décision en entreprise
Pas encore d'évaluation
Méthodes d'aide à la décision en entreprise
14 pages