Christopher Saunders

Answered

2022-10-25

Convert a non-convex QCQP into a convex counterpart

We consider a possibly non-convex QCQP, with nonnegative variable $x\in {\mathbb{R}}^{n}$,

$$\begin{array}{rlrl}& \underset{x}{\text{minimize}}& & {f}_{0}(x)\\ & \text{subject to}& & {f}_{i}(x)\le 0,\phantom{\rule{thickmathspace}{0ex}}i=1,\dots ,m\\ & & & x\ge 0\end{array}$$

where ${f}_{i}(x)=\frac{1}{2}{x}^{T}{P}_{i}x+{q}_{i}^{T}x+{r}_{i}$, with ${P}_{i}\in {\mathbb{S}}^{n}$, ${q}_{i}\in {\mathbb{R}}^{n}$, and ${r}_{i}\in \mathbb{R}$, for $i=0,\cdots ,m$. We do not assume that ${P}_{i}\ge 0$, so this need not to be a convex problem.

Suppose that ${q}_{i}\le 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)=\frac{1}{2}{x}^{T}{P}_{i}x+{q}_{i}^{T}x+{r}_{i},\text{}i=0,1,2,\cdots ,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}Qy$ where $Q\ge 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}=\varphi ({x}_{i})$. But coming up with this may need some "magic" and up to now have found anything that helps.

Answer & Explanation

Hamnetmj

Expert

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)\text{}(i=0,1,\cdots ,m)$ into the form (form clarity, I drop the subscript in ${f}_{i}(x),{P}_{i}$ and ${q}_{i}$.

$$f(x)=\frac{1}{2}\sum _{i}^{n}{P}_{ii}{x}_{i}^{2}+\sum _{i\ne j}{P}_{ij}{x}_{i}{x}_{j}+\sum _{i}^{n}{q}_{i}{x}_{i}+r$$

Notice that $x\ge 0$, apply the change of variable ${y}_{i}={x}_{i}^{2}$, we have

$$f(y)=\frac{1}{2}\sum _{i}^{n}{P}_{ii}{y}_{i}+\sum _{i\ne j}{P}_{ij}\sqrt{{y}_{i}{y}_{j}}+\sum _{i}^{n}{q}_{i}\sqrt{{y}_{i}}+r$$

Step 2

The first term $\sum _{i}^{n}{P}_{ii}{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 $\sum _{i}^{n}{q}_{i}\sqrt{{y}_{i}}+r$ is also convex. Then f(y) is convex.

The "hint" directly from the problem is provided by $x\ge 0$, what indicates the possibility of taking the square root.

Most Popular Questions