com.imsl.math
Class QuadraticProgramming

java.lang.Object
  com.imsl.math.QuadraticProgramming

public class QuadraticProgramming
extends Object

Solves the convex quadratic programming problem subject to equality or inequality constraints.

Class QuadraticProgramming is based on M.J.D. Powell's implementation of the Goldfarb and Idnani dual quadratic programming (QP) algorithm for convex QP problems subject to general linear equality/inequality constraints (Goldfarb and Idnani 1983); i.e., problems of the form

subject to

given the vectors , , and g, and the matrices H, , and . H is required to be positive definite. In this case, a unique x solves the problem or the constraints are inconsistent. If H is not positive definite, a positive definite perturbation of H is used in place of H. For more details, see Powell (1983, 1985).

If a perturbation of H, , is used in the QP problem, then also should be used in the definition of the Lagrange multipliers.

If the constraints are infeasible an exception is thrown. See Example 3 where the exception is caught and printed.

See Also:

Example 1, Example 2, Example 3

Nested Class Summary

static class	QuadraticProgramming.InconsistentSystemException The system of constraints is inconsistent.
static class	QuadraticProgramming.NoLPSolutionException No solution for the LP problem with h = 0 was found by DenseLP.
static class	QuadraticProgramming.ProblemUnboundedException The object value for the problem is unbounded.
static class	QuadraticProgramming.SolutionNotFoundException A solution was not found.

Field Summary

static double

EPSILON_SMALL The smallest relative spacing for doubles.

Constructor Summary

QuadraticProgramming(double[][] h, double[] g, double[][] aEquality, double[] bEquality, double[][] aInequality, double[] bInequality)
Solve a quadratic programming problem.

Method Summary

double[]	getDual() Returns the dual (Lagrange multipliers).
double[]	getSolution() Returns the solution.
boolean	isNoMoreProgress() Returns true if due to computer rounding error, a change in the variables fail to improve the objective function.

Methods inherited from class java.lang.Object

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

Field Detail

EPSILON_SMALL

public static final double EPSILON_SMALL

The smallest relative spacing for doubles.

See Also:

Constant Field Values

Constructor Detail

QuadraticProgramming

public QuadraticProgramming(double[][] h,
                            double[] g,
                            double[][] aEquality,
                            double[] bEquality,
                            double[][] aInequality,
                            double[] bInequality)
                     throws QuadraticProgramming.InconsistentSystemException,
                            QuadraticProgramming.ProblemUnboundedException,
                            QuadraticProgramming.NoLPSolutionException,
                            QuadraticProgramming.SolutionNotFoundException

Solve a quadratic programming problem.

Parameters:

h - is square array containing the Hessian. It must be positive definite.

g - contains the coefficients of the linear term of the objective function.

aEquality - is a rectangular matrix containing the equality constraints. It can be null if there are no equality constraints.

bEquality - contains the right-side of the equality constraints. It can be null if there are no equality constraints.

aInequality - is a rectangular matrix containing the inequality constraints. It can be null if there are no inequality constraints.

bInequality - contains the right-side of the inequality constraints. It can be null if there are no inequality constraints.

Throws:

QuadraticProgramming.InconsistentSystemException - if the system of constraints is inconsistent and there is no solution.

QuadraticProgramming.ProblemUnboundedException

QuadraticProgramming.NoLPSolutionException

QuadraticProgramming.SolutionNotFoundException

Method Detail

getDual

public double[] getDual()

Returns the dual (Lagrange multipliers).

getSolution

public double[] getSolution()

Returns the solution.

isNoMoreProgress

public boolean isNoMoreProgress()

Returns true if due to computer rounding error, a change in the variables fail to improve the objective function. Usually the solution is close to optimum.