Welcome to MathOverflow

Question

2

1

Let $P_1$, $P_2$ be two hermitian matrices. Can anyone comment about the following (QCQP) \begin{equation} \min_{z}~z^{H}z \\ ~~subject~to ~z^{H}P_1z+1\leq 0,~z^{H}P_2z+1\leq 0 \end{equation} I am familiar with semi-definite relaxation. But I was wondering if we could do more here, since the objective is convex.

flag	asked Nov 20 at 4:46 dineshdileep 281●5

S. Sra · Accepted Answer · 2012-11-20 05:48:11Z UTC

2

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.

answered Nov 20 at 5:48

S. Sra
10k●1●16●44

	@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. – dineshdileep Nov 21 at 6:28
	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.... – S. Sra Nov 21 at 6:46
	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. – dineshdileep Nov 21 at 8:12
	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? – Dima Pasechnik Nov 21 at 8:53
	e.g. if you have BLAS and LAPACK on your system then you can easily use CSDP: coin-or.org/projects/Csdp.xml – Dima Pasechnik Nov 21 at 8:58

show 3 more comments

Dima Pasechnik · Answer 2 · 2012-11-20 16:21:10Z UTC

1

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.

answered Nov 20 at 16:21

Dima Pasechnik
3,080●3●14

Wow, that sounds like a cool paper! I need to read it someday! – S. Sra Nov 21 at 18:50

A certain type of Quadratic Constrained Quadratic Programming Problem (QCQP)

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

2 Answers

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.