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:

clear;
close all;
clc;

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

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

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).

Thanks

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.

1 Like

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.

Thanks

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.

1 Like

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?

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.

1 Like

Got it. Thank you for the clarifications.