5
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ 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. $\endgroup$ Commented May 9, 2018 at 7:08
  • $\begingroup$ What makes you think this would be possible (it is not, as for instance binary optimization is a special case of your setup) $\endgroup$ Commented May 9, 2018 at 10:31
  • $\begingroup$ scratch my binary example, I just saw the $q_i\leq 0$ condition (although still impossible, as indicated by the example above) $\endgroup$ Commented May 9, 2018 at 10:40
  • $\begingroup$ @MichalAdamaszek I do not quite understand your point. What does $y$ and $z$ stand for? Could you provide more information? $\endgroup$
    – Mr.Robot
    Commented May 9, 2018 at 19:31
  • $\begingroup$ @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. $\endgroup$
    – Mr.Robot
    Commented May 9, 2018 at 19:37

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ Aha, nice. Yes it appears correct $\endgroup$ Commented May 10, 2018 at 13:23

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .