How to use MATLAB's Linprog to solve LP model of L1 regression

Question

A L1 regression problem is given as:

$\min\limits_{a,b} \sum\limits_{i=1}^n |y_i - ax_i - b|$

It has an equivalent LP model:

$\min \sum\limits_{i = 1}^n z_i$

$|y_i - ax_i - b| \leq z_i$

where $z_i$ are the auxiliary variables

Can someone explain how can MATLAB's linprog solve this problem when $(a,b)$ is not in the objective function?

For example, let's say we are given two data points, currently I have the objective function as

f = [1 1]; %i.e. objective z_1 + z_2

A = [-1 -x_1 -1; -1 -x_2 -2]; %i.e. constrains [z_1 a b; z_2 a b]

b = [-1 1]; %i.e. [z_1 a b; z_2 a b] = [y_1 y_2]

linprog(f,A,b)

When I type this into MATLAB I receive:

Error using linprog (line 233) The number of columns in A must be the same as the number of elements of f.

Obviously because I have not worked $(a,b)$ pair into the objective function but I have them in the constrain equation

How do I let linprog find both the $z_i$'s, $a$ and $b$?

Answer 1

Simply put 0 coefficients in the objective function for the terms corresponding to the other variables.

Your example was unclear, so I'll construct a simple one. Suppose that

y=[1; 2] x=[3; 4]

Then the problem can be written as

$\min z_{1} + z_{2}$

subject to

$ | 1 - 3a- b | \leq z_{1}$

$ | 2 - 4a- b | \leq z_{2}$

Converting the absolute value inequalities into pairs of linear inequalities and adding slack variables gives:

$\min z_{1}+z_{2}$

subject to

$ -3a-b +s_{1} -z_{1}=-1 $

$ +3a+b + s_{2}-z_{1} =1$

$ -4a-b + s_{3} -z_{2} = -2$

$ +4a+b+s_{4}-z_{2} = 2$

Letting the vector $v=\left[ a\; b\; s1\; s2\; s3\; s4\; z1\; z2\right]^{T}$, the problem is

$\min fv$

subject to

$Av=b$

$v_{3}, v_{4}, v_{5}, v_{6}, v_{7}, v_{8} \geq 0$

$v_{1}, v_{2}\;\; \mbox{unrestricted in sign}$

where

$A=\left[\begin{array}{cccccccc} -3 & -1 & +1 & 0 & 0 & 0 & -1 & 0 \\ +3 & +1 & 0 & +1 & 0 & 0 & -1 & 0 \\ -4 & -1 & 0 & 0 & +1 & 0 & 0 & -1 \\ +4 & +1 & 0 & 0 & 0 & +1 & 0 & -1 \\ \end{array}\right]$

and

$f=\left[\begin{array}{cccccc} 0 & 0 & 0 & 0 & 0 & 0 & +1 & +1 \\ \end{array}\right]$

and

$b=\left[ \begin{array}{c} -1 \\ +1 \\ -2 \\ +2 \\ \end{array} \right]$