A new framework to relax composite functions in nonlinear programs
| العنوان: | A new framework to relax composite functions in nonlinear programs |
|---|---|
| المؤلفون: | Mohit Tawarmalani, Taotao He |
| المصدر: | Mathematical Programming. 190:427-466 |
| بيانات النشر: | Springer Science and Business Media LLC, 2020. |
| سنة النشر: | 2020 |
| مصطلحات موضوعية: | Discrete mathematics, 021103 operations research, General Mathematics, Numerical analysis, 0211 other engineering and technologies, Structure (category theory), Estimator, Polytope, 010103 numerical & computational mathematics, 02 engineering and technology, 01 natural sciences, Nonlinear system, Product (mathematics), Graph (abstract data type), Relaxation (approximation), 0101 mathematics, Software, Mathematics |
| الوصف: | 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 polytope P, 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 subset Q of P, with significantly simpler combinatorial structure, such that the separation problem of the graph of the outer-function over P is polynomially equivalent, via a fast combinatorial algorithm, to that of its graph over Q. We specialize our study to consider the product of two inner-functions with one non-trivial underestimator for each inner-function. For the corresponding polytope P, 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. |
| تدمد: | 1436-4646 0025-5610 |
| DOI: | 10.1007/s10107-020-01541-x |
| URL الوصول: | https://explore.openaire.eu/search/publication?articleId=doi_________::be0fc9fb61a30f3bd3e138e72cf0a985 https://doi.org/10.1007/s10107-020-01541-x |
| Rights: | CLOSED |
| رقم الانضمام: | edsair.doi...........be0fc9fb61a30f3bd3e138e72cf0a985 |
| قاعدة البيانات: | OpenAIRE |
| تدمد: | 14364646 00255610 |
|---|---|
| DOI: | 10.1007/s10107-020-01541-x |