maspack.solvers
Class DantzigLCPSolver

java.lang.Object
  extended by maspack.solvers.DantzigLCPSolver

public class DantzigLCPSolver
extends java.lang.Object

Solves linear complementarity problems (LCPs) for symmetric positive semi-definite (SPSD) matrices using Dantzig's method. An LCP is defined by the linear system

 w = M z + q
 
and solving it entails finding w and z subject to the constraints
                  T
 w >= 0, z >= 0, w z = 0
 
Dantig's method does this by a series of pivoting operations. Each pivot corresponds to one solver iteration and entails the exchange of a single variable w_i with its complementary counterpart z_i. A sequence of pivots results in the pivoted system
 w' = M' z' + q'
 
where w' and z' contain complementary combinations of the w and z variables. Any variable (w or z) contained in w' is called a basic variable. When a pivoted system is found for which q' >= 0, this provides a solution to the LCP in which the z and w variables comprising z' are 0 and the z and w variables comprising w' are equal to the corresponding entries in q'. As mentioned above, Dantzig's method only works when M is SPSD.

Full details on the solution of LCPs can be found in The Linear Complementarity Problem, by Cottle, Pang, and Stone.


Nested Class Summary
static class DantzigLCPSolver.Status
          Described whether or not a solution was found.
 
Field Summary
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
           
static int W_VAR_LOWER
           
static int W_VAR_UPPER
           
static int Z_VAR
           
 
Constructor Summary
DantzigLCPSolver()
          Creates a new Dantzig solver.
 
Method Summary
 int getDebug()
           
 int getIterationCount()
          Returns the number of iterations, or pivots, that were used in the most recent solution operation.
 int getIterationLimit()
          Gets the iteration limit for this solver.
 double getTolerance()
          Returns the numeric tolerence for this solver.
 void resolve(VectorNd z, VectorNd q, boolean[] zBasic)
          Solves the system
 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.
 DantzigLCPSolver.Status solve(VectorNd z, MatrixNd M, VectorNd q, boolean[] zBasic)
          Solves the LCP
 DantzigLCPSolver.Status solve(VectorNd z, VectorNd w, MatrixNd M, VectorNd q, VectorNd lo, VectorNd hi, int nub, int[] state)
           
 
Methods inherited from class java.lang.Object
equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

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

Z_VAR

public static int Z_VAR

W_VAR_LOWER

public static int W_VAR_LOWER

W_VAR_UPPER

public static int W_VAR_UPPER
Constructor Detail

DantzigLCPSolver

public DantzigLCPSolver()
Creates a new Dantzig solver.

Method Detail

getDebug

public int getDebug()

setDebug

public void setDebug(int code)

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, or pivots, that were used in the most recent solution operation.

Returns:
iteration count for last solution

solve

public DantzigLCPSolver.Status solve(VectorNd z,
                                     MatrixNd M,
                                     VectorNd q,
                                     boolean[] zBasic)
Solves the LCP
 w = M z + q
 
where M is SPSD. It is possible to use this routine to solve a mixed LCP, by pre-pivoting M and q to make the relevant non-LCP z variables basic and presetting the corresponding entries for these variables in zBasic to true.

Parameters:
z - returns the solution for z
M - system matrix
q - system vector
zBasic - On output, identifies which z variables are basic in the solution. On input, identifies z variables which have been made basic as part of solving a mixed LCP. If the LCP is not mixed, then all entries in this array should be set to false.
Returns:
Status of the solution.

resolve

public void resolve(VectorNd z,
                    VectorNd q,
                    boolean[] zBasic)
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
zBasic - (optional) if specified, returns which z variables are basic in the solution.

solve

public DantzigLCPSolver.Status solve(VectorNd z,
                                     VectorNd w,
                                     MatrixNd M,
                                     VectorNd q,
                                     VectorNd lo,
                                     VectorNd hi,
                                     int nub,
                                     int[] state)