org.ojalgo.optimisation.convex

Class ConvexSolver

java.lang.Object

org.ojalgo.optimisation.GenericSolver

org.ojalgo.optimisation.convex.ConvexSolver

All Implemented Interfaces:

Optimisation, Optimisation.Solver, UpdatableSolver

public abstract class ConvexSolver
extends GenericSolver
implements UpdatableSolver

ConvexSolver solves optimisation problems of the form:

min 1/2 [X]^T[Q][X] - [C]^T[X]
when [AE][X] == [BE]
and [AI][X] <= [BI]

The matrix [Q] is assumed to be symmetric (it must be made that way) and positive (semi)definite:

• If [Q] is positive semidefinite, then the objective function is convex: In this case the quadratic program has a global minimizer if there exists some feasible vector [X] (satisfying the constraints) and if the objective function is bounded below on the feasible region.
• If [Q] is positive definite and the problem has a feasible solution, then the global minimizer is unique.

The general recommendation is to construct optimisation problems using ExpressionsBasedModel and not worry about solver details. If you do want to instantiate a convex solver directly use the ConvexSolver.Builder class. It will return an appropriate subclass for you.

When the KKT matrix is nonsingular, there is a unique optimal primal-dual pair (x,l). If the KKT matrix is singular, but the KKT system is still solvable, any solution yields an optimal pair (x,l). If the KKT system is not solvable, the quadratic optimization problem is unbounded below or infeasible.

Author:

apete

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	ConvexSolver.Builder
static class	ConvexSolver.ModelIntegration

Nested classes/interfaces inherited from interface org.ojalgo.optimisation.Optimisation

Optimisation.Constraint, Optimisation.Integration<M extends Optimisation.Model,S extends Optimisation.Solver>, Optimisation.Model, Optimisation.Objective, Optimisation.Options, Optimisation.Result, Optimisation.Solver, Optimisation.State

Field Summary

Fields inherited from class org.ojalgo.optimisation.GenericSolver

ACCURACY, options

Constructor Summary

Constructors

Modifier	Constructor and Description
protected	ConvexSolver(ConvexSolver.Builder matrices, Optimisation.Options solverOptions)

Method Summary

Modifier and Type	Method and Description
protected boolean	computeGeneral(Access2D.Collectable<Double,? super PhysicalStore<Double>> matrix)
protected boolean	computeQ(Access2D.Collectable<Double,? super PhysicalStore<Double>> matrix)
static void	copy(ExpressionsBasedModel sourceModel, ConvexSolver.Builder destinationBuilder)
protected int	countEqualityConstraints()
protected int	countInequalityConstraints()
protected int	countVariables()
void	dispose() Cleanup when a solver instance is no longer needed.
protected double	evaluateFunction(Access1D<?> solution)
protected MatrixStore<Double>	extractSolution() Should be able to feed this to GenericSolver.evaluateFunction(Access1D).
static ConvexSolver.Builder	getBuilder()
static ConvexSolver.Builder	getBuilder(MatrixStore<Double> Q, MatrixStore<Double> C)
protected abstract Access2D.Collectable<Double,? super PhysicalStore<Double>>	getIterationKKT()
protected abstract Access2D.Collectable<Double,? super PhysicalStore<Double>>	getIterationRHS()
protected MatrixStore<Double>	getMatrixAE()
protected RowsSupplier<Double>	getMatrixAI()
protected SparseArray<Double>	getMatrixAI(int row)
protected RowsSupplier<Double>	getMatrixAI(int[] rows)
protected MatrixStore<Double>	getMatrixBE()
protected MatrixStore<Double>	getMatrixBI()
protected double	getMatrixBI(int row)
protected MatrixStore<Double>	getMatrixBI(int[] selector)
protected MatrixStore<Double>	getMatrixC()
protected PhysicalStore<Double>	getMatrixQ()
protected int	getRankGeneral()
protected MatrixStore<Double>	getSE()
protected MatrixStore<Double>	getSolutionGeneral(Access2D.Collectable<Double,? super PhysicalStore<Double>> rhs)
protected MatrixStore<Double>	getSolutionGeneral(Access2D.Collectable<Double,? super PhysicalStore<Double>> rhs, PhysicalStore<Double> preallocated)
protected MatrixStore<Double>	getSolutionQ(Access2D.Collectable<Double,? super PhysicalStore<Double>> rhs)
protected MatrixStore<Double>	getSolutionQ(Access2D.Collectable<Double,? super PhysicalStore<Double>> rhs, PhysicalStore<Double> preallocated)
protected PhysicalStore<Double>	getSolutionX() Solution / Variables: [X]
protected boolean	hasEqualityConstraints()
protected boolean	hasInequalityConstraints()
protected boolean	hasObjective()
protected boolean	initialise(Optimisation.Result kickStarter)
protected boolean	isSolvableGeneral()
protected boolean	isSolvableQ()
protected abstract boolean	needsAnotherIteration()
protected abstract void	performIteration()
Optimisation.Result	solve(Optimisation.Result kickStarter)
protected boolean	solveFullKKT(PhysicalStore<Double> preallocated)
protected Optimisation.Result	solveLP()
String	toString()
protected boolean	validate() Should validate the solver data/input/structue.

Methods inherited from class org.ojalgo.optimisation.GenericSolver

buildResult, countIterations, countTime, error, getState, incrementIterationsCount, isIterationAllowed, isLogDebug, isLogOff, isLogProgress, log, log, resetIterationsCount, setState

Methods inherited from class java.lang.Object

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

Methods inherited from interface org.ojalgo.optimisation.UpdatableSolver

fixVariable

Methods inherited from interface org.ojalgo.optimisation.Optimisation.Solver

solve

Constructor Detail

ConvexSolver

protected ConvexSolver(ConvexSolver.Builder matrices,
                       Optimisation.Options solverOptions)

Method Detail

copy

public static void copy(ExpressionsBasedModel sourceModel,
                        ConvexSolver.Builder destinationBuilder)

getBuilder

public static ConvexSolver.Builder getBuilder()

getBuilder

public static ConvexSolver.Builder getBuilder(MatrixStore<Double> Q,
                                              MatrixStore<Double> C)

dispose

public void dispose()

Description copied from interface: Optimisation.Solver

Cleanup when a solver instance is no longer needed. The default implementation does nothing,

Specified by:

dispose in interface Optimisation.Solver

solve

public final Optimisation.Result solve(Optimisation.Result kickStarter)

Specified by:

solve in interface Optimisation.Solver

toString

public String toString()

Overrides:

toString in class Object

computeGeneral

protected boolean computeGeneral(Access2D.Collectable<Double,? super PhysicalStore<Double>> matrix)

computeQ

protected boolean computeQ(Access2D.Collectable<Double,? super PhysicalStore<Double>> matrix)

countEqualityConstraints

protected int countEqualityConstraints()

countInequalityConstraints

protected int countInequalityConstraints()

countVariables

protected int countVariables()

evaluateFunction

protected double evaluateFunction(Access1D<?> solution)

Specified by:

evaluateFunction in class GenericSolver

extractSolution

protected MatrixStore<Double> extractSolution()

Description copied from class: GenericSolver

Should be able to feed this to GenericSolver.evaluateFunction(Access1D).

Specified by:

extractSolution in class GenericSolver

getIterationKKT

protected abstract Access2D.Collectable<Double,? super PhysicalStore<Double>> getIterationKKT()

getIterationRHS

protected abstract Access2D.Collectable<Double,? super PhysicalStore<Double>> getIterationRHS()

getMatrixAE

protected MatrixStore<Double> getMatrixAE()

getMatrixAI

protected RowsSupplier<Double> getMatrixAI()

getMatrixAI

protected SparseArray<Double> getMatrixAI(int row)

getMatrixAI

protected RowsSupplier<Double> getMatrixAI(int[] rows)

getMatrixBE

protected MatrixStore<Double> getMatrixBE()

getMatrixBI

protected MatrixStore<Double> getMatrixBI()

getMatrixBI

protected double getMatrixBI(int row)

getMatrixBI

protected MatrixStore<Double> getMatrixBI(int[] selector)

getMatrixC

protected MatrixStore<Double> getMatrixC()

getMatrixQ

protected PhysicalStore<Double> getMatrixQ()

getRankGeneral

protected int getRankGeneral()

getSE

protected MatrixStore<Double> getSE()

getSolutionGeneral

protected MatrixStore<Double> getSolutionGeneral(Access2D.Collectable<Double,? super PhysicalStore<Double>> rhs)

getSolutionGeneral

protected MatrixStore<Double> getSolutionGeneral(Access2D.Collectable<Double,? super PhysicalStore<Double>> rhs,
                                                 PhysicalStore<Double> preallocated)

getSolutionQ

protected MatrixStore<Double> getSolutionQ(Access2D.Collectable<Double,? super PhysicalStore<Double>> rhs)

getSolutionQ

protected MatrixStore<Double> getSolutionQ(Access2D.Collectable<Double,? super PhysicalStore<Double>> rhs,
                                           PhysicalStore<Double> preallocated)

getSolutionX

protected PhysicalStore<Double> getSolutionX()

Solution / Variables: [X]

hasEqualityConstraints

protected boolean hasEqualityConstraints()

hasInequalityConstraints

protected boolean hasInequalityConstraints()

hasObjective

protected boolean hasObjective()

initialise

protected boolean initialise(Optimisation.Result kickStarter)

isSolvableGeneral

protected boolean isSolvableGeneral()

isSolvableQ

protected boolean isSolvableQ()

needsAnotherIteration

protected abstract boolean needsAnotherIteration()

performIteration

protected abstract void performIteration()

solveFullKKT

protected boolean solveFullKKT(PhysicalStore<Double> preallocated)

solveLP

protected Optimisation.Result solveLP()

validate

protected boolean validate()

Should validate the solver data/input/structue. Even "expensive" validation can be performed as the method should only be called if Optimisation.Options.validate is set to true. In addition to returning true or false the implementation should set the state to either Optimisation.State.VALID or Optimisation.State.INVALID (or possibly Optimisation.State.FAILED). Typically the method should be called at the very beginning of the solve-method.

Returns:

Is the solver instance valid?