NMath User's Guide

28.3 Quadratic Programming (.NET, C#, CSharp, Visual Basic, VB.NET)

A quadratic programming (QP) problem is a NLP problem with a specific form for the objective and constraint functions. A QP problem has the following form:

subject to

where H is a symmetric nxn matrix, E and I are finite sets of indices, and c, x, and ai are vectors in Rn. The matrix H is the Hessian of the objective function q(x).

NOTE- Only convex QP problems are supported. A QP problem is convex if the matrix H in the objective function is positive definite.

Encapsulating the Problem

In NMath, class QuadraticProgrammingProblem class encapsulates a QP problem. The objective function is specified by providing the matrix H and the vector c. The matrix H, usually referred to as the Hessian, is the quadratic coefficient matrix. The vector c, sometimes referred to as the gradient, contains the coefficients for the linear terms.

For example, to minimize

q(x) = (x0 - 1)^2 + (x1 - 2.5)^2

Translate the objective function into the form 0.5*x'Hx + x'c. In this case:

H = | 2 0 |
    | 0 2 |

c = [-2 -5]   

This code sets up the QP problem:

DoubleMatrix H = new DoubleMatrix( "2x2[2 0  0 2]" );
DoubleVector c = new DoubleVector( -2.0, -5.0 );
QuadraticProgrammingProblem problem =
  new QuadraticProgrammingProblem( H, c );

Adding Bounds and Constraints

The constraints in a QP problem must be linear. There are several convenience methods provided for adding constraints and variable bounds.

For instance, given constraints:

-x0 + 2*x1 <= 2

 x0 - 2*x1 >= -6
-x0 + 2*x1 >= -2

 x0 >= 0
 x1 >= 0

The following code adds these constraints to an existing QuadraticProgrammingProblem object:

problem.AddUpperBoundConstraint(
  new DoubleVector( -1.0, 2.0 ), 2.0 );

problem.AddLowerBoundConstraint(
  new DoubleVector( 1.0, -2.0 ), -6.0 );
problem.AddLowerBoundConstraint(
  new DoubleVector( -1.0, 2.0 ), -2.0 );

problem.AddVariableLowerBound( 0, 0 );
problem.AddVariableLowerBound( 1, 0 );

Solving the Problem

Class ActiveSetQPSolver solves QP problems using an active set algorithm.

ActiveSetQPSolver solver = new ActiveSetQPSolver();

The Solve() method solves the problem, and returns true if the algorithm terminated successfully:

if ( !solver.Solve( problem ) ) {
  Console.WriteLine( "Solver failed: {0}", solver.Status );
}
else {
  Console.WriteLine("Solver found solution (x0, x1) = ({0}, {1})", 
        solver.OptimalX[0], solver.OptimalX[1] );
  Console.WriteLine("After {0} iterations", solver.Iterations );
  Console.WriteLine( "Optimal objective function value = {0}", 
    solver.OptimalObjectiveFunctionValue );
}

The Solve() method also optionally accepts a starting point for the solution search. The starting point need not be a feasible point.

TOC |  Previous |  Next |  Index