Generic nondegeneracy in convex optimization

Authors:
Dmitriy Drusvyatskiy and Adrian S. Lewis

Journal:
Proc. Amer. Math. Soc. **139** (2011), 2519-2527

MSC (2010):
Primary 49J53, 32F32; Secondary 47H05

Published electronically:
December 21, 2010

MathSciNet review:
2784817

Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We show that minimizers of convex functions subject to almost all linear perturbations are nondegenerate. An analogous result holds more generally for *lower- * functions.

**1.**H.H. Bauschke, M.S. Macklem, and X. Wang,*Chebyshev sets, Klee sets, and Chebyshev centers with respect to Bregman distances: Recent results and open problems*, arXiv:1003.3127v1 [math.OC] (2010).**2.**J. Bolte, A. Daniilidis, and A.S. Lewis,*Generic optimality conditions for semi-algebraic convex programs*, submitted to Mathematics of Operations Research, 2009.**3.**Jonathan M. Borwein, Warren B. Moors, and Xianfu Wang,*Lipschitz functions with prescribed derivatives and subderivatives*, Nonlinear Anal.**29**(1997), no. 1, 53–63. MR**1447569**, 10.1016/S0362-546X(96)00050-8**4.**Frank H. Clarke,*Optimization and nonsmooth analysis*, Canadian Mathematical Society Series of Monographs and Advanced Texts, John Wiley & Sons, Inc., New York, 1983. A Wiley-Interscience Publication. MR**709590****5.**D. G. Larman,*On a conjecture of Klee and Martin for convex bodies*, Proc. London Math. Soc. (3)**23**(1971), 668–682. MR**0293498****6.**George J. Minty,*Monotone (nonlinear) operators in Hilbert space*, Duke Math. J.**29**(1962), 341–346. MR**0169064****7.**Gábor Pataki and Levent Tunçel,*On the generic properties of convex optimization problems in conic form*, Math. Program.**89**(2001), no. 3, Ser. A, 449–457. MR**1814549**, 10.1007/PL00011408**8.**R. A. Poliquin and R. T. Rockafellar,*Prox-regular functions in variational analysis*, Trans. Amer. Math. Soc.**348**(1996), no. 5, 1805–1838. MR**1333397**, 10.1090/S0002-9947-96-01544-9**9.**R. Tyrrell Rockafellar and Roger J.-B. Wets,*Variational analysis*, Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 317, Springer-Verlag, Berlin, 1998. MR**1491362****10.**C. A. Rogers,*Hausdorff measures*, Cambridge Mathematical Library, Cambridge University Press, Cambridge, 1998. Reprint of the 1970 original; With a foreword by K. J. Falconer. MR**1692618**

Retrieve articles in *Proceedings of the American Mathematical Society*
with MSC (2010):
49J53,
32F32,
47H05

Retrieve articles in all journals with MSC (2010): 49J53, 32F32, 47H05

Additional Information

**Dmitriy Drusvyatskiy**

Affiliation:
School of Operations Research and Information Engineering, Cornell University, Ithaca, New York 14853

Email:
dd379@cornell.edu

**Adrian S. Lewis**

Affiliation:
School of Operations Research and Information Engineering, Cornell University, Ithaca, New York 14853

DOI:
http://dx.doi.org/10.1090/S0002-9939-2010-10692-5

Keywords:
Convex functions,
normal cone,
subdifferential,
Hausdorff measure,
lower-$\mathbf{C}^{2}$ functions

Received by editor(s):
May 5, 2010

Received by editor(s) in revised form:
July 8, 2010

Published electronically:
December 21, 2010

Additional Notes:
The work of the first author was supported in part by the NDSEG grant from the Department of Defense.

The work of the second author was supported in part by National Science Foundation Grant DMS-0806057.

Communicated by:
Tatiana Toro

Article copyright:
© Copyright 2010
American Mathematical Society

The copyright for this article reverts to public domain 28 years after publication.