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

$$\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

Nested Classes

Modifier and Type	Class and Description
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 objective value for the problem is unbounded.
static class	QuadraticProgramming.SolutionNotFoundException A solution was not found.

Constructor Summary

Constructors

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

Method Summary

Modifier and Type	Method and Description
double[]	getDual() Returns the dual (Lagrange multipliers).
double	getOptimalValue() Returns the optimal value.
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

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 - if the problem is unbounded.

QuadraticProgramming.NoLPSolutionException - if the problem is actually an LP problem and no LP solution can be found.

QuadraticProgramming.SolutionNotFoundException - if no solution for the problem can be found.

Method Detail

getSolution

public double[] getSolution()

Returns the solution.

getOptimalValue

public double getOptimalValue()

Returns the optimal value.

Returns:

a double, the optimal value.

getDual

public double[] getDual()

Returns the dual (Lagrange multipliers).

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.