Optimization Online


Inclusion Certificates and Simultaneous Convexification of Functions

Mohit Tawarmalani (mtawarma***at***purdue.edu)

Abstract: 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.

Keywords: convex extensions, barycentric coordinates, convexification, submodularity

Category 1: Integer Programming ((Mixed) Integer Nonlinear Programming )

Category 2: Global Optimization (Theory )

Category 3: Integer Programming (0-1 Programming )


Download: [PDF]

Entry Submitted: 09/05/2010
Entry Accepted: 09/06/2010
Entry Last Modified: 09/08/2010

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society