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

Class QPSimpleMinimizer

java.lang.Object

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

public class QPSimpleMinimizer
extends Object

These are the utility functions to solve simple quadratic programming problems that admit analytical solutions.

Objective convention

The objective is 0.5 * x' * H * x + x' * p; do not omit the one-half factor when translating a model. Use a symmetric positive (semi-)definite Hessian. These convenience methods handle unconstrained or equality-constrained problems, not arbitrary inequality constraints. Catch QPInfeasible and inspect isUnique() before treating a returned minimizer as unique.

Example

 import dev.nm.algebra.linear.matrix.doubles.matrixtype.dense.DenseMatrix;
 import dev.nm.algebra.linear.vector.doubles.dense.DenseVector;
 import dev.nm.analysis.function.rn2r1.QuadraticFunction;
 import dev.nm.solver.multivariate.constrained.convex.sdp.socp.qp.QPSimpleMinimizer;
 import dev.nm.solver.multivariate.constrained.convex.sdp.socp.qp.QPSolution;

 QuadraticFunction objective = new QuadraticFunction(
         new DenseMatrix(new double[][]{{2, 0}, {0, 2}}),
         new DenseVector(-2.0, 4.0));
 QPSolution solution = QPSimpleMinimizer.solve(objective);
 assert solution.isUnique();
 assert Math.abs(solution.minimizer().get(1) - 1.0) < 1e-12;
 assert Math.abs(solution.minimizer().get(2) + 2.0) < 1e-12;
 

See Also:

"Andreas Antoniou, Wu-Sheng Lu, "Section 13.2, Convex QP Problems with Equality Constraints," Practical Optimization: Algorithms and Engineering Applications."

Constructor Summary

Constructors

Constructor and Description
QPSimpleMinimizer()

Method Summary

Modifier and Type	Method and Description
static QPSolution	solve(QuadraticFunction f) Solves an unconstrained quadratic programming problem of this form. \[ \min_x \left \{ \frac{1}{2} \times x'Hx + x'p \right \} \]
static QPSolution	solve(QuadraticFunction f, double epsilon) Solves an unconstrained quadratic programming problem of this form. \[ \min_x \left \{ \frac{1}{2} \times x'Hx + x'p \right \} \]
static QPSolution	solve(QuadraticFunction f, LinearEqualityConstraints equal) Solves a quadratic programming problem subject to equality constraints. \[ \min_x \left \{ \frac{1}{2} \times x'Hx + x'p \right \}, Ax = b \]
static QPSolution	solve(QuadraticFunction f, LinearEqualityConstraints equal, double epsilon) Solves a quadratic programming problem subject to equality constraints. \[ \min_x \left \{ \frac{1}{2} \times x'Hx + x'p \right \}, Ax = b \]

Methods inherited from class java.lang.Object

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

Constructor Detail

QPSimpleMinimizer

public QPSimpleMinimizer()

Method Detail

solve

public static QPSolution solve(QuadraticFunction f,
                               double epsilon)
                        throws QPInfeasible

Solves an unconstrained quadratic programming problem of this form. \[ \min_x \left \{ \frac{1}{2} \times x'Hx + x'p \right \} \]

Parameters:

f - the objective function

epsilon - a precision parameter: when a number |x| ≤ ε, it is considered 0

Returns:

a quadratic programming solution

Throws:

QPInfeasible - when the quadratic programming problem is infeasible

solve

public static QPSolution solve(QuadraticFunction f)
                        throws QPInfeasible

Solves an unconstrained quadratic programming problem of this form. \[ \min_x \left \{ \frac{1}{2} \times x'Hx + x'p \right \} \]

Parameters:

f - the objective function

Returns:

a quadratic programming solution

Throws:

QPInfeasible - when the quadratic programming problem is infeasible

solve

public static QPSolution solve(QuadraticFunction f,
                               LinearEqualityConstraints equal,
                               double epsilon)
                        throws QPInfeasible

Solves a quadratic programming problem subject to equality constraints. \[ \min_x \left \{ \frac{1}{2} \times x'Hx + x'p \right \}, Ax = b \]

Parameters:

f - the objective function

equal - the equality constraints

epsilon - a precision parameter: when a number |x| ≤ ε, it is considered 0

Returns:

a quadratic programming solution

Throws:

QPInfeasible - when the quadratic programming problem is infeasible

solve

public static QPSolution solve(QuadraticFunction f,
                               LinearEqualityConstraints equal)
                        throws QPInfeasible

Solves a quadratic programming problem subject to equality constraints. \[ \min_x \left \{ \frac{1}{2} \times x'Hx + x'p \right \}, Ax = b \]

Parameters:

f - the objective function

equal - the equality constraints

Returns:

a quadratic programming solution

Throws:

QPInfeasible - when the quadratic programming problem is infeasible