Computing AD-compatible subgradients of convex relaxations of implicit functions
Yingkai Song, Kamil A. Khan · 2025
Read Computing AD-compatible subgradients of convex relaxations of implicit functions by Yingkai Song, Kamil A. Khan (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-18471.txt.
Introduction
Song and Khan extend a computer algebra technique so it can handle functions defined only indirectly, through equations. Global optimization software builds simple bounding curves for complex functions and follows their slopes automatically. A newer method builds those bounds for implicit functions as best-value problems, which blocked slope tracking.
Their 2025 paper derives the first rules for pushing slopes through such indirectly defined bounds. The rules start from slope data for the leftover equation error, supplied in the same style as standard derivative tools. With them, implicit functions can join the standard libraries used by forward slope-tracking modes. Test code in the Julia language shows the idea works. The authors present the rules as a missing piece for automatic bounding tools.
Catalog record
| CREATOR | Yingkai Song, Kamil A. Khan |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 49 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2501-18471
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Computing AD-compatible subgradients of convex relaxations of implicit functions Yingkai Song, Kamil A. Khan Abstract Automatic generation of convex relaxations and subgradients is critical in global optimization, and is typically carried out using variants of automatic/algorithmic differentiation (AD). At previous AD conferences, variants of the forward and reverse AD modes were presented to evaluate accurate subgradients for convex relaxations of supplied composite functions. In a recent approach for generating convex relaxations of implicit functions, these relaxations are constructed as optimal-value functions; this formulation is versatile but complicates sensitivity analysis. We present the first subgradient propagation rules for these implicit function relaxations, based on supplied AD-like knowledge of the residual function. Our new subgradient rules allow implicit function relaxations to be added to the elemental function libraries for the forward AD modes for subgradient propagation of convex relaxations. Proof-of-concept numerical results in Julia are presented. 1 Introduction Typical state-of-the-art methods for global minimization proceed by generating lower and upper bounds on the unknown optimal value, and then successively improving these bounds. While upper bounds may be evaluated as local minima using standard solvers, typical approaches for computing useful lower bounds (e.g. in the solver BARON [ 26 ] ) involve generating convex relaxations and minimizing those. Based on AD-like construction rules by McCormick [ 22 ] , a forward AD mode variant by Mitsos et al. [ 23 ] automatically evaluates a convex relaxation for a supplied composition of elemental functions from a library. Mitsos et al. also developed a forward AD mode variant to evaluate subgradients for these relaxations; subgradients are useful in convex optimization, and are particularly useful when computing the lower bounds in global optimization. At the AD2012 conference, Beckers et al. [ 2 ] presented an efficient reverse AD mode variant of Mitsos et al.’s subgradient propagation method. These AD modes are in active use today, including in the Julia package EAGO.jl [ 35 ] for global optimization, and in a new approach for computing adjoint subgradients of convex relaxations of differential equation solutions [ 38 ] . Cao and Khan [ 6 ] recently presented a new method to construct useful convex relaxations of implicit functions based on known relaxations of the residual functions. Though this approach is versatile, it constructs implicit function relaxations as convex optimal-value functions, for which sensitivity analysis is traditionally considered to be difficult [ 9 ] . In order to incorporate implicit functions into the forward AD modes for subgradient propagation, we seek subgradients of these new relaxations. This article presents the first useful subgradient computation rules for these relaxations, thus allowing implicit functions to be added to the elemental function libraries for constructing McCormick-style convex relaxations with subgradients computed by forward-mode AD, and to be used in established implementations. We informally refer to these properties as “AD-compatibility”. While AD-compatibility is generally not an issue for compositions of smooth functions due to the structure of the well-known chain-rule, appropriate AD rules only have been developed recently for composite nonsmooth functions [ 2 , 17 , 19 , 23 ] . We nevertheless note that due to the nonlinearity with respect to input directions of one of our new approaches, there may not be a direct reverse AD analog of that approach; a similar situation was discussed in [ 11 ] . We proceed based on recent AD rules for nonsmooth optimal value functions [ 29 ] , bound-constrained convex functions [ 37 ] , and nonsmooth closed-form composite functions [ 18 , 19 ] , the latter of which were presented at the AD2012 and AD2016 conferences. The remainder of this article is laid out as follows. Section 2 summarizes relevant established concepts including convex relaxations, subgradients, and the new implicit function relaxations of [ 6 ] . Section 3 summarizes the particular situations we will later consider. Section 4 presents new subgradients for relaxations of scalar-valued implicit functions, Section 5 covers vector-valued implicit functions, and Section 6 presents numerical examples based on a proof-of-concept implementation in Julia. 2 Preliminaries 2.1 Notation Until Section 6 , scalars are denoted as lowercase letters (e.g. x\in\mathbb{R} ), vectors are denoted as boldface lowercase letters (e.g. \mathbf{x}\in\mathbb{R}^{n} ), and the i^{\mathrm{th}} component of a vector \mathbf{x} is denoted as x_{i} . \mathbf{0} denotes a vector with all components zero, with a dimension that is clear from the context. For each j\in\{1,2,...,n\} , denote the j th unit coordinate vector in \mathbb{R}^{n} as \mathbf{e}^{(j)} . Inequalities involving vectors are to be interpreted componentwise. Matrices are denoted as boldface uppercase letters (e.g. \mathbf{M}\in\mathbb{R}^{n\times m} ). The j^{\mathrm{th}} column of a matrix \mathbf{M} is denoted as \mathbf{m}_{(j)} . Sets are denoted as uppercase letters (e.g. X\subset\mathbb{R}^{n} ). For any \mathbf{x}^{\mathrm{L}},\mathbf{x}^{\mathrm{U}}\in\mathbb{R}^{n} with \mathbf{x}^{\mathrm{L}}\leq\mathbf{x}^{\mathrm{U}} , an interval X:=[\mathbf{x}^{\mathrm{L}},\mathbf{x}^{\mathrm{U}}] is defined as the compact set \{\bm{\xi}\in\mathbb{R}^{n}:\mathbf{x}^{\mathrm{L}}\leq\bm{\xi}\leq\mathbf{x}^{\mathrm{U}}\} . Let \mathbb{I}\mathbb{R}^{n} denote the collection of all intervals in \mathbb{R}^{n} . The interior of a set X is denoted as \mathrm{int}(X) . For a scalar-valued (Fréchet) differentiable function f(\mathbf{x},\mathbf{y}) , \nabla_{\mathbf{x}}f(\mathbf{x},\mathbf{y})\in\mathbb{R}^{n_{x}} and \nabla_{\mathbf{y}}f(\mathbf{x},\mathbf{y})\in\mathbb{R}^{n_{y}} denote the partial gradients of f with respect to \mathbf{x} and \mathbf{y} , respectively. A vector function \mathbf{f} is said to be convex, if each component f_{i} is convex. The abbreviation “s.t.” stands for “subject to”. 2.2 Convex relaxations and subgradients In state-of-the-art global optimization solvers such as BARON [ 26 ] , upper and lower bounds are generated for the unknown optimal value, and are then successively refined. In this setting, lower bounds are typically generated by minimizing convex relaxations; the following definition of convex relaxations accommodates functions with irregular domains. Definition 2.1 (from [ 6 ] ) Consider a convex set P\subset\mathbb{R}^{n_{p}} and a subset Q\subset P . Consider the extended real numbers \bar{\mathbb{R}}:=\mathbb{R}\cup\{-\infty,+\infty\} , and a function \bm{\phi}:Q\to{\mathbb{R}}^{m} . Then: 1. \bm{\phi}^{\mathrm{cv}}:P\to\bar{\mathbb{R}}^{m} is a convex relaxation of \bm{\phi} on P if • \bm{\phi}^{\mathrm{cv}}(\mathbf{p})\leq\bm{\phi}(\mathbf{p}) for all \mathbf{p}\in Q , and • \bm{\phi}^{\mathrm{cv}} is convex on P . 2. \bm{\phi}^{\mathrm{cc}}:P\to\bar{\mathbb{R}}^{m} is a concave relaxation of \bm{\phi} on P if • \bm{\phi}^{\mathrm{cc}}(\mathbf{p})\geq\bm{\phi}(\mathbf{p}) for all \mathbf{p}\in Q , and • \bm{\phi}^{\mathrm{cc}} is concave on P . Definition 2.2 (from [ 27 ] ) Given an open set X\subset\mathbb{R}^{n} , a function \mathbf{f}:X\to\mathbb{R}^{m} , and vectors \mathbf{x}\in X and \mathbf{d}\in\mathbb{R}^{n} , the limit \lim_{\alpha\downarrow 0}\frac{\mathbf{f}(\mathbf{x}+\alpha\mathbf{d})-\mathbf{f}(\mathbf{x})}{\alpha} is called the directional derivative of \mathbf{f} at \mathbf{x} in the direction \mathbf{d} if it exists, and is denoted as \mathbf{f}^{\prime}(\mathbf{x};\mathbf{d}) or [\mathbf{f}]^{\prime}(\mathbf{x};\mathbf{d}) ; the latter notation is clearer when a function’s name includes superscripts. The function \mathbf{f} is directionally differentiable at \mathbf{x} if \mathbf{f}^{\prime}(\mathbf{x};\mathbf{d}) exists and is finite for each \mathbf{d}\in\mathbb{R}^{n} . Convex functions defined on open sets are always directionally differentiable (see [ 25 , Theorem 23.4] ). The following definition of subgradients is standard in convex analysis [ 25 ] . Definition 2.3 (from [ 25 , Page 214] ) Given an open convex set X\subset\mathbb{R}^{n} , a convex function f^{\mathrm{cv}}:X\to\mathbb{R} , and a point \mathbf{x}\in\mathrm{int}(X) , a vector \mathbf{s}^{\mathrm{cv}}\in\mathbb{R}^{n} is a subgradient of f^{\mathrm{cv}} at \mathbf{x}\in X if f^{\mathrm{cv}}(\bm{\xi})\geq f^{\mathrm{cv}}(\mathbf{x})+\langle\mathbf{s}^{\mathrm{cv}},\bm{\xi}-\mathbf{x}\rangle,\quad\forall\bm{\xi}\in X. Similarly, given a concave function f^{\mathrm{cc}}:X\to\mathbb{R} , \mathbf{s}^{\mathrm{cc}}\in\mathbb{R}^{n} is a subgradient of f^{\mathrm{cc}} at \mathbf{x}\in X if f^{\mathrm{cc}}(\bm{\xi})\leq f^{\mathrm{cc}}(\mathbf{x})+\langle\mathbf{s}^{\mathrm{cc}},\bm{\xi}-\mathbf{x}\rangle,\quad\forall\bm{\xi}\in X. The subdifferential \partial f^{\mathrm{cv}}(\mathbf{x})\subset\mathbb{R}^{n} (resp. \partial f^{\mathrm{cc}}(\mathbf{x})\subset\mathbb{R}^{n} ) is the collection of all subgradients of f^{\mathrm{cv}} (resp. f^{\mathrm{cc}} ) at \mathbf{x} ,