Details
We introduce a novel Reformulation-Perspectification Technique (RPT) combined with a spatial Branch & Bound (B&B) technique to solve nonconvex continuous optimization problems. RPT consists of two steps, those are, a reformulation step and a perspectification step. The reformulation step generates nonconvex constraints from pairwise multiplication of the existing constraints. The perspectification step then convexifies the nonconvex components by using perspective functions. The proposed RPT extends the existing Reformulation-Linearization Technique (RLT) in two ways. First, it can multiply constraints that are not linear or not quadratic, and thereby obtain tighter approximations than RLT. Second, it can also handle more types of nonconvexity than RLT. We demonstrate the applicability of RPT by extensively analyzing all 15 possibilities of pairwise multiplication of the five basic cone constraints (linear cone, second-order cone, power cone, exponential cone, semi-definite cone). Numerical experiments on dike height optimization and convex maximization problems demonstrate the effectiveness of the proposed approach. We also show how this RPT and spatial B&B approach can be used to solve Robust Nonlinear Optimization problems.
This is joint work with: Dimitris Bertsimas (MIT), Thodoris Koukouvinos (MIT), Danique de Moor (University of Amsterdam), and Jianzhe Zhen.