Christopher Saunders

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}\left(x\right)\\ & \text{subject to}& & {f}_{i}\left(x\right)\le 0,\phantom{\rule{thickmathspace}{0ex}}i=1,\dots ,m\\ & & & x\ge 0\end{array}$
where ${f}_{i}\left(x\right)=\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 . 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 \left({x}_{i}\right)$. But coming up with this may need some "magic" and up to now have found anything that helps.

Do you have a similar question?

Hamnetmj

Expert

Step 1
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 ${f}_{i}\left(x\right),{P}_{i}$ and ${q}_{i}$.
$f\left(x\right)=\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\left(y\right)=\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.

Still Have Questions?

Free Math Solver