1
$\begingroup$

I have an optimization problem where my objective function and one of my constraints takes the form of a binary variable mulitplied by a continuous variable. I am trying to figure out if this results in the optimization problem being non-convex or convex:

$$ f(x) = (2 + 5y)x $$ $$ x \ge 0 $$ $$ y \in \{0,1\} $$

I am able to understand convexity and non-convexity with a single function of a continuous variable, but I don't really know how to think about it when the function becomes a product of two variables. So my 2 questions are as follows:

  1. Why is f(x) either convex or non-convex?
  2. Assuming that f(x) is non-convex, is there a way to linearize it into convexity?

The solver that I am using right now is called Knitro and to my understanding, it is able to handle non-convex MINLP problems, but of course, I would much prefer if I could keep my problem in the realm of convexity.

$\endgroup$
0

1 Answer 1

Reset to default
2
$\begingroup$

Problems with integer variables are inherently nonconvex. Think of a line segment that joins two points that have different values for some integer variable.

You can linearize the product of a bounded continuous variable $x\in [0,U]$ and a binary variable $y$ as follows: \begin{equation} 0 \le z \le U y \\ -U(1-y) \le z - x \le 0 \end{equation} If $y=0$, the first pair of constraints force $z=0$. If $y=1$, the second pair of constraints force $z=x$. So $z = x y$, as desired.

$\endgroup$
2
  • $\begingroup$ so even after the linearization the problem still remains non-convex. So if I apply that linearization method that you suggested, do you think that would help get the problem closer to a global optimum relative to the non-linearized form or would the linearization just speed up the solution? $\endgroup$ Commented Oct 9, 2019 at 17:36
  • 1
    $\begingroup$ A (non)convex MINLP problem means that the continuous relaxation is (non)convex. Some MINLP solvers handle nonconvexity, and some do not. Linearization will avoid any issue of local optimality and might not speed up the solution. $\endgroup$ Commented Oct 9, 2019 at 17:48

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.