Inclusion Certificates and Simultaneous Convexification of Functions
Inclusion Certificates and Simultaneous Convexification of Functions
复制标题
DOI：
--
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
Mohit Tawarmalani
中科院分区：
文献类型：
--
作者：
Mohit Tawarmalani
We define the inclusion certificate as a measure that expresses each point in the domain of a collection of functions as a convex combination of other points in the domain. Using inclusion certificates, we extend the convex extensions theory to enable simultaneous convexification of functions. We discuss conditions under which the domain of the functions can be reduced without affecting the simultaneous convex hull of the functions. For example, we show that a collection of multilinear functions can be convexified over a cartesian product of compact convex sets by restricting attention to the extreme points of the domain. We relate disjunctive programming to convex extensions theory and provide insights, generalizations, and shorter proofs for convexifying orthogonal disjunctions. Each convex envelope is naturally associated with an inclusion certificate. When the inclusion certificate matches across a collection of functions, we show that convexifying individual functions yields the simultaneous convex hull of a collection of functions. In particular, we show that it is easy to sequentially convexify submodular functions one variable at a time. Further, a collection of submodular functions is convexified by individually convexifying the functions. Various other ways of composing functions and their associated convex envelopes are also discussed.
We define the inclusion certificate as a measure that expresses each point in the domain of a collection of functions as a convex combination of other points in the domain. Using inclusion certificates, we extend the convex extensions theory to enable simultaneous convexification of functions. We discuss conditions under which the domain of the functions can be reduced without affecting the simultaneous convex hull of the functions. For example, we show that a collection of multilinear functions can be convexified over a cartesian product of compact convex sets by restricting attention to the extreme points of the domain. We relate disjunctive programming to convex extensions theory and provide insights, generalizations, and shorter proofs for convexifying orthogonal disjunctions. Each convex envelope is naturally associated with an inclusion certificate. When the inclusion certificate matches across a collection of functions, we show that convexifying individual functions yields the simultaneous convex hull of a collection of functions. In particular, we show that it is easy to sequentially convexify submodular functions one variable at a time. Further, a collection of submodular functions is convexified by individually convexifying the functions. Various other ways of composing functions and their associated convex envelopes are also discussed.