[PDF] Introduction au Compressed sensing. Méthode du simplexe

View - Download Introduction au Compressed sensing. Méthode du simplexe

Previous PDF

Next PDF

Introduction au Compressed sensing.

Methode du simplexe

Guillaume Lecue

1

Resume

Dans les deux chapitres qui se suivent, nous presentons deux types d'algorithmes pour resoudre des problemes de programmation lineaires. Le premier, presente dans ce chapitre, est l'algorithme du simplexe qui est un algorithme iteratif de marche sur les sommets du polytope des contraintes. Le deuxieme, presente dans le chapitre suivant, est une methode de barriere qui s'autorise a traverser le polytope de l'interieur pour atteindre la solution.

1 Introduction

La procedure de Basis Pursuit peut^etre reecrite comme un probleme de programmation lineaire: etant donnesA2RmNety2Rm, on considere le probleme d'optimisation (^z+;^z)2argmin (z+;z)2R2NN X j=1z +j+zjtel que [Aj A]z+ z =yetz+ z

0:(LP)

On rappelle que pour toutx2RN, on notex+2RNetx2RNles vecteurs dont les coordonnees sont donnees pour toutj= 1;:::;Npar (x+)j= max(0;xj) et (x)j= max(0;xj):

L'equivalence entre le Basis Pursuit et (

LP )est ac omprendred el aman ieres uivante. Proposition 1.1.Il y a equivalence entre le probleme d'optimisation du Basis Pursuit et(LP): 1. Si ^xest solution du basis pursuit alors(^x+;^x)est solution de(LP) 2. Si (^z+;^z)est solution de(LP)alors^z+^zest solution du basis pursuit. L'objectif des deux chapitres suivants du cours est de proposer des algorithmes solutionnant le probleme ( LP ).P ource la,on in troduitl esf ormesg eneraleset st andardde spr oblemed ep rogram- mation lineaire. Ensuite, on presente deux types d'algorithmes pour solutionner les problemes de programmation lineaire.

2 Programmation lineaire

Un probleme de programmation lineaire est un probleme d'optimisation sous contraintes ou

la fonction objectif est lineaire et les contraintes sont elles aussi lineaires. C'est donc un probleme

de la forme min x2Rpc1x1++cpxptel queai1x1+ai2x2++aipxpbi;i= 1;:::;m1 a

i1x1+ai2x2++aipxp=bi;i=m1+ 1;:::;m2:(2.1)1. CNRS, CREST, ENSAE. Bureau E31, 3 avenue Pierre Larousse. 92 245 Malakof. Email :

guillaume.lecue@ensae.fr. 1

La fonction objectif

(x1;:::;xn)>2Rn7!c1x1++cnxn est bien lineaire. Il y am1+m2contraintes lineaires dontm1sont des inegalites etm2sont des egalites.

Le probleme

2. 1 es tl aforme generaleouforme canoniquedes problemes de programma- tion lineaire. Il est courant de reecrire ce probleme sous laforme standard: min x2Rn c;xtel queAx=b;x0:(2.2) Proposition 2.1.Il est toujours possible de transformer un probleme de programmation lineaire ecrit sous forme general en un probleme de programmation lineaire sous forme standard.

Demonstration.

Etant donne un probleme sous la forme generale (2.1). On considere deux trans- formations : 1. l escon traintesd 'inegalite" ai1x1+ai2x2++aipxpbi" peuvent ^etre transformee en contraintes d'egalite par l'ajout d'une "slack variable" (variable molle)uipar : a i1x1+ai2x2++aipxp+ui=bietui0 2. on t ransformet outesl esv ariablesxipar x +x=x;x+0 etx0:

On reecrit alors (

2.1 ) sous la forme ( 2.2 ) ou x!2 4x+ x u3 5 ;c!c+ c ;A!A1A1I m1A 2A20 m2 etb!b(2.3) ouA1= (aij: 1im1;1jp) etA2= (aij:m1+ 1im2;1jp) De la m^eme maniere que dans la preuve de Proposition 1. 1 , on verie l'equivalence des deux programmes : 1. Si ^ xest solution de (2.1) alors il existe ^u0 tel que (^x+;^x;^u) est solution de (2.2) pour c;A;bdenis dans (2.3). 2. Si ( ^x+;^x;^u) est solution de (2.2) pourc;A;bdenis dans (2.3) alors ^x+^xest solution de ( 2.1 ).Remarque 2.2.En pratique, la transformation d'un probleme de programmation lineaire sous forme canonique en un probleme standard s'eectue par une suite d'operation du style :

1.x1+ 2x33!x1+ 2x3+s1= 3;s10

2.2x1+x25! 2x1+x2s2= 5;s20ets1;s2sont appelees les slack variables.

Quand une slack variable est nulle la contrainte associee est ditesaturee; cad la solution est sur le bord de la contrainte. 3. " x15" : ici on pourrait introduire une slack variable mais plut^ot que d'augmenter inuti- lement le nombre de variables, on preferera posery1=x15et remplacerx1!y1+ 5 poury10partout oux1appara^t. 2

4.L ev ariablesq uin es ontp asc ontraintes a^ etrep ositivess ontr emplaceesp arde uxv ariables:

x

1=x+1x1oux+1;x10.

On s'interesse dans la suite aux problemes de programmation lineaire ecrits sous forme stan- dard. On remarque que le probleme ( LP ) qu'on souhaite resoudre est directement ecrit sous forme standard. Un probleme de programmation lineaire se denit alors a partir dec2Rn,A2Rmn etb2Rm.

3 Methode du simplexe

On considere un probleme de programmation lineaire sous forme standard min x2Rn c;xtel queAx=b;x0ouc2Rn,A2Rmnetb2Rm. L'ensemble des contraintesaussi appeleensemble de faisabilitedu probleme est

C=fx2Rn:x0 etAx=bg:

C'est l'intersection de l'octant superieur (R+)net de l'espace anefx:Ax=bg. Soit cet ensemble est vide (en particulier, il n'y a pas de solution au probleme d'optimisation), soit il n'est pas compact, soit c'est l'enveloppe convexe d'un nombre ni de points. Dans le troisieme cas,Cest, par denition, appelepolytopeousimplexe. Les points d'un polytope dont il est l'enveloppe convexe et qui ne peuvent pas ^etre ecrits comme combinaison convexe des autres points sont appelessommetsoupoints extr^emes.x

1+ 3x3= 63x1+ 2x2+x3= 10

3x1+ 2x2+x3= 10

x

1+ 3x3= 6Figure1 { Exemples d'espaces de contraintes non vides

3.1 Deux resultats preliminaires

Proposition 3.1.SoitA2Rmnetb2Rm. On noteC= (Rn+)\ fx2Rn:Ax=bg. On suppose queCest non vide et compact. Dans ce cas, au moins un des sommets de l'ensemble des contraintesCest solution du probleme(2.2). 3 Demonstration.L'ensembleCdes contraintes de (2.2) est un polytope, on peut donc ecrire

C= conv(x1;:::;xp) =n

pX j=1 jxj:2(p)o oux1;:::;xpsont les points extr^emes deCet (p)=n = (1;:::;p)>2Rp:i0;i= 1;:::;petpX i=1 i= 1o La fonction objectif est continue. Elle atteint donc son minimum sur l'ensemble compactC.

En particulier, (

2.2 ) admet au moins une solution. Soit ^x2 Ctel que c;^x c;xpour tout x2 C. On a donc pour tout2(p), c;^x c;X ixi=X i c;xi: En prenant le minimum sur2(p)dans la derniere inegalite, on voit que c;^xmin1ip c;xi. Par ailleurs, ^x2 C. Il existe alors^2(p)tel que ^x=P^ixi. Ainsi, par linearite, c;^x=X i^ i c;ximin1ip c;xi:

On en deduit que min

1ip c;xi= c;^xet donc le probleme (2.2) admet au moins une solution

en un des points extr^emes deC.Une solution au probleme (2.2) peut donc ^etre trouvee en identiant tous les points extr^emes

deCet en testant leur optimalite les uns a la suite des autres. En general, cet algorithme n'est pas realisable en grande dimension car le nombre de sommets deCpeut ^etre grand.

Neanmoins, le fait que (

2.2 ) admette une solution en un des sommets deCest central pour l'algorithme du simplexe. En eet, la base de cet algorithme est de trouver un chemin parmi tous les sommets deCqui mene a une solution de (2.2). Idee: L'algorithme du simplexe est une methode iterative qui explore les sommets deC= (Rn+)\ fx2Rn:Ax=bgde proche en proche et qui assure la decroissance de la fonction objectif x! c;xa chaque iteration. A la n de l'algorithme du simplexe, un sommet deCsolutionnant 2.2 )est rendu.A chaque etape de l'algorithme du simplexe, cad a un sommet deC, la question centrale est de determiner quel sommet voisin doit ^etre explore { idealement, pour arriver a une solution de 2.2 ) (cette solution, rendue par l'algorithme du simplexe, est necessairement un sommet) le plus rapidement possible. C'est precisement a cette question que repond (partiellement) l'algorithme du simplexe. Remarque 3.2.Il n'y a pas forcement unicite de la solution de(2.2). SiCest non vide et compact alors il peut tres bien arriver qu'une face entiere du polytopeCsoit solution. QuandC est non vide et non compact, il se peut que la solution soit a l'inni et donc le minimum de(2.2) est1. On verra dans la suite comment l'algorithme du simplexe se comporte dans ces deux cas. La premiere chose qu'on doit s'assurer est qu'etant donne une etape de l'algorithme du sim- plexe, cad etant donne un sommet deC, si la fonction objectivex! c;xn'est pas minimale en ce sommet alors necessairement un des sommets voisins aura une valeur de la fonction objectif strictement plus petite. 4 Proposition 3.3.Soitx1un point extr^eme deC(qu'on suppose non-vide et compact). Six1 n'est pas solution de(2.2)alors pour au moins un des sommets voisins dex1la fonction objectif x! c;xprend une valeur strictement plus petite qu'enx1. Demonstration.Pour cela, il sut de montrer que six1est un sommet deCtel que sur tous les sommets voisins la fonction':x! c;xest plus grande qu'enx1alors'est minimal enx1. On ecritC= conv(x1;:::;xp) oux1;:::;xpsont les sommets deC. On denit l'ensemble S

1 fx1;:::;xpgdes sommets voisins dex1comme etant le plus petit ensemble defx1;:::;xpg

tel que le c^one de sommetx1engendre par conv(S1) contienneC.x

1Par hypothese, on a pour toutx2S1,'(x)'(x1). On en deduit, par linearite, de'que

sur toute demie-droite issue dex1et contenue dans le c^one de sommetx1engendre par conv(S1) la fonction'est croissante (x1etant vu comme l'origine de la demie-droite). En particulier, si x2 fx2;:::;xpgalors le segment [x1;x] est un sous-ensemble d'une telle demie-droite. Donc' cro^t sur ce segment dex1axet donc'(x)'(x1). Ceci etant vrai pour tout sommetxdeC, on en deduit le resultat a l'aide de Proposition 3.1 .Proposition3. 3as suredon cq uel esom metex plorep arl 'algorithmedu si mplexees ts oit solution du probleme ( 2.2 ), soit il y a parmi ces sommets voisins un sommet pour lequel la fonction a minimiser sera strictement plus petite.

3.2 Presentation de l'algorithme du simplexe

L'algorithme du simplexe est un algorithme iteratif d'exploration de sommets du polytope des contraintesC= (R+)n\ fx:Ax=bgqui assure la decroissance de la fonction objectif ':x2Rn! c;xle long de son chemin. 5 Figure2 { Exploration des sommets du polytope des contraintes par l'algorithme du simplexe.

Il est base sur deux regles :

1. l apr emierer eglee stu ncritere d'arr^et 2. l ade uxiemer egle enoncele p rincipep ourpasser d'un sommet a un de ses sommets voisinsassurant la decroissance de'. Chaque iteration s'eectue par une etape dupivot de Gauss(aussi appeleelimination Gaussienneoumethode de Gauss-Jordan). En eet, en introduisant la variablesz= c;x, on voit qu'une solution de ( 2.2 ) sera aussi solution du systeme d'equations lineaires z c;x= 0

Ax=b:(3.1)

On va donc a chaque etape trouver une solution positive au systeme ( 3.1 ) par la methode du pivot de Gauss. A l'etape suivante, on sera amene a resoudre un autre systeme d'equations lineaires semblable a celui de ( 3.1 ) mais pour d'autres coecientsc!c0;A!A0;b!b0obtenus par une etape de pivot de Gauss. Ce systeme est de la forme z c0;x=b00A0x=b0:(3.2) Ce systeme appara^t a chaque iteration de l'algorithme du simplexe. Il est utile de le representer sous forme de tableau.zx >b

1(c0)>b

000A 0b

0nom des variables

ligne 0 lignes d'indices 1;:::;m Figure3 { Representation sous forme de tableau de chaque iteration de l'algorithme du simplexe Si, pour une certaine iteration, le vecteurc0n'a que des coecients positifs ou nuls alors, commex0, on ne pourra plus faire decro^trezet alors la solution au probleme seraz=b00. Ceci correspond au critere d'arr^et de l'algorithme du simplexe et donc a la premiere regle. 6 Premiere regle :Si toutes les coordonnees du vecteur(c0)>de la ligne0sont negatifs ou nuls alors une solution a coordonnees positives ou nulles au systeme(3.2)minimisantzest solutionquotesdbs_dbs33.pdfusesText_39

[PDF] methode simplexe exemple

[PDF] exercices corrigés de recherche opérationnelle méthode du simplexe

[PDF] minimiser simplexe exemple

[PDF] commencer la numérotation ? la page 3 word

[PDF] supprimer numéro de page word

[PDF] word commencer pagination page 3

[PDF] méthode singapour ce1 pdf

[PDF] commencer la numérotation des pages plus loin dans votre document

[PDF] comment numéroter les pages sur word 2007 ? partir dune page

[PDF] commencer numérotation page 3 word 2007

[PDF] numérotation pages mac

[PDF] equation 2 inconnues exercices substitution

[PDF] résolution numérique équation différentielle second ordre

[PDF] résolution numérique équation différentielle non linéaire

[PDF] test de psychologie pdf