eliminateEquations
Purpose
Transforms LP/QP/MPLP/MPQP to LPC/PLCP
Syntax
problem.qp2lcp
qp2lcp(problem)
Description
Transformation of LP, QP, MPLP, and MPQP to LCP/PLCP formulation.
Consider the following MPQP format that is accepted by Opt class:

which contains
inequality constrains and
equality constraints and constraints on the
parameter
. If there are lower and upper bounds on the variables
present, i.e.
lb and ub, these can be merged to inequalities
.
This format is not appropriate for transformation to LCP form because it contains
equality constraints and the inequalities are not nonnegative.
To get appropriate LCP representation, the equality constrains of the problem
are removed using eliminateEquations method
of the Opt class. The intermediate form of the optimization problem is given as

with
as the non-basic variables that map to
affinely.
Problem
can be transformed effectively when
considering the rank of the matrix
.
If the rank of matrix
is less than the number of inequalities in
, then
vector
can be expressed as a difference of two positive numbers, i.e.

Using the substitution

and putting back to
we get

which is a form suitable for PLCP formulation.
If the rank of matrix
is greater or equal than the number of inequalities in
,
we can factorize the matrix
rowwise

where
,
are index sets corresponding to rows from which submatrices are built. The factored system
can be written as

where the matrix
form by rows in the set
must be invertible.
Using this substitution the system
can be rewritten in variable

which is suitable for PLCP formulation where

The corresponding PLCP can be written as follows:

where the problem data are built from MPQP

Original solution to MPQP problem
can be obtained
by affine map from the variables
and
to
. The matrices of the backward map are stored inside
recover property of the Opt class as follows

If the problem was formulated using YALMIP, it is possible that some variables are in the different order. The original
order of variables is stored in problem.varOrder.requested_variables and the map to original variables is given by

Input Arguments
problem |
LP/QP/MPLP/MPQP optimization problem given as Opt class.
Class: Opt
|
Example(s)
Example
1
Consider MPQP in the following form

with one decision variables
and two parameters
,
.
Construct MPQP optimization problem H = 1;
A = [-1; -1]; b = [0.2; 0.4]; pB = [-1, 1; 0.5, -1];
lb = -1; ub = 1;
Ath = [1 0;-1 0;0 1;0 -1]; bth = [1;1;1;1];
problem = Opt('H',H,'A',A,'b',b,'pB',pB,'lb',lb,'ub',ub,'Ath',Ath,'bth',bth)
-------------------------------------------------
Parametric quadratic program
Num variables: 1
Num inequality constraints: 2
Num equality constraints: 0
Num lower bounds 1
Num upper bounds 1
Num parameters: 2
Solver: PLCP
-------------------------------------------------
Transform problem to PLCP form problem.qp2lcp
-------------------------------------------------
Parametric linear complementarity problem
Num variables: 7
Num inequality constraints: 0
Num equality constraints: 0
Num parameters: 2
Solver: PLCP
-------------------------------------------------
Solve the appropriate PLCP solution = problem.solve
mpt_plcp: 3 regions
solution =
xopt: [1x1 PolyUnion]
exitflag: 1
how: 'ok'
stats: [1x1 struct]
Plot the optimizer, for instance the variables
. solution.xopt.fplot('z')

References
[1]
Stephen Boyd and Lieven Vandenberghe: Convex Optimization; Cambridge University Press
[2]
Richard W. Cottle, Jong-Shi Pang, Richard E. Stone: Linear complementarity problem, Academic Press Inc. 1992
See Also
solve, mpt_call_lcp
◀ |
mpt |
|
eliminateequations |
▶ |
© 2010-2013 Colin Neil Jones: EPF Lausanne, colin.jones@epfl.ch
© 2010-2013 Martin Herceg: ETH Zurich, herceg@control.ee.ethz.ch