L-1 norm at equality

MIDCP
1

Given the decision var x, I am not able to satisfy the following two constraints together (there are other objectives and constraints)

norm(x, 1) <= L
-B <= x <= B

Ideally, I am trying to get the first constr to be satisfied at equality, but, that would be non-convex so have the inequality instead. It seems that when I don’t use the second inequality, then, the first becomes satisfied at equality. However, I needed both with the first to be satisfied near equality. Could I add some constraint on “x” (like a lower bound) so that the first become satisfied? I know that a lower bound on L-1 isn’t convex though there are heuristics to deal with it, but, would like to avoid this. Thank you.

2

It is possible to model the L=1 Norm equality constraint in CVX using binary variables to handle the non-convexity, resulting in an MIDCP. It might be a little messy, so I leave the details to you.

If you use YALMIP, and have explicit lower and upper bounds on all involved variables, I think it can do this reformulation as an MIDCP for you.

Here is a simple YALMIP code to minimize sum(x) subject to your desired constrains:

x=sdpvar(2,1);
optimize([norm(x,1)==1,0<=x<=1],sum(x))

If the solver is not specified, YALMIP will choose a MILP solver, such as Gurobi, to solve this.

3

Thank you - is there a reference that shows how to convert the L1-norm equality problem using binary vars? Would mosek be able to solve it? Thank you.

4

Yes, https://docs.mosek.com/modeling-cookbook/mio.html#exact-1-norm

5

Yes, that (Conic) Modeling Cookbook is of great value for CVX, YALMIP, CVXPY, and CVXR users, whether or not using Mosek. The Conic Modeling Cheatsheet https://docs.mosek.com/cheatsheets/conic.pdf is also handy. I suspect that @Michal_Adamaszek was one of the main authors of both of those, but he’s too modest to brag about it.

Yes, Mosek can be used as solver when doing this in CVX. Gurobi also could be used, provided that there are no SDP constraints (although it appears there are some bugs in the CVX/Gurobi interface, sometimes resulting in correct solutiobns reported by CVX)… I think YALMIP reformulates (under the hood) the L1 norm equality in a manner similar to what is shown in the link. CVX makes you di it yourself.