0
$\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$
1
$\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$
  • $\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$ – D.Gray Oct 9 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$ – Rob Pratt Oct 9 at 17:48

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.