A hybrid approximation algorithm for convex multi-parametric quadratically constrained quadratic programs

Abstract

We present a solution method for convex multi-parametric quadratically constrained quadratic programs (mpQCQPs) with a single quadratic constraint. Past contributions have either approached these problems by treating the problem as a multi-parametric nonlinear program (mpNLP) and approximating the solution, or solving the mpQCQP exactly using symbolic computations. In this article, we develop a hybrid method that builds on these contributions and attempts to preserve nonlinearity in the solution where possible, while simultaneously avoiding the need for symbolic computations. We achieve this by computing the exact multi-parametric solution in all critical regions whose active set does not include the quadratic constraint. When the active set contains the quadratic constraint, we linearize the quadratic constraint and use the linearization to approximate the multi-parametric solution. By iteratively refining the linearization, our approach is able to approximate the solution up to a user-defined tolerance. Results indicate that our method is able to obtain high-quality solutions to instances whose exact solution is currently intractable.