Optimization of complex matrices with absolute value constraint on its entries

[Andreas Steimer]

Hi folks,

Using YALMIP I'm trying to optimize the phases of some Fourier transform, for which I use some complex matrix quantity representing the exponentiated phases ( '= exp(i*phase)' ).
Therefore, the complex matrix entries are constrained to have an absolute value of 1 (see code below). The problem is that PENLAB seems to be the only solver working for this nonlinear semidefinite program, but the result it gets is a matrix having all
entries set to zero, which does not even satisfy the constraints.
  Can anybody tell me what the problem is? Any help is appreciated...

much thanks in advance,

    Andreas



CODE (Remark: 'covXdes' and 'absX' are ordinary, real matlab matrices of appropriate size):
*********************************************************************************************************

yalmip('clear');

X = sdpvar(N,M,'full','complex');

constraints = [X(:).*conj(X(:))==1];

objective = sum(sum(abs( (absX.*X)'*(absX.*conj(X)) - covXdes ),1 ),2 );
 
sol = optimize( constraints, objective, sdpsettings('solver','penlab','debug',0,'verbose',2) )

[Mark L. Stone]

Check the PENLAB output. You'll see

PenLab didn't converge: unconstrained minimization failed

YALMIP always reports 'Successfully solved (PENLAB)' despite PEN:AB's failure.

This is not a (nonlinear) semidefinite program. But YALMIP is picking PENLAB as default solver?

I made up random symmetric 3 by 3 abs and covXdes.  Using the default starting value of I think the matrix of zeros, i.e., usex0 not set to 1, PENLAB failed and KNITRO and FMINCON reported infeasible.  Using this same input data, but with starting value of the matrix of ones or twos, with usex0 set to 1, all three solvers converged to the matrix of ones.

[Johan Löfberg]

No reason to use penlab as this is a standard nonlinear nonconvex program. Pretty nasty though as you have the N*M nonsmooth absolute functions in the objective, so I doubt any solver behaves nicely on this

If penlab actually terminated, did you look at the diagnostic flag. Most likely it has simply given up

[Johan Löfberg]

BTW; you can write exp(X) for complex decision-variable X, and you will automatically get cos+i*sin, if that helps

[Mark L. Stone]

Nevertheless, YALMIP chose PENLAB as the default solver, even though KNITRO, FMINCON, and other nonlinear nonconvex solvers are installed.

[Johan Löfberg]

Ah, you're right. The problem is that the abs operator for complex data means a norm expression, which it wants to do using a second-order cone reformulation, but the model is nonlinear, and there is no suitable combination and it ends up in a nonlinear SDP form of the problem

Bad choice, so an alternative form of the objective is probably recommended

[Andreas Steimer]

Thank you Mark and Johan.

as both of you seem to have suggested I have now had a look at the output of PENLAB rather then YALMIP. Indeed, it didn't work as the output was


Warning: Unconstr/eqconstr. min failed (flag 3), remaing attepmts: 0
*******************************************************************************

PenLab didn't converge: unconstrained minimization failed

Moreover, I have also spotted an error in the previous version of the code, as my definition of 'X' did not take the conjugate symmetries of the fast fourier transform into account.

Regarding the general problem, do you have any idea of how I can use YALMIP to optimize phases of complex numbers? What I want to achieve is equality between the matrices (absX.*X)'*(absX.*conj(X))  and covXdes, where absX is a matrix of given absolute values of complex numbers, X the exponentiated phases and covXdes a given matrix of covariance values (NB: If conjugate symmetries are respected the former matrix is guaranteed to be real). I have no idea what solver to use etc. and in many cases it is hard to figure out how YALMIP treats standard functions such as 'abs'. In the given example, does YALMIP interpret 'abs' in the same way as matlab, i.e. 'abs(X)' gives the matrix of absolute values for each entry of X?

thanks for your patience with a rookie YALMIP user...

[Mark L. Stone]

So by specifying a non-SDP solver, YALMIP doesn't try to do the SOCP reformulation, and end ups sending the problem to the nonlinear nonconvex solver as a "generic" nonlinear nonconvex problem?

[Johan Löfberg]

Yes. It keeps the SOCP info internally, but adds a layer outside the fmincon interface layer where it un-socpifies the function evaluation and jacobians etc. Getting norms to work in a nice transparent fashion is a messy affair, and how I want to do this is still not decided upon completely 

[Andreas Steimer]

I have tried using bmibnb instead, but there seems to be some problem with my installation, as bmibnb refers to linprog for which there is no case-sensitive function available.
I will check that out first...

[Andreas Steimer]

I see, so I better start using workarounds for 'abs(X)' such as ' sqrt( X.*conj(X) ) '

[Johan Löfberg]

sounds weird, strange installation of some file linprog which isn't what YALMIP thinks it is

which linprog -all

[Johan Löfberg]

Well, I would try to get rid of non-smooth functions altogether. 

In the end though, you have a nonconvex problem, and if you manage to solve it will be down to luck in the end

[Andreas Steimer]

Thanks Johan and Mark, your tips have been very helpful.
 It seems that I first need to rethink my overall cost function and make sure that it becomes more digestible for the YALMIP solvers.

[Okan Ciftci]

Hello Andreas,

Did you able to solve the problem? 

I'm having the same problem with my code:

I_ijsame = sdpvar(6,1,'full','complex');

Constraints = [Constraints, (0 <= abs(I_ijsame(4:6)))];

Constraints = [Constraints, (abs(I_ijsame(4:6)) <= 700)];

I'm simply trying to have one of the complex-valued variables to be in some real-valued boundaries.

Is there any suggestion from anyone?

Thank you,

Okan

[Johan Löfberg]

Why on earth would you add the nonconvex constraint abs(something)>=0. That's true by definition

Even worse, since argument is complex, and abs is implemented using convexity assuming SOCP representation, it will not even be supported as YALMIP cannot derive a model