JMSLTM Numerical Library 6.1

com.imsl.math
Class QuadraticProgramming

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

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.

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.


JMSLTM Numerical Library 6.1

Copyright © 1970-2010 Visual Numerics, Inc.
Built July 30 2010.