How to dualize a QP model?

[Mayankai]

Hi professor,

I use MOSEK through YALMIP. My model is as follows.

min: w1'*Q*w1

constraint: real(w1)<1; imag(w1)<1;

where w1 is complex variables and Q is full-rank hermitian matrix.

I want to dualize this model, there are obviously two ways. The first is dualizing it directly, but I don't know how to express the dualization of real(w1) and imag(w1). Last question you told me that YALMIP is  x = [1 1i]* [a b], however I don't konw how to deal with it in this model.

The second way is decomposition w1 into w1=[eye(),1i*eye()]*[real(w1); imag(w1)]. However this way will lead to [eye(),1i*eye()]'*Q*[eye(),1i*eye()] is a not full-rank matrix, which cannot find the inverse matrix.

So I am totally confused. Could you help me deal with this problem? Thank you so much.

Regards,

Mayankai

[Johan Löfberg]

I don't think dualize applies to QP models. You would first have to write it with a cone operator. And then I still don't think it would be of any computational benefit

Don't think of real and complex, you simply have w = x+iy means your quadratic is (x+iy)'*Q*(x+iy). Now expand in x and y and work with the variable z = [x;y], and then just use standard duality theory

[Mayankai]

Sorry I didn't mention the background reasons. Actually the whole optimization problem is a MIQP, which is costing too much time. I want to use benders decomposition. Moreover the objective is sum of wi'*Q*wi and the cone operator cannot work.

As you said, z=[x;y] and w=[1 1i]*[x;y]. Obj= z' *[1 ;-1i]*Q*[1 1i] *z    I have tried this method, however  [1 ;-1i]*Q*[1 1i]  not full-rank matrix, which cannot find the inverse matrix.

[Johan Löfberg]

Of course you can use a conic model, if you use a conic solver such as mosek

The fact that you have complex stuff is a red herring. It is completely uninteresting, as you must solve a real problem anyway, and that is obtained when you simply write z=x+iy

You should not get any complex parts in your quadratic when you introduce z = x+iy. Then you've done something wrong. If you get a singular quadratic, most problems would not have a problem with that, but if you absolutely have to work with the inverse of the hessian for some reason, you would be forced to replace z'*H*z with e'*e where e is a new variable, and a new equality e == R*z where R is a wide factor of H, H = R'*R

[Mayankai]

Thank you. I will try to decompose the H with R. And your idea about conic model is inspiring me. I will think about it. Thank you again.