On the stationarity for nonlinear optimization problems with polyhedral constraints
Open Access
- 22 May 2023
- journal article
- research article
- Published by Springer Nature in Mathematical Programming
- Vol. 205 (1-2) , 107-134
Abstract
For polyhedral constrained optimization problems and a feasible point $$\textbf{x}$$ , it is shown that the projection of the negative gradient on the tangent cone, denoted $$\nabla _\varOmega f(\textbf{x})$$ , has an orthogonal decomposition of the form $$\varvec{\beta }(\textbf{x}) + \varvec{\varphi }(\textbf{x})$$ . At a stationary point, $$\nabla _\varOmega f(\textbf{x}) = \textbf{0}$$ so $$\Vert \nabla _\varOmega f(\textbf{x})\Vert $$ reflects the distance to a stationary point. Away from a stationary point, $$\Vert \varvec{\beta }(\textbf{x})\Vert $$ and $$\Vert \varvec{\varphi }(\textbf{x})\Vert $$ measure different aspects of optimality since $$\varvec{\beta }(\textbf{x})$$ only vanishes when the KKT multipliers at $$\textbf{x}$$ have the correct sign, while $$\varvec{\varphi }(\textbf{x})$$ only vanishes when $$\textbf{x}$$ is a stationary point in the active manifold. As an application of the theory, an active set algorithm is developed for convex quadratic programs which adapts the flow of the algorithm based on a comparison between $$\Vert \varvec{\beta }(\textbf{x})\Vert $$ and $$\Vert \varvec{\varphi }(\textbf{x})\Vert $$ .
Keywords
Funding Information
- National Science Foundation (2031213)
- Office of Naval Research Global (N00014-22-1-2397)
This publication has 35 references indexed in Scilit:
- A scaled gradient projection method for constrained image deblurringInverse Problems, 2008
- New adaptive stepsize selections in gradient methodsJournal of Industrial and Management Optimization, 2008
- A New Active Set Algorithm for Box Constrained OptimizationSIAM Journal on Optimization, 2006
- On the convergence properties of the projected gradient method for convex optimizationComputational and Applied Mathematics, 2003
- Benchmarking optimization software with performance profilesMathematical Programming, 2002
- A new method for large-scale box constrained convex quadratic minimization problemsOptimization Methods and Software, 1995
- A new trust region algorithm for bound constrained minimizationApplied Mathematics & Optimization, 1994
- On the Maximization of a Concave Quadratic Function with Box ConstraintsSIAM Journal on Optimization, 1994
- On the Identification of Active Constraints II: The Nonconvex CaseSIAM Journal on Numerical Analysis, 1990
- Two-Point Step Size Gradient MethodsIMA Journal of Numerical Analysis, 1988