Christopher Saunders

Christopher Saunders



Convert a non-convex QCQP into a convex counterpart
We consider a possibly non-convex QCQP, with nonnegative variable x R n ,
minimize x f 0 ( x ) subject to f i ( x ) 0 , i = 1 , , m x 0
where f i ( x ) = 1 2 x T P i x + q i T x + r i , with P i S n , q i R n , and r i R , for i = 0 , , m. We do not assume that P i 0, so this need not to be a convex problem.
Suppose that q i 0 and P i 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 f i ( x ) = 1 2 x T P i x + q i T x + r i ,   i = 0 , 1 , 2 , , m. In this structure, q i T x + r i part is affine, so it does not cause problem. Then I only consider x T P i x.
The first thing that arises in my mind is to decompose P i into certain form and make x T P i x become something like y T Q y where Q 0. 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 y i = ϕ ( x i ). But coming up with this may need some "magic" and up to now have found anything that helps.

Do you have a similar question?

Recalculate according to your conditions!

Answer & Explanation




2022-10-26Added 21 answers

Step 1
I finally came up with a solution, which seems to be a valid reformulation.
Expand f i ( x )   ( i = 0 , 1 , , m ) into the form (form clarity, I drop the subscript in f i ( x ) , P i and q i .
f ( x ) = 1 2 i n P i i x i 2 + i j P i j x i x j + i n q i x i + r
Notice that x 0, apply the change of variable y i = x i 2 , we have
f ( y ) = 1 2 i n P i i y i + i j P i j y i y j + i n q i y i + r
Step 2
The first term i n P i i y i is affine in y i . What is more, since the off-diagonal entries of P are non-positive and this makes the second term convex. Similarly, the last term i n q i y i + r is also convex. Then f(y) is convex.
The "hint" directly from the problem is provided by x 0, what indicates the possibility of taking the square root.

Still Have Questions?

Ask Your Question

Free Math Solver

Help you to address certain mathematical problems

Try Free Math SolverMath Solver Robot

Ask your question.
Get your answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?