maspack.solvers

Class SimpleLCPSolver

java.lang.Object

maspack.solvers.SimpleLCPSolver

All Implemented Interfaces:

LCPSolver

public class SimpleLCPSolver
extends java.lang.Object
implements LCPSolver

Solves linear complementarity problems (LCPs) for symmetric positive semi-definite (SPSD) matrices using the simple principal pivoting method.

This class was formerly named KellerLCPSolver, but the algorithm it implements is not Keller's general (symmetric) principal pivoting method. It is in fact the same simple principal pivoting method implemented by DantzigLCPSolver: at each major cycle the most infeasible variable is chosen as the driving variable and a minimum-ratio test drives it to feasibility using single (1x1) principal pivots. This corresponds to Algorithm 4.2.11 ("Dantzig; van de Panne and Whinston") in The Linear Complementarity Problem by Cottle, Pang, and Stone.

Keller's method proper (E. Keller, "The general quadratic optimization problem", Mathematical Programming 5, 1973; Algorithm 4.3.2 in Cottle, Pang and Stone) additionally employs 2x2 block principal pivots and a negative lower-bound device in order to robustly handle zero-diagonal degeneracies in matrices that are only positive semi-definite or (row) sufficient. Those features are not implemented here; on such a degeneracy this solver simply reports Status#NO_SOLUTION. For nondegenerate SPSD problems, Keller's method and the simple method implemented here produce identical pivot sequences.

Compared with DantzigLCPSolver, this class performs dense explicit tableau pivots (recomputing the pivoted matrix at each step), solves only unbounded LCPs (not BLCPs), and does not support warm starting. It is therefore best regarded as a simple reference implementation, and DantzigLCPSolver should be preferred for performance.

Further background can be found in Claude Lacoursiere's Ph.D. thesis, Ghosts and Machines: Regularized Variational Methods for Interactive Simulations of Multibodies with Dry Frictional Contact (2007), and in "Algorithms for Linear Complementarity Problems" by Joaquim Judice (1994).

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	Z_FREE
static int	Z_LOWER_BOUNDED
static int	Z_UPPER_BOUNDED

Fields inherited from interface maspack.solvers.LCPSolver

INF, W_VAR_LOWER, W_VAR_UPPER, Z_VAR

Constructor Summary

Constructors

Constructor and Description
SimpleLCPSolver() Creates a new simple LCP solver.

Method Summary

Modifier and Type	Method and Description
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	getTolerance() Returns the numeric tolerance 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.
void	mulPivotedMatrix(double[] res, double[] vec) Multiplies the pivoted system matrix, produced by the last solve, by a vector.
void	mulPivotedMatrix(MatrixNd MR, MatrixNd M1) Multiplies the pivoted system matrix, produced by the last solve, by another matrix.
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	setDebug(int code)
void	setIterationLimit(int limit) Sets the iteration limit for this solver.
void	setTolerance(double tol) Sets the numeric tolerance for this solver.
LCPSolver.Status	solve(VectorNd z, VectorNd w, VectorNi state, MatrixNd M, VectorNd q, VectorNd lo, VectorNd hi, int nub) Returns Status#UNIMPLEMENTED since BLCP problems are not supported by this solver class.
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_ALL

public static final int SHOW_ALL

See Also:

Constant Field Values

Z_FREE

public static final int Z_FREE

See Also:

Constant Field Values

Z_UPPER_BOUNDED

public static final int Z_UPPER_BOUNDED

See Also:

Constant Field Values

Z_LOWER_BOUNDED

public static final int Z_LOWER_BOUNDED

See Also:

Constant Field Values

Constructor Detail

SimpleLCPSolver

public SimpleLCPSolver()

Creates a new simple LCP solver.

Method Detail

getDebug

public int getDebug()

setDebug

public void setDebug(int code)

getTolerance

public double getTolerance()

Returns the numeric tolerance 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 Keller'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.

solve

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

Returns Status#UNIMPLEMENTED since BLCP problems are not supported by this solver class.

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.

mulPivotedMatrix

public void mulPivotedMatrix(double[] res,
                             double[] vec)

Multiplies the pivoted system matrix, produced by the last solve, by a vector.

Parameters:

res - used to store result

vec - vector to be multiplied

mulPivotedMatrix

public void mulPivotedMatrix(MatrixNd MR,
                             MatrixNd M1)

Multiplies the pivoted system matrix, produced by the last solve, by another matrix.

Parameters:

MR - matrix result

M1 - matrix to be multiplied