Maximizing the 2 norm of a vector

Nonconvex
1

Dear all,

Is there a way I can re-formulate the maximization problem below to be able to be solved using CVX?

At present, it gives me the error, “Cannot maximize a(n) convex expression.” which makes sense but is there any trick I can use to solve it using CVX?

cvx_begin
variable x(n)
maximize (norm(A*x - b,2))
subject to
l <= x <= u;
cvx_end

1 Like
2

No. That is non-convex.

Bu, presuming all elements of l and u are finite, then because it is a concave programming problem with compact constraints, there must be a global optimum at an extreme of the constraints, i.e., each component of x being on a lower or upper bound. So if n is not too large, you can evaluate the objective function for all 2^n such points, and choose the one with highest objective value.

2 Likes
3

Hi Dr Mark

If its non-convex, meaning concave… on a maximum. there’s no way to run on cvx since we’re maximising a norm function. How then we do achieve global optimum? Are you suggesting to introduce slack variables to reformulate the objective function or introduce additional inequality constraints for a feasible region? A further clarity will be most helpful for the benefit of the audience

Supra

4

I think @mark_l_stone is saying you should not Cvx at all for this. Cvx is not suitable for the problem.
So the question does not even belong on this forum.

However, Mark is nice and tells you the problem is simple so you can evaluate objective on all the vertices of the feasible domain and simply pick the vertex that gives the best objective value and that will be a optimal solution. This is based on a well known fact.

2 Likes
5

Thanks for your prompt response

Regards
Supra

6

Yes, what @Erling said.

And by the way, non-convex does not mean concave. But in this case, the non-convex objective is concave, which along with the convex compact (bounded) constraints. is key to the solution method we mentioned.

1 Like
7

Understood Mark. Thanks

Supra

8

Thank you Mark for your reply. Again out of context for this forum but I was just wondering if you can suggest any available solvers which can solve this problem apart from the heuristic approach that you mentioned?

9

You can try BARON or BMIBNB under YALMIP to (attempt to) solve to global optimality. if n is too large, the solvers may not necessarily succeed within an acceptable amount of time 9or memory. There are also local solvers, such as FMINCON which can be used under YALMIP (or called directly in MATLAB).

The approach I mentioned in my first post is not heuristic. It is rigorous, but it is computationally intractable if n is too large.

1 Like