Imposing discrete solutions

[Ignacio]

Hello,

I am trying to solve a non convex problem of the form (with complex variables):

Min x'*A*x

st    b*x=1

       x.^2=1

where I amimposing constant amplitud of x. I have solved it for small sizes and I have managed to relax the constraints and get good results through SDR.

But now I would like to impose discrete solutions on the phase of x (I know it is highly non convex). As a first step I would like to solve it even with a global solver.

It is explained in the file attached (it is more clear there).

I do not known wich solver is the most suitable for the problem.

Thanks in advance

[Johan Löfberg]

are you saying that you want x to only take certain values on the unit circle, at predefined angeles .1 rad, 0.2 rad, 0.3 rad,...

[Ignacio]

That's right

[Johan Löfberg]

Then each complex number is selected from a finite number of points. I would do that enumeration explicitly using a MIQP approach.

angles = 0:.1:2*pi
v = [cos(angles);sin(angles)];
pick = binvar(size(v,2),N,'full')
z = v*pick;
x = [z(1,:)';z(2,:)'];
cons = [sum(pick,1)==1, ar*x>=1];
solvesdp(cons,x'*A*x);

The MIQP solvers I tried (mosek,cplex) struggle with the model, but I am sure a global nonlinear solver would struggle even more, especially with that nasty atan operator, and the general fact that there are no global solvers, besides bmibnb in YALMIP, which handles atan (bmibnb did not find any feasible solution when I tried with n=1:3)

[Johan Löfberg]

BTW, in case you missed it, YALMIP can work directly with complex variables, so you don't have to convert to real/imag manually

[Ignacio]

Thanks Johan,

I have solved it using Gurobi. It says at the end: "Optimal solution found". 
As it is non convex, Can it be claimed that it is for sure the optimal solution of the problem?

I guess that when the problem is really small yes, but when it grows...

[Johan Löfberg]

Since I formulated it as a MIQP, and Gurobi is a global MIQP solver, you have the global optimum (up to Gurobis tolerances)