L-1 norm at equality

[Jack]

Given the decision var `x`, I am not able to satisfy the following two constraints together

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.

 

[Johan Löfberg]

It's very confusing what you want to do. x_i = (1/L) will work if (1/L) <= B if you simply want to construct an x

Just because it is nonconvex doesn't mean it cannot be solved. You can add norm(x,1) == L to the model to see how well the resulting MILP model behaves

[Jack]

thank you for your reply. the above has objectives and other constraints as well (i was able to hone down to the two constr, i.e., above, that were giving issues in being satisfied together)

do i need to specify to the solver (mosek) to solve the equality as a MILP? I was getting a DCP err when solving at equality.

[Jack]

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.

[Johan Löfberg]

YALMIP does it automatically for you and thus any MILP solver will work

L1-norm is just as sum of absolute values, which easily is modelled using logics, abs case described here

https://yalmip.github.io/tutorial/logicprogramming/

[Jack]

If i split my x into a positive and negative parts, then, would i need to modify my other objectives and constraints accordingly or can those remain w.r.t. the original x?

How can I go about acquiring the non-negative part of x and declaring it as the vector of binary vars z1? Similarly for z2?

For the L-1 norm above, am thinking that I can do

\sum_i z1_i + \sum_i z2_i = L

?

Thank you.

[Johan Löfberg]

If you want to implement it manually, and you don't want to use the model which I linked to ut want to use the alternative form x=z1-z2,z1>=0,z2>=0, you will simply have to change the logical model to implement the disjunction (x=z1,x>=0) or (-x=z2,-x<=0)

[Jack]

I was trying to understand how the reformulation is done, e.g., for the L-1 norm here

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

I am not sure what the "e" variable in rhs of xm/z2 corresponded to? is this a hyper-param that i have to tune? an interpretation of this would be much appreciated.

And the "z" seems to be a R^n vector of binaries so I just needed to declare that outside and also the continuous z1/xp, z2/xn?

Also, just wanted to confirm that my objectives and constraints that are in "x" can remain as is and won't be affected by these changes?

Thank you again

[Johan Löfberg]

e is the vector of 1

It is the logical model for implies(z == 0, xplus<=0) + implies(z == 1, xminus <= 0) which with x == xplus-xminus implies that xplus + xminus will be abs(x)

If you add xplus and xminus to the model and keep x by equality constraint x == xplus-xminus, you can of course still use x. If you intend to replace x by xplus-xminus, you must change the parts where x is used

[Jack]

 Thank you.

Solving the exact equality problem -- ||x||_1 == 1 -- is turning out to be pretty tedious.

I am wondering if the convex-concave procedure (CCCP) might help to solve:

||x||_1 >= 0.95   &   ||x||_1 <= 1

However, I am getting an error on the first constraint. Is this procedure not applicable for the first one?

Also, since the following inequality is true:

||x||_2 <= ||x||_1

then, could I impose a lower bound on ||x||_2 to help get close to my goal of ||x||_1? Would appreciate any advice on this. Thank you.

[Johan Löfberg]

what do you mean with tedious? and error? There should be no modelling problems with norm(x,1)>=, it should invoke exactly the same MILP machinery as norm(x,1)==

Adding a nonconvex lower bound is just as hard, or harder, as having an equality

A lowr bound on norm(x,2) (or better x'*x) is just as hard or harder. While norm(x,1)>= at least is MILP representable, x'*x>= leads to nonconvex quadratic programming which typically is even more nasty