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:

../../../../fig/mpt/modules/solvers/mpt_plcp31.png

where the matrices ../../../../fig/mpt/modules/solvers/mpt_plcp1.png, ../../../../fig/mpt/modules/solvers/mpt_plcp2.png, ../../../../fig/mpt/modules/solvers/mpt_plcp3.png, and vectors ../../../../fig/mpt/modules/solvers/mpt_plcp4.png,../../../../fig/mpt/modules/solvers/mpt_plcp5.png are the problem data, then ../../../../fig/mpt/modules/solvers/mpt_plcp6.png, ../../../../fig/mpt/modules/solvers/mpt_plcp7.png are the decision variables and ../../../../fig/mpt/modules/solvers/mpt_plcp8.png are the parameters. Structure of the algorithm:
  1. Initialisation phase: For any feasible starting point ../../../../fig/mpt/modules/solvers/mpt_plcp9.png solve non-parametric LCP to get feasible basis. The basis is used to determine the initial region ../../../../fig/mpt/modules/solvers/mpt_plcp10.png with the corresponding optimal pair ../../../../fig/mpt/modules/solvers/mpt_plcp11.png and ../../../../fig/mpt/modules/solvers/mpt_plcp12.png.
  2. Exploration phase: For each facet of the initial region ../../../../fig/mpt/modules/solvers/mpt_plcp13.png compute its neighbors ../../../../fig/mpt/modules/solvers/mpt_plcp14.png 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.
  3. 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: 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

Default: []

Default: []

S

Structure of the Opt class.

Class: struct

S.M

Data matrix for linear-complementarity problem ../../../../fig/mpt/modules/solvers/mpt_plcp17.png.

Class: double

S.q

Right hand side vector for linear-complementarity problem ../../../../fig/mpt/modules/solvers/mpt_plcp18.png.

Class: double

S.Ath

Linear part of the inequality constraints ../../../../fig/mpt/modules/solvers/mpt_plcp19.png.

Class: double

Default: []

S.bth

Right hand side of the inequality constraints ../../../../fig/mpt/modules/solvers/mpt_plcp20.png.

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 ../../../../fig/mpt/modules/solvers/mpt_plcp21.png. The map is from the optimization variables involed in LCP ../../../../fig/mpt/modules/solvers/mpt_plcp22.png and in the original LP/QP.

Class: double

Default: []

S.recover.uTh

Matrix of the affine map ../../../../fig/mpt/modules/solvers/mpt_plcp23.png. The map is from the optimization variables involed in LCP ../../../../fig/mpt/modules/solvers/mpt_plcp24.png and in the original LP/QP.

Class: double

Default: []

S.recover.lambdaX

Matrix of the affine map ../../../../fig/mpt/modules/solvers/mpt_plcp25.png. The map is from the optimization variables involed in LCP ../../../../fig/mpt/modules/solvers/mpt_plcp26.png and the Lagrangian multipliers in the original LP/QP.

Class: double

Default: []

S.recover.lambdaTh

Matrix of the affine map ../../../../fig/mpt/modules/solvers/mpt_plcp27.png. The map is from the optimization variables involed in LCP ../../../../fig/mpt/modules/solvers/mpt_plcp28.png and the Lagrangian multipliers in the original LP/QP.

Class: double

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: []

Output Arguments

R

Result structure

Class: struct

R.xopt

Partition of the polyhedra with the associated function values for ../../../../fig/mpt/modules/solvers/mpt_plcp29.png and ../../../../fig/mpt/modules/solvers/mpt_plcp30.png 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


© 2010-2013 Colin Neil Jones: EPF Lausanne, colin.jones@epfl.ch

© 2010-2013 Martin Herceg: ETH Zurich, herceg@control.ee.ethz.ch