Reformulation-Perspectification Technique for nonconvex optimization problems

In this paper, we propose a new global optimization approach for solving nonconvex optimization problems in which the nonconvex components are sums of products of convex functions. A broad class of nonconvex problems can be formulated in this way, such as concave minimization problems, problems with difference of convex functions in the objective and constraints, and fractional optimization problems. Our approach leverages two techniques: first, we introduce a new technique, called the Reformulation-Perspectification Technique (RPT), to obtain a convex approximation of the considered nonconvex continuous optimization problem. Next, we employ a spatial branch and bound scheme, utilizing RPT together with a modified eigenvector branching rule that extends Anstreicher (2022) to the case where X xx‘ may be indefinite, to obtain a global optimal solution. Numerical experiments on sum-of-max-linear-terms maximization, log-sum-exp maximization, linear multiplicative optimization, quadratically constrained quadratic optimization, and dike height optimization demonstrate the effectiveness of the proposed approach. Across these experiments, RPT-BB and RPT-SDP-BB are competitive with state-of-the-art global optimization solvers and are particularly effective on several harder instances.

Article

Download

View PDF