# Convert a non-convex QCQP into a convex counterpart

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.

• Are you not missing any assumption? For example with your setup it is easy to create a constraint $x^2\leq y^2+z^2$ and then I think it becomes a problem. – Michal Adamaszek May 9 '18 at 7:08
• What makes you think this would be possible (it is not, as for instance binary optimization is a special case of your setup) – Johan Löfberg May 9 '18 at 10:31
• scratch my binary example, I just saw the $q_i\leq 0$ condition (although still impossible, as indicated by the example above) – Johan Löfberg May 9 '18 at 10:40
• @MichalAdamaszek I do not quite understand your point. What does $y$ and $z$ stand for? Could you provide more information? – Mr.Robot May 9 '18 at 19:31
• @JohanLöfberg Actually this is a homework problem and I have been working on it for almost a week, so hopefully there is certain way to reformulate this (seemingly impossible) problem. – Mr.Robot May 9 '18 at 19:37

## 1 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.

• Aha, nice. Yes it appears correct – Johan Löfberg May 10 '18 at 13:23