dev.nm.solver.multivariate.constrained.convex.sdp.socp.qp.problem

Class QPProblem

java.lang.Object

dev.nm.solver.multivariate.constrained.convex.sdp.socp.qp.problem.QPProblem

All Implemented Interfaces:

ConstrainedOptimProblem, OptimProblem

public class QPProblem
extends Object
implements ConstrainedOptimProblem

Quadratic Programming is the problem of optimizing (minimizing) a quadratic function of several variables subject to linear constraints on these variables. The standard form, following the convention in the reference, is: \[ \min_x \left \{ \frac{1}{2} \times x'Hx + x'p \right \} \\ Ax \geq b, A_{eq}x = b_{eq} \]

Sign and dimension conventions

QuadraticFunction(H,p) means \(\tfrac12 x^{\mathsf T}Hx+p^{\mathsf T}x\): include the factor of two in H when translating a sum of squared terms. Each constraint matrix row is one constraint, every row has one column per decision variable, and its right-hand side vector has one entry per row. Equality, greater-than, and less-than arguments are distinct; do not change the inequality direction without also negating both the matrix and right-hand side.

A problem object does not optimize itself. Pass it to a QP minimizer, then call the returned solution's search method. A missing constraint family may be represented by null where the constructor permits it. Convex-solver examples assume a symmetric positive-definite Hessian and a nonempty feasible set.

See Also:

• Wikipedia: Quadratic programming
• "Andreas Antoniou, Wu-Sheng Lu, "Chapter 13, Quadratic and Convex Programming," Practical Optimization: Algorithms and Engineering Applications."

Constructor Summary

Constructors

Constructor and Description
QPProblem(QPProblem that) Copy constructor.
QPProblem(QuadraticFunction f, LinearEqualityConstraints equal, LinearGreaterThanConstraints greater) Construct a quadratic programming problem with linear equality and greater-than-or-equal-to constraints.
QPProblem(QuadraticFunction f, LinearEqualityConstraints equal, LinearGreaterThanConstraints greater, LinearLessThanConstraints less) Construct a quadratic programming problem.
QPProblem(QuadraticFunction f, LinearEqualityConstraints equal, LinearLessThanConstraints less) Construct a quadratic programming problem with linear equality and less-than-or-equal-to constraints.
QPProblem(QuadraticFunction f, LinearGreaterThanConstraints greater) Construct a quadratic programming problem with linear greater-than-or-equal-to constraints.
QPProblem(QuadraticFunction f, LinearGreaterThanConstraints greater, LinearLessThanConstraints less) Construct a quadratic programming problem with linear inequality constraints.
QPProblem(QuadraticFunction f, LinearLessThanConstraints less) Construct a quadratic programming problem with linear less-than-or-equal-to constraints.

Method Summary

Modifier and Type	Method and Description
ImmutableMatrix	A() Get the coefficients of the inequality constraints: A as in \(Ax \geq b\).
ImmutableMatrix	Aeq() Get the coefficients of the equality constraints: \(A_{eq}\) as in \(A_{eq}x = b_{eq}\).
ImmutableVector	b() Get the values of the inequality constraints: b as in \(Ax \geq b\).
ImmutableVector	beq() Get the values of the equality constraints: \(b_{eq}\) as in \(A_{eq}x = b_{eq}\).
int	dimension() Get the number of variables.
QuadraticFunction	f() Get the objective function.
LinearEqualityConstraints	getEqualityConstraints() Gets the equality constraints, \(h_{i}(x) = 0\)
LinearGreaterThanConstraints	getGreaterThanConstraints() Get the set of linear greater-than-or-equal-to constraints.
LinearLessThanConstraints	getLessThanConstraints() Gets the less-than-or-equal-to constraints, gi(x) ≤ 0

Methods inherited from class java.lang.Object

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

Constructor Detail

QPProblem

public QPProblem(QuadraticFunction f,
                 LinearEqualityConstraints equal,
                 LinearGreaterThanConstraints greater,
                 LinearLessThanConstraints less)

Construct a quadratic programming problem.

Parameters:

f - the quadratic objective function to be minimized

equal - the linear equality constraints

greater - the linear greater-than-or-equal-to constraints

less - the linear less-than-or-equal-to constraints

QPProblem

public QPProblem(QuadraticFunction f,
                 LinearGreaterThanConstraints greater,
                 LinearLessThanConstraints less)

Construct a quadratic programming problem with linear inequality constraints.

Parameters:

f - the quadratic objective function to be minimized

greater - the linear greater-than-or-equal-to constraints

less - the linear less-than-or-equal-to constraints

QPProblem

public QPProblem(QuadraticFunction f,
                 LinearEqualityConstraints equal,
                 LinearGreaterThanConstraints greater)

Construct a quadratic programming problem with linear equality and greater-than-or-equal-to constraints.

Parameters:

f - the quadratic objective function to be minimized

equal - the linear equality constraints

greater - the linear greater-than-or-equal-to constraints

QPProblem

public QPProblem(QuadraticFunction f,
                 LinearGreaterThanConstraints greater)

Construct a quadratic programming problem with linear greater-than-or-equal-to constraints.

Parameters:

f - the quadratic objective function to be minimized

greater - the linear greater-than-or-equal-to constraints

QPProblem

public QPProblem(QuadraticFunction f,
                 LinearEqualityConstraints equal,
                 LinearLessThanConstraints less)

Construct a quadratic programming problem with linear equality and less-than-or-equal-to constraints.

Parameters:

f - the quadratic objective function to be minimized

equal - the linear equality constraints

less - the linear less-than-or-equal-to constraints

QPProblem

public QPProblem(QuadraticFunction f,
                 LinearLessThanConstraints less)

Construct a quadratic programming problem with linear less-than-or-equal-to constraints.

Parameters:

f - the quadratic objective function to be minimized

less - the linear less-than-or-equal-to constraints

QPProblem

public QPProblem(QPProblem that)

Copy constructor.

Parameters:

that - an quadratic programming problem

Method Detail

dimension

public int dimension()

Description copied from interface: OptimProblem

Get the number of variables.

Specified by:

dimension in interface OptimProblem

Returns:

the number of variables.

f

public QuadraticFunction f()

Description copied from interface: OptimProblem

Get the objective function.

Specified by:

f in interface OptimProblem

Returns:

the objective function

getGreaterThanConstraints

public LinearGreaterThanConstraints getGreaterThanConstraints()

Get the set of linear greater-than-or-equal-to constraints.

Returns:

the set of linear greater-than-or-equal-to constraints

getLessThanConstraints

public LinearLessThanConstraints getLessThanConstraints()

Description copied from interface: ConstrainedOptimProblem

Gets the less-than-or-equal-to constraints, g_i(x) ≤ 0

Specified by:

getLessThanConstraints in interface ConstrainedOptimProblem

Returns:

the less-than-or-equal-to constraints

getEqualityConstraints

public LinearEqualityConstraints getEqualityConstraints()

Description copied from interface: ConstrainedOptimProblem

Gets the equality constraints, \(h_{i}(x) = 0\)

Specified by:

getEqualityConstraints in interface ConstrainedOptimProblem

Returns:

the equality constraints

A

public ImmutableMatrix A()

Get the coefficients of the inequality constraints: A as in \(Ax \geq b\).

Returns:

the inequality constraint coefficients

b

public ImmutableVector b()

Get the values of the inequality constraints: b as in \(Ax \geq b\).

Returns:

the inequality constraint values

Aeq

public ImmutableMatrix Aeq()

Get the coefficients of the equality constraints: \(A_{eq}\) as in \(A_{eq}x = b_{eq}\).

Returns:

the equality constraint coefficients

beq

public ImmutableVector beq()

Get the values of the equality constraints: \(b_{eq}\) as in \(A_{eq}x = b_{eq}\).

Returns:

the equality constraint values