Recouvrement par jauge

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

• l'espace sous-jacent est un espace euclidien général (au lieu de l'espace vectoriel ${ℝ}^n$),
• le critère de sélection est une jauge polyédrique définie sur cet espace (au lieu de la [[Norme (mathématiques)#Exemples|norme ℓModèle:1]]).

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 Modèle:Harvsp.

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

Notations

• Dans cet article, on supposera toujours que $E$ et $F$ sont deux espaces euclidiens, dont les produits scalaires sont tous deux notés $⟨\cdot ,\cdot ⟩$.
• L'image d'une application linéaire $A$ est notée $\mathrm{Im}(A)$ et son noyau est noté $\mathrm{Ker}(A)$.
• L'opérateur adjoint d'un opérateur linéaire $A:E\to F$ est noté $A^{*}:F\to E$.
• L'enveloppe affine d'un convexe non vide $C$ de $E$ est notée $\mathrm{aff}C$ et son intérieur relatif est noté $\mathrm{ir}C$.
• Le polaire d'une partie $P$ de $E$ est noté $P^{\circ }$.

Recouvrement par jauge polyédrique abstraite

Définition du problème

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

$(P_f)\{\begin{array}{c}\inf f(x)\\ Ax=b,\end{array}$

où l'inconnue est un vecteur $x$ de $E$, $f:E\to ℝ\cup \{+\mathrm{\infty }\}$ est une jauge polyédrique (c'est-à-dire dont l'épigraphe est un polyèdre convexe) pouvant donc prendre des valeurs infinies, $A$ est une application linéaire de $E$ dans $F$ et $b\in F$.

On note

$ℬ:=\{x\in E\mid f(x)⩽1\},$

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

$\mathrm{\forall }x\in Ef(x)=\inf \{t>0\mid x\in tℬ\}.$

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

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

$𝒮(x):={\mathrm{argmax}}_{y\in {ℬ}^{\circ }}⟨y,x⟩.$

Contraintes polyédriques

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

$\{\begin{array}{c}\inf f_0(x)\\ x\in P,\end{array}$

où $f_0:E\to ℝ\cup \{+\mathrm{\infty }\}$ est la jauge d'un polyèdre convexe ${ℬ}_0\subset E$ contenant $0$, et $P$ est un autre polyèdre convexe de $E$. Le polyèdre convexe $P$ peut toujours être écrit comme suit

$P=\{x\in E\mid Ax⩽b\},$

où $A:E\to {ℝ}^m$ est une application linéaire, $b\in {ℝ}^m$ et l'inégalité agit composante par composante. Donc le problème s'écrit

$\{\begin{array}{c}\underset{(x,s)\in E\times {ℝ}^m}{\inf }{f}_0(x)\\ Ax+s=b\\ s⩾0.\end{array}$

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

$\{\begin{array}{c}\underset{(x,s)\in E\times {ℝ}^m}{\inf }f(x,s)\\ Ax+s=b,\end{array}$

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

${ℬ}_0\times \mathrm{cone}\{e_1,\dots ,e_m\}={ℬ}_0\times {ℝ}_{+}^m\subset E\times {ℝ}^m,$

où $e_i$ désigne le $i$-ème vecteur de la base canonique de ${ℝ}^m$. L'équivalence entre ces problèmes repose sur le fait que $f(x,s)=f_0(x)$ si $s⩾0$, et $f(x,s)=+\mathrm{\infty }$ si $s⩾̸0$. 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.

Ce résultat ne dit rien sur la valeur optimale de $(P_f)$ et celle-ci peut très bien valoir $+\mathrm{\infty }$ alors que le problème a une solution. Il en sera ainsi si, et seulement si, $b$ est dans l'image de $A$ (ce qui assure l'existence d'une solution par la proposition) et l'ensemble admissible ne rencontre pas le domaine de $f$. 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 $(P_f)$ sont moins aisées à déterminer. On notera que celles présentées ci-dessous dépendent du point $\overline{x}$ considéré comme candidat-solution ; elles s'apparentent donc à des conditions d'optimalité d'un point $\overline{x}\in {ℝ}^n$ donné : la première condition, celle caractérisant $\overline{x}$ comme solution, traduit d'ailleurs l'appartenance de zéro au sous-différentiel de $f+{ℐ}_{𝒳}$ en $\overline{x}$ (${ℐ}_{𝒳}$ est l'indicatrice de l'ensemble admissible $𝒳$) et le vecteur $\overline{y}$ 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 $\mathrm{Sol}(P_f)$ l'ensemble des solutions du problème $(P_f)$.

Dualité lagrangienne

Le problème dual lagrangien de $(P_f)$ s'écrit comme le problème en $y\in F$ suivant :

$(D_f)\{\begin{array}{c}\underset{y}{\sup }⟨b,y⟩\\ A^{*}y\in {ℬ}^{\circ }.\end{array}$

Recouvrement par jauge polyédrique sous description primale

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

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

$(P_f)\{\begin{array}{c}\inf f(x)\\ Ax=b,\end{array}$

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

$\mathrm{\forall }x\in Ef(x)=\inf \{t>0\mid x\in tℬ\}.$

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

$ℬ=\mathrm{co}\{c_i\mid i\in I\}+\mathrm{cone}\{d_j\mid j\in J\},$

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

$0\in ℬ$

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

Soient $I_0\subset I$ et $J_0\subset J$. Il est utile d'introduire les applications linéaires

$\begin{array}{c}{C}_{I_0}:{\alpha }_{I_0}\in {ℝ}^{|I_0|}\mapsto C_{I_0}{\alpha }_{I_0}:=\sum _{i\in I_0}{\alpha }_i{c}_i\in E,C:=C_I,\\ D_{J_0}:\beta \in {ℝ}^{|J_0|}\mapsto D_{J_0}\beta :=\sum _{j\in J_0}{\beta }_j{d}_j\in E,D:=D_I.\end{array}$

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

$(C_{I_0}{D}_{J_0}):({\alpha }_{I_0},{\beta }_{J_0})\in {ℝ}^{|I_0|}\times {ℝ}^{|J_0|}\mapsto (C_{I_0}{D}_{J_0})({\alpha }_{I_0},{\beta }_{J_0})=C_{I_0}{\alpha }_{I_0}+D_{J_0}{\beta }_{J_0}\in E$

et l'on note $(CD):=(C_I{D}_J)$. Avec ces notations, l'ensemble $ℬ$ s'écrit aussi

$ℬ=\{C\alpha +D\beta \mid \alpha \in {\mathrm{\Delta }}_I,\beta \in {ℝ}_{+}^{|J|}\},$

où ${\mathrm{\Delta }}_I:=\{\alpha \in {ℝ}_{+}^{|I|}\mid {\sum }_{i\in I}{\alpha }_i=1\}$ est le simplexe unité de ${ℝ}^{|I|}$.

Grâce à la condition $0\in ℬ$, on a l'équivalence

$f(x)=0⟺x=D\beta \text{pour un}\beta ⩾0(\text{ou}x=0\text{si}J=\varnothing ).$

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

${ℬ}^{\circ }=\{x^{*}\in E\mid \mathrm{\forall }i\in I⟨x^{*},c_i⟩⩽1\text{ et }\mathrm{\forall }j\in J⟨x^{*},d_j⟩⩽0\}.$

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

$𝒮(x):=\underset{\begin{array}{c}{x}^{*}\text{ tel que}\\ \mathrm{\forall }i\in I⟨x^{*},c_i⟩⩽1\text{ et }\\ \mathrm{\forall }j\in J⟨x^{*},d_j⟩⩽0\end{array}}{\mathrm{argmax}}⟨x^{*},x⟩.$

Existence de solution

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

Les coefficients $\overline{\alpha }$ et $\overline{\beta }$ permettant de représenter $\overline{x}$ par $\overline{x}=C\overline{\alpha }+D\overline{\beta }$ 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 $𝒮(\overline{x})$. Au second point, ces coefficients $\overline{\alpha }$ et $\overline{\beta }$ sont des multiplicateurs optimaux satisfaisant en plus la stricte complémentarité.

Existence et unicité de solution

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

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 $I_{+}\subset I$ et $J_{+}\subset J$ satisfaisant les deux premiers points de la condition 2 et détermine ensuite si l'unicité a lieu en vérifiant si $\mathrm{Ker}(A)\cap \mathrm{Im}(C_{I_{+}}{D}_{J_{+}})=\{0\}$.

Méthode de résolution

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

$(P{\text{'}}_f)\{\begin{array}{c}\underset{(\alpha ,\beta ,t)\in {ℝ}^{|I|}\times {ℝ}^{|J|}\times ℝ}{\sup }t\\ A(C\alpha +D\beta )=tb\\ (\alpha ,\beta )\in {\mathrm{\Delta }}_I\times {ℝ}_{+}^{|J|},\end{array}$

où les opérateurs linéaire $C$ et $D$ ont été définis ci-dessus et ${\mathrm{\Delta }}_I$ est le simplexe unité de ${ℝ}^{|I|}$. En quelques mots, dans le problème $(P_f)$, l'ensemble de sous-niveau un $ℬ$ de $f$ est mis à l'échelle de manière que sa frontière vienne en contact avec le sous-espace affine $𝒳=\{x\in E\mid Ax=b\}$ (par l'homogénéité positive de $f$ cela revient à trouver son bon ensemble de sous-niveau), tandis que dans $(P{\text{'}}_f)$, 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 $(P_f)$ et $(P{\text{'}}_f)$ est précisé dans le résultat suivant.

Le fait que le problème $(P_f)$ soit équivalent au problème d'optimisation linéaire $({P_f}^{\prime })$ rend possible la résolution de $(P_f)$ en temps polynomial, par exemple en utilisant un algorithme de points intérieurs.

Le dual lagrangien de $({P_f}^{\prime })$ s'écrit

$({D_f}^{\prime })\{\begin{array}{c}\underset{(y,s)\in F\times ℝ}{\inf }s,\\ \mathrm{\forall }i\in I⟨A^{*}y,c_i⟩⩽s,\\ \mathrm{\forall }j\in J⟨A^{*}y,d_j⟩⩽0,\\ ⟨b,y⟩=1.\end{array}$

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

Détection de l'unicité

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 $(P_f)$.

Annexes

Bibliographie

• Modèle:Article
• Modèle:Article