Class QuadraticProgram

java.lang.Object

com.quantfinlib.optimization.QuadraticProgram

public final class QuadraticProgram
extends Object

Convex quadratic programming by the primal active-set method (Nocedal and Wright, Numerical Optimization, 2nd ed., Algorithm 16.3):

  minimise   ½·x'Qx + c'x
 subject to A·x = b,   G·x ≤ h

with Q symmetric positive semi-definite. The method starts from a feasible point supplied by the caller, keeps a working set of inequalities held as equalities, solves the equality-constrained subproblem exactly through its KKT system, steps to the nearest blocking constraint, and drops the working constraint with the most negative multiplier until every multiplier is non-negative. The result is optimal to rounding, not to a sampling tolerance.

A ridge of 1e-13·(1 + tr Q / n) is added to the diagonal of Q so that the KKT matrix stays nonsingular when Q is only semi-definite (a rank-deficient covariance, or a variable that does not enter the objective). Its effect on the solution is of the order of 1e-13 relative. Dense linear algebra; meant for portfolio-sized problems (hundreds of variables).

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
static final class	QuadraticProgram.Solution	Solution, its objective value, and the active-set iterations used.

Method Summary

Modifier and Type	Method	Description
static QuadraticProgram.Solution	solve(double[][] q, double[] c, double[][] a, double[] b, double[][] g, double[] h, double[] x0)	Solves the quadratic program.

Methods inherited from class Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Method Details

solve

public static QuadraticProgram.Solution solve(double[][] q,
 double[] c,
 double[][] a,
 double[] b,
 double[][] g,
 double[] h,
 double[] x0)

Solves the quadratic program.

Parameters:

q - n×n symmetric PSD

c - length n

a - m×n equality rows (m may be 0), linearly independent

b - length m

g - p×n inequality rows (p may be 0)

h - length p

x0 - a feasible starting point (equalities to 1e-9, inequalities to 1e-9 relative)

Throws:

IllegalArgumentException - if x0 is infeasible or inputs are malformed

IllegalStateException - if the iteration limit is reached