|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectmaspack.solvers.DantzigLCPSolver
public class DantzigLCPSolver
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 + qand solving it entails finding w and z subject to the constraints
T w >= 0, z >= 0, w z = 0Dantig'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 |
---|
public static final int SHOW_NONE
public static final int SHOW_PIVOTS
public static final int SHOW_MIN_RATIO
public static final int SHOW_QM
public static final int SHOW_VARIABLES
public static final int SHOW_RETURNS
public static final int SHOW_ALL
public static int Z_VAR
public static int W_VAR_LOWER
public static int W_VAR_UPPER
Constructor Detail |
---|
public DantzigLCPSolver()
Method Detail |
---|
public int getDebug()
public void setDebug(int code)
public double getTolerance()
setTolerance(double)
public void setTolerance(double tol)
tol
- new numeric tolerance. Negative numbers will be truncated to 0.getTolerance()
public int getIterationLimit()
public void setIterationLimit(int limit)
limit
- new iteration limitpublic int getIterationCount()
public DantzigLCPSolver.Status solve(VectorNd z, MatrixNd M, VectorNd q, boolean[] zBasic)
w = M z + qwhere 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.
z
- returns the solution for zM
- system matrixq
- system vectorzBasic
- 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.
public void resolve(VectorNd z, VectorNd q, boolean[] zBasic)
w = M z + qusing the same matrix M and active set that was determined in the previous call to solve. Non-active z variables are set to 0.
z
- returns the solution for zq
- system vectorzBasic
- (optional) if specified, returns which z variables are basic in the
solution.public DantzigLCPSolver.Status solve(VectorNd z, VectorNd w, MatrixNd M, VectorNd q, VectorNd lo, VectorNd hi, int nub, int[] state)
|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |