Quadratic programming over ellipsoids with applications to constrained linear regression and tensor decomposition

摘要

A novel algorithm to solve the quadratic programming (QP) problem over ellipsoids is proposed. This is achieved by splitting the QP problem into two optimisation sub-problems, (1) quadratic programming over a sphere and (2) orthogonal projection. Next, an augmented-Lagrangian algorithm is developed for this multiple constraint optimisation. Benefitting from the fact that the QP over a single sphere can be solved in a closed form by solving a secular equation, we derive a tighter bound of the minimiser of the secular equation. We also propose to generate a new positive semidefinite matrix with a low condition number from the matrices in the quadratic constraint, which is shown to improve convergence of the proposed augmented-Lagrangian algorithm. Finally, applications of the quadratically constrained QP to bounded linear regression and tensor decomposition paradigms are presented.