Maximize the minimum value

[Ignacio]

Hello,

I have solved (using YALMIP) a problem like:

find x

st    |x' A_i x - M_i|<eps,   i=1....I

I solved it with semidefinite relaxation (also called phase retrieval) with more or less good results in a form like

find X

st |tr(A_i X)-M_i |<eps    i=1....I

Te problem described above fix an upper and lower value to x'Ax. 

Now, I am interested only in the lower bound and fixing a maximum absolute value to x in order to constrain the problem. Can I solve it in a simpler way or it is as difficult to solve as the previous one?

I know both of them are non-convex.

Thank you and best regards,

Ignacio

[Johan Löfberg]

You are minimizing the maximum, you are not maximizing the minimum

Does | | denote absolute value of a real number, or a complex number

[Johan Löfberg]

i.e you are minimizing the max of stuff and -stuff

Do you mean you're only interested in maximizing the minimum of x'Aix-Mi?

[Ignacio]

Thnks Johan for your answer.

Before I was trying to get a value as close as possible to M. Now, I want that the minimum value of x'Ax is bigger than M, (I am not concern if it is much bigger).

I am dealing with complex numbers, || stand for complex numbers.

[Johan Löfberg]

Doesn't make sense to talk about the minimum of x'Ax vs M if they are complex valued. Do you perhaps mean that x and A are complex, but M and x'Ax are real?

Still unclear what you want to do though. You want to find any x such that x'*Ai*x >= M?

[Ignacio]

Yes, exactly. M and xAx are real. Sorry for the missleading

Yes, I am interested in xA_ix>M, with abs(x)<=1 and x complex

[Johan Löfberg]

and you want something more efficient than a semidefinite relaxation? 

[Ignacio]

Yes, I was not sure if a semidefinite relaxation was the best way to go

[Johan Löfberg]

It is still hard

You might try solvemoment so you don't have to reinvent the relaxations if you want to try higher-order relaxations. You can also try bmibnb to see how hard the problem actually is. Might be that LP-based relaxations easily solves the problem

[Ignacio]

Thanks Johan for your comments. How can I do a LP relaxation of the problem mentioned above?

[Johan Löfberg]

The global solver bmibnb is based on LP relaxations as lower bounds during the branching. 1 LP relaxation (i.e. the root relaxation) will not get you anywhere, it is too weak

https://yalmip.github.io/tutorial/envelopesinbmibnb/

What I am saying is that people sometimes gets unhealthily attached to SDP relaxations because it is the cool thing to do since everybody else use it (and it has had success in some prticular problem classes), but it might be that the problem is easy to solve using a global solver, so why bother with problematic SDP relaxations