SIAM Journal on Optimization · 2012 · 112 citations · 33 references
Natural SciencesComputer ScienceMathematicsAlgorithmsDesign OptimizationOptimizationConstrained OptimizationConstraint SatisfactionConvex OptimizationNonlinear ProgrammingOptimization TheoryQuadratic ProgrammingConstraint QualificationsConstraintsConvergenceGlobal Convergence AnalysisLagrangian OptimizationLocal StabilityNonlinear OptimizationSequential Quadratic Programming
RCPLD assumes that many subsets of active constraint gradients maintain local positive linear dependence, yet it was unclear which exact gradients must preserve this property to serve as a valid CQ. The authors aim to introduce two weaker constraint qualifications—CRSC and CPG—that can replace RCPLD in optimization analysis. They define the CRSC and CPG CQs and extend convergence results for major nonlinear optimization algorithm classes, including sequential quadratic programming, augmented Lagrangians, interior point methods, and inexact restoration. The CRSC CQ preserves RCPLD’s desirable properties, such as local stability and an error bound, while being weaker than RCPLD.
We present two new constraint qualifications (CQs) that are weaker than the recently introduced relaxed constant positive linear dependence (RCPLD) CQ. RCPLD is based on the assumption that many subsets of the gradients of the active constraints preserve positive linear dependence locally. A major open question was to identify the exact set of gradients whose properties had to be preserved locally and that would still work as a CQ. This is done in the first new CQ, which we call the constant rank of the subspace component (CRSC) CQ. This new CQ also preserves many of the good properties of RCPLD, such as local stability and the validity of an error bound. We also introduce an even weaker CQ, called the constant positive generator (CPG), which can replace RCPLD in the analysis of the global convergence of algorithms. We close this work by extending convergence results of algorithms belonging to all the main classes of nonlinear optimization methods: sequential quadratic programming, augmented Lagrangians, interior point algorithms, and inexact restoration.
33
Nonlinear programming: theory and algorithms
Computers & Operations Research · 1993 · 5.8K citations
Lagrange Multipliers and Optimality
R. T. Rockafellar · SIAM Review · 1993 · 583 citations
Error bounds in mathematical programming
Jong‐Shi Pang · Mathematical Programming · 1997 · 451 citations