Explicit convex and concave envelopes through polyhedral subdivisions

• 成果类型: Article
• 署名作者: Tawarmalani, Mohit; Richard, Jean-Philippe P.; Xiong, Chuanhui
• 署名单位: Purdue University System; Purdue University; State University System of Florida; University of Florida; University of North Carolina; University of North Carolina at Pembroke
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-012-0581-4
• 发表日期: 2013
• 页码: 531-577
• 关键词: global optimization; nonconvex; PROGRAMS; relaxations; EXTENSIONS; bounds

摘要

In this paper, we derive explicit characterizations of convex and concave envelopes of several nonlinear functions over various subsets of a hyper-rectangle. These envelopes are obtained by identifying polyhedral subdivisions of the hyper-rectangle over which the envelopes can be constructed easily. In particular, we use these techniques to derive, in closed-form, the concave envelopes of concave-extendable supermodular functions and the convex envelopes of disjunctive convex functions.