Tuesday, November 6, 2007 - 3:30 PM
275a

Automatic Convexity Detection for Global Optimization

Xiaowei Bao, Chemical and Biomolecular Engineering, University of Illinois at Urbana-Champaign, 600 South Mathews Avenue, Urbana, IL 61801 and Nick Sahinidis, Chemical Engineering, Carnegie Mellon University, Doherty Hall 4210C, 5000 Forbes Avenue, Pittsburgh, PA 15213.

Convexity of optimization problems has been used extensively to prove theoretical convergence properties and accelerate the convergence of optimization algorithms. As a result, theoretical characterizations of convexity and concavity and their generalizations have been studied extensively [1]. The automatic computational detection of convexity came to attention only recently [2, 3, 4], motivated mostly by recent advances in the area of global optimization, where exploitation of convexity can improve the quality of relaxations used in branch-and-bound algorithms.

Detecting convexity of a general nonlinear function over a bounded domain is a difficult problem. One current method [3] involves the determination of the positive definiteness of the interval Hessian Matrix, a problem that is known to be NP-hard. As a result, this approach is far from being practical for large-scale problems. Another method [2, 4] is based on the use of known convexity and concavity rules. The latter method is more practical, although not extensively studied and, clearly, incomplete since known convexity rules may not suffice to characterize convexity of an arbitrary function.

In this work, an automatic convexity detection algorithm is developed and implemented. The proposed convexity detection scheme has three main parts: a special decomposition of the function to facilitate convexity detection, a bounding process to provide useful bounds as an aid for accurate convexity detection, and a convexity detection process that relies on existing tools from convexity analysis. We study the impact of using this procedure to preprocess problems before they are turned for solution to the branch-and-reduce global optimization algorithm. Computational results with 26 problems from the globallib collection demonstrate that the proposed convexity identification scheme improves the performance of the BARON global optimization solver significantly by allowing the solver to strengthen its lower bounding and reduce the relaxation gap once convexity has been automatically identified and this information has been provided to the solver through its CONVEX_EQUATIONS construct. As a result of exploiting convexity, the total number of BARON iterations, the maximum number of nodes that had to be stored in the memory, and the CPU time reduce by 99%, 99%, and 69%, on average.

References:

[1] M. Avriel, W. E. Diewert, S. Schaible and I. Zang. Generalized Concavity. Plenum Press, New York, NY, 1988.

[2] C. Maheshwari, A. Neumaier and H. Schichl. Convexity and concavity detection. Available at http://www.mat.univie.ac.at/~herman/techreports/D12convcon.ps, 2003.

[3] I. P. Nenov, D. H. Fylstra and L. V. Kolev. Convexity Determination in the Microsoft Excel Solver Using Automatic Differentiation Techniques. AD 2004 Fourth International Workshop on Automatic Differentiation, Chicago, IL, 2004. Abstract Available at http://atlas-conferences.com/c/a/l/x/28.htm.

[4] M. Tawarmalani and N. V. Sahinidis. A polyhedral branch-and-cut approach to global optimization. Mathematical Programming, 103:225-249, 2005.