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:
- Why is f(x) either convex or non-convex?
- 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.
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.