An extension of the Reformulation-Linearization Technique to nonlinear optimization

We introduce a novel Reformulation-Perspectification Technique (RPT) to obtain convex approximations of nonconvex continuous optimization problems. RPT consists of two steps, those are, a reformulation step and a perspectification step. The reformulation step generates redundant 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). We show that many well-known RLT based results can also be obtained and extended by applying RPT. Numerical experiments on dike height optimization and convex maximization problems demonstrate the effectiveness of the proposed approach.

Article

Download

View PDF