A new framework to relax composite functions in nonlinear programs

• 成果类型: Article
• 署名作者: He, Taotao; Tawarmalani, Mohit
• 署名单位: Shanghai Jiao Tong University; Purdue University System; Purdue University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-020-01541-x
• 发表日期: 2021
• 页码: 427-466
• 关键词: convex-hull; concave envelopes; cutting-planes; optimization; relaxations; polytope; facets

摘要

In this paper, we devise new relaxations for composite functions, which improve the prevalent factorable relaxations, without introducing additional variables, by exploiting the inner-function structure. We outer-approximate inner-functions using arbitrary under- and over-estimators and then convexify the outer-function over a polytopeP, which models the ordering relationships between the inner-functions and their estimators and utilizes bound information on the inner-functions as well as on the estimators. We show that there is a subsetQofP, with significantly simpler combinatorial structure, such that the separation problem of the graph of the outer-function overPis polynomially equivalent, via a fast combinatorial algorithm, to that of its graph overQ. We specialize our study to consider the product of two inner-functions with one non-trivial underestimator for each inner-function. For the corresponding polytopeP, we show that there are eight valid inequalities besides the four McCormick inequalities, which improve the factorable relaxation. Finally, we show that our results generalize to simultaneous convexification of a vector of outer-functions.