eliminateEquations

Purpose

Reduce LP/QP/MPLP/MPQP by removing equality constraints

Syntax

problem.eliminateEquations
eliminateEquations(problem)

Description

Remove equality constraints involved in LP, QP, MPLP, and MPQP of the dimension ../../../../../fig/mpt/modules/solvers/@Opt/eliminateequations1.png to get optimization problem in the dimension ../../../../../fig/mpt/modules/solvers/@Opt/eliminateequations2.png where ../../../../../fig/mpt/modules/solvers/@Opt/eliminateequations3.png stands for the number of equalities. Consider the following MPQP

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

which contains ../../../../../fig/mpt/modules/solvers/@Opt/eliminateequations4.pnginequality constrains and ../../../../../fig/mpt/modules/solvers/@Opt/eliminateequations5.png equality constraints. To be able to reduce the optimization problem to a simpler form, it is required that the system of linear equations ../../../../../fig/mpt/modules/solvers/@Opt/eliminateequations6.png is consistent, i.e. no linearly dependent rows are found and the number of equalities ../../../../../fig/mpt/modules/solvers/@Opt/eliminateequations7.png is strictly less than number of variables ../../../../../fig/mpt/modules/solvers/@Opt/eliminateequations8.png, i.e. ../../../../../fig/mpt/modules/solvers/@Opt/eliminateequations9.png. The principle is based on factorizing equality constraints ../../../../../fig/mpt/modules/solvers/@Opt/eliminateequations10.png in basic ../../../../../fig/mpt/modules/solvers/@Opt/eliminateequations11.png and non-basic variables ../../../../../fig/mpt/modules/solvers/@Opt/eliminateequations12.png, i.e.

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

which gives

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

where the index sets Bc, Nc denote the columns from which factored system is built. The factored submatrix ../../../../../fig/mpt/modules/solvers/@Opt/eliminateequations13.png must be invertible in order to express basic variables as a function of non-basic variables, i.e.

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

Using the substitution

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

and

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

the relation between basic and non-basic variables is simplified to

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

The above MPQP problem ../../../../../fig/mpt/modules/solvers/@Opt/eliminateequations14.png can be expressed only in non-basic variables ../../../../../fig/mpt/modules/solvers/@Opt/eliminateequations15.png as follows:

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

where

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

Original solution to LP/QP problem ../../../../../fig/mpt/modules/solvers/@Opt/eliminateequations16.png can be obtained via relation ../../../../../fig/mpt/modules/solvers/@Opt/eliminateequations17.png. The matrices of the backward map are stored inside recover property of the Opt class as follows

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

where the matrix Y corresponds to ../../../../../fig/mpt/modules/solvers/@Opt/eliminateequations18.png and the matrix th to ../../../../../fig/mpt/modules/solvers/@Opt/eliminateequations19.png in ../../../../../fig/mpt/modules/solvers/@Opt/eliminateequations20.png. Note the the reduced problem ../../../../../fig/mpt/modules/solvers/@Opt/eliminateequations21.png has different cost function as the original problem.

Input Arguments

problem

LP/QP/MPLP/MPQP optimization problem given as Opt class.

Class: Opt

Example(s)

Example 1

Consider LP optimization problem with the following data
 f = [-1 1 2]; 

 A = [1 -1 0.4; 0.5 -9 -2; 0.5 -1 0; -5.1 -1 -3]; 

 b = [1; 2; 2; 4]; 

 Ae = [1 0 0]; be = 1; 
 Create the problem 
 problem = Opt('A',A,'b',b,'f',f,'Ae',Ae,'be',be) 
-------------------------------------------------
Linear program
	Num variables:                3
	Num inequality constraints:   4
	Num equality constraints:     1
	Solver:                     LCP
-------------------------------------------------
The problem has equality constraint ../../../../../fig/mpt/modules/solvers/@Opt/eliminateequations22.png which can be verified by solving the problem.
 r = problem.solve 
r = 

        xopt: [3x1 double]
      lambda: [1x1 struct]
         obj: -6.884
         how: 'ok'
    exitflag: 1

 r.xopt 
ans =

                         1
                     0.548
                    -3.216

We can eliminate the equality constaint by calling
 problem.eliminateEquations 
-------------------------------------------------
Linear program
	Num variables:                2
	Num inequality constraints:   4
	Num equality constraints:     0
	Solver:                     LCP
-------------------------------------------------
The solution and the objective value is different
 rn = problem.solve 
rn = 

        xopt: [2x1 double]
      lambda: [1x1 struct]
         obj: -6.884
         how: 'ok'
    exitflag: 1

 rn.xopt 
ans =

                    -3.216
                     0.548

The mapping between the variables in the old and new problem are stored inside recover property.
 problem.recover 
ans = 

     Y: [3x2 double]
    th: [3x1 double]

To get the original solution, use
 xold = problem.recover.Y*rn.xopt + problem.recover.th 
xold =

                         1
                     0.548
                    -3.216

We can see that the solution is the same
 r.xopt - xold 
ans =

     0
     0
     0

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


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

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