Click or drag to resize

Quadratic Programming

This topic contains the following sections:

Quadratic Programming Problem Specification

General form of quadratic programming problem has the form:

QP Problem

where

  • QP H - symmetric matrix that represents the quadratic in the objective function.

  • QP f - linear objective function vector,

  • QP A - matrix for linear equality constraints,

  • QP b - vector for linear equality constraints,

  • QP C - matrix for linear inequality constraints,

  • QP d - vector for linear inequality constraints,

  • QP l - vector of lower bounds,

  • QP u - vector of upper bounds.

Implementation and Usage

The quadratic programming solver implements a variant of Mehrotra's predictor-corrector algorithm, a primal-dual interior-point method. A number of preprocessing steps occur before the algorithm begins to iterate. The quadratic programming solver is implemented by the QuadraticProgramming class. The constructor of this class has the following prototype:

The class implements the IConstrainedProgramming interface.

Constructor

Description

Performance

H, A and C - dense matrices

Creates new instance of QuadraticProgramming class.

methodQuadraticProgramming(Matrix, Vector, Matrix, Vector, Matrix, Vector, Vector, Vector)

H, A and C - sparse matrices

Creates new instance of QuadraticProgramming class.

methodQuadraticProgramming(SparseMatrix, Vector, SparseMatrix, Vector, SparseMatrix, Vector, Vector, Vector)

The class implements an event LogMessage that occurs every time the INumericalOptimization wants to send a log message, and the following methods:

Method

Description

Performance

minimum

Finds minimum of constrained multivariable function and returns true in case the optimization algorithm succeeded.

methodMinimize

minimum with initial point provided

Finds minimum of constrained multivariable function and returns true in case the optimization algorithm succeeded. The initial point for the algorithm is passed as a parameter.

methodMinimize(Vector)

Class provides the following properties:

Property

Description

Performance

iterations done

Number of iterations done.

PropertyIterationsDone

iterations limit

Maximum number of iterations allowed, a positive integer.

PropertyIterationsLimit

minimum point

Minimum point of objective function.

PropertyMinimumPoint

minimum value

Minimum value of objective function.

PropertyMinimumValue

status

Status of algorithm termination.

PropertyStatus

tolerance

Algorithm termination tolerance, a positive scalar.

PropertyTolerance

Note Note

Usually the default tolerance settings provide good convergence so there is no need to adjust them.

Code Sample

The example demonstrate how to determine input parameters in standard form and use the QP solver for the following problem:

QP Sample

To present this problem in the standard form, there should be:

QP Sample H
QP Sample f
QP Sample A
QP Sample b
QP Sample l

The following code solves the problem:

C#
Copy
 1using System;
 2using FinMath.LinearAlgebra;
 3using FinMath.NumericalOptimization.Constrained;
 4
 5namespace FinMath.Samples
 6{
 7    class QuadraticProgrammingSample
 8    {
 9        static void Main()
10        {
11            // Objective function.
12            Matrix H = new Matrix(new Double[,] { { 2.0, 0.0 }, { 0.0, 2.0 } });
13            Vector F = new Vector(new Double[] { -2.0, -50.0 });
14
15            // Linear inequality constraints.
16            Matrix Ai = new Matrix(new Double[,] { { -1.0, 2.0 }, { 1.0, 2.0 } });
17            Vector Bi = new Vector(new Double[] { 2.0, 6.0 });
18
19            // Lower bounds on variables.
20            Vector L = new Vector(new Double[] { 0.0, 0.0 });
21
22            // Create an instance of the solver.
23            QuadraticProgramming solver = new QuadraticProgramming(H, F, null, null, Ai, Bi, L, null);
24
25            // Setting of the solver.
26            solver.Tolerance = 1.0E-8;
27            solver.IterationsLimit = 50;
28
29            // Delegate used to print messages.
30            solver.LogMessage += Console.WriteLine;
31
32            // Find minimum.
33            solver.Minimize();
34
35            // Get minimum point.
36            if (solver.Status == FMStatus.MethodSucceeded)
37            {
38                Console.WriteLine("MinimumPoint = " + solver.MinimumPoint.ToString(""));
39            }
40            else
41            {
42                Console.WriteLine("Linear programming solver failed.");
43            }
44        }
45    }
46}

See Also