[PDF] Méthodes de points intérieurs pour la programmation linéaire

View - Download Méthodes de points intérieurs pour la programmation linéaire

Previous PDF

Next PDF

Méthodes de points intérieurs pour la

programmation linéaire basées sur les fonctions noyaux by

Anane Nassima

Submitted to the

in partial ful...llment of the requirements for the degree of unde...ned at the

MASSACHUSETTS INSTITUTE OF TECHNOLOGY

degreemonth unde...ned degreeyear unde...ned c Massachusetts Institute of Technology degreeyear unde...ned Signature of Author ....................................................

30 juin 2012

Accepted by............................................................

Table des matières

0.1 Notation et terminologie . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

0.2 Introduction générale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

1 Programmation linéaire et méthodes de résolution 9

1.1 Théorie générale de la programmation linéaire . . . . . . . . . . . . . . 9

1.2 Dualité en programmation linéaire . . . . . . . . . . . . . . . . . . . . . 10

1.3 Méthodes de résolution d"un programme linéaire . . . . . . . . . . . . . . 12

1.3.1 Méthode du simplexe . . . . . . . . . . . . . . . . . . . . . . . . . 12

1.3.2 Méthodes modernes de points intérieurs . . . . . . . . . . . . . . 12

2 Méthodes de trajectoire centrale de type primal-dual basées sur une

nouvelle fonction noyau 15 I Méthodes de trajectoire centrale classiques basées sur l"ap- proche barrière logarithmique 16

2.1 Méthodes barrières logarithmiques de type primal-dual de Tc pour PL . 17

2.2 Directions de Newton classiques . . . . . . . . . . . . . . . . . . . . . . . 19

II Méthodes barrières généralisées de type primal-dual de

Tc pour PL 22

2.3 Méthodes barrières généralisées de type primal-dual de Tc pour PL . . . 23

2

2.4 Algorithme générique primal-dual de Tc pour PL . . . . . . . . . . . . . 24

2.5 Fonction noyau et sa quali...cation . . . . . . . . . . . . . . . . . . . . . . 25

2.5.1 Quali...cation de (t). . . . . . . . . . . . . . . . . . . . . . . . . 25

III Analyse de la complexité 34

3 Résultats numériques 48

3.1 Exemples

49

3.2 Conclusion générale et perspectives . . . . . . . . . . . . . . . . . . . . . 69

3

0.1 Notation et terminologie

R n:L"ensemble des vecteurs avecncomposantes réelles. R n+:L"orthant positif de l"espaceRn. x t:Transposé du vecteurxdeRn x0(x >0) =xi0(xi>0);8i xz= (x1z1;:::;xnzn)T(produit deHadamard). x

1= (1x

1;:::;1x

n)T(xi6= 0): v=rxz v 1=s xz 1 px= (px

1;:::;px

n)T(x >0);

X=diag(x)

Z=diag(z)

e= (1;:::;1)T2Rn: F (P)=fx2Rn:Ax=b; x>0g: F

0(P)=fx2Rn:Ax=b; x >0g

F (D)=f(y;z)2Rm+n:ATy+z=c; x0; z0g: F

0(D)=f(y;z)2Rm+n:ATy+z=c; x >0; z >0g:

(x;z) :La fonction potentiel de type primale-duale. lp(x;y;z) :La fonction de Lagrange de problème primal-dual A=1 AV1X X

1=diag(x1)

4x;4z:Sont des directions

d x=v4xx d z=v4zz lb(x;z;) :La fonction barrière logarithmique de type primal-dual rbl(v) :Désigne le gradient de la fonction logarithmique barrièrebl (t) :Fonction noyau. (v) =nX i=1 (vi)mesure de proximité4

Résumé

Le but de ce mémoire est de proposer une méthode de points intérieurs de trajectoire centrale de type primal-dual pour résoudre les problèmes de la programmation linéaire (PL). Cette méthode est basée sur une nouvelle classe de direction de Newton et d"une nouvelle mesure de proximité introduites par une nouvelle fonction Noyau. Contrairement aux fonctions Noyaux existantes, notre fonction est d"une part paramètrisée par un réel q >1;et d"autre part elle possède un terme barrière doublé. On montre que l"algorithme correspondant admet une complexité polynomiale qui est de l"ordreO(qnq+12qlognlogn pour les algorithmes à grand pas. Pour le choixq=12 logn;on trouve la complexité qui est de l"ordreO(pnlognlogn ) et c"est la meilleure complexité polynomiale pour ces algorithmes, etO(q2pnlogn ) pour les algorithmes à petit pas, oùndésigne la taille du problème (PL). Cette étude est suivie par implémentation numérique de ces algorithmes sur des problèmes de (PL). On constate que les résultats numériques donnés par des choix convenables deqnotammentq=12 logn;dans les algorithmes sont les meilleurs par rapport aux autres choix deq. Mots clés: Programmation linéaire; Méthode de points intérieurs; Algorithme primal- dual de trajectoire centrale; Fonctions Noyaux; Complexité des Algorithmes. 5

0.2 Introduction générale

Le but de ce mémoire est de proposer une méthode de points intérieurs de trajec- toire centrale (Tc) de type primal-dual pour résoudre un programme linéaire (PL). La dite méthode est basée sur l"introduction des nouvelles fonctions dites auto-régulières introduites récemment parPeng,Roos et Terlaky en[9, 10,11] inclus les fonctions noyaux utilisées parBai et Roos [20],Bai, Roos et El Ghami[2, 4,8,15] pour ré-

soudre un programme linéaire et semi-dé...ni. Ces méthodes, néanmoins elles déterminent

une nouvelle classe de directions de Newton mais elles sont aussi considèrées comme une proximité pour mesurer la qualité des points par rapport à la trajectoire centrale. Ces fonctions satisfont quelques propriétés qui conduisent à un modèl très important pour développer ces méthodes. Ce nouveau paradigme donne naissance à une nouvelle

classe de méthodes de points intérieurs de (Tc)dites :" méthodes barrières généralisées".

Contrairement aux méthodes barrières classiques de points intérieurs qui sont basées sur la fonction barrière logarithmique (voir [2, 3,4,8,14,15]), ces méthodes sont basées sur la notion des fonctions auto-régulières (incluses les fonctions noyaux). Historiquement, presque tous les résultats de la complexité polynomiale des algorithmes primaux-duaux de (Tc)et leurs implémentation numérique sont analysés moyennant l"approche barrière logarithmique. Dans ce cadre, on distingue deux types d"algorithmes à savoir les algo- rithmes à petit pas (c"est à dire le paramétre barrièreest choisi comme=O(pn) c"est dire quedépend denla taille du programme linéairePL)et à grands pas ( si =O(1)est une constante. La complexité polynomiale trouvée par cette dernière est d"ordreO(pnlogn ) pour les algorithmes à petit pas etO(nlogn )pour les algorithmes grands pas [1, 2,16,17,18,19]. Avec ces nouvelles méthodes la complexité polynomiale est améliorée deO(nlogn ) àO(pnlognlogn ) pour les algorithmes à grands pas. Pour

plus de détails sur ces méthodes voir l"article de Bai et al [3], et la thèse d"ELGhami [15].

6 Pour les algorithmes à petit pas, on conserve la même complexité. Sur le plan numérique ces algorithmes montrent leurs e¢ cacités par rapport aux algorithmes classiques. Dans ce travail, on propose une nouvelle fonction noyau paramétrisée dé...nie par : (t) =t21 +t1q1q1logt; t >0; q >1: rière doublé donné par : t

1q1q1logt:

Avec cette fonction noyau, on dé...nit aussi une proximité donnée par : (v) =nX i=1 (vi)

pour contrôler la qualité des itérés par rapport à la trajectoire centrale. Cela conduit à

développer un nouvel algorithme primal-dual de points intérieurs de (Tc) pour tracer approximativement la trajectoire centrale. On montre que l"algorithme correspondant à grand pas admet une complexité qui est de l"ordreO(qnq+12qlognlogn ),q >1. Pour le choixq=12 logn;on trouve la complexité qui est de l"ordreO(pnlognlogn ) et c"est la meilleure complexité polynomiale pour ces algorithmes jusqu"à nos jours. Pour les algo- rithmes à petit pas on trouve la complexité qui est de l"ordreO(q2pnlogn ),q >1: Ce travail est suivi par implémentation numérique de ces algorithmes sur quelques pro- blèmes de tailles moyennes de la programmation linéaire et les résultats numériques

cacité de ces derniers. On constate que le nombre d"itérations donné par les algorithmes à

grand pas avec le choixq=12 logn;est réduit par rapport aux autres choix du paramètre q:On mentionne que pour le pas de déplacement, on a utilisé dans l"implémentation le

par théorique et les résultats numériques donnés ne sont pas satisfaisants. Alors pour ses

performances, on a proposé une procédure pratique pour calculer celle-ci et les résultats 7 numériques trouvés sont améliorés. chapitres. Dans le premier chapitreune synthèse sur la programmation linéaire et sur les mé- thodes de résolution d"un programme linéaire est présentée. Le deuxième chapitreest composé de trois parties : La première partieconstitue un survol sur les méthodes de points intérieurs de tra- jectoire centrale de type primal-dual basé sur la fonction barrière logarithmique classique pourPL. Dans la deuxième partie,une nouvelle fonction noyau est proposée suivie par une étude de ses propriètés par rapport au prblèmePL. La troisième partieest consacrée à l"analyse de la complexité algorithmique de ces algorithmes basée sur cette fonction noyau. Le dernier chapitreest consacré à l"implémentation numérique de ces algorithmes proposés. Finalement, on ...nira le mémoire par une conclusion et perspectives. 8

Chapitre 1

Programmation linéaire et méthodes

de résolution Dons ce chapitre, on présente une synthèse sur le problème de la programmation linéaire et ainsi sur les méthodes de résolution.

1.1 Théorie générale de la programmation linéaire

Un programme linéaire (PL)est un problème d"optimisation qui consiste à maximiser (ou minimiser) une fonction objectif linéaire denvariables de décision sujet à un ensemble de contraintes exprimées sous forme d"équations ou d"inéquations linéaires. Dé...nition 1.1.1On appelle un programme linéaire tout programme mathématique, où la fonction objectif est linéaire et l"ensemble des contraintes est a¢ ne. Ecriture mathématique :Il existe trois formes pour écrire un programme linéaire qui sont : 9

La forme canonique :

8>>>< >>:min xctx;06=c2Rn(vecteur donné)

Axb; A(mn)-matrice,b2Rm(donnés)

x0;vecteur inconnu deRn( variable )

La forme standard :

n minxctx; Ax=b;x0

La forme générale :

n minxctx; Axb; Bxb0;B(pn)-matrice;b02Rp

1.2 Dualité en programmation linéaire

On considère un programme linéaire sous la forme standard suivante : (P)minxctx:Ax=b ;x0 oùAest une matrice de type(mn); b2Rm; c2Rn. Bien évidemment, n"importe quel (PL)se ramène facilement à cette forme.

Le dual de (P) est dé...ni par :

(D) max(y; z)bty; Aty+z=c ;z0;y2Rm;z2Rn:

On notera par la suite :

F (P)=fx2Rn:Ax=b; x>0g F

0(P)=fx2Rn:Ax=b; x >0g

10 et F (D)=f(y;z)2Rm+n:Aty+z=c; z0g F

0(D)=f(y;z)2Rm+n:Aty+z=c; z >0g;

les ensembles des solutions réalisables et strictement réalisables des deux problèmes de (P)et(D), respectivement. Théorème 1.2.1( Dualité faible)(P) et (D) deux (PL)alors : c txbty;

8xréalisable de (P),8yréalisable de(D).

Théorème 1.2.2(Dualité forte)Six2 F(P)et(y;z)2 F(D);tel quectx=bty;alors x, et(y;z)sont des solutions optimales de(P)et(D),respectivement. Théorème 1.2.3(Théorème des écarts complémentaires )Soientxetydeux solutions réalisables primale et duale respectivement, posant : z=cAty vecteur des variables d"écarts associé ày, alorsxet(y;z)sont optimales sixizi= 0,8 i= 1;:::;n: Dé...nition 1.2.1Une base deAest une sous matriceBformée demcolonnes linéai- rement indépendantes deA. La solution de base associée àBest le pointx= (xB;xN)2Rntel que :xB=B1b, x N= 0: Une solution de base qui véri...exB0est dite solution de base réalisable. Un pointxest un sommet deF(P)si et seulement s"il est une solution de base réalisable.

Un sommet est dit non dégénéré sixB>0. Il est dégénéré dans le cas contraire (au

moins une composante dexBest nulle). 11 Théorème 1.2.4Si un programme linéaire possède une solution optimale, alors au moins un sommet du domaine réalisable est une solution optimale.

1.3 Méthodes de résolution d"un programme linéaire

1.3.1 Méthode du simplexe

Elle a été développée à la ...n des années 40 parG.Dantzig. Elle tient compte systé-

matiquement des résultats établis précédemment. Elle évolue sur la frontière du domaine

réalisable de sommet en sommet adjacent, en réduisant la valeur de l"objectif jusqu"à l"optimum. Un critère d"optimalité simple permet de reconnaître le sommet optimal. Le

nombre de sommet étant ...ni, l"algorithme ainsi dé...ni converge en un nombre ...ni d"itéra-

tions n"excédant pas le nombreCmn=n!m!(nm)!sous l"hypothèse que tous les sommets visités sont non dégénérés. Dans le cas dégénéré l"algorithme risque de cycler, cependant il existe des techniques

convenables pour éviter ce phénomène. En général, la méthode du simplexe possède

un comportement numérique très satisfaisant con...rmé par ses applications multiples dans la résolution d"une large classe de problèmes pratiques. En théorie, la méthode n"a

pas autant de succès, elle est plutôt jugée ine¢ cace de par sa complexité arithmétique

exponentielle qui est de l"ordre deO(2n)opérations.

1.3.2 Méthodes modernes de points intérieurs

Ces méthodes ont été développées dans les années 60 dans le but de résoudre des pro-

grammes mathématiques non linéaires. Leur utilisation pour la programmation linéaire n"a pas reçu autant d"enthousiasme à cause de la dominance quasi totale de la méthode du simplexe à cette époque. Après l"apparition de l"algorithme de Karmarkar en 1984 pour la programmation linéaire, les méthodes de points intérieurs ont connu une véri- table révolution, on enregistre plus de 3000 publications en quelques années. On distingue 12 trois classes fondamentales de méthodes de points intérieurs à savoir : les méthodes a¢ nes, les méthodes de réduction du potentiel et les méthodes de tra- jectoire centrale (suivi du chemin) (en englais : Path-following methods). a/ Méthodes a¢ nes (Dikin 1967) :Il s"agit pratiquement de l"algorithme de Karmarkar sans fonction potentiel et sans transformation projective, on utilise une trans- formation a¢ ne et on remplace la contrainte de non négativité par un ellipsoïde quiquotesdbs_dbs16.pdfusesText_22

[PDF] programmation lineaire methode simplexe

[PDF] programmation linéaire recherche opérationnelle

[PDF] interprétation droite de henry

[PDF] principe droite de henry

[PDF] exercice corrigé droite de henry

[PDF] courbe de henry excel

[PDF] droite de henry pdf

[PDF] programmation linéaire exercices corrigés pdf

[PDF] programmation linéaire exercices corrigés

[PDF] programmation linéaire simplexe

[PDF] recherche opérationnelle programmation linéaire exercices corrigés pdf

[PDF] exercices recherche operationnelle

[PDF] theme astral chinois complet gratuit interpretation

[PDF] cours recherche opérationnelle methode de simplexe

[PDF] recherche opérationnelle simplexe exercices corrigés