Convert a non-convex QCQP into a convex counterpartWe 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 DoneSince 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.

Question

Convert a non-convex QCQP into a convex counterpartWe 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 DoneSince 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 &quot;magic&quot; and up to now have found anything that helps.

Hamnetmj · Accepted Answer

Step 1I 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    +  rNotice 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        +  rStep 2The 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 &quot;hint&quot; directly from the problem is provided by   x  ≥  0, what indicates the possibility of taking the square root.

Convert a non-convex QCQP into a convex counterpart. We consider a possibly non-convex QCQP, with nonnegative variable x in R^n

Answered question

Answer & Explanation

New Questions in Algebra I