Lemme de Hoffman

En mathématiques, et plus précisément en analyse convexe, le lemme de Hoffman est ce que l'on appelle une borne d'erreur, c'est-à-dire une estimation (ou majoration) de la distance à un ensemble (en l'occurrence, un polyèdre convexe) par des quantités aisément calculables, alors que la distance elle-même requiert la résolution d'un problème d'optimisation (quadratique convexe lorsque l'ensemble est un polyèdre convexe). Il s'agit d'une des premières bornes d'erreur non triviales.

Le résultat a été démontré par Alan J. Hoffman en 1952 et a conduit à de nombreux développements en optimisation[1] (voir l'article Borne d'erreur).

Énoncé du lemmeModifier

On considère un polyèdre convexe   de  , écrit sous la forme suivante

 

  est une matrice réelle et  . On note

 

l'ensemble des vecteurs   tels que  . Pour une norme   sur   (pas nécessairement la norme euclidienne), on note

 

la distance de   à  . Pour  , on note   le vecteur de   dont la composante   est  .

Lemme de Hoffman — Il existe une constante   (ne dépendant que de  , de   et d'une norme   sur  ) telle que

 

Le lemme de Hoffman permet donc d'estimer la distance de   à   par la norme du résidu  .

DiscussionModifier

  • La constante   n'est pas une constante universelle : elle peut être arbitrairement grande. Ainsi, si pour  , on définit
     
    alors   lorsque  .
  • La meilleure constante   est étudiée par Azé et Corvellec (2002).

AnnexesModifier

Autres contributionsModifier

  • (en) O. Güler, A. J. Hoffman, U. G. Rothblum (1995). Approximations to solutions to systems of linear inequalities. SIAM Journal on Matrix Analysis and Applications, 16, 688–696.
  • (en) A. D. Ioffe (1979). Regular points of Lipschitz functions. Translations of the American Mathematical Society, 251, 61–69.
  • (ru)(en) A. D. Ioffe (2000). Metric regularity and subdifferential calculus. Uspekhi Mat. Nauk, 55, 103–162. En russe, traduit dans Russian Mathematical Surveys, 55, 501-558.

NoteModifier

  1. Voir par exemple l'article de O. Guler, A. J. Hoffman, U. G. Rothblum (1995). Approximations to solutions to systems of linear inequalities. SIAM Journal on Matrix Analysis and Applications 16, 688-696.

Article connexeModifier

BibliographieModifier

  • (en) D. Azé, J.-N. Corvellec (2002). On the sensitivity analysis of Hoffman constants for systems of linear inequalities. SIAM Journal on Optimization, 12, 913–927.
  • (en) O. Güler (2010). Foundations of Optimization, Graduate Texts in Mathematics 258, Springer, doi.
  • (en) A. J. Hoffman (1952). On approximate solutions of systems of linear inequalities, Journal of Research of the National Bureau of Standard 49, 263-265.