mpt_call_lcp

Purpose

A gateway function to LCP solver (without errorchecks)

Syntax

R = mpt_call_lcp(S)

Description

The function implements calls to LCP solver based on the optimization problem to be solved. Supported problems are LCP, LP, and QP. If the problem type is LCP, then LCP mex-function is called directly. Otherwise a transformation to LCP problem is performed. Assume that QP/LP is written in a form

../../../../fig/mpt/modules/solvers/mpt_call_lcp41.png

We want to transform it to

../../../../fig/mpt/modules/solvers/mpt_call_lcp42.png

which corresponds to the following LCP

../../../../fig/mpt/modules/solvers/mpt_call_lcp43.png

where

../../../../fig/mpt/modules/solvers/mpt_call_lcp44.png

If LP or QP contains equality constraints, these are removed first. It is required that the system of linear equations ../../../../fig/mpt/modules/solvers/mpt_call_lcp1.png is consistent, i.e. no linearly dependent rows are found and the number of equalities is strictly less than number of variables. The principle is based on factorizing equality constraints ../../../../fig/mpt/modules/solvers/mpt_call_lcp2.png in basic ../../../../fig/mpt/modules/solvers/mpt_call_lcp3.png and non-basic variables ../../../../fig/mpt/modules/solvers/mpt_call_lcp4.png, i.e.

../../../../fig/mpt/modules/solvers/mpt_call_lcp45.png

which gives

../../../../fig/mpt/modules/solvers/mpt_call_lcp46.png

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

../../../../fig/mpt/modules/solvers/mpt_call_lcp47.png

With the substitution

../../../../fig/mpt/modules/solvers/mpt_call_lcp48.png

and

../../../../fig/mpt/modules/solvers/mpt_call_lcp49.png

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

../../../../fig/mpt/modules/solvers/mpt_call_lcp50.png

The above QP/LP problem ../../../../fig/mpt/modules/solvers/mpt_call_lcp6.png can be expressed only in non-basic variables ../../../../fig/mpt/modules/solvers/mpt_call_lcp7.png as follows:

../../../../fig/mpt/modules/solvers/mpt_call_lcp51.png

where

../../../../fig/mpt/modules/solvers/mpt_call_lcp52.png

Original solution to QP problem ../../../../fig/mpt/modules/solvers/mpt_call_lcp8.png can be obtained via relation ../../../../fig/mpt/modules/solvers/mpt_call_lcp9.png. Problem ../../../../fig/mpt/modules/solvers/mpt_call_lcp10.png can be transformed to ../../../../fig/mpt/modules/solvers/mpt_call_lcp11.png effectively when considering the rank of the matrix ../../../../fig/mpt/modules/solvers/mpt_call_lcp12.png. If the rank of matrix ../../../../fig/mpt/modules/solvers/mpt_call_lcp13.png is less than the number of inequalities in ../../../../fig/mpt/modules/solvers/mpt_call_lcp14.png vector ../../../../fig/mpt/modules/solvers/mpt_call_lcp15.png can be expressed as a difference of two positive numbers, i.e.

../../../../fig/mpt/modules/solvers/mpt_call_lcp53.png

With the substitution

../../../../fig/mpt/modules/solvers/mpt_call_lcp54.png

and putting back to ../../../../fig/mpt/modules/solvers/mpt_call_lcp16.png we get

../../../../fig/mpt/modules/solvers/mpt_call_lcp55.png

which is a form equivalent to ../../../../fig/mpt/modules/solvers/mpt_call_lcp17.png. If the rank of matrix ../../../../fig/mpt/modules/solvers/mpt_call_lcp18.png is greater or equal than the number of inequalities in ../../../../fig/mpt/modules/solvers/mpt_call_lcp19.png, we can factorize the matrix ../../../../fig/mpt/modules/solvers/mpt_call_lcp20.png rowwise

../../../../fig/mpt/modules/solvers/mpt_call_lcp56.png

where ../../../../fig/mpt/modules/solvers/mpt_call_lcp21.png, ../../../../fig/mpt/modules/solvers/mpt_call_lcp22.png are index sets corresponding to rows from which submatrices are built. The factored system ../../../../fig/mpt/modules/solvers/mpt_call_lcp23.png can be written as

../../../../fig/mpt/modules/solvers/mpt_call_lcp57.png

where the matrix ../../../../fig/mpt/modules/solvers/mpt_call_lcp24.png form by rows in the set ../../../../fig/mpt/modules/solvers/mpt_call_lcp25.png must be invertible. Using the substitution

../../../../fig/mpt/modules/solvers/mpt_call_lcp58.png

the system ../../../../fig/mpt/modules/solvers/mpt_call_lcp26.png can be rewritten in variable ../../../../fig/mpt/modules/solvers/mpt_call_lcp27.png

../../../../fig/mpt/modules/solvers/mpt_call_lcp59.png

which is equivalent to ../../../../fig/mpt/modules/solvers/mpt_call_lcp28.png.

Input Arguments

S

Structure of the Opt class.

Class: struct

S.H

Quadratic part of the objective function.

Class: double

Default: []

S.f

Linear part of the objective function.

Class: double

S.A

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

Class: double

S.b

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

Class: double

S.Ae

Linear part of the equality constraints ../../../../fig/mpt/modules/solvers/mpt_call_lcp31.png.

Class: double

Default: []

S.be

Right hand side of the equality constraints ../../../../fig/mpt/modules/solvers/mpt_call_lcp32.png.

Class: double

Default: []

S.lb

Lower bound for the variables ../../../../fig/mpt/modules/solvers/mpt_call_lcp33.png.

Class: double

Default: []

S.ub

Upper bound for the variables ../../../../fig/mpt/modules/solvers/mpt_call_lcp34.png.

Class: double

Default: []

S.M

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

Class: double

S.q

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

Class: double

S.n

Problem dimension (number of variables).

Class: double

S.m

Number of inequalities in ../../../../fig/mpt/modules/solvers/mpt_call_lcp37.png.

Class: double

S.me

Number of equalities in ../../../../fig/mpt/modules/solvers/mpt_call_lcp38.png.

Class: double

S.problem_type

A string specifying the problem to be solved (only LP, QP and LCP problems are allowed).

Class: char

S.routine

An integer specifying which subroutine to use for factorization. For details, see help for LCP solver.
  • The number 0 indicates to use fast recursive factorization based on rank-1 updates from LUMOD package.
  • The number 1 indicates to use LU factorization based on DGESV routine of LAPACK.
  • The number 2 indicates to use QR factorization based on DGELS routine of LAPACK.

Class: double

S.test

Call (false) or not to call (true) MPT global settings.

Class: logical

Default: false

Output Arguments

R

Result structure

Class: struct

R.xopt

The optimal values for variable ../../../../fig/mpt/modules/solvers/mpt_call_lcp39.png.

Class: double

R.lambda

The optimal values for variable ../../../../fig/mpt/modules/solvers/mpt_call_lcp40.png.

Class: double

R.obj

If the LCP problem was created by conversion from LP/QP, this value represent the optimal cost of the appropriate LP/QP.

Class: double

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

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

mpt_solve


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