Solving LP with two $L_1$ inequality constraints

Question

Is there a "fast" way to solve the following LP formulation with the following constraints: $$ \max_{\mathbf{f}} \mathbf{f}'.\mathbf{g} \\ \mathbf{1}'\mathbf{f}=1\\ \|\mathbf{f}-\mathbf{h}\|_1\le \epsilon_1\\ \|\mathbf{f}-\mathbf{k}\|_1\le \epsilon_2$$

$\mathbf{g}, \mathbf{h}, \mathbf{k}, \epsilon_1,\epsilon_2$, are known. $\mathbf{f}$ is a vector and could be large.

Thanks

Answer 1

Since you already have linprog, let's start there. Your challenge is to reformulate into an LP that is as compact as possible. Enumerating the vertices as you are doing is not the way to go about it. Instead, you want to define vector variables $p$, $q$, and do this: $$\begin{array}{ll} \text{maximize} & g^T f \\ \text{subject to} & \vec{1}^T f = 1 \\ & \vec{1}^T p = \epsilon_1 \\ & \vec{1}^T q = \epsilon_2 \\ & - p \preceq f - h \preceq p \\ & - q \preceq f - k \preceq q \end{array}$$ Do you see what's happening here? We are ensuring that $|f_i-h_i|\leq p_i$ and $|f_i-k_i|\leq q_i$, so that $\sum_i p_i$ bounds $\|f-h\|_1$ and $\sum_i q_i$ bounds $\|f-k\|_1$. This is a very standard transformation to convert the $\ell_1$ norm to an LP-compatible form. Of course, now you need to construct the inputs to linprog by stacking the equality constraint and inequality constraint coefficients into matrices. That can get messy.

Now, if you had my software CVX, it would be even easier. You just type this in, and let it take care of the messy transformations under the hood.

cvx_begin
    variable f(n)
    maximize( g' * f )
    subject to
        sum(f) == 1
        norm(f-h,1) <= epsilon1
        norm(f-k,1) <= epsilon2
cvx_end

Do what is fastest for you first, to see if you like the numerical results you're getting. If you do like the results, but you still need more speed, then you'll probably want to hand-code your model for input to a high-performance LP solver like Gurobi, MOSEK, or CPLEX.