mpt_plcp
Purpose
Parametric linear complementarity solver (PLCP) (without errorchecks)
Syntax
R = mpt_plcp(S)
Description
Implementation of the lexicographic PLCP solver. The PLCP is given as:

where the matrices
,
,
, and vectors
,
are the
problem data, then
,
are the decision variables and
are the parameters.
Structure of the algorithm:
-
Initialisation phase: For any feasible starting point
solve non-parametric
LCP to get feasible basis. The basis is used to determine the initial region
with the corresponding
optimal pair
and
.
-
Exploration phase: For each facet of the initial region
compute its neighbors
by performing lex-pivot steps in the PLCP subproblem. Compute the graph based on the found neighbors. Store
basis of every region to a corresponding hash-table.
-
Termination phase: Verify the graph of the solution, evaluate the statistics.
The algorithm uses variable step approach for exploration of the parameter space by default. The fixed step approach
can be turned on via option fixed_step. Parameter exploration is based on a graph search: depth-first search (BFS)
and breadth-first search (BFS) methods are considered, the default is BFS.
When the computer runs in a parallel mode, the exploration phase run in a parallel for-loop automatically, which
can potentially increases the computational speed.
Any change in default options must be done using mptopt class. Following options can be modified:
-
bfs - Logical value that determines if to use BFS for exploration of the parameter space (default=1).
-
dfs - Logical value that determines if to use DFS for exploration of the parameter space (default=0).
-
debug - Integer value that determines the debugging level (default=0).
-
maxlayers - For BFS-type of exploration, this value limits the number of "layers" starting from the
initial region
. The first layer is defined as the collection of regions that are adjacent to
,
the second layer is given as the new found neighbors to all regions in the first layer etc. The default value is Inf.
-
maxregions - The maximal number of regions to be produced by PLCP algorithm. This option is useful when solving
large PLCP problems when there are memory problems. The default value is Inf.
-
QRfactor - Logical value that select the type of factorization to use for pivoting. If true, then recursive QR
factorization is used instead of direct sparse LU factorization by default. The default value is 0.
-
checkoverlaps - Logical value that launches overlap checking if true. Very time consuming operation, therefore the
default value is 0.
-
rescue - If the variable step approach fails to find all the neighbors, this logical statement indicates if the use
the fixes-step approach as a backup. If true, then the fixed-step approach is run whenever variable step approach does not
find overlaps. The disadvantage of fixed step is, however, overlaps can be produced, specially for degenerate cases. The
default value is 0.
-
maxsteps - If the fixed step approach is turned on, this value limits the number of steps to be performed to find
neighbor. The step size is given by the region_tol. The default value is 200.
-
maxpivots - The maximum limit on the lex-pivot steps to be performed when finding a neighbor. Typically, it suffices
1-2 pivots to find a neighbor. If the problem is very degenerate, or badly posed, or due to numerical problems involved in
factorization, the pivot steps are repeated up to 100-times, which is the default value.
-
cacheregions - This flag causes that regions that have been discovered are remembered and used
for faster exploration of the parameter space. The default value is 1.
Note that to properly preprocess data to PLCP, use Opt class whenever possible. This will avoid unnecessary
numerical problems caused by improper formulation of the problem.
Input Arguments
S |
Structure of the Opt class.
Class: struct |
S.M |
Data matrix for linear-complementarity problem .
Class: double
|
S.q |
Right hand side vector for linear-complementarity problem .
Class: double
|
S.Ath |
Linear part of the inequality constraints .
Class: double
Default: []
|
S.bth |
Right hand side of the inequality constraints .
Class: double
Default: []
|
S.recover |
Affine map for MPLP/MPQP problems after transformation to LCP.
Class: struct |
S.recover.uX |
Matrix of the affine map .
The map is from the optimization variables involed in LCP and in the original LP/QP.
Class: double
Default: []
|
S.recover.uTh |
Matrix of the affine map .
The map is from the optimization variables involed in LCP and in the original LP/QP.
Class: double
Default: []
|
S.recover.lambdaX |
Matrix of the affine map .
The map is from the optimization variables involed in LCP and the Lagrangian multipliers in the original LP/QP.
Class: double
Default: []
|
S.recover.lambdaTh |
Matrix of the affine map .
The map is from the optimization variables involed in LCP and the Lagrangian multipliers in the original LP/QP.
Class: double
Default: []
|
Default: []
S.Internal |
Internal data that came from transformation from LP/QP to LCP.
Class: struct |
S.Internal.H |
Quadratic part of the objective function.
Class: double
Default: []
|
S.Internal.f |
Linear part of the objective function.
Class: double
|
S.Internal.pF |
Linear part of the objective function for parameters.
Class: double
Default: []
|
Default: []
Output Arguments
R |
Result structure
Class: struct |
R.xopt |
Partition of the polyhedra with the associated function values for and variables.
Class: PolyUnion
|
R.exitflag |
An integer value that informs if the result was feasible (1), or otherwise (different from 1).
Class: double
|
R.how |
A string that informs if the result was feasible ('ok'), or if any problem appeared through optimization.
Class: char
|
R.solveTime |
How long did the computation take in seconds.
Class: double
|
R.stats |
Statistical information about the computation: the total number of pivots performed, the total number of facets traversed.
Class: struct |
R.stats.pivs |
The total number of pivots performed.
Class: double
|
R.stats.facetsTraversed |
The total number of facets that have been traversed.
Class: double
|
References
[1]
Richard W. Cottle, Jong-Shi Pang, Richard E. Stone: Linear complementarity problem, Academic Press Inc. 1992
[2]
C.N. Jones, M. Morari: Multiparametric Linear Complementarity Problems, IEEE Conference on Decision and Control, 2006
See Also
mpt_solvemp, lcp
◀ |
mpt_detect_solvers |
|
mpt_call_qpc |
▶ |
© 2010-2013 Colin Neil Jones: EPF Lausanne, colin.jones@epfl.ch
© 2010-2013 Martin Herceg: ETH Zurich, herceg@control.ee.ethz.ch