5
$\begingroup$

I'd like to know whether there are any publicly available tools for solving QCQP with complex variables (and constraints therefore expressed through Hermitian matrices). What I have found so far is the following:

  • A recently created CVXPY package for QCQP with real variables, as well as a paper mentioning the ability of BARON to handle those problems.
  • Two papers that implement solvers for some QCQP problems with complex variables. Their code seems at first glance not to be available online, though.
$\endgroup$
  • $\begingroup$ The quadratic form can be re-written as real symmetric quadratic form. $\endgroup$ – nicoguaro Jun 26 '18 at 1:38
  • $\begingroup$ Definitely. I was feeling like the details of that reduction might be thorny, and decided to keep the idea as a backup in case this search process fails (I also read some comments on qcqp being nicer to deal with in the complex case, which made me hope the search might be successful). Got any pointers to literature describing the complex->real reduction for this kind of program? $\endgroup$ – Abel Molina Jun 26 '18 at 1:48
  • $\begingroup$ Well, I've never done it in the context of optimization but finite elements. I believe that the objective function should not have the linear term, otherwise it might be complex, but I am not that sure for the constrains, though. $\endgroup$ – nicoguaro Jun 26 '18 at 1:52
  • $\begingroup$ I see, thanks for sharing! I suspect that in the instances I have in mind, it's a matter of decomposing all objects into a real and a complex component, and then looking at the real part for each inequality as a function of those components (with no need to associate a complex part to the inequalities because of Hermiticity) $\endgroup$ – Abel Molina Jun 26 '18 at 20:28
  • 1
    $\begingroup$ I will expand my comment as an answer. $\endgroup$ – nicoguaro Jun 26 '18 at 20:29
5
$\begingroup$

Let's consider the following minimization problem

\begin{align} & \text{minimize} && \tfrac12 z^\mathrm{H} P_0 z + q_0^\mathrm{H} z\\ & \text{subject to} && \tfrac12 z^\mathrm{H} P_i z + q_i^\mathrm{H} z + r_i \leq 0 \quad \text{for } i = 1,\dots,m , \\ &&& Az = b, \end{align}

where $P_i$ are Hermitian matrices. The terms $q_i^H z$ can be complex in general, so they should not appear for us to have real-valued objective function and inequality constraints. We have then

\begin{align} & \text{minimize} && \tfrac12 z^\mathrm{H} P_0 z\\ & \text{subject to} && \tfrac12 z^\mathrm{H} P_i z + r_i \leq 0 \quad \text{for } i = 1,\dots,m , \\ &&& Az = b, \end{align} with $r_i$ real numbers.

Now, since $P_i$ is Hermitian, the following holds

$$\mathrm{Re}(P_i) = \mathrm{Re}(P_i)^T\, ,\quad \mathrm{Im}(P_i)=-\mathrm{Im}(P_i)\, ,$$

and we can write

$$z^H P_i z = \begin{pmatrix} x &y\end{pmatrix} \begin{bmatrix} \mathrm{Re}(P_i) &-\mathrm{Im}(P_i)\\ \mathrm{Im}(P_i) &\mathrm{Re}(P_i)\end{bmatrix} \begin{pmatrix} x \\y\end{pmatrix} \equiv X^T Q_i X\, , $$

where $z = x + iy$. The crossed terms cancel out due to skew-symmetry in the imaginary part and symmetry in the real part of the matrix.

Rewriting the original problem, we are left with

\begin{align} & \text{minimize} && \tfrac12 X^\mathrm{T} Q_0 X\\ & \text{subject to} && \tfrac12 X^\mathrm{T} Q_i X + r_i \leq 0 \quad \text{for } i = 1,\dots,m , \\ &&& MX = B, \end{align}

with

\begin{align} &M = \begin{bmatrix} \mathrm{Re}(A) &-\mathrm{Im}(A)\\ \mathrm{Im}(A) &\mathrm{Re}(A)\end{bmatrix}\, ,\\ &B = \begin{pmatrix} \mathrm{Re}(b) \\-\mathrm{Im}(b)\end{pmatrix}\, . \end{align}

$\endgroup$
  • 1
    $\begingroup$ That's actually a very nifty trick that I used myself multiple times when I had codes that were designed to work with real variables only (never for optimization purposes, though). The downside is doubling the amount of memory to store $M$ (as opposed to just storing complex-valued matrices) if they are ever stored explicitly. - I guess the same applies to $Q_i$. $\endgroup$ – Anton Menshov Jun 26 '18 at 21:21
  • $\begingroup$ Yes, the doubling of storage for matrices is a downside of this approach. $\endgroup$ – nicoguaro Jun 26 '18 at 21:27
  • $\begingroup$ But more often than not, I would be glad to pay this price to avoid additional coding and debugging. $\endgroup$ – Anton Menshov Jun 26 '18 at 21:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.