Bounds tightening based on optimality conditions for nonconvex box-constrained optimization

详细信息    查看全文

• 作者：Yash Puranik ; Nikolaos V. Sahinidis
• 关键词：Global optimization ; Bounds tightening ; Optimality conditions ; Box ; constrained optimization
• 刊名：Journal of Global Optimization
• 出版年：2017
• 出版时间：January 2017
• 年：2017
• 卷：67
• 期：1-2
• 页码：59-77
• 全文大小：
• 刊物类别：Business and Economics
• 刊物主题：Optimization; Operation Research/Decision Theory; Real Functions; Computer Science, general;
• 出版者：Springer US
• ISSN：1573-2916
• 卷排序：67

文摘

First-order optimality conditions have been extensively studied for the development of algorithms for identifying locally optimal solutions. In this work, we propose two novel methods that directly exploit these conditions to expedite the solution of box-constrained global optimization problems. These methods carry out domain reduction by application of bounds tightening methods on optimality conditions. This scheme is implicit and avoids explicit generation of optimality conditions through symbolic differentation, which can be memory and time intensive. The proposed bounds tightening methods are implemented in the global solver BARON. Computational results on a test library of 327 problems demonstrate the value of our proposed approach in reducing the computational time and number of nodes required to solve these problems to global optimality.