Université Mohamed El Bachir El Ibrahimi de Bordj Bou Arréridj

Faculté des Mathématiques et de l’Informatique

Département de Recherche Opérationnelle

Mémoire
Présentée par :
AGDOUCHE Fouzia
BENRAI Feriel
Pour l’obtention du diplôme de

Master
Filière : Des Mathématiques appliquées.
Spécialité : Méthodes et outils pour la recherche Opérationnelle.

Thème :
Étude théorique et numérique d’un algorithme de point
intérieur de type correcteur-prédicteur pour la
programmation linéaire.

Soutenu publiquement le 30 juin 2022 devant le jury composé de

[Link] Zoubir M.A.A. Président

[Link] Loubna M.C.B. Encadrant
[Link] Hillal M.A.A. Examinateur

Promotion 2021/2022
 •
Remerciements

A vant tout on remercie ” Allah” tout puissant pour la volonté, la patience que
nous a données d’accomplir ce travail.

U n grand remerciement à notre encadreur ” Dr. GUERRA Loubna ” ; maître

de conférence classe B ; à l’université Mohamed El-Bachir-El-Ibrahimi, Bordj
Bou Arréridj ; pour avoir accepté de diriger ce mémoire, et pour les conseils
fructueux et sa disposition, l’encouragement et l’orientations qu’elle nous a at-
tribuées.

N ous remercions les membres du jury pour leur présence, pour leur lecture atten-
tive de ce mémoire, ainsi que pour les remarques qu’ils m’adresseront lors de
cette soutenance afin d’améliorer mon travail.

N ous remercions tous les enseignants de la faculté des mathématiques et de l’in-

formatique de l’université Mohamed El Bachir El Ibrahimi de Bordj Bou Arré-
ridj.
Dédicace
Je dédie ce travail :

A ma chère mère et à mon cher père qui n’ont jamais

cessé de me supporter, me soutenir et m’encourager
durant mes années d’études. Qu ils trouvent ici le
témoignage de ma profonde gratitude et Te connaissance

A mes frères, mes grands-parents et ma famille qui me

donnent de l’amour et de la vivacité.

A tous ceux qui m’ont aidé - de près ou de loin - et ceux

qui ont partagé avec moi les moments d’émotion lors de
la réalisation de ce travail et qui m’ont chaleureusement
supporté et encouragé tout au long de mon parcours.

A tous mes amis qui m’ont toujours encouragé, et à qui

je souhaite plus de succès.

Merci !

AGDOUCHE F`o˘u˚zˇi`affl -
Dédicace
Je dédie ce modeste travail...

À le plus cher père du monde ’ Lakhmissi ’.

À la plus tendre du monde, ma mère ’Fadila ’.
Pour leur soutien moral, leur encouragement tout a long
de mes études.
Qu’Allah leur présente une bonne santé et une longue
vie.

Sans oublier la personne qui a en beaucoup de mérite

dans ce travail avec sont financier et moral merci
beaucoup ’GHARNOUT Abd Errezak’.

A tous mes frères ’Achref’ et ’Adem ’ et ma chère sœur

’Imen’.

A ma chère binôme ’Fouzia’ pour montre longue amité.

A mes belles amies ’ Imen ’ et ’Merbouha ’ .

Merci !

BENRAI F`eˇr˚i`e¨l -
Table des matières

Introduction 7

1 Rappels sur l’analyse convexe et la programmation mathématique 11

1.1 Préliminaires : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.1.1 Produit scalaire et norme . . . . . . . . . . . . . . . . . . . . . . . 11
1.2 Eléments d’analyse convexe . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.2.1 Ensemble et fonction convexe . . . . . . . . . . . . . . . . . . . . . 12
1.2.2 Ensemble et application affine : . . . . . . . . . . . . . . . . . . . . 16
1.3 Programmation mathématique . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.3.1 Notions de base . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.3.2 Classification d’un programme mathématique . . . . . . . . . . . . 18
1.3.3 Qualification des contraintes . . . . . . . . . . . . . . . . . . . . . 19
1.3.4 Existence et unicité d’une solution optimal d’une programme ma-
thématique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
1.3.5 Conditions d’optimalités . . . . . . . . . . . . . . . . . . . . . . . . 20
1.4 Méthode de Newten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

2 Algorithme de point intérieur de type prédicteur - correcteur pour la pro-

grammation linéaire 22
2.1 Programmation linéaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.1.1 définition du problème . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.2 Dualité en programmation linéaire . . . . . . . . . . . . . . . . . . . . . . . 23
2.2.1 Dualité faible . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.2.2 Dualité forte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.3 Formes d’un programme linéaire . . . . . . . . . . . . . . . . . . . . . . . . 24
2.3.1 Forme canonique . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.3.2 Forme standard . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.4 Modélisation de quelques problèmes linéaires . . . . . . . . . . . . . . . . 25
2.5 Méthode de trajectoire centrale . . . . . . . . . . . . . . . . . . . . . . . . 26
2.5.1 la trajectoire centrale . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.5.2 Nouvelle direction de recherche . . . . . . . . . . . . . . . . . . . . 27
2.5.3 La mesure de proximité . . . . . . . . . . . . . . . . . . . . . . . . 28
2.6 Algorithme correcteur-prédicteur . . . . . . . . . . . . . . . . . . . . . . . 30
2.6.1 Description de l’algorithme . . . . . . . . . . . . . . . . . . . . . . 30
2.6.2 Algorithme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
2.7 La convergence de l’algorithme et la analyse de la complexité . . . . . . . 32
2.7.1 Analyse de la strictement faisabilité après la phase de correction . 33
2.7.2 La convergence quadratique de la mesure de proximité . . . . . . 34
2.7.3 Analyse de la stricte faisabilité . . . . . . . . . . . . . . . . . . . . 37

5
 TABLE DES MATIÈRES

2.7.4 La convergence quadratique de la mesure de la proximité après la

phase de prédiction . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
2.7.5 L’influence du nouveau itéré en saut de dualité après la phase de
prédiction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
2.7.6 La mise à jour du paramètre barrière µ après la phase de prédiction 40
2.7.7 Analyse de la complexité . . . . . . . . . . . . . . . . . . . . . . . . 41

3 Implémentation numérique 42
3.1 Calcul des directions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
3.1.1 La phase de correction . . . . . . . . . . . . . . . . . . . . . . . . . 42
3.1.2 La phase de prédiction . . . . . . . . . . . . . . . . . . . . . . . . . 44
3.2 Choix alternative du pas de déplacement . . . . . . . . . . . . . . . . . . . 46
3.3 Tests numériques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

Conclusion 55

Bibliographie 56

6
Table des figures

1.1 Ensembles convexe et non convexe. . . . . . . . . . . . . . . . . . . . . . . . . 13

1.2 Ensemble S1 convexe. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.3 Ensemble S2 non convexe. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.4 Réunion des parties convexe. . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.5 Fonction convexe- concave. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.6 Ensemble affine(polyèdre). . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.7 Fonction affine. . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . 17
1.8 Minimum local et globale. . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
1.9 Résolution graphique. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

2.1 Un algorithme prédicteur-correcteur. . . . . . . . . . . . . . . . . . . . . . . . 31

7
Introduction

La programmation linéaire (P L) est un domaine important , grâce à son utilisation dans

different domaines, et notamment : l’architecture, ingénierie électrique,...
avant, la résolution d’un programme linéaire qui consistait à utiliser la méthode classique
du simplexe, qui est composé de deux phases dont la premier consiste à trouver une solution
de base réalisable de départ, et la deuxiéme est utilisé pour obtenir une solution optimale
en deuxième phase qui a une complexité exponentielle. Pour cela, on utilise les méthodes
des points intérieurs qui ont été initialisées pour la première fois par Karmakar en 1984
[14]. les méthodes de points intérieurs se distinguent en quatre types :
— Méthodes affines.
— Méthodes projectives.
— Méthodes de réduction de potentiel.
— Méthodes de la trajectoire centrale.
L’algorithme de trajectoire central (TC) de type primal-dual pour PL a été présenté pour
la première fois par Roos et al en 1997[22], ils utilisent les directions de Newton classiques
pour obtenir le nouveau itéré et ils ont montré que cet algorithme a une complexité poly-
nomiale. On note que l’algorithme de type correcteur-prédicteur pour la programmation
linéaire à été presenté par [18, 23]. En 2003 [5], Darvay a √ introduit une transformation
algébrique à l’équation de centralité ψ( xz
µ ) = ψ(e) où ψ(t) = t pour obtenir une nouvelle
direction de recherche.
En 2005, Darvay [6] a introduit l’algorithme
√ correcteur-prédicteur pour PL qui est basé
sur le même technique où ψ(t) = t avec le domaine D = [0, +∞] afin d’obtenir nouvelle
direction de recherche, il a montré que l’algorithme proposé a une complexité polynomiale.
Le meme auteur en 2016 [8] développe un algorithme de trajectoire central pour PL basé
sur une nouvelle
√ direction de recherche où la transformation algébrique équivalente est
ψ(t) = t − t. Pour θ = 271√n , ils ont montré théoriquement que la complexité de l’al-
gorithme proposé est polynomial mais numériquement est lente alors ils ont introduit un
algorithme correcteur-prédicteur.
En effet, en 2020 Darvay et al [10] proposent un algorithme
√ correcteur-prédicteur pour PL,
ils ont utilisé la transformation algébrique ψ(t) = t − t. ils ont montré que l’algorithme
associé a une complexité polynomiale avec θ = 5√1 n .
On s’intéresse à implémenter numériquement l’algorithme qui présente par Darvay se-
lon le choix de θ théorique et un autre choix alternative pour voir l’influence de θ sur le
comportement numérique. Ce mémoire est composé de trois chapitres :
• Dans le premier chapitre, on présente quelque définitions de produit scalaire, norme
et l’analyse convexe ainsi la programmation mathématique et la méthode de Newton
qui utilisé par la suite.
• Le deuxième chapitre est consacré à la définition des problèmes primal-dual de la
programmation linéaire, on a étudié l’algorithme correcteur-prédicteur basé sur une

8
 Introduction

√
nouvelle direction de recherche pour resoudre le PL où ψ(t) = t − t.
• Dans le troisième chapitre, on implémente numériquement des pas de déplace-
ment θ de la phase de prédiction, et on présente les tests numériques appliqués sur
quelques problemes linéaire, avec la comparaison entre le choix théorique de θ et
d’autre alternatives du pas de déplacement.
On terminera ce mémoire par une conclusion générale.

9
 Introduction

Notations
Rn : L’espace des vecteurs réels de dimension n,
Rn+ : L’orthant positif de Rn ,
Rm×n : L’espace vectoriel des matrices réelles de taille (m × n),
k.k : Norme euclidienne sur Rn ,
rg(A) : Le rang de la matriceA ∈ Rm×n ,
At : Le transposé d’une matrice A ∈ Rm×n ,
aij : Elément de la matrice A ∈ Rm×n ,
xt : Transposé d’un vecteurx ∈ Rn ,
xz = xi zi , ∀i,
x xi
z = zi , ∀i; zi , 0,
x 2 = xi2 , ∀i,
−1 1
x = xi (xi , 0, ∀i),
x ≥ 0(x > 0) = xi ≥ 0(xi > 0), ∀i,
ò 0(x < 0) =
x x ≤ 0(xi < 0), ∀i,
√i
x = xi (xi > 0, ∀i),
e : Un vecteur de Rn tel que ei = 1, ∀i = 1, ..., n,
1
2e = ( 12 , ..., 21 ),
∆x, ∆z : les directions de Newton,
0m×n : La matrice zéro (m × n),
Im : La matrice identité de taille (m × m),
min(x) : min(xi ), i = 1, ..., n,
diag(x) = X la matrice diagonale avec Xii = xi .

10
 Introduction

Terminologie
PM : Programmation mathématique,
PL : Programmation linéaire,
(P) : Le problème linéaire sous forme primal,
(D) : Le problème dual de (P),
K.K.T : Karush-Kuhn-Tucker,
TC : Trajectoire centrale,
CPI : Condition de points intérieurs.

11
Chapitre 1

Rappels sur l’analyse convexe et la

programmation mathématique

Dans ce chapitre, nous rappelons brièvement certaines propriétés de l’analyse convexe, et

quelques notions fondamentales de la programmation mathématiques.

1.1 Préliminaires :
1.1.1 Produit scalaire et norme
On commence par la définition du produit scalaire de deux vecteurs.

Définition 1.1.1.
Étant donné deux vecteurs x, y ∈ Rn , le produit scalaire euclidien est définie par :
n
X
t
hx, yi = x y = xi yi .
i=1

Et de la norme euclidienne associée :

 1 p
||x|| = xt x 2 = hx, xi.

Définition 1.1.2.
La norme vectorielle est une application de Rn dans R+ notée par k.k et vérifie les conditions
suivantes :
1. ∀x ∈ Rn : kxk = 0 ⇔ x = 0,
2. ∀λ ∈ R, ∀x ∈ Rn : kλxk = |λ|kxk,
3. ∀x, y ∈ Rn : kx + yk ≤ kxk + kyk.

On note que les normes usuelles sur Rn , pour tout x ∈ Rn sont :

n
X
kxk1 = |xi |,
i=1
v
n
t
X
kxk2 = (xi )2 ,
i=1

12
 CHAPITRE 1. RAPPELS SUR L’ANALYSE CONVEXE ET LA PROGRAMMATION
MATHÉMATIQUE

kxk∞ = max |xi |.

i
Sur Rn les trois normes kxk1 , kxk2 , kxk∞ sont équivalentes. C’est à dire :

kxk∞ ≤ kxk2 ≤ kxk1 ≤ nkxk∞ .

Ces définitions est très importante par la suite.

Définition 1.1.3.
L’ensemble de m vecteurs vi est dit linéairement indépendant si et seulement si :
m
X
λi vi = 0 ⇒ λi = 0, ∀i = 1, ..., m.
i=1

Remarque 1.1.1.
La matrice B ∈ Rm×m qui est formé de m vecteurs linéairement indépendantes est inversible.

Définition 1.1.4.
Soit A ∈ Rm×n , le nombre maximale des lignes ( ou des colonnes) de A linéairement indépen-
dantes est appelé le rang de A, est noté par rg(A).
De plus, A est dite de plein rang si :

rg(A) = min(m, n).

1.2 Eléments d’analyse convexe

La notion de convexité est un propriété mathématique important pour l’étude théorique et
numérique des problèmes d’optimisation. On présente dans cette section quelques notions
d’analyse convexe d’usage courant.

1.2.1 Ensemble et fonction convexe

Définition 1.2.1.
Un sous ensemble S ⊆ Rn est dit convexe si le segment joignant toute paire de points apparte-
nant à S appartient également entièrement à S. C’est à dire :

∀(x, y) ∈ S, λx + (1 − λ)y ∈ S. pour tout λ ∈ [0, 1] .

13
 CHAPITRE 1. RAPPELS SUR L’ANALYSE CONVEXE ET LA PROGRAMMATION
MATHÉMATIQUE

Figure 1.1 – Ensembles convexe et non convexe.

Exemple 1.1.
Soit S1 = {x ∈ R2 : x12 + x22 ≤ 4, x1 + x2 ≤ 1}.
La figure (1.2) montre que S1 est convexe.

Figure 1.2 – Ensemble S1 convexe.

Soit S2 = {x ∈ R2 : x12 + x22 − 6 ≤ 0, x13 − x2 ≥ 0, x1 , x2 ≥ 0}.

La figure suivante montre que S2 est non convexe.

Figure 1.3 – Ensemble S2 non convexe.

14
 CHAPITRE 1. RAPPELS SUR L’ANALYSE CONVEXE ET LA PROGRAMMATION
MATHÉMATIQUE

• Opérations sur les ensembles convexe

1. L’intersection ∩i∈I Si d’une famille quelconque d’ensembles convexes (Si )i∈I est un en-
semble convexe.
2. Soient S1 , S2 deux ensembles convexes, alors les ensembles :

S1 + S2 = {x + y : x ∈ S1 et y ∈ S2 },
S1 − S2 = {x − y : x ∈ S1 et y ∈ S2 },
S1 × S2 = {(x, y) : x ∈ S1 et y ∈ S2 },
sont convexes.
3. Le produit d’un ensemble convexe S avec un scalaire α ∈ R est un convexe

αS = {αx : x ∈ S}.

Remarque 1.2.1.
La réunion des parties convexes généralement pas convexes : l’hexagone et l’ellipse ci-dessous
sont convexes, leur intersection il est convexe mais leur réunion ne l’est pas convexe.

Figure 1.4 – Réunion des parties convexe.

Définition 1.2.2.
Soit S un ensemble non vide. On dit que S est un polyèdre convexe s’il est de la forme :

S = {x ∈ Rn : αit x ≤ bi , i = 1, · · · , m},

où αi est un vecteur non nul de Rn et bi un scalaire pour i = 1, · · · , n.

Remarque 1.2.2.
S peut s’écrire sous la forme matricielle suivante :

S = {x ∈ Rn : Ax ≤ b},

où A est un matrice de Rm×n et b un vecteur de Rm .

15
 CHAPITRE 1. RAPPELS SUR L’ANALYSE CONVEXE ET LA PROGRAMMATION
MATHÉMATIQUE

Définition 1.2.3.
La fonction f : S −→ R est dite convexe sur S si :

f (λx + (1 − λ) y) ≤ λf (x) + (1 − λ) f (y), ∀λ ∈ [0, 1] , ∀x, y ∈ S.

Où d’une manière équivalente : si ∀n ∈ N ∗ , ∀λi ≥ 0, ni=1 λi = 1, xi ∈ S.
P

f Σni=1 λi xi ≤ Σni=1 λi f (xi ) ,

 

et si l’inégalité au dessus est stricte, alors f est dite strictement convexe pour tout x , y.

Remarque 1.2.3.
On dit que f est concave si (−f ) est convexe.

Figure 1.5 – Fonction convexe- concave.

Exemple 1.2.
- la fonction R −→ R, x −→ |x| est convexe.
- la fonction R∗+ −→ R, x −→ ln (x) est concave.

• Opérations sur les fonctions convexes

1. Soient f1 , ..., fk : Rn −→ R des fonctions convexes alors :
k
(i) f (x) = αi fi (x) , αi ≥ 0 est convexe.
P
i=1
(ii) f (x) = max1≤i≤k fi (x) est convexe.
2. Soit g : R −→ R une fonction convexe croissante et h : Rn −→ R une fonction convexe,
alors la fonction composée g ◦ h est convexe.
3. Soit g : Rn −→ R une fonction concave et

S = {x ∈ Rn : g (x) > 0}.

Supposons que S non vide, alors la fonction f : S −→ R définie par :f (x) = 1

g(x)
est convexe.

16
 CHAPITRE 1. RAPPELS SUR L’ANALYSE CONVEXE ET LA PROGRAMMATION
MATHÉMATIQUE

1.2.2 Ensemble et application affine :

Définition 1.2.4.
Un sous ensemble C de Rn est dit affine si :

∀x, y ∈ C et ∀λ ∈ R, λx + (1 − λ) y ∈ C.

Définition 1.2.5.
L’ensemble C qui s’écrit sous la forme :

C = {x ∈ Rn : pit x ≤ αi , i = 1, · · · , m},

où pi est un vecteur non nulle de Rn et αi est un scalaire pour i = 1, · · · , m est dite polyèdre .

Figure 1.6 – Ensemble affine(polyèdre).

Définition 1.2.6.
Une fonction f : C ⊆ Rn −→ Rm est dite affine si :

∀x, y ∈ C, ∀λ ∈ R, f [λx + (1 − λ)y] ≤ λf (x) + (1 − λ) f (y) .

17
 CHAPITRE 1. RAPPELS SUR L’ANALYSE CONVEXE ET LA PROGRAMMATION
MATHÉMATIQUE

Figure 1.7 – Fonction affine.

Remarque 1.2.4.
Soit g : Rm −→ R une fonction et h : Rn −→ Rm une fonction affine (i.e., h (x) = Ax + b, A ∈
Rm×n et b ∈ Rm ), alors la fonction composée g ◦ h est convexe.

1.3 Programmation mathématique

1.3.1 Notions de base
• Problème d’optimisation
Sous sa forme générale, un problème d’optimisation s’écrit comme suit :

minf (x)


x ∈ C,



où f : Rn → R continue, φ , C ⊆ Rn est l’ensemble des contraintes .

Si C = Rn , ce problème est appelé problème d’optimisation sans contraintes.

• Programme mathématique
Un programme mathématique est un problème d’optimisation qui consiste à trouver une
solution du problème qui maximise ou minimise une fonction donnée sous un ensemble de
contraintes.
En générale, un programme mathématique est défini par :

min f (x)

(P M) 

x ∈ D,


où f : Rn → R est appelée fonction objective de (P M), D ⊆ Rn est l’ensemble des

contraintes. Souvent D est présenté comme suit :
D = {x ∈ Rn /gi (x) ≤ 0, hj (x) = 0, i = 1, .., m, j = 1, ..., p},

18
 CHAPITRE 1. RAPPELS SUR L’ANALYSE CONVEXE ET LA PROGRAMMATION
MATHÉMATIQUE

avec gi , hj sont des fonctions de Rn → R.

• Solution réalisable
On appelle solution réalisable de (P M) tout point vérifiant les contraintes c’est à dire :
x∗ ∈ D.

• Solution optimale globale

Une solution réalisable qui optimise l’objectif sur D est dit solution optimale globale de
(P M) (c’est à dire : x∗ ∈ D est un minimum global de f si et seulement si pour tout x ∈
D, f (x∗ ) ≤ f (x)).

• Solution optimale locale

Tout point x∗ ∈ D satisfaisant :

f (x∗ ) ≤ f (x) , ∀x ∈ D ∩ v,

où v est un voisinage de x∗ est appelée solution optimale locale.

On note que f (x∗ ) est appelée valeur optimale de (P M).

Figure 1.8 – Minimum local et globale.

1.3.2 Classification d’un programme mathématique

On classifie le problème(P M) à partir de deux propriétés fondamentales à savoir la convexité
et la différentiabilité de la fonction objectif et les contraintes :
1. (P M) est différentiable si les fonctions f , gi , hj sont différentiables.
2. (P M) est convexe si f , gi sont convexes et hj sont affines.
On note que Si (P M) est convexe, alors tout optimum locale est un optimum globale.

19
 CHAPITRE 1. RAPPELS SUR L’ANALYSE CONVEXE ET LA PROGRAMMATION
MATHÉMATIQUE

1.3.3 Qualification des contraintes

La condition de qualification des contraintes est satisfaite pour tout x ∈ D dans l’un des
trois cas suivants :
1. Les contraintes sont affines (D est un polyèdre convexe).

2. La condition de Slater : Si D est convexe (c-à-d gi (x) sont convexes et hj (x) sont affines)
et int(D) , φ c-à-d
∃x0 : gi (x0 ) < 0 et hj (x0 ) = 0 , ∀i, j.
3. La condition de Magazarian-Fromowitz : Si les gradients des contraintes saturées en x ∈ D
sont linéairement indépendants.

1.3.4 Existence et unicité d’une solution optimal d’une programme

mathématique
• Existence

Théorème 1.3.1. (Weirstrass)

Si f est une fonction continue sur D ⊆ Rn , D est compact (fermé et borné), alors (PM) admet
au moins une solution optimale x∗ ∈ D.

Exemple 1.3.
Considérons le (P M) suivant :

minf (x) = x1 + x2



x12 + x22 ≥ 1


(1.1)


x12 + x22 ≤ 2




x1 , x2 ≥ 0.



f est une fonction continue et l’ensemble des solutions réalisables qui donne par l’arc est compact
(voir la figure 1.9). D’après le théorème 1.3.1 on obtient une solution optimale de (1.1) qui n’est
pas unique.

20
 CHAPITRE 1. RAPPELS SUR L’ANALYSE CONVEXE ET LA PROGRAMMATION
MATHÉMATIQUE

Figure 1.9 – Résolution graphique.

Corollaire 1.3.1.
Si D ⊆ Rn est non vide et fermé et si f est continue et coercive sur D (c-à-d f (x) → +∞ lorsque
||x|| → +∞), alors (P M) admet au moins une solution optimale.

• Unicité
Si f est strictement convexe et l’ensemble D est convexe, alors si (P M) admet une solution
optimale, la solution est unique .

Remarque 1.3.1.
La strict convexité n’assure pas l’existence de la solution mais assure l’unicité .

1.3.5 Conditions d’optimalités

Le théorème suivant dit de Karush-Kuhn-Tucker-Lagrange donne une condition nécessaire
d’optimalité (condition du premier ordre).

Théorème 1.3.2.
Supposons que les fonctions f , gi , hj sont de classe C 1 dans un voisinage de x ∈ D et que les
contraintes vérifient une des trois conditions de qualification déja citée. Si f a un minimum
local en x sur D alors ∃λ ∈ Rm p
+ , ∃µ ∈ R tel que :
 m p
5f (x) + λ 5 g (x) + µj 5 hj (x) = 0,

 P P

 i i
i=1 j=1

(K.K.T )


λi gi (x) = 0, ∀i = 1, ....., m





h (x) = 0, ∀j = 1, ...., p.

j

Les quantités λi et µi sont appelées multiplicateurs de Karush-Kuhn-Tucker-Lagrange.

Remarque 1.3.2.
1. Si les contraintes de (P M) ne sont pas qualifiées en x, les conditions de (K.K.T) ne
s’appliquent pas.
2. Si (P M) est convexe, les conditions de (K.K.T) sont à la fois nécessaires et suffisantes
pour que x soit un minimum global.

21
 CHAPITRE 1. RAPPELS SUR L’ANALYSE CONVEXE ET LA PROGRAMMATION
MATHÉMATIQUE

1.4 Méthode de Newten

Parmi les méthodes les plus populaires appliquées pour la résolution du système d’équa-
tions non linéaire(K.K.T) est la méthode de Newton ,dans ce qui suit nous décrivons son
principe.
On considère le problème suivant :

F(x) = 0, où F : Rn → Rn et n ≥ 2.
c-à-d trouver x ∈ Rn tel que : 



f1 (x1 , ..., xn ) = 0,
f2 (x1 , ..., xn ) = 0,



....





fn (x1 , ..., xn ) = 0.



Chaque équation fi (x1 , .., xn ) = 0 est considéré comme une surface de Rn × Rn ; l’intersec-
tion de n surfaces nous donne la solution x ∈ Rn ; F(x) = 0. Alors on peut remplacer chaque
surface associé à fi (x) = 0 par l’hyperplan qui est tangent au point x(k) .

On définit alors le point x(k+1) comme l’intersection de ces n hyperplan avec l’hyperplan
y = 0.
On a :
F(x(k+1) ) ' F(x(k) ) + F 0 (x(k) )(x(k+1) − x(k) ),
alors :
0 = F(x(k) ) + F 0 (x(k) )(x(k+1) − x(k) ),
et par conséquent :
x(k+1) = x(k) − [F 0 (x(k) )]−1 F(x(k) ).
Puisque F : Rn → Rn , alors F 0 (x(k) ) = J(x(k) ) ou J(x) désigne la matrice jacobienne donc :

x(k+1) = x(k) − [J(x(k) )]−1 F(x(k) ).

Pour éviter le calcul de l’inverse de la matrice jacobienne on résoud le système linéaire

suivant :
OF 0 (x(k) )∆x(k) = −F(x(k) ).
Et on prend :
x(k+1) = x(k) + ∆x(k) .

22
Chapitre 2

Algorithme de point intérieur de type

prédicteur - correcteur pour la
programmation linéaire

Dans ce chapitre, on présente une synthèse sur le problème linéaire et ainsi la méthode de
point intérieur de type prédicteur -correcteur basée sur une nouvelle direction de recherche
pour PL.

2.1 Programmation linéaire

2.1.1 définition du problème
Un programme linéaire est un modèle d’optimisation mathématique qui à pour objectif de
trouver le maximum où le minimum d’une forme linéaire dite fonction objectif en satis-
faisant certaines égalités et / ou inégalités dites contraintes. En langage mathématique un
programme linéaire s’écrit sous sa forme primal standard suivante :
min ct x




(P) 

Ax = b,


x ≥ 0.



tels que :
c ∈ Rn , A ∈ Rm×n , b ∈ Rm des données et x ∈ Rn+ (inconnu).
On note par :
— L’ensemble des solutions réalisables primales de (P) est :

FP = {Ax = b, x ≥ 0} .
On note que Fp est un polyèdre convexe fermé.
— L’ensemble des solutions strictement réalisable primales est :
Fp+ = {Ax = b, x > 0} .
— La valeur optimale primale du problème (P) est définie par :
val(P ) = inf ct x : Ax = b, x ∈ Rn+ .
n o
x
— x∗ est une solution optimale primale du problème (P) si :
x∗ ∈ Fp et val(P ) = ct x∗ .

23
 CHAPITRE 2. ALGORITHME DE POINT INTÉRIEUR DE TYPE PRÉDICTEUR -
CORRECTEUR POUR LA PROGRAMMATION LINÉAIRE

2.2 Dualité en programmation linéaire

Le dual de (P) est donné par :

max bt y




(D) 
 t

A y + z = c,
y ∈ Rm , z ≥ 0,



où l’inconnu est (y, z) ∈ Rm × Rn+ .

— L’ensemble des solutions réalisables duales de (D) est noté par :

FD = At y + z = c, z ≥ 0 et y ∈ Rm .
n o

— L’ensemble des solutions strictement réalisable duales de (D) est noté par :
+
= At y + z = c, z > 0 et y ∈ Rm .
n o
FD

— La valeur optimale dual de (D) est définie par :

val(D) = sup bt y : At y + z = c, z ≥ 0 et y ∈ Rm .
n o
(y,z)

— On dit que (y ∗ , z∗ ) est une solution optimal dual de (D) si :

(y ∗ , z∗ ) ∈ FD et val(D) = bt y ∗ .

— Et on note par :

FP × FD et FP+ × FD
+
,
les ensembles des solutions réalisables primales-duales et strictement réalisable primales-
duales de (P) et (D) respectivement.

2.2.1 Dualité faible

Définition 2.2.1. (Saut de dualité)
Soient x ∈ FP , (y, z) ∈ FD , alors la différence :

val(P ) − val(D) = ct x − bt y,
= xt z.

est appelée le saut de dualité des problèmes (P) et (D).

Théorème 2.2.1. [22]

Soit x et z deux solutions réalisables de (P) et (D) respectivement, alors

ct x − bt y = xt z ≥ 0.

Si le saut de dualité xt z = 0, alors x est un solution optimal de (P) et (y, z) solution optimale
de (D).

24
 CHAPITRE 2. ALGORITHME DE POINT INTÉRIEUR DE TYPE PRÉDICTEUR -
CORRECTEUR POUR LA PROGRAMMATION LINÉAIRE

Preuve.
On a :

ct x − bt y = (At y + z)t x − (Ax)t y,

= (y t A + zt )x − xt At y,
= hAt y, xi + hz, xi − hAx, yi.

Comme hAt y, xi = hAx, yi, donc :

ct x − bt y = xt z,
n
xi zi ≥ 0 car x ≥ 0 et z ≥ 0.
X
=
i=1

Ce qui achève la preuve.

2.2.2 Dualité forte

Théorème 2.2.2. [22]
Soient (x, y) ∈ FP × FD une solution réalisable de (P) et (D), respectivement tel que :

bt y = ct x.

Alors x et y sont des solutions optimales de (P) et (D).

Corollaire 2.2.1.

— Si ct x est non borné inférieurement sur FP alors (D) est non réalisable ( l’ensemble des
contraintes duales FD est vide ).
— Si bt y est non borné supérieurement alors (P) est non réalisable (c-à-d :FP est vide).
— Si (P) est non réalisable alors (D) est non borné(et réciproquement ).

2.3 Formes d’un programme linéaire

On peut montrer que tout programme linéaire peut se ramener à l’une des deux formes
suivantes :

2.3.1 Forme canonique

On peut écrire un programme linéaire sous forme canonique, lorsque toutes ses contraintes
sont des inégalités et toutes ses variables sont non-négatives. C’est à dire :

min ct x





Ax ≥ b(ou ≤),



x ≥ 0,



où x = (x1 , ..., xn )t ∈ Rn , c = (c1 , ..., cn )t ∈ Rn , b = (b1 , ..., bm )t ∈ Rm et A est une matrice de

taille m × n.

25
 CHAPITRE 2. ALGORITHME DE POINT INTÉRIEUR DE TYPE PRÉDICTEUR -
CORRECTEUR POUR LA PROGRAMMATION LINÉAIRE

2.3.2 Forme standard

On peut écrire un programme linéaire sous forme standard, lorsque toutes ses contraintes
sont des égalités et toutes ses variables sont non-négatives. C’est à dire :

min ct x





Ax = b,



x ≥ 0.



2.4 Modélisation de quelques problèmes linéaires

Rappel
Les étapes de modélisation d’un problème de PL sont les suivantes :

1) Identifier les variables de décision .

2) Identifier les contraintes en les exprimant sous la forme d’équations ou d’inéquations
linéaires.
3) Identifier l’objectif et le représenter sous forme linéaire en fonction des variables de
décision, puis spécifier s’il faut maximiser ou bien minimiser l’objectif.

Exemple 2.1.
Une avion peut porter W kg supplémentaire sur un vol régulier, il y a n colis à transporter et
chaque colis i, i = 1, 2, .., n pèse ai et génère un profit de pi en dinar.
Ce problème est un modèle du sac à dos.
Considérons les variables binaires

1 si le coli i, i = 1, 2, 3, ..., n

xi = 

0 si non .


Le modèle peut s’écrire sous la forme suivante :

max Z = ni=1 pi xi
 P



Pn


 i=1 ai xi ≤ W ,
x ∈ {0, 1}.



Exemple 2.2.
Une compagnie de taxi dispose de quatre véhicules libres et doit transporter quatre clients. Le
but de la compagnie est d’assigner un taxi par client en minimisant la somme des distances par-
courues. Les distances respectives (en kilomètres) entre les taxis et les voyageurs sont données
par le tableau suivant :

Distance Client 1 Client 2 Client 3 Client 4

Taxi 1 6 3 4 5
Taxi 2 4 5 4 6
Taxi 3 5 6 6 7
Taxi 4 4 4 3 5

26
 CHAPITRE 2. ALGORITHME DE POINT INTÉRIEUR DE TYPE PRÉDICTEUR -
CORRECTEUR POUR LA PROGRAMMATION LINÉAIRE

Le problème de cette compagnie de taxis appartient à la classe "Problème d’affectation" où il

s’agit d’affecter chacun des taxi à un seul client ou voyageur.
Pour cela, considérons les variables de décision suivantes :

1 si le taxi "i" est affecter au voyageur "j" ,

xij = 

0 si non .


Avec i = 1, 2, 3, 4 et j = 1, 2, 3, 4 au total on dispose de 16 variables de décision.

Les contraintes :
— Chaque taxi i est affecté à un et un seul voyageur j
4
X
xij = 1, i = 1, 2, 3, 4.
j=1

— Chaque voyageur j est affecté à un et un seul taxi i

4
X
xij = 1, j = 1, 2, 3, 4.
i=1

— Toutes les variables sont booléennes xij ∈ {0, 1}, i = 1, 234, j = 1, 2, 3, 4.

La fonction objectif :
L’objectif de la compagnie en question est d’affecter ces 4 taxis aux 4 voyageurs de manière
à minimiser les distances parcourues. Notons par cij la distance en kilomètre entre le taxi
i = 1, 2, 3, 4 et le voyageur j = 1, 2, 3, 4. Notons que ces distances sont données dans le tableau
précédent.
La fonction objectif s’écrit alors 4i=1 4i=1 cij xij .
P P

min Z = 4i=1 4i=1 cij xij

 P P



 P4
 j=1 xij = 1, i = 1, 2, 3, 4 ,



P4
i=1 xij = 1, j = 1, 2, 3, 4 ,





xij ∈ {0, 1}, i = 1, 2, 3, 4, j = 1, 2, 3, 4.



2.5 Méthode de trajectoire centrale

2.5.1 la trajectoire centrale
On rappelle qu’on cherche à résoudre un programme linéaire (P) qui est défini par :

min ct x




(P) 

Ax = b,


x ≥ 0,



et sont dual est donné par :

max bt y




(D) 
 t

A y + z = c,
y ∈ Rm , z ≥ 0.



Pour résoudre les deux problèmes (P) et (D), on suppose qu’ils vérifient les hypothèses
suivantes :

27
 CHAPITRE 2. ALGORITHME DE POINT INTÉRIEUR DE TYPE PRÉDICTEUR -
CORRECTEUR POUR LA PROGRAMMATION LINÉAIRE

Hypothèses
1. la matrice A est de plein rang ( c-à-d : rg(A) = m ≤ n).
2. Condition de point intérieur (CPI) : ∃(x0 , y 0 , z0 ) ∈ FP+ × FD
+
, tels que :
Ax0 = b,




At y 0 + z0 = c,




x0 > 0, z0 > 0, y 0 ∈ Rm .



On note que (P) consiste à minimiser une fonction linéaire (convexe) sous l’ensemble des
contraintes qui est un polyèdre convexe. Comme FP est non vide (hypothèse 2), ∃z ∈
Rn+ ; ∃y ∈ Rm . Alors les conditions d’optimalité de Karuch -Kuhn- Tucher sont nécessaires
et suffisantes et s’écrivent comme suit :
 n m

O(c t x) − P z (Ox ) + P y (O(b − Ax)) = 0,
i i i



i=1 j=1

(K.K.T ) 

.



At x = b,
z x = 0.


i i

Après la dérivation de premier équation de ce système on obtient :

c − z − At y = 0,




 t


 A x = b,
zx = 0.



Donc :



Ax = b,
At y + z = c, (2.1)




xz = 0, x > 0, z > 0 et y ∈ Rm .



Dont la dernière équation est dite équation de complémentarité.

- L’idée principal de la méthode de trajectoire est de perturbé la dernière équation le sys-
tème(2.1). Alors, on obtient :



Ax = b,
(2.2)
 t


A y + z = c,
xz = µe, x > 0, z > 0 et y ∈ Rm ,



tel que µ > 0, e = (1, ..., 1)t ∈ Rn . Il est prouvé [22] qu’il existe une solution unique (x(µ), y(µ), z(µ))
pour le système (2.2) pour tout µ > 0. L’ensemble (x(µ), y(µ), z(µ)); µ > 0 s’appelle la tra-
jectoire central (voir [17, 23]). De plus, si µ −→ 0 alors xt z tend vers le zéro c-à-d trouver
une solution optimale pour (P) et (D) revient à résoudre le système (2.2).

2.5.2 Nouvelle direction de recherche

Afin d’obtenir de nouvelles directions
! de recherche , Darvay [8], a remplacé l’équation
xz
de centralité xz = µe par ψ = ψ(e), où ψ : R+ −→ R+ qu’on suppose l’invere ψ −1
µ

28
 CHAPITRE 2. ALGORITHME DE POINT INTÉRIEUR DE TYPE PRÉDICTEUR -
CORRECTEUR POUR LA PROGRAMMATION LINÉAIRE

existe. Donc le système (2.2) s’écrit sous la forme équivalent suivante :

Ax = b, x ≥ 0,




(2.3)
 t
A y +z = c, z ≥ 0,



ψ xz = ψ (e) .


µ

En utilisant la méthode de Newton pour résoudre le système non linéaire (2.3), on obtient
le système suivant :

A∆x = 0,




(2.4)
 t
A ∆y +∆z = 0,  



 z ψ 0 xz ∆x + x ψ 0 xz ∆z = ψ (e) − ψ xz .

  
µ µ µ µ µ

Où 4x, 4y, 4z désigne les directions de recherche, par conséquent on définit le vecteur v
pour tout vecteur réalisable primal x > 0, et le vecteur réalisable dual z > 0 :

xz
r
v= .
µ
On définit les vecteurs normés de la direction de déplacement dx et dz comme suit :
v∆x v∆z
dx := , dz := . (2.5)
x z
On a,

µv(dx + dz ) = z∆x + x∆z, (2.6)

et
∆x∆z
dx dz = . (2.7)
µ
On peut facilement vérifier que le système (2.4) s’écrit sous la forme suivante :

Adx = 0,



 t ∆y

A µ + dz = 0, (2.8)




d + d = p ,

x z v

où
x
A := A diag( ),
v
et

ψ(e) − ψ(v 2 )
pv := .
vψ 0 (v 2 )

2.5.3 La mesure de proximité

pour analyser l’algorithme on définie une mesure de proximité comme suit :
kpv k2
δ(v) = .
2
• Pour les différents choix de ψ on obtient des valeurs différents pour pv et δ(v) :

29
 CHAPITRE 2. ALGORITHME DE POINT INTÉRIEUR DE TYPE PRÉDICTEUR -
CORRECTEUR POUR LA PROGRAMMATION LINÉAIRE

1. Si ψ(t) = t alors pv = v −1 − v et δ(v) = 12 kv −1 − vk qui étudié par Ross [22].

√
2. Si ψ(t) = t alors pv = 2(e − v) et δ(v) = ke − vk présenté par Darvay [5].
√
3. Si ψ(t) = t − t alors :

2(v − v 2 )
pv = , (2.9)
2v − e
et
v − v2
δ(v) = ,
2v − e 2
présenté par dravay[8]
C’est facile de vérifie que :

δ(v) = 0 =⇔ v = e ⇔ xz = µe.

Soit

qv = dx − dz .
Puisque dx et dz sont orthogonal, c-à-d dxt dz = 0 alors :

kpv k2 = kqv k2 ,
c-à-d :

kdx + dz k2 = kdx − dz k2 .
Et par conséquent :

kqv k2 kpv k2
δ (x, z; µ) = = .
2 2
De plus,
pv + qv p − qv
dx = et dz = v ,
2 2
alors :

pv2 − qv2
dx dz = . (2.10)
4
Les bornes inférieure et supérieure sur les composantes du vecteur v sont présentées par le
lemme suivant.

Lemme 2.5.1. ( [15], Lemme 2) Si δ := δ(v), alors

1 1 1
+ ≤ vi ≤ + ρ(δ), i = 1, .., n ,
2 4ρ(δ) 2
q
1
où ρ(δ) = δ + 4 + δ2 .

30
 CHAPITRE 2. ALGORITHME DE POINT INTÉRIEUR DE TYPE PRÉDICTEUR -
CORRECTEUR POUR LA PROGRAMMATION LINÉAIRE

2.6 Algorithme correcteur-prédicteur

2.6.1 Description de l’algorithme
Dans cette section, on présent un algorithme de trajectoire central (TC) pour les problèmes
PL basés sur les techniques de Darvay et al. Pour cela, on définit un voisinage N (τ) du
trajectoire central comme suit :

N (τ) := (x, y, z) : Ax = b, At y + z = c, x > 0, z > 0, δ(x, z; µ) ≤ τ ,

n o

où 0 < τ < 1. L’algorithme commence par une solution primale-duale strictement réalisable
donnée (x0 , y 0 , z0 ) ∈ N (τ). Si pour l’itération courante (x, y, z), nµ > , alors l’algorithme
calcule une nouvelle itération en exécutant les étapes de correction et prédiction.
Dans l’étape de correction, on définit :

xz x
r
v= , A = A diag( ),
µ v

on obtient les directions de recherche dx et dz par la résolution de (2.8) avec pv donné en

(2.9), c’est-à-dire :
Adx = 0,



 At ∆y + d = 0,

(2.11)


 µ z
2
 d + d = 2(v−v ) .


x z 2v−e
En utilisant (2.5), on obtient :
x z
∆x = dx , ∆z = dz , (2.12)
v v
l’itération du correcteur est obtenue par une étape de Newton complet comme suit :

(x+ , y + , z+ ) := (x, y, z) + (∆x, ∆y, ∆z).

Dans l’étape du prédiction, on définit :

x+ z+ + x+
r
+
v = , A = Adiag( + ),
µ v
p p
et on obtient les directions de recherche dx et dz en résolvant le système suivant :
p
A+ dx = 0,



 + t ∆p y

p
(2.13)


 A µ + dz = 0,
 dxp + dzp = −2v + .



On note que la partie droite du système (2.13) est inspirée de l’étape du prédicteur proposée
dans Darvay (2005). Comme pour ∆x et ∆z, on définit

x+ p p z+ p
∆p x = d x , ∆ z = dz , (2.14)
v+ v+
et l’itération du prédiction est obtenue par :

(xp , y p , zp ) := (x+ , y + , z+ ) + θ(∆p x, ∆p y, ∆p z),

31
 CHAPITRE 2. ALGORITHME DE POINT INTÉRIEUR DE TYPE PRÉDICTEUR -
CORRECTEUR POUR LA PROGRAMMATION LINÉAIRE

où θ ∈ (0, 12 ) et aussi µp = (1−2θ)µ. Au début de l’algorithme, on suppose que (x0 , y 0 , z0 ) ∈

N (τ). On veut déterminer les valeurs de τ et θ de telle manière qu’après une étape de cor-
rection (x+ , y + , z+ ) ∈ N (ω(τ))(où ω(τ) < τ) et après une étape de prédiction (xp , y p , zp ) ∈
N (τ). L’algorithme répète alternativement les étapes du correcteur et du prédicteur jusqu’à
ce que xt z ≤  soit satisfaite. Une description formelle de l’algorithme est donnée dans la
fig .2.1.

Figure 2.1 – Un algorithme prédicteur-correcteur.

32
 CHAPITRE 2. ALGORITHME DE POINT INTÉRIEUR DE TYPE PRÉDICTEUR -
CORRECTEUR POUR LA PROGRAMMATION LINÉAIRE

2.6.2 Algorithme
Dans cette partie, on présente un algorithme de point intérieur de type correcteur-prédicteur
basé sur une nouvelle direction de recherche pour (PL) :

Algorithme de point intérieur de type correcteur-prédicteur pour PL

Début Algorithme
Données :
Un paramètre de précision  > 0;
1
 
Un paramètre de proximité τ, 0 < τ < 1 défaut τ = ;
4
1
!
Un paramètre θ, 0 < θ < 21 défaut θ = √ ;
5 n
0 t
(x ) z 0
Un paramètre de barrière µ0 = .
n
Initialisation : soit (x q, y , z ) vérifiant CPI tel que :
0 0 0
0 0
δ(x0 , z0 ; µ0 ) ≤ τ, v 0 = xµz0 > 12 e et k = 0;
Tant que xt z >  faire :
• l’étape de correcteur :
résoudre le système (2.11) et calculer (4x, 4y, 4z) via (2.5) ;
((x+ )k , (y + )k , (z+ )k ) = (xk , y k , zk ) + (4xk , 4y k , 4zk );
• l’étape de prédicteur :
résoudre le système (2.13) et calculer (4p x, 4p y, 4p z) via (2.14) ;
((xp )k , (y p )k , (zp )k ) = ((x+ )k , (y + )k , (z+ )k ) + θ(4p xk , 4p y k , 4p zk );
• mise à jour :
xk+1 = (xp )k ;
y k+1 = (y p )k ;
zk+1 = (zp )k ;
µ(k+1) := (1 − 2θ)µ(k) , et k = k + 1;
Fin Tant que
Fin algorithme.
Algorithme 2.6.2

2.7 La convergence de l’algorithme et la analyse de la

complexité
On a le lemme technique suivant :

Lemme 2.7.1. ( [26], Lemme 5.3)

Soit u et v deux vecteurs arbitraires dans Rn avec u t v ≥ 0. Alors :
1
kuvk ≤ √ ku + vk2 .
2 2
Par la suite, on analyse en détail les étapes du correcteur et du prédicteur.

33
 CHAPITRE 2. ALGORITHME DE POINT INTÉRIEUR DE TYPE PRÉDICTEUR -
CORRECTEUR POUR LA PROGRAMMATION LINÉAIRE

L’étape de correcteur
Dans cette sous-section, on va traiter l’étape du correcteur. On peut observer que l’algo-
rithme 2.6.2 effectue une étape de Newton complète comme une étape de correcteur, qui
peut être obtenu de la même manière que celui présenté dans l’algorithme primal-dual de
Darvay et al .(2016). Ainsi, pour l’analyse de ce cas les Lemmes prouvés dans [8] On peut
appliquée .

2.7.1 Analyse de la strictement faisabilité après la phase de correc-

tion
Dans le Lemme suivant, on donne une condition pour assurer la stricte faisabilité du pas de
Newton complet.

Lemme 2.7.2. ( [8], Lemme 5.1)

Soit δ := δ(x, z, µ) < 1 et on suppose que v > 12 e. Alors, x+ > 0 et z+ > 0.

Preuve.
Pour chaque 0 6 α 6 1 on note x+ (α) = x + α∆x et z+ (α) = z + α∆z. Maintenant, on écrit

x+ (α)z+ (α) = (x + α∆x)(z + α∆z),

= xz + α(z∆x + x∆z) + α 2 ∆x∆z.

Donc
x+ (α)z+ (α) = xz + α(z∆x + x∆z) + α 2 ∆x∆z.
En utilisant (2.6) et (2.7), on obtient :
1 + + 2 2
µ x (α)z (α) = v + αv(dx + dz ) + α dx dz . (2.15)

De (2.8) et (2.10), il résulte que :

1 + 2 qv2
!
+ 2 2 2 pv
x (α)z (α) = (1 − α)v + α(v + vpv ) + α − .
µ 4 4
De plus, d’après (2.9) on obtient :
2(v 2 −v 3 )
v 2 + vpv = v 2 + 2v−e ,
v2
(2.16)
= 2v−e ,

donc on obtient :
(v−e)2 pv2 qv2
 
1 + + 2
µ x (α)z (α) = (1 − α)v + α e+ 2v−e +α 4 −α 4 . (2.17)

En utilisant v > 21 e, on obtient :

(v − e)2 p2
≥− v.
2v − e 4
Ainsi,
1 + pv2 qv2
!
+ 2
x (α)z (α) ≥ (1 − α)v + α e − (1 − α) − α .
µ 4 4

34
 CHAPITRE 2. ALGORITHME DE POINT INTÉRIEUR DE TYPE PRÉDICTEUR -
CORRECTEUR POUR LA PROGRAMMATION LINÉAIRE

L’inégalité est x+ (α)z+ (α) > 0 vraie si

pv2 q2
(1 − α) +α v < 1.
4 4 ∞

On a :
pv2 q2 kpv2 k∞ kq2 k
(1 − α) +α v ≤ (1 − α) +α v ∞,
4 4 ∞
4 4
kpv k22 kqv k22
≤ (1 − α) +α = δ2 < 1.
4 4
Ainsi, on obtient que pour chaque n l’inégalité x+ (α)z+ (α) > 0 est vraie, ce qui signifie que
les fonctions linéaire de α, x+ (α) et z+ (α) ne change pas de signe sur l’intervalle [0, 1]. En
conséquence, x+ (0) = x > 0 et z+ (0) = z > 0 donne x+ (1) = x+ > 0 et z+ (1) = z+ > 0.

2.7.2 La convergence quadratique de la mesure de proximité

On a le lemme technique suivant :
Lemme 2.7.3. ([8], Lemme 5.2)
Soit f : D → (0, ∞) une fonction décroissante, où D = [d, ∞], d > 0.
De plus, on considère le vecteur v ∈ Rn+ tel que min(v) > d. Puis,

kf (v).(e − v 2 )k ≤ f (min(v)).ke − v 2 k ≤ f (d).ke − v 2 k.

Dans le Lemme suivant, on donne la convergence quadratique de la mesure de la de proxi-

mité après une étape de correction.
Lemme 2.7.4. ([8], Lemme 5.3)
Si δ := δ(x, y, µ) < 12 et v > 12 e. Alors, v + > 12 e, de plus
√
3−3δ2 −3 1−δ(1−2δ2 ) (2.18)
δ+ := δ(x+ , z+ ; µ) ≤ 3−4δ2
.

En outre, √
δ+ := δ(x+ , z+ ; µ) ≤ 9−3 3 2
2 δ ,
(2.19)
Preuve.
On a le Lemme 2.7.2 que x+ > 0 et z+ > 0. En considérant la notation

x+ z+
r
+
v = ,
µ
et la substitution α = 1 dans l’inégalité (2.17), après quelques réductions on obtient :
p2 qv2
(2.20)
2
(v + )2 = e − e−2v−v
v2
. 4v − 4.

De la condition v > 21 e, on obtient :

v 2 + 2v − e > 0,

et cela implique
qv2
(v + )2 ≥ e − .
4

35
 CHAPITRE 2. ALGORITHME DE POINT INTÉRIEUR DE TYPE PRÉDICTEUR -
CORRECTEUR POUR LA PROGRAMMATION LINÉAIRE

Par conséquent,
q
kq k2 √
(2.21)
q
1 2
min(v + ) ≥ 1 − 4 kqv k∞ ≥ 1 − 4v 2 = 1 − δ2 .

De δ < 1
il s’ensuit que
2 √
+ 3
min(v ) > ,
2
donc
1
v + > e.
2
De plus, on a :

+ + v + − (v + )2 v+
δ(x , z ; µ) = = .(e − (v + )2 ) .
2v + − e 2
+ +
(2v − e)(e + v ) 2

Considérons la fonction f (t) = (2t−1)(1+t)

t
> 0 pour tout t > 21 . De f 0 (t) < 0 il s’ensuit que f
est décroissante, donc en utilisant (2.21) et le Lemme (2.7.3), on obtient :
√
1−δ 2
δ(x+ , z+ ; µ) ≤ √ .ke − (v + )2 k2 . (2.22)
2(1−δ )+ 1−δ2 −1
2

On écrit f (t) de la manière suivante :

t(2t + 1)(1 − t)
f (t) = .
(4t 2 − 1)(1 − t 2 )
√
En substituant 1 − δ2 et en faisant quelques réductions élémentaires on obtient :
√
√  1 − δ2 − 1 − δ2 (1 − 2δ2 )
f 1 − δ2 = . (2.23)
δ2 (3 − 4δ2 )
t 2 +2t−1
On a 1 < t2
≤ 2, pour tout t > 1
2 et

+ 2 e − 2v − v 2 pv2 qv2
e − (v ) = . + .
v2 4 4
Ainsi,
p2 qv2
ke − (v + )2 k2 ≤ 2 − 4v + 4 2,
2
2 2 (2.24)
≤ 2δ + δ ,
= 3δ2 .
Et en utilisant (2.22) et (2.23) on obtient (2.18), ce qui prouve la première partie du Lemme.
De plus on a :
 √ √
3δ2 −1 + 2 1 − δ2
  
3 1 − 1 − δ2
δ(x+ , z+ ; µ) ≤ + .
3 − 4δ2 3 − 4δ2
Soit  √ √
3δ2 −1 + 2 1 − δ2
  
3 1 − 1 − δ2
Φ1 (δ) := et Φ2 (δ) := .
3 − 4δ2 3 − 4δ2

36
 CHAPITRE 2. ALGORITHME DE POINT INTÉRIEUR DE TYPE PRÉDICTEUR -
CORRECTEUR POUR LA PROGRAMMATION LINÉAIRE

De δ < 12 , il s’ensuit que :

√
√ 2 + 3
1 + 1 − δ2 > .
2

On a :
1 √
√ < 4 − 2 3,
1 + 1 − δ2
et
√
1 4−2 3 2
Φ (δ) < δ .
3 1 3 − 4δ2
De plus, si δ < 12 , alors 4δ2 < 1. Ainsi, 1
3−4δ2
< 1
2 et on obtient :
√
1
Φ
3 1 (δ) < 4−2 3 2
2 δ .
(2.25)

Un calcul simple donne :

1 δ2
Φ2 (δ) = √ .
3 1 + 2 1 − δ2
√
On a √1 < 3−1
2 et
1+2 1−δ2 √
1
3 Φ2 (δ) <
3−1 2
2 δ .
(2.26)
De (2.25) et (2.26), on obtient :
√ √ √
1 4−2 3+ 3−1 2 3− 3 2
(Φ (δ) + Φ2 (δ)) < δ = δ ,
3 1 2 2
et il en résulte (2.19), ce qui prouve le Lemme.

L’influence de nouveau itéré en saut de dualité après la phase de cor-

rection
Le lemme suivant donne une borne supérieur du saut de dualité après une étape de correc-
tion.

Lemme 2.7.5. ([8], Lemme 5.4)

soit δ := δ(x, z, µ) < 12 et v > 12 e. Alors,

1
(x+ )t z+ ≤ µ(n + ).
4
Preuve.
En substituant α = 1 dans (2.15) et en utilisant (2.8) on a :
1 + +
x z = v 2 + vpv + dx dz .
µ

En utilisant (2.9) et (2.16) on déduit :

1 + + p2
x z ≤ e + v + dx dz .
µ 4

37
 CHAPITRE 2. ALGORITHME DE POINT INTÉRIEUR DE TYPE PRÉDICTEUR -
CORRECTEUR POUR LA PROGRAMMATION LINÉAIRE

Par conséquent, en utilisant l’orthogonalité des vecteurs dx et dz , on obtient

(x+ )t z+ = et (x+ z+ ),
et pv2
≤ µ(et e + + et dx dz ),
4
kpv k22
= µ(n + + dxt dz ),
4
= µ(n + δ2 ).

Ceci complète la première partie du Lemme. De δ < 12 on a δ2 < 1

4 . En utilisant cela, on
obtient
1
(x+ )t z+ ≤ µ(n + ).
4
Ce qui prouve la seconde affirmation du Lemme.

L’étape de prédicteur
2.7.3 Analyse de la stricte faisabilité
Le Lemme suivant montre la stricte faisabilité après une étape de prédiction

Lemme 2.7.6. [Darvay 2020]

Soit (x+ , y + , z+ ) une solution primale-dual strictement réalisable obtenue après un pas de cor-
rection et µ > 0. De plus, soit 0 < θ < 12 , et

xp = x+ + θ∆p x, y p = y + + θ∆p y, zp = z+ + θ∆p z,

désignent les itérations après une étape de prédicteur. Alors (xp , y p , zp ) est une solution primale-
duale strictement réalisable si :
#2 √ 2  2
1 1 2θ n 1
"
+ +
h(δ , θ, n) := + − + ρ(δ ) > 0,
2 4ρ(δ+ ) 1 − 2θ 2

où δ+ := δ(x+ , z+ ; µ).

Preuve.
Pour chaque 0 ≤ α ≤ 1, on note que xp (α) = x+ + αθ∆p x et zp (α) = z+ + αθ∆p z. Par
conséquent, on a :
p
A+ dx = 0,



 + t ∆p y

p
(2.27)


 A µ + dz = 0,
p p
 dx + dz = −2v + .



En utilisant la troisième équation de (2.27), on obtient :

x+ z+ + p p
v + + αθdz ,
  
xp (α)zp (α) = (v + )2 v + αθdx
 p p p p
= µ (v + )2 + αθv + dx + dz + α 2 θ 2 dx dz , (2.28)
h  i

p p
= µ (1 − 2αθ)(v + )2 + α 2 θ 2 dx dz .
h i

38
 CHAPITRE 2. ALGORITHME DE POINT INTÉRIEUR DE TYPE PRÉDICTEUR -
CORRECTEUR POUR LA PROGRAMMATION LINÉAIRE

De (2.28), il s’ensuit que :

α2θ2 p p
" p
x (α)zp (α)
# " #
+ 2
min = min (v ) + dx dz ,
(1 − 2αθ)µ 1 − 2αθ
α2θ2 p p
≥ min((v + )2 ) − kdx dz k∞ ,
1 − 2αθ
θ2 p p
≥ min((v + )2 ) − kdx dz k∞ ,
1 − 2θ
#2
1 1 θ2
"
p p
≥ + +
− √ kdx + dz k22 ,
2 4ρ(δ ) 2 2(1 − 2θ)
#2
1 1 4θ 2
"
= + − √ kv + k22 ,
2 4ρ(δ+ ) 2 2(1 − 2θ)
#2 n
1 1 4θ 2
" X
= + +
− √ (v + )2i ,
2 4ρ(δ ) 2 2(1 − 2θ) i=1
#2 √ 2  2
1 1 2θ n 1
"
+
≥ + − + ρ(δ ) ,
2 4ρ(δ+ ) (1 − 2θ) 2
= h (δ+ , θ, n) > 0.
2 2
La deuxième inégalité est satisfaite de fait que f (α) := 1−2αθ
α θ
est croissant monotone par
rapport à α et 0 < α < 1 ; c’est, f (α) ≤ f (1). La troisième inégalité découle des Lemmes
2.5.1 et 2.7.1. La deuxième égalité peut être dérivée de la troisième équation (2.27). l’inégalité
avant la dernière ligne découle de la borne supérieure donnée dans le Lemme 2.5.1. L’in-
égalité ci-dessus implique que xp (α)zp (α) > 0, pour tout0 ≤ α ≤ 1. Donc, xp (α) et zp (α)
ne changent pas de signe sur 0 ≤ α ≤ 1. Puisque xp (0) = x+ > 0 et zp (0) = z+ > 0, donc
on conclue que xp (1) = x+ + θ∆p x = xp > 0 et zp (1) = z+ + θ∆p z = zp > 0 et la preuve est
complète.
On définit :
xp zp
r
p
v = . (2.29)
µp
Il résulte de (2.28) avec α = 1, que
θ2 p p
(v p )2 = (v + )2 + dx dz , (2.30)
1 − 2θ
et
min(v p )2 ≥ h(δ+ , θ, n). (2.31)

2.7.4 La convergence quadratique de la mesure de la proximité après

la phase de prédiction
Lemme 2.7.7. [Darvay 2020]
Soit (x+ , y + , z+ ) une solution primale-duale strictement réalisable et µp = (1 − 2θ)µ avec 0 <
θ < 21 . De plus, soit h(δ+ , θ, n) > 14 et on suppose que (xp , y p , zp ) désigne l’itération après une
étape de prédiction. Alors v p > 21 e et
 √ 2 h i2 
+ 2 2θ n 1 +
p
h(δ , θ, n) 3δ + 1−2θ 2 + ρ(δ )
δp := δ(xp , zp ; µp ) ≤ .
2h(δ+ , θ, n) + (δ+ , θ, n) − 1
p

39
 CHAPITRE 2. ALGORITHME DE POINT INTÉRIEUR DE TYPE PRÉDICTEUR -
CORRECTEUR POUR LA PROGRAMMATION LINÉAIRE

Preuve.
Puisque h(δ+ , θ, n) > 14 , d’après (2.31) on a min(v p )2 ≥ 41 , ce qui donne v p > 12 e. De plus,
du Lemme 2.7.6 on déduire que l’étape de prédiction est strictement réalisable ; xp > 0 et
zp > 0. Maintenant, par la définition de la mesure de proximité, on a :
v p −(v p )2 vp
e − (v p )2
 
δp : = δ(xp , zp ; µp ) = 2v p −e 2 = (2v p −e)(e+v p )
,
2
p
vmin
≤ p p (e − (v p )2 2
,
(2vmin )(vmin +1)
√
h(δ+ ,θ,n)
≤ √ e − (v p )2 2
, (2.32)
2h(δ+ ,θ,n)+ h(δ+ ,θ,n)−1
√
h(δ+ ,θ,n) 2 p p
= √ e − (v + )2 − 1−2θ
θ
dx dz ,
2h(δ+ ,θ,n)+ h(δ+ ,θ,n)−1 2
√
h(δ+ ,θ,n) 2 p p
e − (v + )2
h i
≤ √ + θ
2 1−2θ
dx dz 2
,
2h(δ+ ,θ,n)+ h(δ+ ,θ,n)−1

où les deux première inégalités sont dues au Lemme 5.2 dans [8] et (2.31), respectivement.
La dernière égalité découle de (2.30) et la dernière inégalité est due à l’inégalité triangulaire.
q
x+ z+
On donne une limite supérieure pour ke−(v 2 )2 k2 . En utilisant la définition de v + = µ
et (2.10) , on a :
ke − (v + )2 k2 = k(v + dx )(v + dz ) − ek2 ,
= kv 2 + v(dx + dz ) − e + dx dz k2 , (2.33)
pv2 −qv2
≤ kv 2 + vpv − ek2 + k 4 k2 .
De plus, la troisième équation du système (2.11) donne :
2v 2 (e−v)
v 2 + vpv − e = v 2 + 2v−e − e,
(v−e)2
= 2v−e , (2.34)
(v−e)2 v 2 pv2
≤ (2v−e)2
= 4.

En utilisant (2.33), (2.34) et le fait que kx2 k2 ≤ kxk22 , on a :

kpv k22 kpv k22 kqv k22

+ 2
ke − (v ) k2 ≤ + + ≤ 3δ2 . (2.35)
4 4 4
Ainsi, en utilisant (2.35) et les Lemmes 2.5.1 et 2.7.1, on obtient :

θ2 p p θ2 p p
ke − (v + )2 k2 + kdx dz k2 ≤ 3δ2 + √ kdx + dz k22 ,
1 − 2θ 2 2(1 − 2θ)
√ 2
2θ
= 3δ2 + kv + k22 ,
1 − 2θ
√ 2  2
2 2θ n 1 +
≤ 3δ + + ρ(δ ) .
1 − 2θ 2
La substitution de cette borne dans (2.32) donne l’inégalité souhaitée.

40
 CHAPITRE 2. ALGORITHME DE POINT INTÉRIEUR DE TYPE PRÉDICTEUR -
CORRECTEUR POUR LA PROGRAMMATION LINÉAIRE

2.7.5 L’influence du nouveau itéré en saut de dualité après la phase

de prédiction
Le but de l’algorithme est de réduire le saut de dualité produit de la paire primale-duale.
Par conséquent, pour mesurer cette réduction, dans le Lemme suivant on donne une borne
supérieure pour le saut de dualité obtenu après la phase de prédiction.
Lemme 2.7.8. [Darvay 2020]
Supposons que δ := δ(x, z; µ) < 12 et v > 12 e. De plus, soit 0 < θ < 12 .
Alors
1
 
(xp )t zp ≤ µp n + .
4
Preuve.
En utilisant (2.29) et (2.30), on obtient :

θ2
"#
p t p p t p 2 tp p + 2
(x ) z = µ e (v ) = (1 − 2θ)µe (v ) + dx dz ,
1 − 2θ
p p
= (1 − 2θ)(x+ )t z+ + µθ 2 (dx )t dz ,
1
 
≤ µ(1 − 2θ) n + ,
4
1
 
= µp n + ,
4
p p
où l’inégalité est due au Lemme 2.7.5 et (dx )T dz = 0. Ceci termine la preuve.

2.7.6 La mise à jour du paramètre barrière µ après la phase de pré-

diction
Dans cette section, on veut fixer les paramètres τ et θ avec des valeurs appropriées, qui
garantir qu’après une itération principal, la mesure de proximité ne dépassera pas τ.
Soit (x, y, z) ∈ N (τ) soit l’itéré au début d’une itération principale avec x > 0 et z > 0
tel que δ = δ(x, z; µ) ≤ τ ≤ 12 . Après une étape de correcteur, d’après Lemme 2.7.4, on a
√
9 − 3 3 2
δ+ ≤ δ .
2
Il est évident que le membre droite de l’inégalité ci-dessus est croissante de façons monotone
par rapport à δ, et cela implique que :
√
δ+ ≤ 9−3 3 2
2 τ =: ω(τ). (2.36)

Après l’étape du prédicteur et la mise à jour de µ, d’après le Lemme 2.7.7, on a :

√ + 
2
√
2nθ 2 1 + 2

h(δ ,θ,n) 3δ + [ 2 +ρ(δ )]
δp := δ(xp , zp ; µp ) ≤ √
1−2θ
, (2.37)
2h(δ+ ,θ,n)+ h(δ+ ,θ,n)−1

où δ+ et h(δ+ , θ, n) sont définis comme dans le Lemme 2.7.6. On peut facilement vérifier
que h(δ+ , θ, n) est décroissante par rapport
√
à δ+ , donc h(δ+ , θ, n) ≥ h(ω(τ), θ, n).
On considére la fonction f (t) = √t , pour t > 14 . De f 0 (t) < 0, il s’ensuit que f est
2t+ t−1
décroissant, donc :
f (h(δ+ , θ, n)) ≤ f (h(ω(τ), θ, n)) . (2.38)

41
 CHAPITRE 2. ALGORITHME DE POINT INTÉRIEUR DE TYPE PRÉDICTEUR -
CORRECTEUR POUR LA PROGRAMMATION LINÉAIRE

En utilisant (2.36), (2.37), (2.38) et le fait que ρ est croissante par rapport à δ+ , on obtient :
 √ 
2 2nθ 2 1 2
p
h(ω(τ), θ, n) 3τ + 1−2θ [ 2 + ρ(ω(τ))]
δp ≤ p ,
2h(ω(τ), θ, n) + h(ω(τ), θ, n) − 1
quand h(ω(τ), θ, n) > 41 . Si on prend τ = 14 et θ = 5√1 n , ensuite δp < τ et h(δ+ , θ, n) > 14 .
Il convient de mentionner, que les itérations après les étapes du correcteur sont dans le
voisinage N (ω(τ)), tandis que les itérations après les étapes du predicteur sont dans le
voisinage N (τ).

2.7.7 Analyse de la complexité

Dans cette partie, on présente le nombre d’itération à partir du quel l’algorithme 3.1.2
converge.
Lemme 2.7.9. [Darvay 2020]
(x0 )t z0
Soit (x0 , y 0 , z0 ) être une solution primale-duale strictement réalisable µ0 = n et
δ(x0 , z0 , µ0 ) ≤ τ. De plus, soit xk et zk les itérations obtenues après k itérations, alors
(xk )t zk ≤ ,
est satisfaite si :
1 5(x0 )t z0
" #
k ≥ 1+ log .
2θ 4
Preuve.
D’après le Lemme2.7.8, on a :
1 5 5
(xk )t zk ≤ µk (n + ) < (1 − 2θ)k−1 µ0 n = (1 − 2θ)k−1 (x0 )t z0 .
4 4 4
Avec
µk = (1 − 2θ)k−1 µ0 .
Cela signifie que l’inégalité (xk )t zk ≤  est satisfait si :
5
(1 − 2θ)k−1 (x0 )t z0 ≤ .
4
En utilisant la fonction log on obtient :
5(x0 )t z0
(k − 1) log(1 − 2θ) + log ≤ log .
4
Puisque log(1 + ξ) ≤ ξ, pour ξ > −1, en utilisant ξ = −2θ, on obtient que l’inégalité ci-
dessus est vrai si :
5(x0 )t z0
−2θ(k − 1) + log ≤ log .
4
Ceci prouve le Lemme.

Théorème 2.7.1 (Darvay 2020).

Soit τ = 41 et θ = 5√1 n . Alors, l’algorithme de point intérieur de type correcteur-prédicteur est
√ 5(x0 )t z0
bien défini et l’algorithme nécessite au plus O(5 n log 4 ) itération.
La sortie est une solution primale-duale strictement réalisable (x, y, z) satisfaisant xt z ≤ .

42
Chapitre 3

Implémentation numérique

Dans ce chapitre, on s’intéresse aux expériences numériques issues de l’application de l’al-

gorithme 2.6.2 sur quelques problèmes linéaires, avec la comparaison entre le choix théo-
rique de θ et une autre alternative du pas de déplacement. On utilise le langage de MATLAB
et éxecuté sur (R2009a) sous windows intel Core i3.
On note par :

• (x0 , y 0 , z0 ) : un point initial strictement réalisable et vérifie δ(x0 , z0 ; µ0 ) ≤ 1

4 pour
(x0 )t z0
l’algorithme 2.6.2 avec µ0 = n > 0.
• (x∗ , y ∗ , z∗ ) : la solution optimale du problème primal (P) et dual (D), respectivement.
• iter : le nombre des itérations produites par l’algorithme 2.4.2.
• CPU : le temps d’exécution d’un algorithme en seconde.

3.1 Calcul des directions

L’algorithme de point intérieur de type correcteur-prédicteur consiste à résoudre le pro-
gramme linéaire (P) et (D) en deux phase comme suite :

3.1.1 La phase de correction

Pour obtenir les directions (∆x; ∆y; ∆z), on résout le système suivant :

Adx = 0,



 t ∆y

A µ + dz = 0, (3.1)



 d + d = 2(v−v 2 ) .


x z 2v−e
Tel que :
x
A = Adiag( ).
v

On obtient, les directions (dx ;∆y ;dz ). puis on utilisant le changement de variable :
v∆x v∆z
dx := , dz := .
x z

43
 CHAPITRE 3. IMPLÉMENTATION NUMÉRIQUE

Alors on obtient, les directions (∆x; ∆y; ∆z).

pour éviter ce changement de variable, on résoud le système équivalent suivant :

A∆x = 0,




(3.2)
 t
A ∆y + ∆z = 0,  



 z 0  xz  x 0 xz
 
xz
 ψ ∆x + ψ ∆z = ψ (e) − ψ µ .

µ µ µ µ
√
Dans ce travail, on s’intéresse par ψ(t) = t − t alors, ψ 0 (t) = 1 − √
1
.
2 t
On pose t = µ , alors on obtient :
xz

!
xz xz xz
r
ψ = − , (3.3)
µ µ µ
!
0 xz e
ψ =e− q , (3.4)
µ 2 xzµ
√
ψ (e) = e − e = 0. (3.5)
En remplaçant (3.3),(3.4) et (3.5) dans la troisièmme équation de le système (3.2) on obtient :
! ! !
z 0 xz x 0 xz xz
ψ ∆x + ψ ∆z = ψ (e) − ψ ,
µ µ µ µ µ
   
z  e  x  e  xz xz
    r
⇐⇒ e − q  ∆x + e − q  ∆z = − + ,
µ  2 xz  µ  2 xz  µ µ
µ µ
   
e  e  √
   
⇐⇒ z e − q  ∆x + x e − q  ∆z = −xz + xzµ,
 
 
 2 xz   2 xz 
µ µ
 
e  √
 
⇐⇒ e − q  (z∆x + x∆z) = −xz + xzµ,


 2 xz 
µ
 √
q 
xz
2
−xz + xzµ µ
⇐⇒ (z∆x + x∆z) = q ,
xz
2 µ −e
 q 
2xz e − xz µ
⇐⇒ (z∆x + x∆z) = q ,
2 xzµ − e
⇐⇒ (z∆x + x∆z) = pv .

Tel que
 q 
2xz e − xz
µ xz 1
r
pv = , v= > e.
µ 2
q
xz
2 µ −e

44
 CHAPITRE 3. IMPLÉMENTATION NUMÉRIQUE

Alors on obtient le le système suivant :

A∆x = 0,



 t
A ∆y + ∆z = 0,


 z∆x + x∆z = pv .



La forme matricielle est :

 0 A 0   ∆y   0 
    
 t
 A 0 I   ∆x  =  0  .
    
0 Z X pv

∆z
Avec X = diag(x) et Z = diag(z), ce dernier est un système linéaire carré a (m + 2n) équa-
tions, et (m + 2n) inconnus. on résoud ce dernier système pour obtenir (∆x; ∆y; ∆z).
Par conséquent, le nouveau itéré obtenu après la phase de correction est donnée par :

x+ = x + ∆x ; y + = y + ∆y ; z+ = z + ∆z.

3.1.2 La phase de prédiction

Pour calculer les nouvelles directions de la phase de prédiction, on résout le système sui-
vant :  + p

 A dx = 0,
 t ∆p y

(3.6)
 p

 A µ + dz = 0,
 d p + d p = −2v + .


x z
Avec

x+ z+ x+
r
+
v + := , A := Adiag( ),
µ v+

et

p v + ∆p x p v + ∆p z
dx := , dz := .
x+ z+
+ p p
En remplaçant v + , A , dx et dz dans le système (3.6) on obtient :

x+ v+ p
! !
+ p
• A dx = 0 ⇐⇒ Adiag + ∆ x = 0,
v x+
p
⇐⇒ A∆ x = 0,

car
x+ v+
! !
diag + = e.
v x+

45
 CHAPITRE 3. IMPLÉMENTATION NUMÉRIQUE

√
py
x + At p v+
!
t+ ∆ p
• A + dz = 0 ⇐⇒ diag + ∆ y + + ∆p z = 0,
µ v µ z
q
x+ z+
x+ At µ
⇐⇒ diag( q ) ∆p y + ∆p z = 0,
x+ z+ µ z+
µ
s
x+ µ At p
r
x+ p
⇐⇒ diag ∆ y + ∆ z = 0,
z+ µ z+ µ
 s  r
+ x+ p
!
 x t p 
⇐⇒ diag A ∆ y  + ∆ z = 0,

 µ  µ

⇐⇒ At ∆p y + I∆p z = 0.
 

v+ v+ x+ z+
r
p p +
• dx + dz = −2v ⇐⇒ + ∆p x + + ∆p z = −2 ,
x z µ
q q
x+ z+ x+ z+
x+ z+
r
µ µ
⇐⇒ ∆p x + ∆p z = −2 ,
x+ z+ µ
s s s
z+ p x+ P x+ z+
⇐⇒ + ∆ x + ∆ z = −2 ,
µx µz+ µ
√
r r
z+ p x+ p
⇐⇒ ∆ x + ∆ z = −2 x+ z+ ,
x+ z+
√
en multipliant les deux membres de cette équation par x+ z+ , on obtient :

z+ ∆p x + x+ ∆p z = pv + ,

tel que
pv + = −2x+ z+ .
par conséquent, on obtient le nouveau système suivant :



A∆x = 0,

(3.7)

 t p


A ∆ y + I∆p z = 0,
z+ ∆p x + x+ ∆p z = pv + .



La forme matricielle :
 p  
 0 A 0   ∆ y   0 
 
 t   p  
 A 0 I   ∆ x  =  0  .

0 Z X+
+  p  
∆ z pv +
 

Avec X + = diag(x+ ) et Z + = diag(z+ ), ce dernier est un système linéaire carré a (m + 2n)

équations et (m+2n) inconnus. On résout ce dernier système pour obtenir (∆p x; ∆p y; ∆p z).
Par conséquent, le nouveau itéré obtenu après la phase de correction est donnée par :

xp = x+ + θ∆p x ; y p = y + + θ∆p y ; zp = z+ + θ∆p z.

Avec θ ∈ [0, 21 ]

46
 CHAPITRE 3. IMPLÉMENTATION NUMÉRIQUE

3.2 Choix alternative du pas de déplacement

On cherche à résoudre le problème linéaire par l’algorithme 2.6.2 selon le choix de θ. On
établit numériquement l’influence de pas de déplacement θ durant la phase de prédiction
sur le comportement numérique de cet algorithme, dont le choix théorique de θ est donné
par :
1
θtho = √
5 n
et le choix pratique est basé sur la stratégie suivante qui été déjà présenté par Achache [2]
pour PL. A chaque phase de prédiction, on calcule le pas de déplacement maximal θalter
tel que
xp = x+ + ρθalter ∆p x
et
zp = z+ + ρθalter ∆p z
avec
θalter = min(θx , θz )
et ρ ∈ ]0, 1[ , où θx et θz sont les pas de déplacement réalisable primal et dual donnés par :

min(− ∆xpix ) ∆p xi < 0

(
if
θx 1 i

2 if ∆p xi ≥ 0,

et
min(− ∆zpiz ) ∆p zi < 0
(
if
θz 1
i

2 if ∆p zi ≥ 0.

3.3 Tests numériques

Exemple 3.1. .
On considère le programme linéaire n = 5 et m = 3, on a

2 1 1 0 0 42

   
A = 1 2 1 0 0 , b = 41 ,
   
0 1 0 0 1 24
   
h it
c= 8 8 5 2 2 .

On prend comme un point réalisable initial

it
x0 = 10 9 13 7 15 ,
h

it
y0 = 3 1 1 ,
h

it
z0 = 1 2 1 2 1 .
h

On a  = 10−5 avec µ(0) = ((x0 )t z0 )/n = 14, ρ = 0.89 et δ(x0 , z0 ; µ0 ) = 0.2299 ≤ 14 .

Une solution optimale approximative est donnée par :

47
 CHAPITRE 3. IMPLÉMENTATION NUMÉRIQUE

it
x∗ = 14.3333 13.3333 0.0001 0 10.6667 ,
h
it
y ∗ = 3.3333 1.3333 2 ,
h
it
z∗ = 0 0 0.3333 2 0 .
h

La valeur optimale pour les deux problèmes est 242.6667.

Le tableau suivant présente les résultats numériques obtenus par l’algorithme 2.6.2

θtho θalter
iter 81 9
CPU 0.0270 0.0157
Tableau 1. Résultats comparatifs entre le choix théorique et alternative de θ.
Exemple 3.2. .
Soient n = 6 et m = 5, on a

 7 10 1 3 −2 6   122 
   
−8 −6 2 7 3 6  −12
   
A =  2 2 −5 8 −2 3  , b =  17  ,
   
 7 4 1 −1 5 −8  27 
  
−5 1 −4 9 10 9 60
   
h it
c = −2 26 −11 84 77 48 .

On prend comme un point réalisable initial

it
x0 = 3 7 4 1 3 5 ,
h
it
y0 = 2 3 1 4 5 ,
h
it
z0 = 3 1 2 8 4 2 .
h

On a  = 10−5 avec µ(0) = ((x0 )t z0 )/n = 9, ρ = 0.89 et

δ(x0 , z0 ; µ0 ) = 0.2174.

Une solution optimale approximative est donnée par :

it
x∗ = 0 9.7728 4.2460 1.6842 2.2764 3.2544 ,
h
it
y ∗ = 2.3417 3.9295 1.2587 4.6860 4.8982 ,
h
it
z∗ = 2.2157 0 0 0 0 0 .
h

La valeur optimale pour les deux problèmes est 680.3528.

Le tableau suivant présente les résultats numériques obtenus par l’algorithme 2.6.2
θtho θalter
iter 88 9
CPU 0.0260 0.0191
Tableau 2. Résultats comparatifs entre le choix théorique et alternative de θ.

48
 CHAPITRE 3. IMPLÉMENTATION NUMÉRIQUE

Exemple 3.3. .
Soient n = 7 et m = 4, on a

−8 −2 −8 6 −3 −1 7   −99 
   
−5 10 −2 −9 4 −4 −5  −88 
A =   , b =  ,
  
−8 1 −1 −3 −8 −6 −6 −204
−4 −3 −4 −2 6 −3 −1 −94
   
h it
c = −57 −28 −35 54 −32 −14 36 .
On prend comme un point réalisable initial

it
x0 = 9 6 8 6 5 7 5 ,
h

it
y 0 = 5 −3 4 2 ,
h

it
z0 = 8 14 11 13 15 9 12 .
h

On a  = 10−5 avec µ(0) = ((x0 )t z0 )/n = 74.2857, ρ = 0.89 et δ(x0 , z0 ; µ0 ) = 0.1778 ≤ 41 .

Une solution optimale approximative est donnée par :

it
x∗ = 8.3138 2.9970 0 0 1.8489 20.9492 0 ,
h

it
y ∗ = 5.6730 −1.5396 1.8897 1.0491 ,
h

it
z∗ = 0 0 13.3912 13.8726 0 0 0.9779 .
h

La valeur optimale pour les deux problèmes est -910.2548.

Le tableau suivant présente les résultats numériques obtenus par l’algorithme 2.6.2

θtho θalter
iter 110 11
CPU 0.0451 0.0239

Tableau 3. Résultats comparatifs entre le choix théorique et alternative de θ.

Exemple 3.4. .
Soient n = 9 et m = 6, on a

−8 7 −6 8 −2 9 10 7 −8 −91

   
−2 −5 8 7 4 3 −5 2 1   67 
   
 4 −4 7 1 9 8 3 2 5   240 
   
A =   , b =  126  ,
 7 4 −1 1 5 −6 −8 2 3 
  
 
−9 5 4 2 7 −8 −3 −4 5   17 
   
1 8 −5 −3 1 2 7 9 −3 51
   
h it
c = −68 78 25 127 86 59 16 88 −17 .

49
 CHAPITRE 3. IMPLÉMENTATION NUMÉRIQUE

On prend comme un point réalisable initial

it
x0 = 10 1 4 2 11 1 4 5 9 ,
h
it
y0 = 8 7 2 5 4 2 ,
h
it
z0 = 1 9 2 5 1 8 3 2 1 .
h

On a  = 10−4 avec µ(0) = ((x0 )t z0 )/n = 9.6667, ρ = 0.89 et δ(x0 , z0 ; µ0 ) = 0.1956 ≤ 14 .

Une solution optimale approximative est donnée par :
it
x∗ = 10.6395 0 4.5250 0 16.5498 0.1372 3.7816 2.1878 0 ,
h
it
y ∗ = 8.2826 7.1190 2.3845 4.9568 3.7238 1.7774 ,
h
it
z∗ = 0 12.4897 0 1.4492 0 0.0001 0 0 2.0616 .
h

La valeur optimale pour les deux problèmes est 1.0741.103 .

Le tableau suivant présente les résultats numériques obtenus par l’algorithme 2.6.2

θtho θalter
iter 97 10
CPU 0.0297 0.0186

Tableau 4. Résultats comparatifs entre le choix théorique et alternative de θ.

Exemple 3.5. .
Soient n = 10 et m = 8, on a

3 −5 2 −8 −5 2 6 10 5 2   47 
   
2 −8 −6 −7 6 5 5 6 −9 −8  79 
  
6 1 9 5 −2 3 10 −5 6 −7  63 
   
6 3 −2 1 −4 7 −8 10 8 4   107 
 
A =   , b =  ,
 
1 −3 −1 5 −8 −4 4 1 4 −2 −108
4 −1 3 −2 5 −8 4 1 −6 0 

 85 
 

4 −2 6 −8 8 8 −2 −1 6 7   246 
   
 
8 0 −9 −5 5 4 −8 −6 5 5 155
  
h it
c = 223 −115 12 −210 106 204 68 125 117 21 .

On prend comme un point réalisable initial

it
x0 = 12 1 2 1 14 5 3 4 2 6 ,
h
it
y 0 = 9 10 6 5 1 3 10 7 ,
h
it
z0 = 1 15 5 13 1 3 4 3 5 2 .
h

On a  = 10−4 avec µ(0) = ((x0 )t z0 )/n = 12.5, ρ = 0.89 et δ(x0 , z0 ; µ0 ) = 0.2218 ≤ 41 .

Une solution optimale approximative est donnée par :

it
x∗ = 12.8335 0 3.4809 0 12.2422 5.0197 1.0532 3.1823 0.8708 5.1070 ,
h
it
y ∗ = 8.3769 10.5129 5.6116 5.0390 2.9947 3.0126 11.6177 6.4280 ,
h

50
 CHAPITRE 3. IMPLÉMENTATION NUMÉRIQUE

it
z∗ = 0 25.4914 0 13.6418 0 0 0 0 0 0 .
h

La valeur optimale pour les deux problèmes est 5.9039.103 .

Le tableau suivant présente les résultats numériques obtenus par l’algorithme 2.6.2

θtho θalter
iter 105 9
CPU 0.0226 0.0162

Tableau 5. Résultats comparatifs entre le choix théorique et alternative de θ.

51
 Exemple 3.6.

Soient n = 15 et m = 13, on a
 
 10 −5 9 −5 −14 −2 13 11 15 12 25 16 32 −17 −22 

 −2 8 5 7 16 25 −15 11 −9 8 32 18 −15 51 −10 
 
 1 9 6 3

−5 9 −7 −12 16 −27 36 −24 −29 38 42 

 9 8 −12 −31 4
 −7 8 20 48 −64 18 19 −27 48 4 

 −1 −2 −5
 8 4 −4 −2 34 −24 −25 17 29 −31 26 56 


 8 10 −9 −5 10 4 −8 −6 6 7 −1 3 −2 5 −8 
 4 8 8 6 17 7 
A =  4 1 −6 −2 6 −8 12 −2 −1
 
 8 11 10 −9 −5
 7 4 −8 −6 5 26 13 −9 −36 18 

52
 47 79 63 10 −18 53 24 15 68 21 14 13 −15 17 −7 
 
 22 14 17 −29 −30
 21 45 36 27 −31 −24 12 9 19 22 


 −2 −5 −2 11 12 16 32 −17 18 5 −6 2 21 13 −18 
 
 8 19 −12 −31 10 7 3 1 −5 14 12 6 −11 18 11 
 
14 51 23 −19 11 6 34 −18 13 19 10 17 29 26 9
h it
b = 317 1320 835 732 1847 45 441 432 1971 888 −104 838 1279 ,
h it
c = 1351 1897 1177 −741 −363 1853 1970 668 2181 −114 792 995 343 1968 321 .
h it
On prend comme un point réalisable initial x0 = 13 1 8 1 15 2 5 17 1 9 13 7 1 9 16 ,
h it h it
CHAPITRE 3. IMPLÉMENTATION NUMÉRIQUE

y 0 = 9 10 6 5 1 3 10 7 12 19 21 9 7 , z0 = 1 16 2 13 1 9 3 1 15 2 1 2 18 2 1 ,
 On a  = 10−4 avec µ(0) = ((x0 )t z0 )/n = 15.6667, ρ = 0.9 et δ(x0 , z0 ; µ0 ) = 0.2327 ≤ 14 .
Une solution optimale approximative est donnée par :

x∗ = [14.0125 0 8.2989 0.9732 13.3889 1.1786 5.1504 15.4611 0.8829 9.6936 12.5683 8.2176 0 9.8387 15.826]t

y ∗ = [8.8205 9.9097 5.876 5.17 1.05 2.5128 10.5706 7.2279 12.1843 18.7913 21.3726 8.9889 6.8437]t ,

z∗ = [0 15.8769 0 0 0 0 0 0 0 0 0 0 23.8163 0 0]t ,

53
CHAPITRE 3. IMPLÉMENTATION NUMÉRIQUE
  
 −2 −5 11 16 14 10 −9 −4 12 15 17 42 36 −15 4 21 21 33 
 
 51 −10 18 32 19 −13 16 12 10 2 8 5 15 7 35 −15 −19 14 
 

 56 26 −32 17 −25 −6 8 −4 16 27 −39 45 10 9 6 −12 7 9 


 19 11 16 12 −5 −17 14 −11 −19 13 21 8 −12 4 −8 7 23 −18 


 20 48 −63 14 19 36 −27 4 41 27 50 63 −20 32 66 45 34 19 


Exemple 3.7. .
 

 14 22 17 −29 2 −17 −1 2 5 18 34 13 21 9 14 34 13 −27 


 10 5 1 17 19 25 22 −21 −30 −24 −25 7 9 −3 6 5 −8 −6 


 46 70 9 −59 17 81 22 6 10 5 −9 13 21 −11 33 −56 14 16 

 
A =  15 −59 −23 31 18 24 67 13 14 54 −39 10 4 −6 −21 37 30 17 
 
21 21 20 27 45 12 23
Soient n = 18 et m = 17 on a
 −44 −88 91 −33 −29 13 38 −8 −36 −18 13 
 

 51 23 14 −68 55 −28 26 −11 6 −7 45 17 −35 −9 22 −14 10 9 


 11 −16 23 −19 −29 25 9 18 21 49 14 −13 6 −3 18 41 48 53 

 
 26 17 −10 −1 11 20 12 14 −16 6 34 11 −6 4 22 60 46 51 
iter

 

 17 6 −17 −28 6 18 52 −12 −21 16 77 29 26 50 −30 11 16 −2 


54

 8 19 61 80 71 26 −41 −9 −5 27 14 −88 −51 15 20 31 22 −17 


 18 −29 17 31 6 −34 10 −17 26 9 −7 33 −22 37 41 10 −11 22 

136

 
14 −26 18 11 −2 5 −4 12 16 35 −19 12 −14 9 26 17 14 −19
8

b = [1652 1591 980 386 3060 1029 78 − 16 1236 632 630 1027 1749 666 1062 1679 992]t ,
CPU 0.0569 0.0168
θtho θalter

c = [2063 1965 751 1138 1942 − 21 − 211 − 475 1682 1569 3256 1326 − 757 1294 3740 1293 1472 2029]t .
On prend comme un point réalisable initial
La valeur optimale pour les deux problèmes est 8.9169.104 .

h it
x0 = 11 1 5 12 7 1 2 5 12 1 7 13 4 1 7 14 1 2 ,
h it
y 0 = 22 15 −5 12 17 3 4 8 −12 11 17 16 −8 4 11 20 −6 ,
h it
z0 = 1 14 2 1 2 14 7 2 1 13 2 1 3 12 2 1 13 7 .
Tableau 6. Résultats comparatifs entre le choix théorique et alternative de θ.
CHAPITRE 3. IMPLÉMENTATION NUMÉRIQUE

On a  = 10−4 avec µ(0) = ((x0 )t z0 )/n = 12.7778, ρ = 0.9 et δ(x0 , z0 ; µ0 ) = 0.2482 ≤ 41 .

tableau suivant présente les résultats numériques obtenus par l’algorithme 2.6.2

Une solution optimale approximative est donnée par :

x∗ = [10.9407 1.3032 5.2473 12.0278 6.8655 1.22 2.1124 5.1849 11.8104 1.4931 7.1376 13.2997 3.5676 0.6783 6.7844 14.3127 0 2.1714]t

y ∗ = [22.1341 14.7693 − 4.9554 11.9192 16.7897 3.0414 3.7455 8.3139 − 12.0118 11.1156 16.8928 15.7754 − 7.7422 4.1773 11.1 20.2289 − 5.8313]t ,

z∗ = [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1.6056 0]t ,
 CHAPITRE 3. IMPLÉMENTATION NUMÉRIQUE

La valeur optimale pour les deux problèmes est 1.6270.105 .

Le tableau suivant présente les résultats numériques obtenus par l’algorithme 2.6.2

θtho θalter
iter 149 9
CPU 0.0752 0.0241

Tableau 7. Résultats comparatifs entre le choix théorique et alternative de θ.

Discussins :
Pour voir l’influence du pas de déplacement durant la phase de prédiction sur le compor-
tement numérique de l’algorithme, on a fait une comparaison entre le choix théorique de
θ et le choix alternative. On déduit que malgré le choix théorique garantie la convergence
de la méthode, il conduit à des résultats non favorable c’est à dire la convergence de l’al-
gorithme correspondant est lente, mais dans le choix alternative on obtient des résultats
encourageant.

55
Conclusion

Dans ce travail, on s’intéresse à résoudre le problème linéaire (P L) par une méthode

primale-duale de point intérieur de type correcteur-prédicteur basée sur une nouvelle di-
rection de recherche, on utilise la transformation algébrique présenté par Darvay (2020) ,
il introduit ψ à l’équation de centralité pour obtenir des nouvelles directions de recherche
et on note que Darvay a montre la complexité polynomial de cet algorithme qui de l’ordre
√ 5(x0 )t z0
O(5 n log 4 ), avec les paramètres qui ont un rôle important dans l’algorithme : θ =
q
x0 z0
1
√
5 n
, τ = 1
4 et la mesure de proximité δ(x 0 , z0 ; µ0 ) ≤ 1 et v 0 =
4 µ0
> 12 justifiant la diffi-
culté ( le point initial qui vérifie la condition de trajectoire central, et être positive).
Notons que notre étude a réalisé les contributions suivantes :
— On a appliqué cet algorithme sur quelques problèmes linéaires pour montrer son ef-
ficacité.
— On compare entre le choix théorique durant la phase de prédiction θ = 5√1 n et autre
alternative de pas de déplacement pour voir l’influence de θ sur le comportement
numérique de cet algorithme.

56
Bibliographie

[1] M. Achache. A new primal-dual path-following method for convex quadratic program-
ming. Computational and Applied Mathematics, (25) pp. 97-110, (2006).
[2] M. Achache. A new parameterized kernel function for LO yielding the best known
iteration bound for a large-update interior point algorithm, article (2015).
[3] M. Achache, L. Guerra. A full-Nesterov-Todd-step primal-dual interior point algorithm
for convex quadratic semidefinite optimization. Computational and Applied Mathema-
tics,(231) : 581-590, (2014).
[4] B. Bounibane, Extension de quelques méthodes de points intérieurs pour un problème
d’optimisation, thèse doctorat, université de Batna 2, (2019).
[5] Zs. Darvay, New interior point algorithms in linear programming, Advanced modeling
and optimisation , 51-92, (2003).
[6] Zs. Darvay, A new predictor-corrector algorithm for linear programming. Alkalm Mat
Laplok 22 : 135-161, (2005).
[7] Zs. Darvay, predictor-corrector algorithm for linearly constrained convex optimiztion.
Studia Uni Babes-Bolyai Ser Inform 54(2) : 121-138, (2009).
[8] Zs. Darvay, I. M. Papp and P. R. Takács, Complexity analysis of a full-Newton step
interior-point method for linear optimization, Period. Math. Hungar. 73(1), 27–42, (2016).
[9] Zs. Darvay, P-R. Takács. New method for determining search directions for interior-
point algorithms in linear optimization. Optimization Letter. (2017).
[10] Zs. Darvay, T. Illés, B. Kheirfam, P. R. Rigó, A corrector-predictor interior-point me-
thod with new search direction for linear optimization. Central European Journal of
Operation Research, 28 : 1123-1140, (2020).
[11] Zs. Darvay, T. Illés, P. Renáta Rigó,Predictor-corrector interior-point algorithm for
P∗ (k)-linear complementarity problems based on a new type of algebraic equvalent trans-
formation technique, European Journal of Operation Research (298), 25-35, (2022).
[12] H. Debbiche, Cours optimisation sans contrainte, Université Mohamed El Bachir El
Ibrahimi de Bordj Bou Arréridj, (2015).
[13] J. CH. Gilbert, Extrait de Fragments d’optimisation Différentiable : Théorie et Algo-
rithmes, mémoire de master en France, (2020).
[14] N. Karmarkar, A new polynomial-time algorithm for linear programming, Combina-
torica. 4, 373-395, (1984).
[15] B. Kheirfam, An infeasible interior point method for the monotone SDLCP based on a
transformation of the central path. J Appl Math Comput, 57(1), 685-702. (2018).
[16] E. De Klerk. Interior point methods for semidefinite programming. Master of Science
in the Faculty of Enginnering University of Pretoria, (1997).

57
 BIBLIOGRAPHIE

[17] N. Megiddo, Pathways to the optimal set in linear programming. In : [Link] (ed)
Progress in mathematical programming. Interior-point and related methods. Springer,
New York : 131-158, (1989).
[18] S. Mehrotra, On the implementation of a primal-dual interior point metho. SIAM J
Optim, 24(1), 575-601, (1992).
[19] Y. E. Nesterov and A. S. Nemirovskii, Interior-Point Polynomial Algorithms in Convex
Programming (SIAM, Philadelphia, PA, 1994).
[20] Z. Ramdani. Cours d’optimisation non linéaire, Université Mohamed El Bachir El Ibra-
himi de Bordj Bou Arréridj, (2021).
[21] Z. Ramdani. Cours de programmation linéaire,Université Mohamed El Bachir El Ibra-
himi de Bordj Bou Arréridj, (2021).
[22] C. Roos, T. Terlaky, J. Ph. Vial, Theory and algorithms for linear optimization. An
interior point approach. John-Wiley. Sons, Chichester, UK, (1997).
[23] Gy. Sonnevend, An "analytic center" for polyhedrons and new classes of global algo-
rithms for linear (smooth, convex) programming. In : A Prékopa, J Szelezsán, B Strazi-
cky (eds) System Modelling and Optimization : Proceedings of the 12th IFIP-Conference
held in Budapest, Hungary, September 1985, Lecture Notes in Control and Information
Sciences. vol. 84 Springer, Berlin, 866–876, (1986).
[24] T. Terlaky, An easy way to teach interior-point methods. Eur J Oper Res 130(1), 1-19,
(2001).
[25] Gy Sonnevend, J Stoer, G Zhao, On the complexity of following the central path by
linear extrapolation in linear programming. Methods Oper Res 62 : 19-31, (1990).
[26] SJ. Wright, Primal-dual interior-point methods . SIAM, Philadelphia, (1997).

58
 :Pl› •
TyW˜ T›rb˜ ™˜ Tyl d˜ ªAqnl˜ T§wžA-Ty˜¤ Ty›EC w AnFC ,™m`˜ £@¡ ¨
™§w šA A –˜Ð¤ ­d§d˜ b˜ A¡A  Ylˆ dmt` ¨t˜ rqm-O› Šwn˜ Ÿ›
.xz = µe T§z•rm˜ T˜ A`m˜ Ylˆ ©rb
√
dyq`  Ð Ty›EC w˜
b y ψ(t) = t − t ,Darvay (2020) TF C š® Ÿ›
T E³ ­wW˜ ©r\n˜ CAyt³ Ÿy TžCAqml˜ T§ dˆ  CAbtA Anmq Ÿž A›
,© ¤d
© d`˜ —wls˜ Ylˆ X¶AFw˜ £@¡ ry Tr`m˜ ™§db˜ CAyt³ ¤ rq› Tlr› ºAn

.Ty›EC w˜ £@h˜

:TyAtfm˜ Amlk˜ •
,¸Ak› ©rb ™§w , rqm-O› Ty›EC w ,TyW˜ T›rb˜ ,Tyl d˜ ªAqn˜ ”rV
.© ¤d dyq`
• Résumé :

Dans ce travail, on a étudié un algorithme primal-dual de points intérieurs de type correcteur-

prédicteur basé sur une nouvelle direction de recherche pour résoudre un problème linéaire
(P L) on déduit une transformation algébrique
√ sur l’équation de centralité xz = µe.
Par l’étude de Darvay(2020)ou ψ(t) = t − t qui a prouvé que l’algorithme a une complexité
polynomial, nous avons fait des tests numériques comparatives entre le choix théorique du
pas de déplacement durant la phase de prédiction et le choix alternative pour voir l’influence
de ces paramètres sur le comportement numérique de cet algorithme.

• Mots clés :

Méthode de points interieurs, Programmation lineaire, Algorithme correcteur- predicteur, trans-

fermation algébrique équivalente, Complexité polynomiale.

• Abstract:

In this work, we studied a primal-dual algorithm of interior points of corrector-predictor type

based on a new search direction to solve a linear problem (LP ), we have introduce algebraic
transformation on the equation of centrality
√ xz = µe.
By the study of Darvay(2020), ψ(t) = t − t who proved that the algorithm has polynomial
complexity, we have done comparative numerical tests between the theoretical choice of the
displacement step during the prediction phase and the alternative choice to see the influence
of these parameters on the numerical behavior of this algorithm.

• Keywords:

interior point method, linear optimisation, corrector-predictor algorithm, algebraic equivalent

transfermation, polynomial complexity.