Tractable Relaxations of Composite Functions

Taotao He () and Mohit Tawarmalani ()
Additional contact information
Taotao He: Antai College of Economics and Management, Shanghai Jiao Tong University, Shanghai 200030, China PRC
Mohit Tawarmalani: Krannert School of Management, Purdue University, West Lafayette, Indiana 47907

Mathematics of Operations Research, 2022, vol. 47, issue 2, 1110-1140

Abstract: In this paper, we introduce new relaxations for the hypograph of composite functions assuming that the outer function is supermodular and concave extendable. Relying on a recently introduced relaxation framework, we devise a separation algorithm for the graph of the outer function over P , where P is a special polytope to capture the structure of each inner function using its finitely many bounded estimators. The separation algorithm takes O ( d n log d ) time, where d is the number of inner functions and n is the number of estimators for each inner function. Consequently, we derive large classes of inequalities that tighten prevalent factorable programming relaxations. We also generalize a decomposition result and devise techniques to simultaneously separate hypographs of various supermodular, concave-extendable functions using facet-defining inequalities. Assuming that the outer function is convex in each argument, we characterize the limiting relaxation obtained with infinitely many estimators as the solution of an optimal transport problem. When the outer function is also supermodular, we obtain an explicit integral formula for this relaxation.

Keywords: Primary: 90C11; 90C26; 90C30; secondary: 60E15; mixed-integer nonlinear programs; factorable programming; supermodularity; staircase triangulation; convexification via optimal transport (search for similar items in EconPapers)
Date: 2022
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/moor.2021.1162 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:47:y:2022:i:2:p:1110-1140

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().