TOMLAB OPTIMIZATION ENVIRONMENT: L1LinSolve

L1LinSolve

Purpose

For finding a linearly constrained L1 solution of a function of several variables with the use of any suitable TOMLAB LP solver

Syntax

   Result = L1LinSolve(Prob, PriLev);

Description

Finds a linearly constrained L1 solution of a function of several variables with the use of any suitable TOMLAB LP solver

Problem

        min  sum_i |Cx - y| + alpha*|Lx|, where y is in R^m
         x
        s/t   x_L <=   x  <= x_U, x is in R^n
              b_L <= A x  <= b_U

The L1 problem is solved in L1LinSolve by rewriting the problem as a linear programming problem.

 A set of m additional variables v, stored as x(n+1:m), and 
 a set of m additional variables z, stored as x(n+m+1:n+2*m), is added

If damping alpha is nonzero and nonempty:

 A set of n additional variables r, stored as x(n+2m+1:n+2m+n), and 
 a set of n additional variables s, stored as x(n+2m+n+1:n+2m+2*n), is added

        min    sum_i(v_i+z_i + alpha(r_i+s_i))
         x
        s/t   x_L <=   x              <= x_U
                0 <=   y              <= Inf
                0 <=   z              <= Inf
                0 <=   r              <= Inf
                0 <=   s              <= Inf
              b_L <= A x              <= b_U
                y <= C x  + v - z     <= y
                0 <= L x  + r - s     <= 0

Example

See L1LinDemo.m in tomlab\examples

Input Parameters

   Prob       Structure Prob. Prob must be defined!!! 
              Best is to use Prob = llsAssign(.....), if using the TQ format.
              The problem should be created in the Tomlab linear 
              least squares format (lls)

   PriLev     The second input argument. Default == 2.
              If PriLev == 0, L1LinSolve is silent, except for error messages.
              If > 0, L1LinSolve prints summary output about problem
              transformation
              L1LinSolve calls PrintResult(Result,PriLev), i.e. printing in
              PrintResult is made if PriLev > 0. 
              PriLev == 2 displays standard output in PrintResult. 

Extra fields used in Prob:

   SolverL1    Name of the Tomlab solver. Valid names are:
               lpSolve, qld
               If Tomlab /MINOS is installed: minos, lpopt, qpopt
               If Tomlab /SOL is installed: sqopt, snopt, npopt
               If Tomlab /Xpress is installed: xpress-mp
               If Tomlab /Cplex is installed: cplex
               If Tomlab /MINLP is installed: bqpd

   LS.C       Linear matrix C m x n
   LS.y       Data vector y m x 1
   LS.damp    Damping parameter alpha
   LS.L       Damping matrix L in damping term alpha*||Lx||

The rest of the fields in Prob should be defined as wanted by the selected solver. See the help for the solver.

In particular:

   x_0:     Starting point
   x_L:     Lower bounds for x
   x_U:     Upper bounds for x
   b_L:     Lower bounds for linear constraints
   b_U:     Upper bounds for linear constraints
   A:       Linear constraint matrix

Output Parameters

 Result Structure with results from optimization. See help for the used solver
        The output in Result, i.e. fields Result.x_k, Result.r_k, Result.J_k,
        Result.x_0, Result.xState, Result.cState,
        Result.v_k, is transformed back to the original problem. 
        Result.g_k is Result.J_k'*Result.r_k.
        The output in Result.Prob is the result after L1LinSolve
        transformed the problem, i.e. the altered Prob structure

infSolve

L1Solve