Identifying Active Constraints via Partial Smoothness and Prox-Regularity

W. L. Hare; A. S. Lewis

doi:10.68381/jca11017

Abstract

Active set algorithms, such as the projected gradient method in nonlinear optimization, are designed to "identify" the active constraints of the problem in a finite number of iterations. Using the notions of "partial smoothness" and "prox-regularity" we extend work of Burke, More and Wright on identifiable surfaces from the convex case to a general nonsmooth setting. We further show how this setting can be used in the study of sufficient conditions for local minimizers.

Author information

Contact details are reproduced from the original publication and may be historical.

W. L. Hare

Dept. of Mathematics, Simon Fraser University, Burnaby, BC V5A 1S6, Canada

whare@cecm.sfu.ca

A. S. Lewis

Dept. of Mathematics, Simon Fraser University, Burnaby, BC V5A 1S6, Canada

aslewis@sfu.ca

Keywords

nonlinear program
nonsmooth optimization
variational analysis
partly smooth
prox-regular
identifiable surface
projected gradient

Mathematics Subject Classification

91C30, 49K40, 65K10

References

J. V. Burke, J. J. Moré: On the identification of active constraints, SIAM J. Numer. Anal. 25 (1988) 1197–1211.https://doi.org/10.1137/0725068 Google Scholar
J. V. Burke: On the identification of active constraints II: The nonconvex case, SIAM J Numer. Anal. 25 (1990) 1081–1102.https://doi.org/10.1137/0727064 Google Scholar
S. Fitzpatrick, R. R. Phelps: Differentiability of the metric projection in Hilbert space, Trans. Am. Math. Soc. 270 (1982) 483–501.https://doi.org/10.1090/S0002-9947-1982-0645326-5 Google Scholar
R. B. Holmes: Smoothness of certain metric projections of Hilbert space, Trans. Amer. Math. Soc. 184 (1973) 87–100.https://doi.org/10.1090/S0002-9947-1973-0326252-2 Google Scholar
A. S. Lewis: Active sets, nonsmoothness and sensitivity, SIAM J. Optim. 13 (2003) 702–725.https://doi.org/10.1137/S1052623401387623 Google Scholar
R. A. Poliquin, R. T. Rockafellar: Prox-regular functions in variational analysis: Trans. Amer. Math. Soc. 384 (1996) 1805–1838.https://doi.org/10.1090/S0002-9947-96-01544-9 Google Scholar
R. A. Poliquin, R. T. Rockafellar, L. Thibault: Local differentiablity of distance functions, Trans. Amer. Math. Soc. 352 (2000) 5231–5249.https://doi.org/10.1090/S0002-9947-00-02550-2 Google Scholar
R. T. Rockafellar, R. J.-B. Wets: Variational Analysis, Springer, New York (1998).https://doi.org/10.1007/978-3-642-02431-3 Google Scholar
A. S. Shapiro: Existence and differentiability of metric projections in Hilbert spaces, SIAM J. Optim. 4 (1994) 130–141.https://doi.org/10.1137/0804006 Google Scholar
S. J. Wright: Identifiable surfaces in constrained optimization, SIAM J. Control Optimization 31 (1993) 1063–1079.https://doi.org/10.1137/0331048 Google Scholar

Suggested citation

Published by Heldermann Verlag, 2004. Rights now held by Banach Press LLC.

[1] J. V. Burke, J. J. Moré: On the identification of active constraints, SIAM J. Numer. Anal. 25 (1988) 1197–1211.https://doi.org/10.1137/0725068 Google Scholar

[2] J. V. Burke: On the identification of active constraints II: The nonconvex case, SIAM J Numer. Anal. 25 (1990) 1081–1102.https://doi.org/10.1137/0727064 Google Scholar

[3] S. Fitzpatrick, R. R. Phelps: Differentiability of the metric projection in Hilbert space, Trans. Am. Math. Soc. 270 (1982) 483–501.https://doi.org/10.1090/S0002-9947-1982-0645326-5 Google Scholar

[4] R. B. Holmes: Smoothness of certain metric projections of Hilbert space, Trans. Amer. Math. Soc. 184 (1973) 87–100.https://doi.org/10.1090/S0002-9947-1973-0326252-2 Google Scholar

[5] A. S. Lewis: Active sets, nonsmoothness and sensitivity, SIAM J. Optim. 13 (2003) 702–725.https://doi.org/10.1137/S1052623401387623 Google Scholar

[6] R. A. Poliquin, R. T. Rockafellar: Prox-regular functions in variational analysis: Trans. Amer. Math. Soc. 384 (1996) 1805–1838.https://doi.org/10.1090/S0002-9947-96-01544-9 Google Scholar

[7] R. A. Poliquin, R. T. Rockafellar, L. Thibault: Local differentiablity of distance functions, Trans. Amer. Math. Soc. 352 (2000) 5231–5249.https://doi.org/10.1090/S0002-9947-00-02550-2 Google Scholar

[8] R. T. Rockafellar, R. J.-B. Wets: Variational Analysis, Springer, New York (1998).https://doi.org/10.1007/978-3-642-02431-3 Google Scholar

[9] A. S. Shapiro: Existence and differentiability of metric projections in Hilbert spaces, SIAM J. Optim. 4 (1994) 130–141.https://doi.org/10.1137/0804006 Google Scholar

[10] S. J. Wright: Identifiable surfaces in constrained optimization, SIAM J. Control Optimization 31 (1993) 1063–1079.https://doi.org/10.1137/0331048 Google Scholar