4
$\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$ – Michal Adamaszek May 9 '18 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$ – Johan Löfberg May 9 '18 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$ – Johan Löfberg May 9 '18 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 May 9 '18 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 May 9 '18 at 19:37
1
$\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$ – Johan Löfberg May 10 '18 at 13:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.