JMSLTM Numerical Library 4.0

com.imsl.math
Class QuadraticProgramming

java.lang.Object
  extended bycom.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

mathop {min }limits_{x in R^n } g^Tx + 
  frac{1}{2} x^THx

subject to

A_1 x = b_1

A_2 x ge b_2

given the vectors b_1, b_2, and g, and the matrices H, A_1, and A_2. 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, H + alpha I, is used in the QP problem, then H + alpha I also should be used in the definition of the Lagrange multipliers.

See Also:
Example 1, Example 2

Nested Class Summary
static class QuadraticProgramming.InconsistentSystemException
          Inconsistent system.
 
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
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.
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.


JMSLTM Numerical Library 4.0

Copyright 1970-2006 Visual Numerics, Inc.
Built June 1 2006.