maspack.solvers

Class DantzigLCPSolver

java.lang.Object

maspack.solvers.DantzigLCPSolver

All Implemented Interfaces:

LCPSolver

public class DantzigLCPSolver
extends java.lang.Object
implements LCPSolver

Solves linear complementarity problems (LCPs) and bounded linear complementarity problems (BLCPs) for symmetric positive semi-definite (SPSD) matrices using a principal pivoting method.

The algorithm implemented here is the simple principal pivoting method attributed to Dantzig. At the start of each major cycle the most infeasible variable (the one whose residual is most negative, or for a BLCP most violates its bound) is selected as the driving variable; a minimum-ratio test then determines a sequence of single (1x1) principal pivots that drive it to feasibility while keeping all other variables feasible. This corresponds to Algorithm 4.2.11 ("Dantzig; van de Panne and Whinston") in The Linear Complementarity Problem by Cottle, Pang, and Stone. This implementation generalizes the method to the bounded (BLCP) case, and maintains an incrementally updated Cholesky factorization of the basis matrix, which makes it considerably faster than a dense tableau implementation such as SimpleLCPSolver.

Warm starting is supported and may be enabled with setWarmStartEnabled(boolean); when enabled, the state argument to the solve methods is used to seed the initial basis, which can greatly reduce the number of pivots when a sequence of related problems is solved with a slowly changing active set.

Note that SimpleLCPSolver implements the same simple principal pivoting method (for LCPs only), so for nondegenerate SPSD problems the two classes produce the same sequence of pivots. They would differ only at zero-diagonal degeneracies: robustly handling those requires the 2x2 block pivots and negative lower-bound device of Keller's general (symmetric) principal pivoting method (Algorithm 4.3.2 in Cottle, Pang and Stone; E. Keller, "The general quadratic optimization problem", Mathematical Programming 5, 1973), neither of which is implemented here or in SimpleLCPSolver.

The method is also described in Claude Lacoursiere's Ph.D. thesis, Ghosts and Machines: Regularized Variational Methods for Interactive Simulations of Multibodies with Dry Frictional Contact (2007). Be aware, however, that Lacoursiere uses the name "Cottle-Dantzig" for an incremental variant that introduces the variables one at a time in a fixed index order; that is not the method implemented here (which, like Algorithm 4.2.11 above, selects the most infeasible variable from the full set at each cycle).

Nested Class Summary

Nested classes/interfaces inherited from interface maspack.solvers.LCPSolver

LCPSolver.Status

Field Summary

Fields

Modifier and Type	Field and Description
static int	SHOW_ALL
static int	SHOW_MIN_RATIO
static int	SHOW_NONE
static int	SHOW_PIVOTS
static int	SHOW_QM
static int	SHOW_RETURNS
static int	SHOW_VARIABLES

Fields inherited from interface maspack.solvers.LCPSolver

INF, W_VAR_LOWER, W_VAR_UPPER, Z_VAR

Constructor Summary

Constructors

Constructor and Description
DantzigLCPSolver() Creates a new Dantzig solver.

Method Summary

Modifier and Type	Method and Description
boolean	getComputeResidual()
int	getDebug()
int	getIterationCount() Returns the number of iterations that were used in the most recent solution operation.
int	getIterationLimit() Gets the iteration limit for this solver.
double	getLastSolveTol() Returns the numeric tolerance used to determine complementarity for the most recent solution.
int	getPivotCount() Returns the number of pivots that were used in the most recent solution operation.
double	getResidual()
boolean	getSilent()
double	getTolerance() Returns the numeric tolerence for this solver.
boolean	isBLCPSupported() Queries whether this solver supported the solution of bounded linear complementarity problems (BLCPs).
boolean	isWarmStartSupported() Queries whether this solver supports warm starts.
int	numFailedPivots() Returns the number of pivots that were attempted and rejected because they would have resulted in a basis matrix that was not SPD.
void	resolve(VectorNd z, VectorNd q, int[] state) Solves the system
void	setComputeResidual(boolean enable)
void	setDebug(int code)
void	setIterationLimit(int limit) Sets the iteration limit for this solver.
void	setSilent(boolean code)
void	setTolerance(double tol) Sets the numeric tolerance for this solver.
void	setWarmStartEnabled(boolean enable) Enables or disables warm starts.
LCPSolver.Status	solve(VectorNd z, VectorNd w, VectorNi state, MatrixNd M, VectorNd q, VectorNd lo, VectorNd hi, int nub) If LCPSolver.isBLCPSupported() returns true, solves the BLCP
LCPSolver.Status	solve(VectorNd z, VectorNi state, MatrixNd M, VectorNd q) Solves the LCP

Methods inherited from class java.lang.Object

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

Methods inherited from interface maspack.solvers.LCPSolver

clearState, stateToChar, stateToString, stateToString, stateToString, stringToState

Field Detail

SHOW_NONE

public static final int SHOW_NONE

See Also:

Constant Field Values

SHOW_PIVOTS

public static final int SHOW_PIVOTS

See Also:

Constant Field Values

SHOW_MIN_RATIO

public static final int SHOW_MIN_RATIO

See Also:

Constant Field Values

SHOW_QM

public static final int SHOW_QM

See Also:

Constant Field Values

SHOW_VARIABLES

public static final int SHOW_VARIABLES

See Also:

Constant Field Values

SHOW_RETURNS

public static final int SHOW_RETURNS

See Also:

Constant Field Values

SHOW_ALL

public static final int SHOW_ALL

See Also:

Constant Field Values

Constructor Detail

DantzigLCPSolver

public DantzigLCPSolver()

Creates a new Dantzig solver.

Method Detail

getDebug

public int getDebug()

setDebug

public void setDebug(int code)

getSilent

public boolean getSilent()

setSilent

public void setSilent(boolean code)

getComputeResidual

public boolean getComputeResidual()

setComputeResidual

public void setComputeResidual(boolean enable)

getResidual

public double getResidual()

getTolerance

public double getTolerance()

Returns the numeric tolerence for this solver.

Returns:

numeric tolerance

See Also:

setTolerance(double)

setTolerance

public void setTolerance(double tol)

Sets the numeric tolerance for this solver. This is used to determine when q' >= 0, as described in the class documentation. In particular, a solution will be considered found whenever q' >= -tol.

Parameters:

tol - new numeric tolerance. Negative numbers will be truncated to 0.

See Also:

getTolerance()

getIterationLimit

public int getIterationLimit()

Gets the iteration limit for this solver. This value multiplied by the size of the LCP matrix gives the maximum number of iterations allowed for the solver.

Returns:

iteration limit

setIterationLimit

public void setIterationLimit(int limit)

Sets the iteration limit for this solver. This value multiplied by the size of the LCP matrix gives the maximum number of iterations allowed for the solver. The maximum number of iterations is specified in this way because the expected number of iterations for Dantzig's algorithm is proportional to the size of the LCP matrix.

Parameters:

limit - new iteration limit

getIterationCount

public int getIterationCount()

Returns the number of iterations that were used in the most recent solution operation.

Specified by:

getIterationCount in interface LCPSolver

Returns:

iteration count for last solution

getPivotCount

public int getPivotCount()

Returns the number of pivots that were used in the most recent solution operation. For solvers that support block pivoting and have block pivoting enabled, this will usually exceed the number of iterations. Otherwise, this number should be roughly equal to the number of iterations.

Specified by:

getPivotCount in interface LCPSolver

Returns:

pivot count for last solution

getLastSolveTol

public double getLastSolveTol()

Returns the numeric tolerance used to determine complementarity for the most recent solution. These tolerances may be updated dynamically during the solution.

Specified by:

getLastSolveTol in interface LCPSolver

numFailedPivots

public int numFailedPivots()

Returns the number of pivots that were attempted and rejected because they would have resulted in a basis matrix that was not SPD.

Specified by:

numFailedPivots in interface LCPSolver

solve

public LCPSolver.Status solve(VectorNd z,
                              VectorNi state,
                              MatrixNd M,
                              VectorNd q)

Solves the LCP

 w = M z + q
 

where M is a matrix whose characteristics should match the capabilities of the solver.

Specified by:

solve in interface LCPSolver

Parameters:

z - returns the solution for z

state - optional argument, which if non-null, returns the state vector resulting from the LCP solve. For solvers capable of warm starts (i.e., if LCPSolver.isWarmStartSupported() returns true), the value of this vector on input will also specify the initial starting state.

M - system matrix

q - system vector

Returns:

Status of the solution.

resolve

public void resolve(VectorNd z,
                    VectorNd q,
                    int[] state)

Solves the system

 w = M z + q
 

using the same matrix M and active set that was determined in the previous call to solve. Non-active z variables are set to 0.

Parameters:

z - returns the solution for z

q - system vector

state - (optional) if specified, returns which z variables are basic in the solution.

solve

public LCPSolver.Status solve(VectorNd z,
                              VectorNd w,
                              VectorNi state,
                              MatrixNd M,
                              VectorNd q,
                              VectorNd lo,
                              VectorNd hi,
                              int nub)

If LCPSolver.isBLCPSupported() returns true, solves the BLCP

 w = M z + q = wpos - wneg,
 0 ≤ hi - z perp wneg ≥ 0,
 0 ≤ z - lo perp wpos ≥ 0,
 

where M is a matrix whose characteristics should match the capabilities of the solver. If BLCPs are not supported, then this method returns LCPSolver.Status.UNIMPLEMENTED.

Specified by:

solve in interface LCPSolver

Parameters:

z - returns the solution for z

w - returns the solution for w

state - optional argument, which if non-null, returns the state vector resulting from the LCP solve. For solvers capable of warm starts (i.e., if LCPSolver.isWarmStartSupported() returns true), the value of this vector on input will also specify the initial starting state.

M - system matrix

q - system vector

lo - lower bounds for the z variables

hi - upper bounds for the z variables

nub - number of unbounded variables (corresponding to bilateral constraints). If nub > 0, then the first nub entries of lo and hi must be negative and positive infinity, respectively.

Returns:

Status of the solution.

isBLCPSupported

public boolean isBLCPSupported()

Queries whether this solver supported the solution of bounded linear complementarity problems (BLCPs).

Specified by:

isBLCPSupported in interface LCPSolver

Returns:

true if BLCPs are supported.

isWarmStartSupported

public boolean isWarmStartSupported()

Queries whether this solver supports warm starts.

Specified by:

isWarmStartSupported in interface LCPSolver

Returns:

true if warm starts are supported.

setWarmStartEnabled

public void setWarmStartEnabled(boolean enable)

Enables or disables warm starts. When warm starts are enabled, the state argument of the solve() methods, when non-null, is used to supply an initial guess for the LCP solution. Warm starts are disabled by default. Enabling them causes isWarmStartSupported() to return true.