Transcript
Page 1: Programmation linéaire, polarité et lancer de rayons (la programmation linéaire autrement) Yan Gerard LAIC (Université d’Auvergne) gerard@laic.u-clermont1.fr

Programmation linéaire, polarité et lancer de rayons

(la programmation linéaire autrement)

Yan Gerard

LAIC (Université d’Auvergne)

[email protected]

Page 2: Programmation linéaire, polarité et lancer de rayons (la programmation linéaire autrement) Yan Gerard LAIC (Université d’Auvergne) gerard@laic.u-clermont1.fr

Une escroquerie

Un imposteur:

Une escroquerie : Vous vendre la théorie bien connue de la Programmation Linéaire sous une forme différente

(ni expert en Programmation Linéaire ni expert en Géométrie Algorithmique)

Y.G

(plus géométrique)

Page 3: Programmation linéaire, polarité et lancer de rayons (la programmation linéaire autrement) Yan Gerard LAIC (Université d’Auvergne) gerard@laic.u-clermont1.fr

Escroc sans le savoir ?

Reconnaissance de morceaux de plans discrets

Données: une partie finie S de Z3

Réponse à la question: S appartient-elle à un plan discret ?

=?

Page 4: Programmation linéaire, polarité et lancer de rayons (la programmation linéaire autrement) Yan Gerard LAIC (Université d’Auvergne) gerard@laic.u-clermont1.fr

=?

Escroquerie: vendre la Programmation Linéaire sous une forme méconnaissable…

Escroc sans le savoir ?

Page 5: Programmation linéaire, polarité et lancer de rayons (la programmation linéaire autrement) Yan Gerard LAIC (Université d’Auvergne) gerard@laic.u-clermont1.fr

A) Programmation Linéaire

Plan de l’exposé

1 Introduction

2 Lemme de Farkas

3 Géométrie des solutions

B) Lancer de Rayon

4 Problèmes de Lancer de Rayon

5 Algorithmes de Lancer de Rayon

Page 6: Programmation linéaire, polarité et lancer de rayons (la programmation linéaire autrement) Yan Gerard LAIC (Université d’Auvergne) gerard@laic.u-clermont1.fr

A) Programmation Linéaire

1 Introduction

2 Lemme de Farkas

3 Géométrie des solutions

Page 7: Programmation linéaire, polarité et lancer de rayons (la programmation linéaire autrement) Yan Gerard LAIC (Université d’Auvergne) gerard@laic.u-clermont1.fr

1 Introduction

Page 8: Programmation linéaire, polarité et lancer de rayons (la programmation linéaire autrement) Yan Gerard LAIC (Université d’Auvergne) gerard@laic.u-clermont1.fr

1.1 Bref rappel: Qu’est-ce qu’un programme linéaire ?

L’objectif de la programmation linéaire est de résoudre des systèmes d’inégalités linéaires

2 x1 - 3 x2+ 4 x3 ≤ 6

et de trouver une solution x Є Rd (si il en existe) pour laquelle une forme linéaire donnée c.x (c Є Rd ) ait une valeur maximale.

Exemple :

1 x1 - 2 x3 ≤ 4 4 x1 + x3 ≤ -5- x1 +2 x2+ x3 ≤ -1

- 3 x2 ≤ 0

Exemple : Maximiser x1 + 4 x2

1 Introduction

Page 9: Programmation linéaire, polarité et lancer de rayons (la programmation linéaire autrement) Yan Gerard LAIC (Université d’Auvergne) gerard@laic.u-clermont1.fr

Données : - Des inégalités linéaires dans Rd

a1 x1+a2 x2+…+ aj xj+…+ad xd ≤ ad+1

- Une forme linéaire de Rd c.x où c Є Rd (non nul)

Questions : Existe-t-il une solutions aux inégalités?

Si oui, trouver une solution telle que c.x soit maximal

Si un programme linéaire a des solutions, il est dit réalisable.Vocabulaire:

Un programme linéaire est donc un problème d’optimisation de la forme suivante:

Algorithmes de résolution:

simplex (Dantzig 1947) , l’ellipsoïde (Khachiyan 1979) – polynomial -

points intérieurs (Kamarkar 1984) …

Page 10: Programmation linéaire, polarité et lancer de rayons (la programmation linéaire autrement) Yan Gerard LAIC (Université d’Auvergne) gerard@laic.u-clermont1.fr

1.2 Une inégalité linéaire ≈ un point

2 x1 - 3 x2+ 4 x3 ≤ 6Exemple :

1 x1 - 2 x3 ≤ 4 4 x1 + x3 ≤ -5- x1 +2 x2+ x3 ≤ -1

- 3 x2 ≤ 0(2,- 3, 4, 6)

(1, 0, -2, 4)(0, 4, 1, -5)(-1, 2, 1,-1)

(0,- 3, 0, 0)

On formalise l’identification inégalité linéaire/point en introduisant la relation binaire # : Soient a Є Rd+1 et b Є Rd ,

la relation a # b est satisfaite a1 b1+a2 b2+…+ aj bj+…+ad bd ≤ ad+1

Notation:

Exemple : L’inégalité linéaire 2 x1 - 3 x2+ 4 x3 ≤ 6 est notée (2, -3, 4, 6) # x

L’inégalité linéaire a1 x1+a2 x2+…+ aj xj+…+ad xd ≤ ad+1

se note donc simplement a # x où a Є Rd+1 .

Page 11: Programmation linéaire, polarité et lancer de rayons (la programmation linéaire autrement) Yan Gerard LAIC (Université d’Auvergne) gerard@laic.u-clermont1.fr

1.3 Les demi-droites True et FalseIl y a certains points a Є Rd+1 pour lesquels l’inégalité linéaire a # x a la propriété d’être toujours vraie ou toujours fausse, indépendamment du point x Є Rd considéré.

Prenons le point (0,0,…,0,1) Є Rd+1 , l’inégalité linéaire (0,0,…,0,1) # x est 0 x1+0 x2+…+ 0 xj+…+0 xd ≤ 1

soit 0 ≤ 1Elle est toujours vraie.

Cette propriété s’étend à tous les points a Є Rd+1 dont les d premières coordonnées sont nulles et la dernière ad+1 est positive (ad+1 ≥ 0).

La demi-droite True

Page 12: Programmation linéaire, polarité et lancer de rayons (la programmation linéaire autrement) Yan Gerard LAIC (Université d’Auvergne) gerard@laic.u-clermont1.fr

Prenons le point (0,0,…,0,1) Є Rd+1 , l’inégalité linéaire (0,0,…,0,1) # x est 0 x1+0 x2+…+ 0 xj+…+0 xd ≤ 1

soit 0 ≤ 1Elle est toujours vraie.

Cette propriété s’étend à tous les points a Є Rd+1 dont les d premières coordonnées sont nulles et la dernière ad+1 est positive (ad+1 ≥ 0).

La demi-droite True

Page 13: Programmation linéaire, polarité et lancer de rayons (la programmation linéaire autrement) Yan Gerard LAIC (Université d’Auvergne) gerard@laic.u-clermont1.fr

Par construction, l’inégalité a # x est toujours vraie ssi a Є True .

Il s’agit de la demi-droite [O,xd+1[ qu’on notera désormais True.

Prenons le point (0,0,…,0,1) Є Rd+1 , l’inégalité linéaire (0,0,…,0,1) # x est 0 x1+0 x2+…+ 0 xj+…+0 xd ≤ 1

soit 0 ≤ 1Elle est toujours vraie.

Cette propriété s’étend à tous les points a Є Rd+1 dont les d premières coordonnées sont nulles et la dernière ad+1 est positive (ad+1 ≥ 0).

La demi-droite True

Page 14: Programmation linéaire, polarité et lancer de rayons (la programmation linéaire autrement) Yan Gerard LAIC (Université d’Auvergne) gerard@laic.u-clermont1.fr

On s’intéresse aux inéquations linéaires qui sont toujours fausses:

Prenons par exemple l’inéquation linéaire (0,0,…,0,-1) # x .

0 x1+0 x2+…+ 0 xj+…+0 xd ≤ -1

soit 0 ≤ -1

Elle s’écrit

D’une manière générale, l’inéquation a # x est toujours fausse ( indépendamment de x ) ssi a est dans la demi droite Є ]O, - xd+1 [ .

Cette demi-droite (ouverte) est appelée False.

La demi-droite False

Page 15: Programmation linéaire, polarité et lancer de rayons (la programmation linéaire autrement) Yan Gerard LAIC (Université d’Auvergne) gerard@laic.u-clermont1.fr

1.4 Un système d’inégalités linéaires ≈ un ensemble de points

La relation binaire # définie sur les paires de points s’étend facilementaux paires d’ensembles de points

soient A C Rd+1 et B C Rd , la relation A # B est satisfaite si et seulement si

pour tout élément a Є A et b Є B, on a a # b.

Le système d’inégalités linéaires

se note simplement A # x où A est une partie de Rd+1 .

a1,1 x1+a1,2 x2+…+ a1,j xj+…+a1,d xd ≤ a1,d+1

a2,1 x1+a2,2 x2+…+ a2,j xj+…+a2,d xd ≤ a2,d+1

ai,1 x1+ai,2 x2+…+ ai,j xj+…+ai,d xd ≤ ai,d+1

an,1 x1+an,2 x2+…+ an,j xj+…+an,d xd ≤ an,d+1

……

Page 16: Programmation linéaire, polarité et lancer de rayons (la programmation linéaire autrement) Yan Gerard LAIC (Université d’Auvergne) gerard@laic.u-clermont1.fr

Le système d’inégalités linéaires

se note simplement A # x où A est une partie de Rd+1 .

a1,1 x1+a1,2 x2+…+ a1,j xj+…+a1,d xd ≤ a1,d+1

a2,1 x1+a2,2 x2+…+ a2,j xj+…+a2,d xd ≤ a2,d+1

ai,1 x1+ai,2 x2+…+ ai,j xj+…+ai,d xd ≤ ai,d+1

an,1 x1+an,2 x2+…+ an,j xj+…+an,d xd ≤ an,d+1

……

Page 17: Programmation linéaire, polarité et lancer de rayons (la programmation linéaire autrement) Yan Gerard LAIC (Université d’Auvergne) gerard@laic.u-clermont1.fr

Le système d’inégalités linéaires

se note simplement A # x où A est une partie de Rd+1 .

a1,1 x1+a1,2 x2+…+ a1,j xj+…+a1,d xd ≤ a1,d+1

a2,1 x1+a2,2 x2+…+ a2,j xj+…+a2,d xd ≤ a2,d+1

ai,1 x1+ai,2 x2+…+ ai,j xj+…+ai,d xd ≤ ai,d+1

an,1 x1+an,2 x2+…+ an,j xj+…+an,d xd ≤ an,d+1

……

2 x1 - 3 x2+ 4 x3 ≤ 6Exemple :

1 x1 - 2 x3 ≤ 4 4 x1 + x3 ≤ -5- x1 +2 x2+ x3 ≤ -1

- 3 x2 ≤ 0Le système d’inégalités linéaires

se note simplement A # x où A = { (2,-3,4,6) , (0,-3,0,0) , (1,0,-2,4) , (0,4,1,-5) , (-1,2,1,-1) } .

Page 18: Programmation linéaire, polarité et lancer de rayons (la programmation linéaire autrement) Yan Gerard LAIC (Université d’Auvergne) gerard@laic.u-clermont1.fr

2 x1 - 3 x2+ 4 x3 ≤ 6Exemple :

1 x1 - 2 x3 ≤ 4 4 x1 + x3 ≤ -5- x1 +2 x2+ x3 ≤ -1

- 3 x2 ≤ 0Le système d’inégalités linéaires

se note simplement A # x où A = { (2,-3,4,6) , (0,-3,0,0) , (1,0,-2,4) , (0,4,1,-5) , (-1,2,1,-1) } .

Page 19: Programmation linéaire, polarité et lancer de rayons (la programmation linéaire autrement) Yan Gerard LAIC (Université d’Auvergne) gerard@laic.u-clermont1.fr

A est un ensemble de points.

Le fait que le système d’inégalités linéaires A # x soit ou non réalisable a-t-il une interprétation géométrique sur A ?

2 x1 - 3 x2+ 4 x3 ≤ 6Exemple :

1 x1 - 2 x3 ≤ 4 4 x1 + x3 ≤ -5- x1 +2 x2+ x3 ≤ -1

- 3 x2 ≤ 0Le système d’inégalités linéaires

se note simplement A # x où A = { (2,-3,4,6) , (0,-3,0,0) , (1,0,-2,4) , (0,4,1,-5) , (-1,2,1,-1) } .

Peut-on caractériser géométriquement les ensembles A dont le système d’inégalités linéaires A # x est réalisable ?

Page 20: Programmation linéaire, polarité et lancer de rayons (la programmation linéaire autrement) Yan Gerard LAIC (Université d’Auvergne) gerard@laic.u-clermont1.fr

Peut-on caractériser géométriquement les ensembles A dont le système d’inégalités linéaires A # x est réalisable ?

Page 21: Programmation linéaire, polarité et lancer de rayons (la programmation linéaire autrement) Yan Gerard LAIC (Université d’Auvergne) gerard@laic.u-clermont1.fr

2 Lemme de Farkas

En Programmation Linéaire, les lemmes qui caractérisent les systèmes d’inégalités linéaires réalisables sont appelés lemmes de Farkas.

Un système d’inégalités linéaires est réalisable si et seulement si

aucune combinaison linéaire à coefficients positifs des inégalités n’est aberrante ( 0 ≤ -1 ).

2.1 Lemme de Farkas standard

Peut-on caractériser géométriquement les ensembles A dont le système d’inégalités linéaires A # x est réalisable ?

Page 22: Programmation linéaire, polarité et lancer de rayons (la programmation linéaire autrement) Yan Gerard LAIC (Université d’Auvergne) gerard@laic.u-clermont1.fr

2.2 Hauteur dans Rd+1

On considère que la coordonnée verticale est la dernière: xd+1

On prend l’intersection de l’enveloppe convexe de A et de l’axe vertical Oxd+1.

- Si l’intersection est vide, par convention la hauteur de A est +∞

- Sinon, c’est la borne inférieure des coordonnées xd+1 des points de l’intersection.

Page 23: Programmation linéaire, polarité et lancer de rayons (la programmation linéaire autrement) Yan Gerard LAIC (Université d’Auvergne) gerard@laic.u-clermont1.fr

2.3 Lemme de Farkas géométrique

Le système A # x (où A est une partie de Rd+1 ) est réalisable ssi

la hauteur de A est positive ( hauteur(A) ≥ 0 ).

hauteur(A)<0 hauteur(A) ≥ 0

A # x non réalisable A # x réalisable

hauteur(A) ≥ 0

A # x réalisable

Exemples :

Page 24: Programmation linéaire, polarité et lancer de rayons (la programmation linéaire autrement) Yan Gerard LAIC (Université d’Auvergne) gerard@laic.u-clermont1.fr

On sait caractériser géométriquement les ensembles A dont le système d’inégalités linéaires A # x est réalisable.

Y a-t-il une relation géométrique entre l’ensemble A et l’ensemble des solutions ?

nouvelle question

2.3 Lemme de Farkas géométrique

Le système A # x (où A est une partie de Rd+1 ) est réalisable ssi

la hauteur de A est positive ( hauteur(A) ≥ 0 ).

Page 25: Programmation linéaire, polarité et lancer de rayons (la programmation linéaire autrement) Yan Gerard LAIC (Université d’Auvergne) gerard@laic.u-clermont1.fr

3 Géométrie des solutions

3.1 Remarque préliminaire

L’ensemble A est une partie de Rd+1.L’ensemble des solutions de A # x est une partie de Rd.

Comment relier géométriquement une partie de Rd+1 à une partie de Rd ?

Il faut plonger Rd dans Rd+1.

3.2 Quel plongement de Rd dans Rd+1 ?

Page 26: Programmation linéaire, polarité et lancer de rayons (la programmation linéaire autrement) Yan Gerard LAIC (Université d’Auvergne) gerard@laic.u-clermont1.fr

3.2 Quel plongement de Rd dans Rd+1 ?

Page 27: Programmation linéaire, polarité et lancer de rayons (la programmation linéaire autrement) Yan Gerard LAIC (Université d’Auvergne) gerard@laic.u-clermont1.fr

L’espace affine Rd. L’espace affine Rd+1.

L’espace Rd se plonge naturellement dans l’hyperplan xd+1=0 de Rd+1.

On utilisera un autre plongement:

L’espace Rd se plonge dans l’hyperplan xd+1=-1 de Rd+1.

Pourquoi l’hyperplan xd+1=-1 ?

Parce que si on considère une inégalité linéaire a # x :a1 x1+a2 x2+…+ aj xj+…+ad xd ≤ ad+1

avec a Є Rd+1 et x Є Rd , elle se réécrit simplementa.(x,-1) ≤ 0

3.2 Quel plongement de Rd dans Rd+1 ?

Page 28: Programmation linéaire, polarité et lancer de rayons (la programmation linéaire autrement) Yan Gerard LAIC (Université d’Auvergne) gerard@laic.u-clermont1.fr

x Є Rd est solution de l’inégalité linéaire a # x ssi

le produit scalaire de a et du plongement de x ((x,-1) Є Rd+1) est négatif.

En plongeant Rd dans l’hyperplan xd+1=-1 de Rd+1 on a l’équivalence

Soit a Є Rd+1 .

3.2 Quel plongement de Rd dans Rd+1 ?

3.3 Propriété du plongement de Rd dans Rd+1

Page 29: Programmation linéaire, polarité et lancer de rayons (la programmation linéaire autrement) Yan Gerard LAIC (Université d’Auvergne) gerard@laic.u-clermont1.fr

x Є Rd est solution du système d’inégalités A # x ssi

le plongement de x a des produits scalaires négatifs avec tous les points de A.

Soit a Є Rd+1 . Soit A C Rd+1 .

3.3 Propriété du plongement de Rd dans Rd+1

3.2 Quel plongement de Rd dans Rd+1 ?

Page 30: Programmation linéaire, polarité et lancer de rayons (la programmation linéaire autrement) Yan Gerard LAIC (Université d’Auvergne) gerard@laic.u-clermont1.fr

x Є Rd est solution du système d’inégalités A # x ssi

le plongement de x a des produits scalaires négatifs avec tous les points de A.

Page 31: Programmation linéaire, polarité et lancer de rayons (la programmation linéaire autrement) Yan Gerard LAIC (Université d’Auvergne) gerard@laic.u-clermont1.fr

x Є Rd est solution du système d’inégalités A # x ssi

le plongement de x a des produits scalaires négatifs avec tous les points de A.

Soit A C Rd+1 .Soit A C Rd+1 et son enveloppe convexe coniqueSoit A C Rd+1 et le plongement des solutions dusystème d’inégalités linéaires A # x .

et b une solution du système linéaire A # x .Le bord de l’ensemble des solutions est donné par les faces du cône de A.

Page 32: Programmation linéaire, polarité et lancer de rayons (la programmation linéaire autrement) Yan Gerard LAIC (Université d’Auvergne) gerard@laic.u-clermont1.fr

3.4 Polarité conique

Définition analytiqueLe cône polaire d’une partie A de Rd+1 est l’ensemble des points de Rd+1 ayant un produit scalaire négatif avec tous les points de A :

cône polaire(A)={x Є Rd+1 / forall y Є A, x.y ≤ 0}

Cône A

Cône polaire de A

Page 33: Programmation linéaire, polarité et lancer de rayons (la programmation linéaire autrement) Yan Gerard LAIC (Université d’Auvergne) gerard@laic.u-clermont1.fr

3.5 Polarité et solutions

L’ensemble des solutions du système d’inégalités A # x est donné par l’intersection de l’hyperplan xd+1=-1 et du cône polaire de A .

Cône polaire de A

Cône convexe engendré par A

Page 34: Programmation linéaire, polarité et lancer de rayons (la programmation linéaire autrement) Yan Gerard LAIC (Université d’Auvergne) gerard@laic.u-clermont1.fr

3.6 Solution optimaleOn cherche maintenant une solution du système d’inégalités A # x telle que le produit scalaire c.x soit maximal (c Є Rd ).

La formulation duale du programme linéaire affirme que la solution est donnée par la face du cône rencontrée par le rayon vertical passant par (c,0) (ou (c,-1) ).

Cône polaire de A

Cône convexe engendré par A

Page 35: Programmation linéaire, polarité et lancer de rayons (la programmation linéaire autrement) Yan Gerard LAIC (Université d’Auvergne) gerard@laic.u-clermont1.fr

On cherche maintenant une solution du système d’inégalités A # x telle que le produit scalaire c.x soit maximal (c Є Rd ).

Solution optimale

La formulation duale du programme linéaire affirme que la solution est donnée par la face du cône rencontrée par le rayon vertical passant par (c,0) (ou (c,-1) ).

3.6 Solution optimale

Cône polaire de A

Cône convexe engendré par A

Page 36: Programmation linéaire, polarité et lancer de rayons (la programmation linéaire autrement) Yan Gerard LAIC (Université d’Auvergne) gerard@laic.u-clermont1.fr

3.7 Point de vue conique

La recherche de la solution optimale consiste à déterminer la face du cône convexe engendré par A qui est touchée par le rayon vertical passant par (c,0) .

C’est un problème de lancer de rayon sur un cône.

Si on s’intéresse à la solution optimale, en quoi consiste son calcul ?

Page 37: Programmation linéaire, polarité et lancer de rayons (la programmation linéaire autrement) Yan Gerard LAIC (Université d’Auvergne) gerard@laic.u-clermont1.fr

3.7 Point de vue sphérique

Si on assimile géométrie conique et sphérique…

La programmation linéaire consiste à déterminer la face de l’enveloppe convexe (sphérique) de A’ touchée par le rayon dans la direction c.

C’est un problème de lancer de rayon dans la sphère.

Page 38: Programmation linéaire, polarité et lancer de rayons (la programmation linéaire autrement) Yan Gerard LAIC (Université d’Auvergne) gerard@laic.u-clermont1.fr

3.8 Conclusion

Géométriquement, la programmation linéaire est un problème de lancer de rayon sur un cône convexe engendré par un ensemble de points ou de façon équivalente, un problème de lancer de rayon sur l’enveloppe convexe (sphérique) d’un ensemble de points de la sphère.

Quelle relation entre le problème de lancer de rayon dans la sphère Sd

et le problème posé dans Rd.

La programmation linéaire est un problème de lancer de rayon posé dans la sphère Sd (de Rd+1 ).

nouvelle question

Page 39: Programmation linéaire, polarité et lancer de rayons (la programmation linéaire autrement) Yan Gerard LAIC (Université d’Auvergne) gerard@laic.u-clermont1.fr

B) Lancer de Rayon

4 Problèmes de Lancer de Rayon

5 Algorithmes de Lancer de Rayon

Page 40: Programmation linéaire, polarité et lancer de rayons (la programmation linéaire autrement) Yan Gerard LAIC (Université d’Auvergne) gerard@laic.u-clermont1.fr

4 Problèmes de Lancer de Rayon

4.1 Lancer de Rayon dans Sd

Données : - Une partie finie A de la sphère Sd - Un demi-cercle C vertical allant de False à True.

Questions : Le point False est-il dans l’enveloppe convexe de A ?Sinon, trouver la face de l’enveloppe convexe de A rencontrée par C.

Page 41: Programmation linéaire, polarité et lancer de rayons (la programmation linéaire autrement) Yan Gerard LAIC (Université d’Auvergne) gerard@laic.u-clermont1.fr

4 Problèmes de Lancer de Rayon

4.2 Lancer de Rayon dans Rd

Données : - Une partie finie A de l’espace affine Rd - Une droite orientée D.

Question : Trouver la face de l’enveloppe convexe de A rencontrée par D.

Page 42: Programmation linéaire, polarité et lancer de rayons (la programmation linéaire autrement) Yan Gerard LAIC (Université d’Auvergne) gerard@laic.u-clermont1.fr

Quelle relation entre le problème de lancer de rayon dans la sphère Sd

et le problème posé dans Rd ?

Et l’inverse ?

4.3 De l’espace Rd à la sphère Sd

Le problème dans Rd se projette facilement dans Sd .

Page 43: Programmation linéaire, polarité et lancer de rayons (la programmation linéaire autrement) Yan Gerard LAIC (Université d’Auvergne) gerard@laic.u-clermont1.fr

Il faut avoir un plan de projection sur lequel se projettent tous les points de la partie de la sphère.

Et l’inverse ?

4.4 De la sphère Sd à l’espace Rd ?

Page 44: Programmation linéaire, polarité et lancer de rayons (la programmation linéaire autrement) Yan Gerard LAIC (Université d’Auvergne) gerard@laic.u-clermont1.fr

Il faut avoir un plan de projection sur lequel se projettent tous les points de la partie de la sphère.

4.4 De la sphère Sd à l’espace Rd ?

autrement dit un plan qui sépare l’origine de l’ensemble A.

Pour trouver un tel plan on peut faire un lancer de rayon sur l’ensemble A en tant que partie de Rd+1 (un rayon partant de l’origine et dirigé par exemple vers le barycentre de A).

Page 45: Programmation linéaire, polarité et lancer de rayons (la programmation linéaire autrement) Yan Gerard LAIC (Université d’Auvergne) gerard@laic.u-clermont1.fr

4.5 Synthèse

Lancer de rayon dans Sd

Lancer de rayon dans Rd

Lancer de rayon dans Rd+1

Réduction

Réduction

Page 46: Programmation linéaire, polarité et lancer de rayons (la programmation linéaire autrement) Yan Gerard LAIC (Université d’Auvergne) gerard@laic.u-clermont1.fr

5 Algorithmes de Lancer de Rayon

4 algorithmes de Lancer de Rayon dans Rd

- Simplex

- QuickFace

- SpherePush

- Megiddo (d=2)

Page 47: Programmation linéaire, polarité et lancer de rayons (la programmation linéaire autrement) Yan Gerard LAIC (Université d’Auvergne) gerard@laic.u-clermont1.fr

Données : une partie finie A de Rd et une droite orientée D

Résultat : le premier simplex à sommets dans A rencontré par D

Page 48: Programmation linéaire, polarité et lancer de rayons (la programmation linéaire autrement) Yan Gerard LAIC (Université d’Auvergne) gerard@laic.u-clermont1.fr

5.1 Simplex

Initialisation une (d-1)-face de l’enveloppe convexe de ARoutine Pivot autour d’une (d-2)-arête (Gift-Wrapping)

Page 49: Programmation linéaire, polarité et lancer de rayons (la programmation linéaire autrement) Yan Gerard LAIC (Université d’Auvergne) gerard@laic.u-clermont1.fr

5.2 QuickFace

Initialisation un (d-1)-simplex de A qui coupe DRoutine

calcul de la normale au (d-1)-simplex orienté vers D

calcul du point extrémal dans cette direction

calcul de la face entrante du d-simplex

Page 50: Programmation linéaire, polarité et lancer de rayons (la programmation linéaire autrement) Yan Gerard LAIC (Université d’Auvergne) gerard@laic.u-clermont1.fr

5.2 QuickFace

Quelques résultats expérimentaux (Stage recherche M1 –Christian Franco)

Caractéristiques du problème (LP)

QuickFace C-plex (points intérieurs)

2400 contraintes 100 variables 2.5 s15 s

2400 contraintes 200 variables 8.5 s156 s

2400 contraintes 300 variables 17 s702 s

2400 contraintes 400 variables 28,2 s1880 s

Sensibilité exponentielle à la dimension ?

Page 51: Programmation linéaire, polarité et lancer de rayons (la programmation linéaire autrement) Yan Gerard LAIC (Université d’Auvergne) gerard@laic.u-clermont1.fr

5.3 Megiddo (2D)

Étape 1 On apparie les points de A (de façon quelconque)

Page 52: Programmation linéaire, polarité et lancer de rayons (la programmation linéaire autrement) Yan Gerard LAIC (Université d’Auvergne) gerard@laic.u-clermont1.fr

5.3 Megiddo (2D)

Étape 2 On reporte les cordesÉtape 3 On détermine une direction médiane (temps linéaire)

On distingue 4 types de sommets (gauche et droite)

On distingue 2 types de cordes

Page 53: Programmation linéaire, polarité et lancer de rayons (la programmation linéaire autrement) Yan Gerard LAIC (Université d’Auvergne) gerard@laic.u-clermont1.fr

5.3 Megiddo (2D)

Étape 3 De quel côté de D se trouve le point extrémal dans la direction médiane ?

L’arête optimale (recherchée) ne peut pas

être dans le domaine grisé

La direction de l’arête optimale étant dans le domaine rose, elle ne peut avoir un sommet

vert

Page 54: Programmation linéaire, polarité et lancer de rayons (la programmation linéaire autrement) Yan Gerard LAIC (Université d’Auvergne) gerard@laic.u-clermont1.fr

Étape 4 On élimine les points verts (un quart des points) et on recommence

5.3 Megiddo (2D)

(temps linéaire)…….

Page 55: Programmation linéaire, polarité et lancer de rayons (la programmation linéaire autrement) Yan Gerard LAIC (Université d’Auvergne) gerard@laic.u-clermont1.fr

5.3 Megiddo (2D)

L’algorithme de Megiddo est basé sur un appariement des points.

Intérêt à faire des groupes de plus points ?

(comme dans l’algorithme d’enveloppe convexe de Chan)

Page 56: Programmation linéaire, polarité et lancer de rayons (la programmation linéaire autrement) Yan Gerard LAIC (Université d’Auvergne) gerard@laic.u-clermont1.fr

5.4 Sphere Push

Initialisation une sphère contenant ARoutine On exerce une pression selon la droite D

5.4 SpherePush

Page 57: Programmation linéaire, polarité et lancer de rayons (la programmation linéaire autrement) Yan Gerard LAIC (Université d’Auvergne) gerard@laic.u-clermont1.fr

5.4 SpherePush

A chaque étape, SpherePush fournit un hyperplan extérieur à l’ensemble A qu’on pousse progressivement le long de D.

Par dualité et en termes de programmation linéaire, SpherePush est donc un algorithme de points intérieurs.

Peut-on comprendre par ce biais les algorithmes classiques de points intérieurs ?

Page 58: Programmation linéaire, polarité et lancer de rayons (la programmation linéaire autrement) Yan Gerard LAIC (Université d’Auvergne) gerard@laic.u-clermont1.fr

5.5 Conclusion

Lancer de Rayon dans Sd

Lancer de Rayon dans Rd

Lancer de Rayon dans Rd+1

Réduction

Réduction

Les algorithmes de Programmation Linéaire peuvent s’interpréter géométriquement comme des algorithmes de Lancer de Rayon.

Inversement, les algorithmes de Lancer de Rayon permettent de résoudre géométriquement des programmes linéaires.

Devenir un escroc de la programmation linéaire, c’est facile…

Page 59: Programmation linéaire, polarité et lancer de rayons (la programmation linéaire autrement) Yan Gerard LAIC (Université d’Auvergne) gerard@laic.u-clermont1.fr

Merci de votre attention…