Problem
We consider a possibly non-convex QCQP, with nonnegative variable $x\in \mathbb{R}^n$,
\begin{equation*}
\begin{aligned}
& \underset{x}{\text{minimize}}
& & f_0(x) \\
& \text{subject to}
& & f_i(x) \leq 0, \; i = 1, \ldots, m\\
& & & x \geq 0
\end{aligned}
\end{equation*}
where $f_i(x)=\frac{1}{2}x^TP_ix+q_i^Tx+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\geq0$, so this need not to be a convex problem.
Suppose that $q_i\leq 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^TP_ix+q_i^Tx+r_i, \ i=0,1,2,\cdots,m$. In this structure, $q_i^Tx+r_i$ part is affine, so it does not cause problem. Then I only consider $x^TP_ix$.
- The first thing that arises in my mind is to decompose $P_i$ into certain form and make $x^TP_ix$ become something like $y^TQy$ where $Q \geq 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=\phi (x_i)$. But coming up with this may need some "magic" and up to now have found anything that helps.
Could someone help me, thank you in advance.
Best Answer
I finally came up with a solution, which seems to be a valid reformulation.
Expand $f_i(x) \ (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\neq j}P_{ij}x_i x_j+ \sum_i^n q_i x_i + r$$
Notice that $x \geq 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\neq j}P_{ij}\sqrt{y_i y_j}+ \sum_i^n q_i\sqrt{y_i} + r$$
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\geq 0$, what indicates the possibility of taking the square root.