linear programmingMATLABoptimization
When solving a linear programming problem in MATLAB using linprog of the form
$$ \min c^T x $$
subject to
$$ Ax \leq b, \; \left\| x \right\|_{1} = 1 $$
if we need to enforce the additional constraint that $L_1$ norm of $x$ is $1$, or $\|x\|_1=1$, how can this be converted into a set of inequations of the above form so that the trivial solution $x=0$ can be avoided?
If you have min $\|Ax-b\|_1$ where $A$ is $n\times m$ for $n>m$ and $b$ is $n\times 1$ (so the sum of the absolute values of all the components of the result vector $y=Ax-b$ where y is $n\times 1$) then you can solve this as an LP with linprog with a command like this:
linprog([zeros(m,1);ones(n,1)],[+A,-eye(n);-A,-eye(n)],[b;-b])
which is just a translation into Matlab of the usual trick described on Wikipedia.
Here is a polynomial fitting example that compares least absolute deviations to linear least squares.
clc
x = [0:1/100:1]';
%random polynomial of degree 4
poly = [7/960;-1/8;227/320;-23/15;1]/0.0583;
A = [x.^0,x.^1,x.^2,x.^3,x.^4];
b = A*poly;
% bigger k means less outliers. k = 2 has too many outliers
% for the least absolute deviations solution to lie on the initial
% polynomial
k = 3;
b(k*[1:101/k]) = x(k*[1:101/k]);
% linear least squares
poly = A\b;
y = A*poly;
% least absolute deviations
[n,m] = size(A);
poly = linprog([zeros(m,1);ones(n,1)],[+A,-eye(n);-A,-eye(n)],[b;-b]); poly = poly(1:m);
z = A*poly;
% blue lines: original data
% green lines: least squares solution
% magenta crosses: least absolute deviations solution
% red circles: outliers
plot(x,b,'b-',x,y,'g-',x,z,'m+',x(k*[1:101/k]),x(k*[1:101/k]),'ro')
% check least absolute deviations
check = fminsearch(@(x) norm(A*x-b,1), poly);
[[poly; norm(A*poly-b,1)], [check; norm(A*check-b,1)]]
This is what the output looks like
As far as I know the answer is negative: the point-wise minimum of affine functions is not convex and thus you cannot cast an an LP.
Best Answer
As Brian notes, the problem is not convex. There are two workarounds for this.
It seems like the right hand side of $||x||_1=1$ is arbitrary. Maybe you can replace it with $x_1=1$ (if you know that $x_1\geq 0$)? Or solve two problems: one with $x_1=1$ and one with $x_1=-1$? This only works if you know $x_1 \neq 0$.
You can use binary variables to deal with the nonconvexity: $$ \sum y_i = 1$$ $$ y_i = x_i + s_i$$ $$ y_i = -x_i + t_i$$ $$ 0 \leq s_i \leq M b_i$$ $$ 0 \leq t_i \leq M (1-b_i)$$ $$ y_i \geq 0$$ $$ b_i \in \{0,1\}$$ The big-M constraints set either $s_i=0$ or $t_i=0$. Consequently, $y_i = x_i$ or $y_i = -x_i$. Since $y_i\geq 0$, we obtain $y_i = |x_i|$.