Trying to solve an optimization problem

[David1]

Hi, I'm new with Yalmip and I'm trying to solve an optimization problem.

This is the code I wrote:

clear;
close all;
clc;


n = 10;
d = 3;


A = rand(n,d);
b = rand(n,1);
x = sdpvar(d,1);


Objective = norm(A*x-b,2);
cons = [norm(x,2)==1];
options = sdpsettings('verbose',1);


sol= optimize(cons,Objective, options);
value_x = value(x)
sol.info

I want to find a vector $x$ that minimizes ||Ax-b||_2 under the constraint that ||x||_2=1.

This problem is for sure solvable. You can solve it using Lagrange multipliers. but Yalmip prints "'Model creation failed (Model not available in constraint #1 at level 1)'" in sol.info.

Why is that? How can I change to code (if possible) so it can solve the problem?

My real goal is to solve the problem when cons = [norm(x,1)==1] (meaning norm(x,1)==1 instead of norm(x,2)==1).

I'm not sure that this problem is solvable.

Is there a way to solve both problems?

Thanks

[Johan Löfberg]

First, in case you're missing this, norm(x,anything)==1 is a nonconvex constraint

norm(x,2) is overloaded using an socp-representation, and thus requires a convex constraint.

https://yalmip.github.io/command/norm/

To solve this, you best approach is to write it as x'*x == 1 which is a nonconvex quadratic constraints, and that is no problems to handle (except for the fact that the solver might fail to solve the nonconvex problem of course)

norm(x,1) == 1 will lead to a mixed-integer representation, so the problem you really want to solve will lead to a mixed-integer second-order cone program. You might want to minimize norm(A*x-b)^2 instead, as YALMIP autoamatically will represent that as (A*x-b)'*(A*x-b) meaning it is solvable by mixed-integer quadratic programming solvers (alsthough most MIQP solvers solve MISOCP also, butquite often MIQP is easier/more efficiently solved than MISOCP)

[David1]

Thank you for your answer!

I'd like to check something a little different from what I asked before.

If I change the objective and the cons to the following:

Objective = norm(A*x-b,1);
cons = [x'*x==1];

Is the solution to this problem optimal? or approximation of the optimal solution?

Thanks!

[Johan Löfberg]

By default YALMIP will use a local solver (fmincon I guess) to solve this nonconvex problem. If you want a global solution, you will have to specify a global solver (built-in bmibnb or baron or scip-nl)

[David1]

Thanks.

And if I specify bmibnb solver. Is it guaranteed that the solution is optimal?

[Johan Löfberg]

yes, up to the specified tolerances, and general problems that can arise in any numerical solver.

[David1]

Thank you.

Can you tell me which algorithm is used for finding the global solution for this problem?

I would really appreciate if you can send me a reference for this algorithm since I didn't know such algorithm exists (my research is about this topic exactly).

Do you know if this problem can be solved also for outliers? For example if b(1) is very noisy then it is best to solve the optimization problem for ||A(2:n,:)x-b(2:n)||_1 under the constraint that ||x||_2=1.

[Johan Löfberg]

YALMIPs bmibnb implements a vanilla spatial branch and bound, and baron and scip use the same basic strategy.

https://en.wikipedia.org/wiki/Global_optimization

Changing to that objective makes no particular difference in the contect of global optimization, as that objective is LP-representable. It is your nonlinear equalities which are problematic

[David1]

Thank you very much for your help!