Cours MOD
Description
Jean-Baptiste Delorme MOD 2005 Programmation quadratique et semidéfinie 1. Introduction : du linéaire au non-linéaire Classiquement, parmi les premiers problèmes rencontrés en optimisation se trouvent les problèmes linéaires. Il s’agit de maximiser (ou de minimiser) une fonction objectif linéaire de ses paramètres tout en se conformant à des conditions, elles aussi, linéaires. Ceci peut être formalisé de la manière suivante : nMaximiser (ou minimiser) f (x ,..., x ) = a x 1 n ∑ i ii =1nSous les contraintes : g (x ,..., x ) = b x ≤ 0 ∀j ∈1..m j 1 n ∑ i, j ii =1 La résolution de ce style de problème peut être comprise aisément de manière graphique : 706050Contraintes40Optimum30Objectif201000 5 10 15 20 25 Les contraintes forment un polygone P de solutions acceptables. C’est dans cet ensemble qu’il faut chercher les solutions au problème. Ainsi, l’optimisation correspond à trouver le point de P qui maximise la fonction objectif. Nous pouvons observer que la solution optimale se trouve sur un des sommets de P, ici dans le carré noir. Mais cette configuration est évidemment un cas particulier des problèmes rencontrés en optimisation. Les fonctions étudiées peuvent, bien sur, sortir du cadre linéaire. 605040Contraintes30Optimum201000 5 10 15 20 25 Par exemple, dans le cas représenté ci-dessus, c’est la contrainte qui a été changée pour devenir non linéaire. De même, il est possible de rencontrer des ...
Informations
| Publié par | Iddo |
| Nombre de lectures | 38 |
| Langue | Français |
Extrait
Jean-Baptiste Delorme
MOD 2005
Programmation quadratique et
semidéfinie
1.
Introduction : du linéaire au non-linéaire
Classiquement, parmi les premiers problèmes rencontrés en optimisation se trouvent
les problèmes linéaires. Il s’agit de maximiser (ou de minimiser) une fonction objectif linéaire
de ses paramètres tout en se conformant à des conditions, elles aussi, linéaires. Ceci peut être
formalisé de la manière suivante :
Maximiser (ou minimiser)
i
n
i
i
n
x
a
x
x
f
∑
=
=
1
1
)
,...,
(
Sous les contraintes :
0
)
,...,
(
1
,
1
≤
=
∑
=
i
n
i
j
i
n
j
x
b
x
x
g
∈
∀
j
m
..
1
La résolution de ce style de problème peut être comprise aisément de manière graphique :
0
10
20
30
40
50
60
70
0
5
10
15
20
25
Contraintes
Optimum
Objectif
Les contraintes forment un polygone P de solutions acceptables. C’est dans cet ensemble qu’il
faut chercher les solutions au problème. Ainsi, l’optimisation correspond à trouver le point de
P qui maximise la fonction objectif. Nous pouvons observer que la solution optimale se trouve
sur un des sommets de P, ici dans le carré noir.
Mais cette configuration est évidemment un cas particulier des problèmes rencontrés en
optimisation. Les fonctions étudiées peuvent, bien sur, sortir du cadre linéaire.
0
10
20
30
40
50
60
0
5
10
15
20
25
Contraintes
Optimum
Par exemple, dans le cas représenté ci-dessus, c’est la contrainte qui a été changée
pour devenir non linéaire.
De même, il est possible de rencontrer des cas où la fonction objectif est non-linéaire :
0
10
20
30
40
50
60
70
0
5
10
15
20
25
Contraintes
Optimum
Dans ces deux cas, il apparaît alors comme évident que la recherche de la solution optimale
est plus difficile que dans le cas linéaire, puisqu’elle doit se faire tout le long du polygone des
contraintes, et non seulement en quelques points particuliers. De plus, si la solution est
cherchée entière, la complexité est encore augmentée. Ainsi, ces développements ouvrent à la
modélisation de plus de problèmes d’optimisation, mais au prix de la difficulté théorique de
leur résolution. Et, comme nous le verrons plus loin, il n’existe pas dans le domaine non-
linéaire d’équivalent au fameux algorithme du simplexe, outil simple et efficace de résolution
des problèmes linéaires.
La programmation quadratique et semidéfinie, que nous allons définir dans la partie
suivante, traite d’une partie spécifique de ces problèmes non linéaires : ceux qui font appel à
des fonctions quadratiques.
2.
Programmation quadratique et semidéfinie
a.
Définitions
Un problème de programmation quadratique est un problème qui peut se mettre sous
la forme suivante :
Minimiser
i
n
i
i
j
i
n
j
ij
n
i
n
x
b
x
x
a
x
x
f
∑
∑
∑
=
=
=
+
=
1
1
1
1
)
,...,
(
(1)
Sous les contraintes :
0
)
,...,
(
1
,
1
≤
=
∑
=
i
n
i
j
i
n
j
x
c
x
x
g
∈
∀
j
m
..
1
Ou encore, en utilisant le formalisme matriciel :
Minimiser
BX
AX
X
X
f
T
+
=
)
(
Sous les contraintes :
0
)
(
≤
=
X
C
X
g
j
j
∈
∀
j
m
..
1
Et un problème de programmation semidéfinie est un cas particulier des problèmes décrits ci-
dessus, pour lequel la matrice A a la particularité d’être semidéfinie positive (parfois dite
positive), c’est-à-dire que :
0
:
≥
ℜ
∈
∀
AX
X
X
T
n
Mais selon les cas et les publications, il arrive souvent que les notions de programmation
quadratique et semidéfinie couvrent aussi les cas où les contraintes sont quadratiques, soit :
0
)
,...,
(
1
,
1
,
1
1
≤
+
=
∑
∑
∑
=
=
=
i
n
i
j
i
k
i
n
k
j
ik
n
i
n
j
x
d
x
x
c
x
x
g
∈
∀
j
m
..
1
Ainsi, et pour revenir à ce qui a été présenté dans l’introduction, ce sont des problèmes
d’optimisation avec une fonction objectif (ou fonction de coût) quadratique, et des conditions
linéaires ou quadratiques. Mais il est important de comprendre que cela représente une
généralisation du cas linéaire, et non seulement une situation différente.
b.
La relaxation semidéfinie : un outil de résolution
« Un des problèmes majeurs rencontrés lorsque l’on souhaite utiliser la
programmation semidéfinie est l’absence d’outils numériques commerciaux éprouvés. Cela
est dû en partie au fait que l’élaboration de méthodes de résolution de SDP
[SemiDefinite
Programming]
est un domaine de recherche récent et encore très actif » peut on lire dans
l’article de Frédéric Roupin du bulletin n°13 Automne-Hiver 2004 de la Société Française de
Recherche Opérationnelle et d’Aide à la Décision (ROADEF).
Mais derrière cette apparente absence d’outil se cache malgré tout la relaxation
semidéfinie, extension au cas que nous étudions de la relaxation lagrangienne.
Dans le cadre du problème décrit ci-dessus dans l’encadré (1), nous construisons la
fonction
de Lagrange
:
)
(
)
(
)
(
)
(
)
,
(
)
,
(
:
1
x
g
u
x
f
x
g
u
x
f
u
x
L
u
x
L
T
j
m
j
j
m
n
+
=
+
=
→
ℜ
→
ℜ
×
ℜ
∑
=
On dit que L est une fonction de la variable primale x et de la variable duale u (ou
multiplicateur). Les contraintes
0
)
(
≤
x
g
j
se traduisent par une contrainte sur la variable
duale :
0
≥
j
u
. Si ce sont des égalités :
0
)
(
=
x
g
j
, cela n’introduit pas de contrainte.
Ensuite, nous définissons la
fonction duale
de la manière suivante :
)
,
(
inf
)
(
:
u
x
L
u
u
n
x
m
ℜ
∈
=
→
ℜ
→
ℜ
θ
θ
Et enfin, tout ceci nous mène à poser le
problème dual
:
Maximiser
)
(
u
θ
pour
m
u
+
ℜ
∈
Une chose importante à remarquer concernant le problème dual est que c’est un problème
bien plus facile à résoudre que le problème primal. En effet, la fonction
)
(
u
θ
est toujours une
fonction concave et semi-continue supérieurement.
Ceci dit, la résolution du problème dual n’est pas équivalente à celle du problème initial. Si on
note
opt(I) la valeur optimale du problème initial
, et
opt(D) la valeur optimale du
problème dual
, on a toujours :
opt(I)-opt(D)
≥
0
. Les cas les plus intéressants sont ceux pour
lesquels cette différence vaut exactement 0, puisque cette méthode permet alors de résoudre
notre problème initial. Mais ce n’est pas toujours le cas, cela dépend par exemple de la forme
de la matrice A, des fonctions g
j
etc.
Ainsi, nous pouvons dire que nous disposons d’un outil pour la résolution des
problèmes de programmation semidéfinie avec cette relaxation. Mais ce n’est pas pour autant
une méthode qui nous mènera dans tous les cas à une solution. Pour cela, tous les paramètres
doivent vérifier des conditions strictes. Je ne vais pas, dans ce cadre, exposer les
développements théoriques sur ce sujet. Ils sont nombreux et, d’après moi, relativement
difficiles d’approche. Mais j’invite évidemment toute personne intéressée à se plonger dans la
lecture du rapport de recherche de l’INRIA n°3710 : « Semidefinite relaxations and
Lagrangian duality with application to combinatorial optimization » de Claude Lemaréchal et
François Oustry, ainsi que de suivre les liens indiqués dans cet article vers les différents
ouvrages de référence.
c.
Exemple d’application : le problème Max-Cut
Nous disposons d’un graphe G = (X,U) orienté. Et nous noterons n le nombre de
sommets de ce graphe. De plus, nous le supposerons valué, c'est-à-dire que à chaque arc de G
(du noeud i au noeud j) est associé un poids p
ij
.
Le problème que nous souhaitons résoudre est de trouver une coupe de capacité
maximum. C'est-à-dire trouver comment séparer les sommets en deux ensembles
S
et
S
, de
manière à ce que la capacité de cette coupe soit maximum. La capacité d’une coupe étant
définie comme la somme des capacités des arcs interconnectant
S
et
S
. R.M. Karp a
démontré que ce problème est NP-complet.
Nous allons ici le modéliser sous la forme d’un problème de programmation
quadratique. A chacun des sommets i du graphe, nous allons associer une valeur x
i
de la
manière suivante :
x
i
= 1 si le sommet i est dans
S
x
i
= -1 si le sommet i est dans
S
Il est évident qu’il y a une bijection entre {-1 ;1}
n
et toutes les coupes possibles de G.
Ainsi, trouver une coupe de capacité maximum revient à trouver la distribution des x
i
correspondante.
Nous allons étudier la valeur suivante :
j
i
n
i
n
j
ij
x
x
p
Q
∑∑
=
=
=
1
1
Alors, la valeur x
i
x
j
vaut : 1 lorsque les sommets i et j sont dans la même partie de la coupe
-1 lorsque les sommets i et j sont répartis entre les deux parties
Donc :
=
Q
[capacité des arcs internes aux deux parties de la coupe]
- [capacité des arcs interconnectant
S
et
S
]
Or la somme de toutes les capacités de G est une constante que l’on va noter C. Et on a alors :
=
Q
C - 2.[capacité des arcs interconnectant
S
et
S
]
Alors, trouver une coupe de capacité maximum revient exactement à minimiser Q. Et ceci
avec les contraintes suivantes : (x
i
)²-1 = 0 pour i = 1..n.
Ainsi, nous sommes bien ramenés à un problème de programmation quadratique.
Nous allons donc créer la fonction de Lagrange associée à ce problème :
u
e
X
u
D
P
X
x
u
x
x
p
u
x
L
T
T
i
n
i
i
n
i
n
j
j
i
ij
−
+
=
−
+
=
∑
∑∑
=
=
=
))
(
(
)
1
(
)
,
(
2
1
1
1
Où D(u) est la matrice diagonale composée des termes u
i
, et e
n
ℜ
∈
est le vecteur composé
uniquement de 1.
Minimiser cette fonction de Lagrange sur x est alors un jeu d’enfant, deux cas se présentent :
- si Q + D(u) n’est pas semidéfinie positive, on obtient -
∞
- dans le cas contraire, le mieux à faire est de prendre x = 0
Ainsi, on obtient la forme suivante pour la fonction duale :
⎪
⎩
⎪
⎨
⎧
∞
−
+
−
=
contraire
cas
le
dans
positive
e
semidéfini
u
D
Q
si
u
e
u
T
)
(
)
(
θ
Le problème dual est donc de maximiser
u
e
T
−
sous la contrainte : Q + D(u) semidéfinie
positive.
Nous n’allons pas rentrer plus profondément dans la résolution de ce dernier problème, mais
nous pouvons dire qu’il admet une solution optimale car en prenant u assez grand, Q + D(u)
prend la forme voulue, et il suffit alors de résoudre le problème dual qui, nous le rappelons, es
bien plus simple que le problème initial.
d.
Conclusion
Pour citer encore le bulletin n°13 de la ROADEF, nous pouvons dire que « d’un point
de vue théorique, la SDP a permis d’améliorer significativement les résultats sur
l’approximation de nombreux problèmes. […] Cependant, il est clair que l’approche
semidéfinie doit être réservée au traitement de problèmes très difficiles, en particulier pour
ceux
où la programmation linéaire est inefficace ». En effet, la résolution d’un SDP provoque
une perte de temps importante, même si « les derniers progrès montrent que cette approche est
dorénavant tout à fait exploitable dans la pratique ».
Ainsi, la programmation semidéfinie, bien que très complexe et souvent coûteuse en
temps, est un développement utile qui permet, dans certaines situations « difficiles »,
d’obtenir des résultats très satisfaisants en un temps acceptable et dans la majorité des cas.
C’est le cas en particulier du problème MAXCUT évoqué ci-dessus.
Mais évidemment, il existe d’autres méthodes pour résoudre certains problèmes de
programmation quadratique. C’est ce que nous allons voir dans la partie suivante.
3.
Le problème d’affectation quadratique
a.
Présentation et modélisation du problème
Pour toute cette partie, les personnes intéressées pourront se référer, comme moi, au
chapitre « Affectation quadratique » du livre « Métaheuristiques et RO », rédigé par Thierry
Mautor.
Le problème d’affectation quadratique consiste à placer
n
unités communiquant entre
elles sur
n
sites prédéterminés. Entre une unité
i
placée sur un site
k
et une unité
j
placée sur
un site
l
se passe une interaction qui a un coût : c
ijkl
. En général, ce coût est le produit du flux
f
ij
entre les deux unités par la distance entre les deux sites d
kl
. Et le problème consiste à
minimiser le coût total de l’implantation des
n
unités sur les
n
sites.
Pour prendre un exemple concret, cela correspond à une entreprise qui possède
plusieurs usines de production qui interagissent entre elles. L’usine 2 a besoin du produit sorti
de l’usine 1 pour pouvoir faire son travail. Ainsi, il va se créer un flux de marchandises entre
ces usines, qui va lui-même générer des coûts financiers pour la firme. Celle-ci a donc tout
intérêt à bien répartir ses différentes usines sur les terrains qu’elle possède de manière à
diminuer le prix du transport des marchandises entre les sites, et donc ses coûts de production.
Plus le flux entre deux usines sera grand, plus la distance entre elles devra être petite.
Nous pouvons formaliser ce problème en introduisant les variables de décision x
ik
valant 1 si l’unité
i
est placée sur le site
k
et 0 sinon. Alors, le problème est le suivant :
{
}
{
}
{
}
⎪
⎪
⎩
⎪
⎪
⎨
⎧
∈
∀
=
∈
∀
=
∈
∑
∑
∑∑∑∑
=
=
=
=
=
=
n
i
x
n
k
x
et
x
Avec
x
x
d
f
Minimiser
n
k
ik
n
i
ik
n
i
n
j
n
k
n
l
jl
ik
kl
ij
,..,
1
1
,..,
1
1
1
,
0
1
1
1
1
1
1
Une autre formalisation classique de ce problème est de représenter une solution sous la
forme d’une permutation
p
de {1,..,n} où p(i) est le numéro du site sur lequel est placée
l’unité i. Alors, il faut :
{
}
n
de
ns
permutatio
des
ensemble
l
est
P
où
d
f
Minimiser
j
p
i
p
n
i
n
j
ij
P
p
,...,
1
'
)
(
)
(
1
1
∑∑
=
=
∈
Ce problème appartient à la classe des problèmes NP-difficiles. Et on peut constater
facilement que l’augmentation de la taille de l’instance engendre une explosion combinatoire
des répartitions possibles des unités sur les sites, ce qui rend illusoire une résolution exacte de
ce problème.
En effet, les nombre de permutations de {1,..,n} est de factorielle n. Il est donc impensable
d’envisager de parcourir toutes les possibilités pour en trouver la meilleure. D’où
l’omniprésence des heuristiques dans la résolution de ce problème. Du recuit simulé aux
colonies de fourmis, en passant par les méthodes Tabou, GRASP, ou les algorithmes
génétiques, quasiment toutes les métaheuristiques classiques ont été adaptées à ce problème.
b.
Utilisation des métaheuristiques pour ce problème
Les heuristiques font majoritairement appel soit à la recherche locale, soit à des
évolutions des solutions. C’est pourquoi nous allons classer ceux-ci selon ce critère.
•
Méthodes de recherche locale
La solution courante de ces algorithmes évolue en allant « regarder autour » si il n’y a
pas d’amélioration possible. Ceci fait donc appel à une notion de voisinage qu’il faut définir
dans notre cas.
Pour le problème d’affectation quadratique, une définition simple du voisinage est la
suivante : une permutation
p1
est voisine d’une permutation
p2
si elles diffèrent seulement
par un échange entre deux de leurs valeurs. Cette définition du voisinage a un double
avantage : d’une part, il est d’un taille raisonnable (
2
)
1
.(
−
n
n
voisins pour chaque
permutation), et d’autre part, la différence de coût entre deux permutations voisines est
facilement calculable.
Avec :
p
la solution courante
p
uv
la solution obtenue en échangeant le placement des unités
u
et
v
de
p
∆
p
(u,v) la variation de coût occasionnée par le passage de p à
p
uv
.
On a :
∑
≠
≠
=
−
−
=
∆
n
v
j
u
j
j
j
p
u
p
j
p
v
p
vj
uj
d
d
f
f
v
u
p
,
,
1
)
(
)
(
)
(
)
(
)
).(
(
.
2
)
,
(
Ainsi, par ces avantages, ce voisinage est très majoritairement utilisé dans toutes les
heuristiques de recherche locale.
La méthode qui a donné les meilleurs résultats est
la méthode Tabou
. Sa première
application au problème d’affectation quadratique est due
à Skorin-Kapov en 1990. Mais ce
sont des variantes que nous allons étudier ici.
La méthode Tabou robuste
, proposée par Taillard en 1991, reste une référence dans le
domaine. Elle est basée sur le voisinage décrit ci-dessus. Elle part d’une solution qu’elle
change en recherchant des améliorations dans son voisinage. Mais le principe de la méthode
tabou et qu’une liste des dernières positions rencontrées est tenue à jour. Par exemple, on
mémorise les 10 dernières solutions. Et un retour à une des positions de cette liste est interdit,
d’où le nom de la méthode. Cela permet de « visiter » les voisinages sans revenir
constamment au même endroit. La première particularité de la méthode Tabou robuste est que
la longueur de sa liste Tabou (ie le nombre de positions mémorisées et par conséquent
interdites) est réactualisée périodiquement et aléatoirement entre deux bornes (inférieures et
supérieures). La seconde particularité est que en plus d’accepter les modifications
améliorantes, cette méthode enregistre aussi les modifications qui replacent conjointement
deux unités sur des sites qu’elles n’ont pas occupées depuis très longtemps. Cela permet de
diversifier les recherches et d’essayer de sortir de minimums locaux.
La méthode Tabou réactive
, quant à elle, se base sur la mémorisation, en parallèle de la liste
Tabou, d’absolument toutes les positions déjà visitées. Ainsi, il est possible de détecter un
cycle à tout moment. Et dans ce cas, la longueur de la liste Tabou est modifiée pour empêcher
celui-ci. La longueur de la liste Tabou varie donc au cours de la recherche. Mais ici, son
évolution n’est pas aléatoire, mais liée à la recherche elle-même.
Il existe évidemment bien d’autres méthodes de recherche locale qui sont efficaces sur
ce problème. Nous ne pourrons malheureusement pas toutes les énumérer sous peine d’obtenir
un exposé extrêmement fastidieux, mais nous pouvons tout de même dire quelques mots sur
quelques unes d’entre elles.
Le recuit simulé
a été proposé dès 1984 pour ce problème par Burkard et Rendl, mais les
solutions obtenues alors ont été améliorées lors de variantes de cet algorithme d’années en
années.
La méthode GRASP
a elle aussi été adaptée au problème d’affectation quadratique en 1994
par Li, Pardalos et Resende. Cette méthode est simple, rapide et efficace : une approche
intéressante…
Enfin, les algorithmes dits de
colonies de fourmis
ont eux aussi été appliqués dans ce cadre,
avec, là encore, de multiples variantes.
Mais ce qu’il faut retenir de tous ces algorithmes, c’est qu’ils donnent tous des solutions
extrêmement satisfaisantes sur une grande partie des instances. Mais nous verrons ceci dans la
partie consacrée aux résultats de l’utilisation de ces heuristiques.
•
Les algorithmes évolutifs
Evidemment, la recherche locale n’a pas été la seule voie explorée pour la résolution
de ce problème tant étudié. Des heuristiques telles que les
algorithmes génétiques
(voir le
chapitre associé dans ce récapitulatif), ou les
méthodes de recherche par dispersion
ont
également pris part à la course à la meilleure solution. Ces deux exemples sont basés sur une
population de solutions qui évolue. Mais finalement, ils n’offrent, tous seuls, que peu de
résultats, se confinant souvent dans un domaine de l’espace et n’atteignant que rarement
l’optimum global.
Et c’est ainsi que sont nés les algorithmes hybrides évolutifs/recherche locale. En effet, lors
de l’évolution de la population dans ces algorithmes, les auteurs ont pensé à utiliser la
recherche locale sur ces solutions pour les améliorer, avant de les « accoupler » en
mélangeant leurs gênes. Ces hybridations d’algorithmes se sont finalement avérées très
efficaces, et c’est précisément ce que nous allons voir tout de suite.
•
Les résultats
Le problème d’affectation quadratique ayant généré un grand nombre de publications,
d’algorithmes tentant d’apporter des solutions, de variantes à ces algorithmes etc, Burkard,
Karisch et Rendl ont décidé de créer ce qui s’appelle la QAPLib, que l’on peut retrouver sur
l’adresse suivante :
http://www.opt.math.u-graz.ac.at/qaplib/
. Il s’agit en fait d’une
bibliothèque d’instances de problème d’affectation quadratique, sur laquelle tout le monde
peut essayer ses algorithmes.
Gambardella, Taillard et Dorigo ont testé, dans leur article de 1999 :
-
la recherche tabou robuste (RobuTS)
-
la recherche tabou réactive (ReacTS)
-
une implémentation récente du recuit simulé (Rec-Sim)
-
un algorithme hybride génétique/recherche locale (Hybrid-Gen)
-
un algorithme hybride colonies de fourmis/recherche locale (Hybrid-Ant)
sur un panel de 38 instances de la QAPLib de taille variant de 19 à 90, en laissant les
algorithmes tourner au maximum 2000 secondes.
Ils ont mesuré à partir de là le pourcentage d’erreurs de chaque solution trouvée par chaque
algorithme sur chaque instance par rapport à la meilleure solution connue. Vous pourrez voir
les résultats sur la page suivante. Mais ce que nous pouvons retenir de ce tableau, c’est que
toutes ces méthodes sont très efficaces pour la résolution de ce problème NP-difficile. Et
même si les algorithmes hybrides, complexes à implémenter, se montrent très performants, ils
restent comparables au vieux mais comme son nom l’indique très robuste RobuTS.
Intervalle d'erreur
RobuTS
ReacTS
(22 inst.)
Rec-Sim Hybrid-Gen Hybrid-Ant
< 0,01 %
12
-
1
13
13
0,01 % - 0,1 %
9
1
4
7
7
0,1 % - 1 %
12
17
18
15
10
1 % - 10 %
5
4
1
3
3
8
> 10 %
-
-
2
-
-
4.
Conclusion générale
Pour conclure sur cette synthèse, il est important de rappeler la place importante
qu’occupent les problèmes quadratiques dans les utilisations pratiques de l’optimisation. Il est
évident que toutes les situations ne peuvent pas être formalisées dans un contexte linéaire. Et
il arrive plus que fréquemment de tomber sur un problème d’optimisation qui s’avère être
quadratique.
Certes, d’un côté, les développements théoriques engendrés par l’exploration des
possibilités de la programmation quadratique et semidéfinie peuvent être extrêmement pointus
et obscurs. Malgré tout, ils offrent dans un nombre conséquent de cas une solution optimale. Il
est évident que la connaissance de tous ces concepts échappe à la plupart d’entre nous. Mais il
me semble important d’en présenter au moins une introduction, ce que je me suis attaché à
faire dans cet exposé. En effet, certaines méthodes, comme la relaxation lagrangienne par
exemple, s’avèrent très efficaces sur certains problèmes.
De l’autre côté se trouvent pour tous ces grands problèmes combinatoires (dont les
problèmes quadratiques font partie) les heuristiques qui permettent, elles, de trouver une
solution satisfaisante en un temps correct, mais dont on ne peut garantir l’optimalité.
Ainsi, je ne saurais que conseiller, malgré l’apparente difficulté de l’exercice (qui est
par ailleurs bien réelle), d’essayer de se plonger dans les multiples papiers de recherche sur
les développements théoriques dans ce domaine, avant de se jeter corps et âme dans
l’utilisation de toutes les heuristiques citées précédemment.
Alors pour en savoir plus sur la programmation quadratique et semidéfinie, c’est à
vous !
© 2010-2024 YouScribe