Quadratic Programming
Mathwrist C++ API Series

Copyright ©Mathwrist LLC 2023
(January 20, 2023)
Abstract

This document details the C++ programming interface of quadratic programming (QP) features in Mathwrist’s Numerical Programming Library (NPL). Please refer to our quadratic programming white paper for technical overview.

1 Introduction

Quadratic programming (QP) solves the following minimization problem subject to linear constraints.

min𝐱∈ℝn⁡𝐜T⁢𝐱+12⁢𝐱T⁢𝐇𝐱, s.t. ⁢𝐛l≤𝐀𝐱≤𝐛u⁢ and ⁢𝐥≤𝐱≤𝐮 (1)

The objective function has a linear term with cost vector 𝐜 and a quadratic term with a Hessian matrix 𝐇. When 𝐇 is positive definite, the QP problem is called a convex QP problem. When 𝐇 is indefinite, it is called a general QP problem. Mathwrist NPL solves both type problems in the active set framework equipped with an inertia control strategy.

In the constraint part, 𝐛l≤𝐀𝐱≤𝐛u is referred as general linear constraints. 𝐥≤𝐱≤𝐮 is referred as simple bound constraints. The constraint specification is exactly same as linear programming, specifically represented by LinearProg::Constraints struct. Please refer to our LP API for constraint specification details.

QuadraticProg is the pure virtual base class for actual QP solvers. It defines a nested structure QuadraticProg::Objective to represent the objective function and provides a public solver operator function. QuadraticProg class is defined in header file “quadratic_prog.h”.

1.1 Constructor

1 protected:
2   QuadraticProg(const Matrix& G, const Matrix& d);

Description:

The constructor initializes the QP objective by taking constant references to the Hessian matrix from parameter G and cost vector from parameter d.

REQUIRED: G needs be a n×n symmetric matrix. d needs be a n×1 vector. Both these two matrix objects need be alive during the lifecycle of the QP solver.

1.2 Destructor

1 virtual ~QuadraticProg() {}

Description:

Virtual destructor to properly free resouces from derived classes.

1.3 QP Objective

1 const Objective& objective();

Description:

Return a constant reference to the object of objective funciton stored in QuadraticProg base class.

1.4 Solver Operator

1 virtual double operator() (Matrix& x) = 0;

Description:

It is the public interface of solving a QP problem, to be implemented by derived QP solvers. Parameter x holds the initial guess on call and holds the solution on return. REQUIRED: x is a n×1 vector.

2 QP Objective Definition

QP objective function is defined by a nested QuadraticProg::Objective struct, derived from FunctionND base class.

1 struct Objective : public FunctionND
2 {
3   const Matrix& G;   // Hessian matrix
4   const Matrix& d;   // Additional cost column vector
5   Objective(const Matrix& _G, const Matrix& _d);
6   ...
7 };

The constructor initializes data member Hessian matrix reference G from parameter _G and data member cost vector reference d from parameter _d.

REQUIRED: The Hessian and cost matrix objects need be kept alive during the lifecycle of the QP solver.

2.1 Virtual Functions from FunctionND

The following functions are virtual functions inherited from FunctionND base class and implemented by QP objective.

1 FunctionND* clone() const;
2 double eval(const Matrix& x, Matrix* _g=0, Matrix* _H=0) const;
3 size_t dimension_size() const;

Description:

  1. 1.

    Clone a new QP objective function referring the same Hessian matrix and cost vector.

  2. 2.

    Return the QP objective function value at a given point x. If parameter _g and parameter _H are not null, the gradient and Hessian of the objective function are saved to these parameters.

  3. 3.

    Return the number of unknown variables in the QP problem.

3 QP Active Set

1 class QP_ActiveSet : public QuadraticProg, public ActiveSet

QP_ActiveSet class in header file qp_active_set.h inherits from QuadraticProg base class as a concrete QP problem solver. It also inherits from ActiveSet class to reuse the active set framework implementation to solve QP problems. Please refer to the “Active Set” section in our LP API for public interface of ActiveSet, i.e. controls of iteration, convergence, feasibility, stationary, Lagrange multiplier etc.

3.1 Constructor

1 QP_ActiveSet(
2   const Matrix& G,
3   const Matrix& d,
4   const LinearProg::Constraints& c);

Description:

Create a QP solver object with a given Hessian matrix from parameter G, the linear cost vector from parameter d and a linear constraint specification from paramter c. Please refer to the constraint specification details in our LP API.

REQUIRED: The QP object takes references to Hessian and cost as data members. Therefore these two matrix objects need be kept alive during the lifecycle of the QP solver.

3.2 Destructor

1 ~QP_ActiveSet();

Description:

Free all resources used by the solver.

3.3 Solver Operator

1 double operator() (Matrix& x);

Description:

This function implements the public interface of the QuadraticProg base class. On call, parameter x holds the initial guess. On return it holds the solution found by the solver. REQUIRED: x is a n×1 vector.