General convex relaxations of implicit functions and inverse functions

Huiyi Cao () and Kamil A. Khan ()
Additional contact information
Huiyi Cao: McMaster University
Kamil A. Khan: McMaster University

Journal of Global Optimization, 2023, vol. 86, issue 3, No 1, 545-572

Abstract: Abstract Convex relaxations of nonconvex functions provide useful bounding information in applications such as deterministic global optimization and reachability analysis. In some situations, the original nonconvex functions may not be known explicitly, but are instead described implicitly by nonlinear equation systems. In these cases, established convex relaxation methods for closed-form functions are not directly applicable. This article presents a new general strategy to construct convex relaxations for such implicit functions. These relaxations are described as convex parametric programs whose constraints are convex relaxations of the original residual function. This relaxation strategy is straightforward to implement, produces tight relaxations in practice, is particularly efficient to carry out when monotonicity properties can be exploited, and does not assume the existence or uniqueness of an implicit function on the entire intended domain. Unlike all previous approaches to the authors’ knowledge, this new approach permits any relaxations of the residual function; it does not require the residual relaxations to be factorable or to be obtained from a McCormick-like traversal of a computational graph. This new convex relaxation strategy is extended to inverse functions, compositions involving implicit functions, feasible-set mappings in constraint satisfaction problems, and solutions of parametric ODEs. Based on a proof-of-concept implementation in Julia, numerical examples are presented to illustrate the convex relaxations produced for various implicit functions and optimal-value functions.

Keywords: Implicit functions; Nonconvex optimization; Convex underestimators; McCormick relaxations; Constraint satisfaction problems (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10898-023-01281-0 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:spr:jglopt:v:86:y:2023:i:3:d:10.1007_s10898-023-01281-0

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/10898

DOI: 10.1007/s10898-023-01281-0

Access Statistics for this article

Journal of Global Optimization is currently edited by Sergiy Butenko

More articles in Journal of Global Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().