4
$\begingroup$

Let $P_1$, $P_2$ be two Hermitian matrices. Can anyone comment on the following QCQP?

$$\begin{array}{ll} \text{minimize} & z^{H} z\\ \text{subject to} & z^{H} P_1 z +1 \leq 0\\ & z^{H} P_2 z + 1 \leq 0\end{array}$$

I am familiar with semidefinite relaxation. But I was wondering if we could do more here, since the objective is convex.

Improve this question
$\endgroup$
1
  • $\begingroup$ How exactly is this convex? The constraints look non-convex to me. $\endgroup$
    – Rodrigo de Azevedo
    Commented Mar 24, 2021 at 14:08

2 Answers 2

Reset to default
4
$\begingroup$

Yes, a lot can be said for your special case. Given the notation, I presume you are optimizing over $\mathbb{C}^n$. In this case, see Section 2 in the paper Strong Duality in Nonconvex Quadratic Optimization with two Quadratic Constraints, A. Beck and Y. Eldar, SIAM J. Optimization, 17(3), 2006.

PS: The complex variable case seems to be easier than the real variable case.

Improve this answer
$\endgroup$
8
  • $\begingroup$ @Suvrit thanks for that link. As I understand, the paper talks about the lagrangian relaxation of the above problem and it works well (I tested it). It is essentially a SDP problem. I was wondering if we could come up with some kind of fixed point algorithm for the dual problem of this. $\endgroup$
    – dineshdileep
    Commented Nov 21, 2012 at 6:28
  • $\begingroup$ But theorem 2.2 in that paper seems to say that under a finiteness and strict feasibility condition, the relaxation (given by (2.1) in the paper) has the same optimal value as the original problem.... $\endgroup$
    – Suvrit
    Commented Nov 21, 2012 at 6:46
  • $\begingroup$ They prove that the duality gap is zero, so the relaxation should give the same value as the original problem. In fact, they say that if we take the dual of this, we will get the semi definite relaxation. The problem for me is I need to implement this in a real time system where I can't assume the availability of a convex optimization package. So I need to come up with an iterative algorithm. It is fine if it converges to a local minimum or not a optimal solution. $\endgroup$
    – dineshdileep
    Commented Nov 21, 2012 at 8:12
  • $\begingroup$ well, if your RT system has an floating point processor, and you can compile C code for it, then you can get some open source SDP solver and use it, why not? $\endgroup$
    – Dima Pasechnik
    Commented Nov 21, 2012 at 8:53
  • $\begingroup$ e.g. if you have BLAS and LAPACK on your system then you can easily use CSDP: coin-or.org/projects/Csdp.xml $\endgroup$
    – Dima Pasechnik
    Commented Nov 21, 2012 at 8:58
1
$\begingroup$

Quadratic optimization subject to fixed number of quadratic constraints is "easy", even without any convexity assumptions. The algorithms are polynomial-time, but in practice quite hard to implement efficiently. See e.g. this.

The complex case can obviously be reduced to the real one.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Wow, that sounds like a cool paper! I need to read it someday! $\endgroup$
    – Suvrit
    Commented Nov 21, 2012 at 18:50

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .