Infinity norm == 1

MIDCP
1

Hello,

I am doing something like the following but that runs the optimizer several times, which is slow.

for i = 1:nDimY
cvx_begin quiet
      variables W_y(nDimY) W_x(nDimX)
      minimize (norm(W_y'*trout - W_x'*trin,2))
      subject to
           W_y(i) == 1
cvx_end
end

Result is the minimum of the loop. Assuming that 0 <= W_y(i) <=1 then I can write

subject to
     norm(W_y,Inf) == 1

as a convex optimization task
but that constraint is not allowed. Can I reword this constraint in a way CVX will appreciate?

Thanks

2

Prove it is convex, please. I will follow up with further suggestions once you have done so. Instead of posting a new answer just edit your question above.

3

Inside of the loop is convex and CVX works fine like that. The final results is min(r1, r2, r3,…,rn) which is combining the results of each iteration. So the optimization is convex. But my workaround is slow.

4

Yes. It is convex in the loop. The combined model is not convex. The fact that you can reach a global solution by enumerating all nDimY combinations is not evidence of convexity. Just the opposite—it’s evidence of nonconvexity.

5

But I think it can be expressed as a mixed-integer convex model. Again, that is nonconvex, but at least solvers like MOSEK and Gurobi can handle it with branch-and-bound techniques. Before I offer that suggestion, I need to ask: are W_x and/or W_y positive? If so, add those constraints…

6

Thank you for your help. No they are not positive. But I can bound them from top and bottom. say -1 <= Wx , Wy <= 1

7

OK, that’s good. It’s definitely worthwhile to include such bounds in your model whenever you know them.

8

What it seems like you want to do is to ensure that at least one of the elements of W_y is exactly one. This is not a convex constraint, but it can be represented with a binary variable. As you said in your comments, you can bound W_y by -1 and 1, which helps. I think this will accomplish that:

cvx_begin quiet
      variables W_y(nDimY) W_x(nDimX)
      binary variable b(nDimY)
      minimize (norm(W_y'*trout - W_x'*trin,2))
      subject to
           -1 <= W_x <= 1
           2*b-1 <= W_y <= 1
           sum(b) >= 1
cvx_end

Notice that when b(i) is equal to one, the corresponding constraint for W_y(i) is -1 <= W_y(i) <= 1, which is satisfied only if W_y(i)==1. The constraint sum(b) >= 1 ensures that at least one of the values of b is nonzero.

Keep in mind that you need MOSEK or Gurobi to solve this problem, along with a CVX Professional license.