Recouvrement par jauge

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

Le recouvrement par jauge[1] est une technique d'optimisation mathématique, structurellement et intentionnellement semblable à la poursuite de base, qui étend cette dernière sur deux points :

Cette généralisation permet d'appliquer cette technique de recouvrement de données codées, dans des contextes plus variés. Par exemple, on pourra s'intéresser au recouvrement d'objets représentés par des matrices et utiliser la norme nucléaire comme critère de sélection.

Nous renvoyons aux articles « Poursuite de base » et « Acquisition comprimée » pour des indications sur les problématiques pratiques conduisant à des problèmes de ce type. Voir aussi Chandrasekaran et al. 2012.

Connaissances supposées : le vocabulaire de l'optimisation mathématique et de l'algèbre linéaire.

Notations[modifier | modifier le code]

  • Dans cet article, on supposera toujours que et sont deux espaces euclidiens, dont les produits scalaires sont tous deux notés .
  • L'image d'une application linéaire est notée et son noyau est noté .
  • L'opérateur adjoint d'un opérateur linéaire est noté .
  • L'enveloppe affine d'un convexe non vide de est notée et son intérieur relatif est noté .
  • Le polaire d'une partie de est noté .

Recouvrement par jauge polyédrique abstraite[modifier | modifier le code]

Définition du problème[modifier | modifier le code]

De manière plus précise, le problème s'écrit comme suit

où l'inconnue est un vecteur de , est une jauge polyédrique (c'est-à-dire dont l'épigraphe est un polyèdre convexe) pouvant donc prendre des valeurs infinies, est une application linéaire de dans et .

On note

l'ensemble de sous-niveau 1 de la jauge , qui joue le rôle de boule-unité (c'est ce qu'il serait si le jauge était une norme). Comme est une jauge polyédrique, est un polyèdre convexe contenant . Il revient au même de se donner et d'en déduire comme ci-dessus, ou de se donner un polyèdre convexe contenant et d'en déduire la jauge polyédrique par la formule de Minkowski :

C'est ce qui sera fait dans la section suivante, avec une description plus précise de .

Le sous-différentiel de la jauge en joue un rôle important dans les conditions d'existence et d'unicité de solution. Il est noté et sa valeur est donnée par la formule

Contraintes polyédriques[modifier | modifier le code]

Le modèle de problème peut prendre en compte des contraintes polyédriques, c'est-à-dire un problème de la forme

est la jauge d'un polyèdre convexe contenant , et est un autre polyèdre convexe de . Le polyèdre convexe peut toujours être écrit comme suit

est une application linéaire, et l'inégalité agit composante par composante. Donc le problème s'écrit

Ce dernier problème peut s'écrire sous la forme d'un problème de recouvrement par jauge sous la forme standard , à savoir

en prenant pour la jauge du polyèdre convexe contenant suivant :

désigne le -ème vecteur de la base canonique de . L'équivalence entre ces problèmes repose sur le fait que si , et si .

Existence de solution[modifier | modifier le code]

On notera que n'est pas nécessairement coercive et peut prendre la valeur . C'est en réalité sa polyédricité qui permet d'obtenir la condition nécessaire et suffisante de solution de la proposition suivante, comme en optimisation linéaire.

Existence de solution I — Soit une jauge polyédrique. Alors l'ensemble des solutions de est un polyèdre convexe ; celui-ci est non vide si, et seulement si, est dans l'image de .

Ce résultat ne dit rien sur la valeur optimale de et celle-ci peut très bien valoir alors que le problème a une solution. Il en sera ainsi si, et seulement si, est dans l'image de (ce qui assure l'existence d'une solution par la proposition) et l'ensemble admissible ne rencontre pas le domaine de . Une telle situation (sans intérêt) ne se rencontre pas en optimisation linéaire, car le critère ne prend alors que des valeurs finies.

Des conditions nécessaires et suffisantes assurant l'existence et l'unicité de la solution de sont moins aisées à déterminer. On notera que celles présentées ci-dessous[2] dépendent du point considéré comme candidat-solution ; elles s'apparentent donc à des conditions d'optimalité d'un point donné : la première condition, celle caractérisant comme solution, traduit d'ailleurs l'appartenance de zéro au sous-différentiel de en ( est l'indicatrice de l'ensemble admissible ) et le vecteur apparaissant dans toutes les conditions est une solution du problème dual (voir la section « Dualité lagrangienne »).

Dans le résultat ci-dessous, on note l'ensemble des solutions du problème .

Existence de solution II — Soient une jauge polyédrique dont le domaine intersecte et . Alors

Existence et unicité de solution[modifier | modifier le code]

Existence et unicité de solution — Soient une jauge polyédrique dont le domaine intersecte et . Alors si, et seulement si,

Dualité lagrangienne[modifier | modifier le code]

Le problème dual lagrangien de s'écrit comme le problème en suivant :

Pas de saut de dualité — Si est une jauge polyédrique, alors (qui peut valoir ).

Recouvrement par jauge polyédrique sous description primale[modifier | modifier le code]

Cette section donne les détails du problème de recouvrement par jauge polyédrique lorsque celle-ci est vue comme jauge d'un polyèdre convexe , lequel est décrit comme une enveloppe convexe de points plus une enveloppe conique de directions (description primale ou interne d'un polyèdre convexe).

Définition du problème[modifier | modifier le code]

Le problème considéré s'écrit comme dans le cas abstrait, à savoir

mais la jauge polyédrique est définie comme jauge d'un polyèdre convexe par la formule

Le polyèdre convexe est décrit comme suit :

où les points sont dans et en nombre fini ( est fini) et les directions sont dans et en nombre fini ( est fini). Tout polyèdre convexe peut s'écrire de cette manière. On doit supposer que

pour que la jauge associée s'annule en l'origine. Mais on ne suppose pas que est intérieur à , si bien que peut prendre la valeur . Comme est fermé, la jauge est « fermée », c'est-à-dire semi-continue inférieurement.

Soient et . Il est utile d'introduire les applications linéaires

On adopte la notation matricielle pour l'application linéaire

et l'on note . Avec ces notations, l'ensemble s'écrit aussi

est le simplexe unité de .

Grâce à la condition , on a l'équivalence

Le polaire de l'ensemble introduit ci-dessus s'écrit

Alors le sous-différentiel de la jauge en est donné par la formule

Existence de solution[modifier | modifier le code]

Le résultat d'existence de solution II du cas abstrait devient le suivant.

Existence de solution II — Soient une jauge polyédrique sous description primale dont le domaine intersecte et . Alors

  • si, et seulement si, les deux conditions suivantes ont lieu
    1. ,
    2. il existe tel que pour tout on a si , si , si et si ,
  • si, et seulement si, les deux conditions suivantes ont lieu
    1. ,
    2. il existe tel que pour tout on a si , si , si et si .

Les coefficients et permettant de représenter par dans ce résultat sont en réalité les multiplicateurs de Lagrange associés aux contraintes du problème d'optimisation linéaire définissant . Au second point, ces coefficients et sont des multiplicateurs optimaux satisfaisant en plus la stricte complémentarité.

Existence et unicité de solution[modifier | modifier le code]

Le résultat d'existence et d'unicité de solution du cas abstrait devient le suivant.

Existence et unicité de solution — Soient une jauge polyédrique sous description primale dont le domaine intersecte et . Alors les conditions suivantes sont équivalentes :

  1. est l'unique solution de  ;
  2. on peut trouver des ensembles d'indices et tels que :
    • , pour des et ,
    • il existe tel que si , si , si et si ,
    • quels que soient ces ensembles d'indices et vérifiant ces deux premières conditions, on a  ;
  3. on peut trouver des ensembles d'indices et tels que :
    • , pour des et ,
    • il existe tel que si , si , si et si ,
    • .

La seconde condition semble plus forte que la troisième, mais ce résultat montre qu'il n'en est rien. Cette seconde condition est utilisée par l'algorithme de détection d'unicité présenté plus loin. Cet algorithme détermine d'abord des ensembles d'indices et satisfaisant les deux premiers points de la condition 2 et détermine ensuite si l'unicité a lieu en vérifiant si .

Méthode de résolution[modifier | modifier le code]

La méthode de résolution du problème de recouvrement par jauge sous forme primale décrite dans cette section transforme ce problème en le problème d'optimisation linéaire suivant

où les opérateurs linéaire et ont été définis ci-dessus et est le simplexe unité de . En quelques mots, dans le problème , l'ensemble de sous-niveau un de est mis à l'échelle de manière à ce que sa frontière vienne en contact avec le sous-espace affine (par l'homogénéité positive de cela revient à trouver son bon ensemble de sous-niveau), tandis que dans , le même sous-espace affine est translaté de manière à ce qu'il vienne en contact avec la frontière de . Le sens de cette équivalence entre et est précisé dans le résultat suivant.

Équivalence entre et  — Soit une jauge polyédrique sous description primale. Alors, on peut trouver un couple tel que . De plus

  • pour un ,
  • ,
  • si , alors  ; de plus,
    • si est une solution de , alors est une solution de ,
    • inversement, si est une solution de , alors pour un couple et, pour toute expression de de cette forme, est solution de .

Le fait que le problème soit équivalent au problème d'optimisation linéaire rend possible la résolution de en temps polynomial, par exemple en utilisant un algorithme de points intérieurs.

Le dual lagrangien de s'écrit

Il n'y a pas de saut de dualité :

.

Détection de l'unicité[modifier | modifier le code]

Le résultat d'existence et unicité de solution ci-dessus permet de mettre au point un algorithme détectant l'unicité de solution du problème .

Détection de l'unicité — 

  1. On résout le problème d'optimisation linéaire par un solveur fournissant une solution strictement complémentaire (lorsqu'une solution existe : cas 3 et 4 ci-dessous).
  2. Si la valeur optimale , alors et
    • soit , auquel cas (la solution n'est pas unique),
    • ou , auquel cas (la solution est unique).
  3. Si la valeur optimale , alors (le problème est non borné).
  4. Sinon , auquel cas . Soit la solution primale-duale strictement complémentaire calculée par le solveur. Alors est une solution de et celle-ci est unique si, et seulement si,


    et .

Annexes[modifier | modifier le code]

Notes[modifier | modifier le code]

  1. Gauge recovery en anglais : voir par exemple Chandrasekaran et al. 2012 ou Gilbert 2016.
  2. Voir Gilbert 2016.

Bibliographie[modifier | modifier le code]

  • (en) V. Chandrasekaran, B. Recht, P. A. Parrilo et A. S. Willsky, « The convex geometry of linear inverse problems », Foundations of Computational Mathematics, vol. 12, no 6,‎ , p. 805-849 (DOI 10.1007/s10208-012-9135-7, arXiv 1012.0621)
  • (en) J. Ch. Gilbert, « On the solution uniqueness characterization in the L1 norm and polyhedral gauge recovery », Journal of Optimization Theory and Applications, vol. 1, no 1,‎ , p. 1-32 (DOI 10.1007/s10957-016-1004-0, lire en ligne)