Hidden Convexity in a Class of Optimization Problems with Bilinear Terms

Some Bilinear Optimization Problems Are Surprisingly Easy to Solve Bilinear terms in a continuous optimization problem are computationally challenging and are typically addressed with global optimization techniques or McCormick-based relaxations. In “Hidden convexity in a class of optimization problems with bilinear terms,” Gorissen, den Hertog, and Reusken discover a reformulation technique that provides an equivalent convex formulation that is solvable in polynomial time for a rich subclass of problems. The subclass is characterized by products of variables where one variable is nonnegative and the other variable interacts only with variables that are multiplied with the same nonnegative variable. Their finding provides a new avenue to efficiently solve inverse optimization problems, nonlinear robust optimization problems via their dual problem, and problems with variable coefficients.