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:

../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp33.png

which contains ../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp1.pnginequality constrains and ../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp2.png equality constraints and constraints on the parameter ../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp3.png. If there are lower and upper bounds on the variables ../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp4.png present, i.e. lb and ub, these can be merged to inequalities ../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp5.png. 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 ../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp6.png are removed using eliminateEquations method of the Opt class. The intermediate form of the optimization problem is given as

../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp34.png

with ../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp7.png as the non-basic variables that map to ../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp8.png affinely. Problem ../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp9.png can be transformed effectively when considering the rank of the matrix ../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp10.png. If the rank of matrix ../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp11.png is less than the number of inequalities in ../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp12.png, then vector ../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp13.png can be expressed as a difference of two positive numbers, i.e.

../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp35.png

Using the substitution

../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp36.png

and putting back to ../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp14.png we get

../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp37.png

which is a form suitable for PLCP formulation. If the rank of matrix ../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp15.png is greater or equal than the number of inequalities in ../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp16.png, we can factorize the matrix ../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp17.png rowwise

../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp38.png

where ../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp18.png, ../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp19.png are index sets corresponding to rows from which submatrices are built. The factored system can be written as

../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp39.png

where the matrix ../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp20.png form by rows in the set ../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp21.png must be invertible. Using this substitution the system ../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp22.png can be rewritten in variable ../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp23.png

../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp40.png

which is suitable for PLCP formulation where

../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp41.png

The corresponding PLCP can be written as follows:

../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp42.png

where the problem data are built from MPQP ../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp24.png

../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp43.png

Original solution to MPQP problem ../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp25.png can be obtained by affine map from the variables ../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp26.png and ../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp27.png to ../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp28.png. The matrices of the backward map are stored inside recover property of the Opt class as follows

../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp44.png

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

../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp45.png

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

../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp46.png

with one decision variables ../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp29.png and two parameters ../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp30.png, ../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp31.png. 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 ../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp32.png.
 solution.xopt.fplot('z') 

../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp_img_1.png

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


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

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