An infeasible-start framework for convex quadratic optimization, with application to constraint-reduced interior-point and other methods

• 成果类型: Article
• 署名作者: Laiu, M. Paul; Tits, Andre L.
• 署名单位: United States Department of Energy (DOE); Oak Ridge National Laboratory; University System of Maryland; University of Maryland College Park; University System of Maryland; University of Maryland College Park
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-021-01692-5
• 发表日期: 2022
• 页码: 327-366
• 关键词: exact penalty-function; feasible directions; dual algorithms; CONVERGENCE; reduction

摘要

A framework is proposed for solving general convex quadratic programs (CQPs) from an infeasible starting point by invoking an existing feasible-start algorithm tailored for inequality-constrained CQPs. The central tool is an exact penalty function scheme equipped with a penalty-parameter updating rule. The feasible-start algorithm merely has to satisfy certain general requirements, and so is the updating rule. Under mild assumptions, the framework is proved to converge on CQPs with both inequality and equality constraints and, at a negligible additional cost per iteration, produces an infeasibility certificate, together with a feasible point for an (approximately) l(1)-least relaxed feasible problem, when the given problem does not have a feasible solution. The framework is applied to a feasible-start constraint-reduced interior-point algorithm previously proved to be highly performant on problems with many more inequality constraints than variables (imbalanced). Numerical comparison with popular codes (OSQP, qpOASES, MOSEK) is reported on both randomly generated problems and support-vector machine classifier training problems. The results show that the former typically outperforms the latter on imbalanced problems. Finally, application of the proposed infeasible-start framework to other feasible-start algorithms is briefly considered, and is tested on a simplex iteration.