Convert a non-convex QCQP into a convex counterpart
We consider a possibly non-convex QCQP, with nonnegative variable ,
where , with , , and , for . We do not assume that , so this need not to be a convex problem.
Suppose that and have non-positive off-diagonal entries. Explain how to reformulate this problem as a convex problem.
What I Have Done
Since both objective function and constraints are possibly non-convex, I consider their common structure, that is . In this structure, part is affine, so it does not cause problem. Then I only consider .
The first thing that arises in my mind is to decompose into certain form and make become something like where . However, I did not find anything useful (actually it seems that I should not or any non-convex quadratic programming could be solved in this way).
Even though the previous random thought does not seem to work, I still think certain transformation is necessary, and perhaps some non-linear transformation . But coming up with this may need some "magic" and up to now have found anything that helps.
Answer & Explanation
I finally came up with a solution, which seems to be a valid reformulation.
Expand into the form (form clarity, I drop the subscript in and .
Notice that , apply the change of variable , we have
The first term is affine in . What is more, since the off-diagonal entries of P are non-positive and this makes the second term convex. Similarly, the last term is also convex. Then f(y) is convex.
The "hint" directly from the problem is provided by , what indicates the possibility of taking the square root.
Most Popular Questions