Solving quadratically constrained quadratic programming (QCQP) problems

Quadratic functions are a powerful modelling construct in mathematical programming and appear in various disciplines such as statistics, machine learning (Lasso regression), finance (portfolio optimization), engineering (OPF) and control theory. At Mark 27.1 of the NAG Library, NAG introduced two new additions to the NAG Optimization Modelling Suite to help users to easily define quadratic objective functions and/or constraints, seamlessly integrate them with other constraints and solve the resulting problems by compatible solvers without the need of a reformulation or any extra effort.

Formally, a QCQP problem can be written in its pure form with only quadratic functions in both objective and constraints as follows:

minimizex n1 2xTQ 0x + r0Tx + s 0 subject to 1 2xTQ ix + riTx + s i 0,i = 1,,p,

where Qi n×n,i = 0,,p, are symmetric matrices, ri n,i = 0,,p, are vectors and si scalars. However, in practice it will often be stated with linear constraints and simple bounds as well. The two new routines are handle_set_qconstr (e04rs) which defines quadratic functions in assembled form as above and handle_set_qconstr_fac (e04rt) which uses factored form 1 2xTF iTF ix + riTx + s i. The latter form is useful in many applications where the factors Fi appear naturally, such as in data fitting Fx - b2.

image The key question is if the problem is convex or non-convex as it determines if the problem can be solved via conic optimization (second-order cone programming, SOCP) or only by generic nonlinear programming (NLP). The problem is convex if all Qi,i = 0,,p, are positive semidefinite (the factored form is positive semidefinite by definition).

QCQP problems were solvable even without the new additions in this release but a nontrivial knowledge of reformulation techniques was required if an SOCP solver was to be used or callbacks covering the quadratic functions had to be introduced in the general case. To remove the unnecessary burden from practitioners, the new routines provide the quadratic data directly to the solvers with an appropriate automatic reformulation as is required by the chosen solver from the Suite.

  • For non-convex QCQP, NAG will use the input data to automatically assembly first and second derivatives that are used by the nonlinear programming solver (such as handle_solve_ipopt (e04st)).
  • Even though convex QCQP problems can also be solved via nonlinear programming, we generally recommend the second-order cone programming solver (handle_solve_socp_ipm (e04pt)) due to its computational efficiency and ability to detect infeasibility. In that case, NAG will take care of the reformulation of quadratic functions to cones, including the factorization of all Qi matrices in an efficient and numerically robust way. This is particularly helpful in the case of singular or close-to-singular matrices.

By maintaining the consistency of the interface of the solvers within the NAG Optimization Modelling Suite, e04rs and e04rt become part of the suite that simplifies building models and enhances NAG’s offering in mathematical optimization. For examples and further reading visit our GitHub Local optimisation page.