2019/12/09 by M. Paul Laiu, Laiu, M. Paul, André L. Tits +1
Computer Science · Engineering · Mathematics · #Advanced Control Systems Optimization #Advanced Optimization Algorithms Research #FOS: Mathematics #Optimization and Control (math.OC) #Optimization and Variational Analysis
paper · pdf · doi:10.48550/arxiv.1912.04335
openalex publication_date 2019/12/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A framework is proposed for solving general convex quadratic programs (CQPs)\nfrom an infeasible starting point by invoking an existing feasible-start\nalgorithm tailored for inequality-constrained CQPs. The central tool is an\nexact penalty function scheme equipped with a penalty-parameter updating rule.\nThe feasible-start algorithm merely has to satisfy certain general\nrequirements, and so is the updating rule. Under mild assumptions, the\nframework is proved to converge on CQPs with both inequality and equality\nconstraints and, at a negligible additional cost per iteration, produces an\ninfeasibility certificate, together with a feasible point for an\n(approximately) \ℓ1-least relaxed feasible problem when the given problem\ndoes not have a feasible solution. The framework is applied to a feasible-start\nconstraint-reduced interior-point algorithm previously proved to be highly\nperformant on problems with many more constraints than variables\n("imbalanced"). Numerical comparison with popular codes (SDPT3, SeDuMi, MOSEK)\nis reported on both randomly generated problems and support-vector machine\nclassifier training problems. The results show that the former typically\noutperforms the latter on imbalanced problems.\n