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}(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.

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.

Hamnetmj

Beginner2022-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.

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.

Find the volume V of the described solid S

A cap of a sphere with radius r and height h.

V=??

Whether each of these functions is a bijection from R to R.

a) $f(x)=-3x+4$

b) $f\left(x\right)=-3{x}^{2}+7$

c) $f(x)=\frac{x+1}{x+2}$

?

$d)f\left(x\right)={x}^{5}+1$In how many different orders can five runners finish a race if no ties are allowed???

State which of the following are linear functions?

a.$f(x)=3$

b.$g(x)=5-2x$

c.$h\left(x\right)=\frac{2}{x}+3$

d.$t(x)=5(x-2)$ Three ounces of cinnamon costs $2.40. If there are 16 ounces in 1 pound, how much does cinnamon cost per pound?

A square is also a

A)Rhombus;

B)Parallelogram;

C)Kite;

D)none of theseWhat is the order of the numbers from least to greatest.

$A=1.5\times {10}^{3}$,

$B=1.4\times {10}^{-1}$,

$C=2\times {10}^{3}$,

$D=1.4\times {10}^{-2}$Write the numerical value of $1.75\times {10}^{-3}$

Solve for y. 2y - 3 = 9

A)5;

B)4;

C)6;

D)3How to graph $y=\frac{1}{2}x-1$?

How to graph $y=2x+1$ using a table?

simplify $\sqrt{257}$

How to find the vertex of the parabola by completing the square ${x}^{2}-6x+8=y$?

There are 60 minutes in an hour. How many minutes are there in a day (24 hours)?

Write 18 thousand in scientific notation.