I have the following non-convex constraint in variables $x \geq 0$ and $\textbf{p}$

$$ax+bx\|\textbf{p}\|^2-c \leq 0$$

where $a,b,c$ are positive constants. We can see that the above constraint does not result in a convex set. How to handle such kind of constraints in the optimization problem?

  • 1
    $\begingroup$ There are lots of algorithms that handle nonconvex objectives and constraints, for example using penalty or barrier functions. You're just not guaranteed to converge to the global optimum, but you will find a local optimum. $\endgroup$ – Rahul Mar 13 '18 at 9:46
  • 2
    $\begingroup$ How do $x$ and $p$ enter the rest of the model? That could be important in order to see possibilities for suitable variable changes etc. $\endgroup$ – Johan Löfberg Mar 13 '18 at 11:44
  • 3
    $\begingroup$ Yes. what Johan said. My first thought is to try to rewrite the problem in terms of $x^{-1}$. $\endgroup$ – Michael Grant Mar 13 '18 at 12:10
  • $\begingroup$ @MichaelGrant you mean writing the constraint as $a+b\|\textbf{p}\|^2-cx^{-1}\leq 0$. Now this constraint becomes difference of two convex functions. I read somewhere that in this case we can leave the convex part and linearize the concave part (in this case $-c x^{-1}$). Now one more thing that is particular to this problem is that the constraint should be met with equality. So in this case $x$ cannot have a zero value so its first order Taylor expansion would suffice. Is it right thinking? Please comment. Thank you in advance. $\endgroup$ – Frank Moses Mar 13 '18 at 23:36
  • 1
    $\begingroup$ Well, what I am suggesting is a change of variables $y=x^{-1}$. $\endgroup$ – Michael Grant Mar 14 '18 at 0:29

We have the following nonlinear constraint in $x \geq 0$ and $\mathrm y \in \mathbb R^n$

$$a x + b x \| \mathrm y \|_2^2 - c \leq 0$$

where $a, b, c > 0$ are given. Using Michael Grant's suggestion, we divide both sides by $x > 0$

$$a + b \| \mathrm y \|_2^2 - c x^{-1} \leq 0$$

Let $z := x^{-1}$. Hence, we obtain the following inequality in $\mathrm y \in \mathbb R^n$ and $z > 0$

$$(c z - a) - \mathrm y^\top \left( b^{-1} \mathrm I_n \right)^{-1} \mathrm y \geq 0$$

Since $b > 0$, we can use the Schur complement to write the inequality above as a (convex) linear matrix inequality (LMI) in $\mathrm y \in \mathbb R^n$ and $z > 0$

$$\begin{bmatrix} b^{-1} \mathrm I_n & \mathrm y\\ \mathrm y^\top & c z - a\end{bmatrix} \succeq \mathrm O_{n+1}$$


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.