Recouvrement par jauge

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.

NotationsModifier

  • 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 abstraiteModifier

Définition du problèmeModifier

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édriquesModifier

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  . 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 solutionModifier

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

 

Dualité lagrangienneModifier

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 primaleModifier

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èmeModifier

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 solutionModifier

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 solutionModifier

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ésolutionModifier

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 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 à venir 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

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  .

AnnexesModifier

NotesModifier

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

BibliographieModifier

  • (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)