A computationally useful algebraic representation of nonlinear disjunctive convex sets using the perspective function

Nonlinear disjunctive convex sets arise naturally in the formulation or solution methods of many discrete–continuous optimization problems. Often, a tight algebraic representation of the disjunctive convex set is sought, with the tightest such representation involving the characterization of the convex hull of the disjunctive convex set. In the most general case, this can be explicitly expressed through the use of the perspective function in higher dimensional space—the so-called extended formulation of the convex hull of a disjunctive convex set. However, there are a number of challenges in using this characterization in computation which prevents its wide-spread use, including issues that arise because of the functional form of the perspective function. In this paper, we propose an explicit algebraic representation of a fairly large class of nonlinear disjunctive convex sets using the perspective function that addresses this latter computational challenge. This explicit representation can be used to generate (tighter) algebraic reformulations for a variety of different problems containing disjunctive convex sets, and we report illustrative computational results using this representation for several nonlinear disjunctive problems.

Citation

Furman, K.C., Sawaya, N.W. & Grossmann, I.E. A computationally useful algebraic representation of nonlinear disjunctive convex sets using the perspective function. Comput Optim Appl (2020). https://doi.org/10.1007/s10589-020-00176-0