Solving minimize( norm(A*x-b, 1) ) subject to norm(x,2)==1


Hi, I’m new with cvx. I know that this problem is not convex but is there any way of solving the optimization problem minimize( norm(A*x-b, 1) ) subject to norm(x,2)==1?

I wrote this code:

close all;

n = 8;
d = 3;
A = randn(n,d);
b = randn(n,1);

variable x(d)
minimize( norm(A*x-b, 1) )
subject to
x’*x <= 1;

fprintf(‘norm(x) = %f\n’,norm(x));

If I change x’*x<=1 to x’*x==1 it won’t work, but even for this code it sometimes prints that norm(x) is exactly 1. Meaning, cvx actually do solve my problem sometimes. but I need it to always solve it. is it possible? (in Yalmip it worked so I know the problem is solvable).


(Mark L. Stone) #2

YALMIP can handle non-convex problems, bur CVX can not, except those problems which can be modeled as convex except for binary or integer constraints.

x'*x <= 1 is a convex relaxation of x'*x == 1. CVX can solve that convex relaxation, and it may happen that x'*x = 1 (i.e, norm(x) = 1) at the returned optimum, in which case the solution is globally optimal for the non-relaxed non-convex problem. If the optimal x returned is such that x'*x < 1, then all you get is a lower bound on the optimal objective value of the non-relaxed non-convex problem.


Thank you very much for your clarification!
Can you tell me what other tools can solve the problem I mentioned (except for Yalmip)?
Do you know which one is considered the fastest?
When I used yalmip with ‘bnb’ solver it took a long time to solve it for big n (say n=200) and d=2. Here in cvx when I used n=5000 d=2 it solved the problem very quickly (for x’*x<=1) and sometimes it gave me the solution I wanted (norm(x)=1). If I do the same in yalmip I guess it will take hours.
I’d appreciate if you can write to me other tools that I can try.


(Mark L. Stone) #4

YALMIP ought to be able to solve the same relaxed problem as fast as CVX. As for the non-relaxed non-convex problem, there are several solver options available under YALMIP, and I suggest you inquire on the YALMIP forum if you need further guidance on formulation and solution via YALMIP.


Thanks. I didn’t know that yalmip can solve the relaxed problem as fast as cvx. I will ask there about other solvers.
Just to make sure I understand. Solving the relaxed problem can be instantly while solving the unrelaxed problem can take hours eventhough the final result can be the same result. Is that correct?

(Mark L. Stone) #6

The relaxed problem is an easy to solve convex problem. The non-relaxed problem is non-convex and might take a long time to solve to global optimality.


Got it. Thank you for the clarifications.