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 easily define quadratic objective functions and/or constraints, seamlessly integrate them with other constraints and solve the resulting problems using 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:
where \(Q_{i} \in \mathbb{R}^{n \times n}, i = 0, \ldots, p\) are symmetric matrices, \( r_{i} \in \mathbb{R}^{n}, i = 0, \ldots, p \) are vectors and \(s_i\) 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 \( \frac{1}{2} x^{T} F_{i}^{T} F_{i} x + r_{i}^{T} x + s_{i} \). The latter form is useful in many applications where the factors \(F_i\) appear naturally, such as in data fitting \( \| Fx – b \|_{2} \).
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 \( Q_{i}, i = 0, \ldots, 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.
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.