(522a) Global Optimization of Nonconvex Problems with Convex-Transformable Intermediates

Current global optimization solvers rely on factorable programming techniques to construct convex relaxations of nonconvex optimizations problems [5–7]. These techniques iteratively decompose a nonconvex factorable function by introducing auxiliary variables for intermediate expressions, until each intermediate expression can be outer-approximated by a convex feasible set. While they are easy to automate, factorable programming techniques often result in large relaxation gaps.

Factorable relaxations of global optimization problems can be strengthened through the use of functional transformations. A particular example of this approach is the use of power and exponential transformations to convexify signomial terms [2–4]. A more general transformation scheme was recently proposed by Khajavirad et al. [1]. This technique exploits convex transformability of component functions of factorable programs, and is applicable to various classes of functional forms including signomials, products and ratios of convex and/or concave functions, and logarithmically-concave functions. As illustrated in [1], this transformation method often leads to relaxations which are tighter than those obtained by standard approaches.

Motivated by the potential of these new relaxations to enhance the performance of global solvers, in this paper, we introduce a new class of cutting planes for convex-transformable functions, and describe its implementation into the branch-and-reduce global solver BARON. The proposed implementation involves a recognition tool which identifies convex-transformable functions that are present in the problem, including those in intermediate expressions of factorable functions. To exploit local information regarding variable bounds for relaxation construction, as well as utilize the generated cutting planes for range reduction, we embed the proposed cutting plane generation technique at each node of the branch-and-reduce algorithm. An extensive computational study is carried out on problems selected from a collection of publicly available test sets. Results demonstrate that the generated cutting planes accelerate the convergence speed of the branch-and-reduce algorithm, by significantly reducing the average CPU time and number of nodes in the search tree.

References cited

[1] A. Khajavirad, J. J. Michalek, and N. V. Sahinidis. Relaxations of factorable functions with convex-transformable intermediates. Mathematical Programming, 144:107–140, 2014.

[2] H. Lu, H. Li, C. E. Gounaris, and Ch. A. Floudas. Convex relaxation for solving posynomial programs. Journal of Global Optimization, 46:147–154, 2010.

[3] A. Lundell and T. Westerlund. Convex underestimation strategies for signomial functions. Optimization Methods and Software, 24:505–522, 2009.

[4] C. D. Maranas and Ch. A. Floudas. Global optimization of generalized geometric programming. Computers & Chemical Engineering, 21:351–369, 1997.

[5] G. P. McCormick. Computability of global solutions to factorable nonconvex programs: Part I—Convex underestimating problems. Mathematical Programming, 10:147–175, 1976.

[6] H. D. Sherali and H. Wang. Global optimization of nonconvex factorable programming problems. Mathematical Programming, 89:459–478, 2001.

[7] M. Tawarmalani and N. V. Sahinidis. Global optimization of mixed-integer nonlinear programs: A theoretical and computational study. Mathematical Programming, 99:563–591, 2004.