Pith. sign in

REVIEW 2 major objections 4 minor 38 references

Computing AD-compatible subgradients of convex relaxations of implicit functions

T0 review · 2 major / 4 minor · reviewed 2026-08-09 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read This paper establishes the first LP-based subgradient propagation rules for convex relaxations of implicit functions, making those relaxations compatible with forward-mode automatic differentiation.

desk verdict Useful first subgradient rules for implicit-function relaxations, but the Section 5 LP claims are wrong as stated and need major revision. read the letter →

arxiv 2501.18471 v1 pith:XWYDLJFC submitted 2025-01-30 math.OC cs.NAmath.NA

Yingkai Song , Kamil A. Khan This is my paper · ORCID
classification math.OCcs.NAmath.NA MSC 90C2690C3149J5265K05
keywords convexrelaxationsimplicitfunctionssubgradientsautomaticdifferentiationlexicographicderivativesglobaloptimizationoptimal-valuelinearprogramming
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper aims to make a recent class of convex relaxations of implicit functions usable inside automatic-differentiation-based subgradient propagation for global optimization. It claims that the subgradient of such a relaxation can be computed from the relaxations of the residual function alone, without differentiating through the original implicit equation. The paper establishes closed-form rules for scalar implicit functions and LP-based rules, using directional derivatives or lexicographic derivatives, for vector-valued ones. Since the relaxed value function is convex, the computed lexicographic derivative is a valid subgradient. If correct, this adds implicit functions to the elemental function library used by forward-mode AD subgradient propagation.

What carries the argument

The load-bearing mechanism is the auxiliary linear program (5.12), which converts the nonlinear sensitivity of the optimal-value relaxation into a direction-dependent LP formed from the active inequality constraints and the affine equality constraints at an optimal solution. In the scalar case the mechanism is instead the closed-form reduction $x^{cv}(p)=\max\{x_L,h^{cv}(p)\}$, whose subgradient is the slope of the active affine piece. In higher-dimensional parameter spaces, Theorem 5.1 feeds the directional-derivative LP through the homogenization sequence that defines lexicographic derivatives, directional derivatives taken successively in prescribed directions, and equation (2.5) turns the resulting LD-derivative into an L-derivative, which is a valid subgradient because the relaxation is convex.

What would settle it

Take a vector-valued implicit function whose defining relaxation (5.11) has two distinct optimal solutions $u_1$ and $u_2$ at the reference parameter while Assumption 5.2 holds; solve the auxiliary LP (5.12) in a fixed direction $d$ using each solution in turn. If the two computed directional derivatives differ, Proposition 5.1's claim that any optimal solution works would be false, and the LP-based subgradient rules built on it would not be reliable.

Watch

Extended reading notes

Core claim

On the paper's own terms, the central claim is that the convex relaxation $x_i^{cv}$ defined in (2.3) as the optimal value of minimizing $\xi_i$ over the relaxed residual inequalities $f^{cv}(\xi,p) \le 0 \le f^{cc}(\xi,p)$ can be differentiated in the AD sense using only the relaxations of the residual function. For scalar implicit functions with piecewise affine residual relaxations, the relaxation reduces to $x^{cv}(p)=\max\{x_L,h^{cv}(p)\}$ and a subgradient is read off from whichever piece is active. For vector-valued implicit functions, the paper proves that a directional derivative $[x_i^{cv}]'(p;d)$ can be computed by solving a small LP formed from the active constraints at any optimal solution of the defining program, and that composing these directional derivatives through the L-derivative homogenization sequence yields a valid subgradient because $x_i^{cv}$ is convex. This is the first subgradient propagation rule for these implicit-function relaxations, and it is designed to drop into the existing forward mode for subgradient propagation.

Load-bearing premise

The vector-valued subgradient rules all require a strong Slater condition: near the reference parameter the relaxed feasible region must contain a point that satisfies every inequality strictly and all equalities exactly, with the affine equality constraints linearly independent.

Editorial extensions

If this is right

  • Implicit functions defined by residual equations enter the elemental function library of forward-mode AD subgradient propagation, so global optimization solvers can build and minimize convex relaxations of models that contain implicit functions.
  • In the scalar case, when the residual relaxations are piecewise affine, both the relaxation value and a subgradient are obtained in closed form without solving any optimization problem.
  • For one parameter, the directional derivative in the single available direction is already a subgradient; for two parameters, four cardinal directional derivatives, each from one LP, give a subgradient.
  • In the high-dimensional parameter case, the L-derivative method requires only a short sequence of LPs, and in practice often just two: the first LP plus an auxiliary LP that tests uniqueness of its optimal solution.
  • Concave relaxations are covered with no extra machinery, by applying the same rules to $-x_i^{cc}$.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • A likely consequence is that any convex relaxation expressed as the optimal value of a parameterized convex program with piecewise smooth data could be given AD-compatible subgradients by the same LP-based route, not just the implicit-function relaxations treated here.
  • Because the paper notes that one new approach is nonlinear in the input direction, reverse-mode integration would probably need to store or recompute the LP solutions rather than run a straightforward adjoint sweep, a practical trade-off the paper does not address.
  • When the strong Slater condition fails because the relaxed optimizer sits on a variable bound, a pragmatic workaround would be to enlarge the enclosing interval $X$ slightly to restore a strict interior point, accepting a looser relaxation in exchange for a valid subgradient.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 4 minor

Summary. The manuscript proposes subgradient computation rules for convex relaxations of implicit functions defined by residual equations (the optimal-value relaxations of Cao and Khan). For a scalar implicit function (nx = 1) with piecewise affine residual relaxations, it derives closed-form subgradients. For vector-valued implicit functions (nx > 1), it presents an LP-based formula for the directional derivative of the convex relaxation and uses this to construct subgradients for np = 1, np = 2, and np > 2 (the last via lexicographic derivatives). The claimed goal is to make implicit function relaxations compatible with forward-mode AD subgradient libraries for global optimization. Numerical proof-of-concept examples in Julia are provided.

Significance. If correct, the nx > 1 subgradient rules would be a valuable contribution, enabling implicit functions to enter standard AD-based subgradient propagation. The scalar case in Section 4 is elegant and appears sound, and the numerical examples illustrate the intended use. However, the central claims for nx > 1 are invalid as stated: the LP formula (5.12) is not independent of the chosen optimal solution of (5.11), and the claimed subgradient rule for np = 1 fails for the direction d = -1 at differentiable points with a nonzero derivative. These errors invalidate Propositions 5.2, 5.3, and Theorem 5.1, which are the core advertised results of the paper. The paper therefore does not currently support its main claims, although the defect is localized to Section 5 and the scalar-section remains a useful contribution.

major comments (2)
  1. [Section 5, Proposition 5.1, Eq. (5.12)] The assertion that (5.12) computes [x_cv_i]'(\hat{p}; d) for any optimal solution \hat{\xi} of (5.11) is false. Consider the convex program v(p) = min{ x : x >= 0, 0 <= y <= 1, x + y >= p }, which satisfies Assumption 5.2 at \hat{p} = 0: the Slater condition holds, e.g., at (x,y) = (1, 0.5) for p near 0. The value function is v(p) = max(0, p - 1), so v'(0; 1) = 0. The two points (0,0) and (0,1) are both optimal at p = 0. Applying (5.12) at (0,0) with d = 1 yields min{ w_x : w_x >= 0, w_y >= 0, w_x + w_y >= 1 } = 1, while at (0,1) it yields 0. Thus the value of (5.12) depends on the chosen optimal solution and can be a non-derivative. Since the proof cites only [29, Theorem 3 and Proposition 1] and Assumption 5.2 imposes no uniqueness or tie-breaking condition, the claim 'any optimal solution' cannot be correct as stated. Proposition 5.2, Proposition 5.3, and Theorem 5.1 all rely on Proposition 5.1, so they inherit this failure.
  2. [Section 5.1, Proposition 5.2] The claim that for np = 1 the directional derivative in direction d = -1 is a subgradient is false. For a differentiable convex function f at an interior point p with f'(p) != 0, the directional derivative is f'(p; -1) = -f'(p), which is a subgradient only when f'(p) = 0. For example, f(t) = t^2 at p = 1 has f'(1; -1) = -2, while the unique subgradient is 2. Consequently, even if the directional derivative in (5.12) were computed correctly, the advertised np = 1, nx > 1 case does not provide a valid subgradient in general.
minor comments (4)
  1. [Section 5, Assumption 5.1] In the displayed definition of the concave pieces, the final term '... , \tilde f^{cv,l_i}_i' should presumably read '\tilde f^{cc,l_i}_i' to match the notation for the concave relaxation.
  2. [Section 4, Proposition 4.1] In the bullet for the concave case, the text writes 'scv := - a^{cc,j} / \alpha^{cc,j}' and 'scv := - a^{cv,i} / \alpha^{cv,i}' where 'scc' is clearly intended; this is a notation slip that should be corrected.
  3. [Section 6, Example 6.2] The numerical active-constraint tolerance of 1e-7 is a free parameter, but the sensitivity of the resulting subgradients to this tolerance is not discussed; a brief remark on how to choose this tolerance robustly would strengthen the proof-of-concept presentation.
  4. [Section 5, Proposition 5.1 proof] The proof delegates entirely to [29] without stating which theorem is being invoked or verifying its hypotheses in this setting; given that the result is central and false as stated, the paper should state the precise conditions from [29] and check them explicitly.

Circularity Check

0 steps flagged · score 2.0 of 10

No significant circularity: the subgradient formulas are derived by applying prior general theorems to the specific optimal-value function, not by fitting the claimed output into the inputs.

full rationale

I walked the derivation chain from Definition 2.4 and Proposition 2.1 through Sections 4 and 5. The relaxation x_cv_i is defined in (2.3) as the optimal value of a convex program built from supplied residual-function relaxations; the proposed subgradient rule is not part of that definition. Proposition 5.1 computes the directional derivative via the LP (5.12), with the proof delegated to [29, Theorem 3 and Proposition 1]; Theorem 5.1 then iterates that formula using LP duality and the directional derivative as the first homogenization step. Proposition 4.1 follows from the closed form (4.9), which is itself derived from the relaxation construction rather than assumed. In no step does the paper take the claimed subgradient as an assumption, fit a parameter to a target quantity, or define the output in terms of itself. The main caveat is that several load-bearing theorems come from prior work by the same authors, namely [29], [36], and [37], so the paper is not fully independent of its own research lineage; however, those cited results are general theorems about parameterized convex programs and convex functions of two variables, and the present paper does not redefine them in terms of the present claim. This self-citation burden justifies a modest score of 2, but no actual circular step was identified.

Assumptions & free parameters 2 free parameters · 5 assumptions · 0 invented entities

No invented entities: the paper uses existing concepts, including implicit function relaxations from [6], L-derivatives from [24], and LP sensitivity from [29]. The free parameters listed are confined to the numerical examples; the theoretical subgradient rules have no fitted constants.

free parameters (2)
  • Example 6.1 subtangent reference points = (17.67, 0.68, 274.27), (67.78, 0.73, 288.82)
    Hand-picked points used to build the two-piece affine residual relaxations in the scalar example; they affect that example's relaxation but not the theoretical rules.
  • Active-constraint tolerance = 1e-7
    Used in Example 6.2 to decide which constraints enter the directional-derivative LP (5.12); a different tolerance could produce a different active set.
assumptions (5)
  • domain assumption Existence of an implicit function and a known interval X enclosing all solutions
    Definition 2.4; needed so x_cv_i and x_cc_i are well-defined relaxations on P.
  • ad hoc to paper Residual relaxations are piecewise affine
    Assumption 4.1; enables the closed-form box reformulation (4.8)-(4.9). This excludes general nonlinear relaxations in the scalar case.
  • domain assumption Residual relaxations are piecewise differentiable as max/min of continuously differentiable functions
    Assumption 5.1; satisfied by McCormick, differentiable McCormick and alphaBB relaxations, but not by all relaxations.
  • domain assumption Strong Slater condition and linear independence of affine constraint gradients
    Assumption 5.2; required for [29]'s LP directional derivative formula to apply.
  • standard math External LP sensitivity results [29, Thm 3/4] and bivariate subgradient formula [36, Thm 3.3]
    Propositions 5.1, 5.3 and Theorem 5.1 cite these published theorems as black boxes.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Computing AD-compatible subgradients of convex relaxations of implicit functions." pith.science (2026). https://pith.science/paper/XWYDLJFC

@misc{pith2026250118471,
  author       = {Pith},
  title        = {Pith review of: Computing AD-compatible subgradients of convex relaxations of implicit functions},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/XWYDLJFC}},
  note         = {Machine review of arXiv:2501.18471}
}
read the original 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.

Figures

Figures reproduced from arXiv: 2501.18471 by the authors.

Figure 1
Figure 1. The implicit function V (blue) in terms of P and T on [0.5, 1.1] × [250, 320], along with the constructed convex and concave relaxations (red), for Example 6.1. and similarly, a two-piece affine concave relaxation is constructed as the pointwise minimum of two subtangents of the concave McCormick relaxations: f cc(V, P, T) = min ( 1.13V + 9.95P − 0.08T − 10.97, 0.43V + 69.95P − 0.08T − 30.11) . Then, with the functi… view at source ↗
Figure 2
Figure 2. A cross-section at p1 := 0.6 of the implicit function z3 (solid blue) of (p1, p2), along with convex and concave relaxations (dashed red) and subtangents (dotted black) generated from the reference point (p1, p2) := (0.6, 1.348), for Example 6.2. constraints at an optimal solution of the optimization problem in (2.3). Numerically, we consider a constraint gi( ˆξ, pˆ) = 0 to be active if the value of the residual fun… view at source ↗
Figure 3
Figure 3. A cross-section at p1 := 0.40 of the implicit function z1 (blue) of (p1, p2, p3), along with convex and concave relaxations (red) and subtangents constructed using our new approach (black), for Example 6.3. One subtangent is generated using the subgradient of the convex relaxation at (p1, p2, p3) := (0.40, 0.0575, 8.7), and another is generated using the subgradient of the concave relaxation at (p1, p2, p3) := (0.40… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

38 extracted references · 36 canonical work pages

  1. [1]

    C. S. Adjiman, S. Dallwig, C. A. Floudas, and A. Neumaier, A global optimization method, αBB, for general twice- differentiable constrained NLPs—I. Theoretical advances, Comput. Chem. Eng., 22 (1998), pp. 1137–1158

    work page 1998

  2. [2]

    Beckers, V

    M. Beckers, V. Mosenkis, and U. Naumann, Adjoint mode computation of subgradients for McCormick relaxations , in Recent Advances in Algorithmic Differentiation, S. Forth, P. Hovland, E. Phipps, J. Utke, and A. Walther, eds., Springer, Berlin, 2012, pp. 103–113

    work page 2012

  3. [3]

    Bertsimas and J

    D. Bertsimas and J. N. Tsitsiklis, Introduction to Linear Optimization , Athena Scientific, Belmont, 1997

    work page 1997

  4. [4]

    Bezanson, A

    J. Bezanson, A. Edelman, S. Karpinski, and V. B. Shah, Julia:A fresh approach to numerical computing , SIAM Rev., 59 (2017), pp. 65–98

    work page 2017

  5. [5]

    Boyd and L

    S. Boyd and L. Vandenberghe, Convex optimization , Cambridge University Press, Cambridge, 2004

    work page 2004

  6. [6]

    Cao and K

    H. Cao and K. A. Khan, General convex relaxations of implicit functions and inverse functions , J. Glob. Optim., 86 (2023), pp. 545–572

    work page 2023

  7. [7]

    H. Cao, Y. Song, and K. A. Khan, Convergence of subtangent-based relaxations of nonlinear programs , Processes, 7 (2019), p. 221

    work page 2019

  8. [8]

    Dunning, J

    I. Dunning, J. Huchette, and M. Lubin, JuMP: A modeling language for mathematical optimization , SIAM Rev., 59 (2017), pp. 295–320

    work page 2017

Show all 38 references
  1. [9]

    A. V. Fiacco and Y. Ishizuka, Sensitivity and stability analysis for nonlinear programming, Ann. Oper. Res., 27 (1990), pp. 215–235

    1990

  2. [10]

    Gowda, Y

    S. Gowda, Y. Ma, A. Cheli, M. Gw´ o´ zd´ z, V. B. Shah, A. Edelman, and C. Rackauckas,High-performance symbolic- numerics via multiple dispatch , ACM Commun. Comput. Algebra, 55 (2022), p. 92–96. Copyright © 2025 by SIAM Unauthorized reproduction of this article is prohibited

    2022

  3. [11]

    Griewank, Automatic directional differentiation of nonsmooth composite functions , in Recent Developments in Optimization: French-German Conference on Optimization, R

    A. Griewank, Automatic directional differentiation of nonsmooth composite functions , in Recent Developments in Optimization: French-German Conference on Optimization, R. Durier and C. Michelot, eds., Dijon, 1995, Springer, pp. 155–169

    1995

  4. [12]

    Hiriart-Urruty and C

    J.-B. Hiriart-Urruty and C. Lemar´ echal, Convex Analysis and Minimization Algorithms I: Fundamentals , Springer, Berlin, 2013

    2013

  5. [13]

    https://github.com/JuliaNLSolvers/NLsolve.jl

    JuliaNLSolvers, NLsolve.jl: Julia solvers for systems of nonlinear equations and mixed complementarity problems . https://github.com/JuliaNLSolvers/NLsolve.jl. Accessed:April 23, 2024

    2024

  6. [14]

    https://github.com/JuliaOpt/GLPK.jl

    JuliaOpt, GLPK.jl: A Julia interface to GLPK . https://github.com/JuliaOpt/GLPK.jl. Accessed: April 23, 2024

    2024

  7. [15]

    Khajavirad and N

    A. Khajavirad and N. V. Sahinidis, Convex envelopes of products of convex and component-wise concave functions , J. Glob. Optim., 52 (2012), pp. 391–409

    2012

  8. [16]

    Program., 137 (2013), pp

    , Convex envelopes generated from finitely many compact convex sets , Math. Program., 137 (2013), pp. 371–408

    2013

  9. [17]

    K. A. Khan, Branch-locking AD techniques for nonsmooth composite functions and nonsmooth implicit functions , Optim. Methods Softw., 33 (2018), pp. 1127–1155

    2018

  10. [18]

    K. A. Khan and P. I. Barton, Evaluating an element of the Clarke generalized Jacobian of a piecewise differentiable function, in Recent Advances in Algorithmic Differentiation, S. Forth, P. Hovland, E. Phipps, J. Utke, and A. Walther, eds., Springer-Verlag, Berlin, 2012, pp. 115–125

    2012

  11. [19]

    Methods Softw., 30 (2015), pp

    , A vector forward mode of automatic differentiation for generalized derivative evaluation , Optim. Methods Softw., 30 (2015), pp. 1185–1212

    2015

  12. [20]

    K. A. Khan, H. A. Watson, and P. I. Barton, Differentiable McCormick relaxations , J. Glob. Optim., 67 (2017), pp. 687–729

    2017

  13. [21]

    Mangasarian, Uniqueness of solution in linear programming , Linear Algebra Appl., 25 (1979), pp

    O. Mangasarian, Uniqueness of solution in linear programming , Linear Algebra Appl., 25 (1979), pp. 151–162

    1979

  14. [22]

    G. P. McCormick, Computability of global solutions to factorable nonconvex programs: Part I—Convex underestimat- ing problems, Math. Program., 10 (1976), pp. 147–175

    1976

  15. [23]

    Mitsos, B

    A. Mitsos, B. Chachuat, and P. I. Barton, McCormick-based relaxations of algorithms , SIAM J. Optim., 20 (2009), pp. 573–601

    2009

  16. [24]

    Nesterov, Lexicographic differentiation of nonsmooth functions , Math

    Y. Nesterov, Lexicographic differentiation of nonsmooth functions , Math. Program., 104 (2005), pp. 669–700

    2005

  17. [25]

    R. T. Rockafellar, Convex Analysis, Princeton University Press, Princeton, 1970

    1970

  18. [26]

    N. V. Sahinidis, BARON: A general purpose global optimization software package , J. Glob. Optim., 8 (1996), pp. 201– 205

    1996

  19. [27]

    Scholtes, Introduction to Piecewise Differentiable Equations , Springer, Berlin, 2012

    S. Scholtes, Introduction to Piecewise Differentiable Equations , Springer, Berlin, 2012

    2012

  20. [28]

    J. K. Scott, M. D. Stuber, and P. I. Barton, Generalized McCormick relaxations, J. Glob. Optim., 51 (2011), pp. 569– 606

    2011

  21. [29]

    Song and P

    Y. Song and P. I. Barton, Generalized derivatives of optimal-value functions with parameterized convex programs embedded, J. Glob. Optim., 89 (2024), pp. 355–378

    2024

  22. [30]

    Y. Song, H. Cao, C. Mehta, and K. A. Khan, Bounding convex relaxations of process models from below by tractable black-box sampling, Comput. Chem. Eng., 153 (2021), p. 107413

    2021

  23. [31]

    M. D. Stuber and P. I. Barton, Semi-infinite optimization with implicit functions , Ind. Eng. Chem. Res., 54 (2015), pp. 307–317

    2015

  24. [32]

    M. D. Stuber, J. K. Scott, and P. I. Barton, Convex and concave relaxations of implicit functions , Optim. Methods Softw., 30 (2015), pp. 424–460

    2015

  25. [33]

    Thibault, On subdifferentials of optimal value functions , SIAM J

    L. Thibault, On subdifferentials of optimal value functions , SIAM J. Control Optim., 29 (1991), pp. 1019–1036

    1991

  26. [34]

    W¨ achter and L

    A. W¨ achter and L. T. Biegler, On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming, Math. Program., 106 (2006), pp. 25–57

    2006

  27. [35]

    M. E. Wilhelm and M. D. Stuber, EAGO. jl: easy advanced global optimization in Julia , Optim. Methods Softw., 37 (2022), pp. 425–450

    2022

  28. [36]

    Yuan and K

    Y. Yuan and K. A. Khan, Constructing a subgradient from directional derivatives for functions of two variables , Journal of Nonsmooth Analysis and Optimization, 1 (2020)

    2020

  29. [37]

    , Automatic differentiation rules for Tsoukalas–Mitsos convex relaxations in global process optimization , Digit. Chem. Eng., 7 (2023), p. 100097

    2023

  30. [38]

    Zhang and K

    Y. Zhang and K. A. Khan, Evaluating subgradients for convex relaxations of dynamic process models by adapting current tools, Comput. Chem. Eng., 180 (2024), p. 108462. Copyright © 2025 by SIAM Unauthorized reproduction of this article is prohibited

    2024

Pith tools

Reviewed August 9, 2026 · model on record in the stance chip above.