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 that combines RPT with eigenvector branching to obtain a global optimum 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 that the proposed approach is competitive with state-of-the-art global optimization solvers and can substantially outperform them on selected challenging instances, particularly when strengthened with semidefinite constraints.

Article

Download

View PDF