Convexifying products and quotients

472 Views Asked by At

I would like to ask about convexity of the product of two continuous decision variables. Would it be possible to convexify it?

What about the case where two continuous variables are divided? Would the treatment be equivalent to the product of two variables where the denominator will have a negative power?

1

There are 1 best solutions below

5
On

I presume the context is that you wish to solve an optimization problem involving such a product (or quotient) using a convex optimization solver, perhaps called by a convex optimization modeling tool, such as CVX.

As you perhaps know, the product of tow continuous variables has a Hessian which is indefinite. Therefore, the product is neither convex nor concave.

The product of two continuous variables is MILP (Mixed Integer Linear Program) representable, providing that there are finite lower and upper bounds on both variables, and requiring discretization (limited number of binary "decimal" places) for one of the variables. This is accomplished using binary expansion for one of the variables. Then model all binary, continuous product terms per FICO MIP formulations and linearizations https://www.artelys.com/uploads/pdfs/Xpress/mipformref-1.pdf section 2.8. I leave the slightly messy details to you. However, I absolutely do not recommend doing this. Rather, use a non-convex optimization solver.

The simplest way to convexify such a product, which is a bilinear function, is to fix one variable (at a time). Then the product is convex (actually linear) in the other variable. You could then formulate a convex optimization problem, starting with some initial value for the variable which is fixed, and finding the optimal solution of that problem (which is convex if the rest of the model is). Then fix the just optimized variables at its optimal value and optimize with respect to the other variables. Iterate until convergence. However, such an alternating minimization scheme is not guaranteed to converge to anything, let alone a local minimum of the original problem, let alone a global minimum of the original problem.