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 optimisationVoir 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. (voir l'article Borne d'erreur).
Énoncé du lemme
On considère un polyèdre convexe de , écrit sous la forme suivante
où 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 .
Le lemme de Hoffman permet donc d'estimer la distance de à par la norme du résidu .
Discussion
La constante n'est pas une constante universelle : elle peut être arbitrairement grande. Ainsi, si pour , on définitalors lorsque . La meilleure constante est étudiée par Azé et Corvellec (2002).
Annexes
Autres contributions
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. A. D. Ioffe (1979). Regular points of Lipschitz functions. Translations of the American Mathematical Society, 251, 61–69. 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.
Note
Article connexe
Borne d'erreur : fait le point sur les généralisations du lemme de Hoffman à des ensembles plus complexes qu'un polyèdre convexe
Bibliographie
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. O. Güler (2010). Foundations of Optimization, Graduate Texts in Mathematics 258, Springer, doi. A. J. Hoffman (1952). On approximate solutions of systems of linear inequalities, Journal of Research of the National Bureau of Standard 49, 263-265.
Catégorie:Analyse convexe