REVIEW 3 major objections 3 minor 29 references
A sensitivity-based method for bilevel optimization problems: Theoretical analysis and computational performance
T0 review · 3 major / 3 minor · reviewed 2026-08-04 · deepseek-v4-flash
Pith's one-line read A reformulation-free bilevel solver converges to S-stationary points with one adjoint solve per step.
desk verdict The algorithmic package is plausible but the central equivalence theorem is false—there's a simple counterexample, so take the theory with a grain of salt. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The sensitivity system — a linear system built from the Hessian of the lower-level Lagrangian and the Jacobian of the active constraints — is the engine of the method. Nonsingularity of its matrix (guaranteed by the regularity assumptions) makes the lower-level solution y-bar(x) locally differentiable and defines the total gradients of the upper-level functions. Rather than forming the full sensitivity matrix from this system, the algorithm solves an adjoint system that yields the same gradient at the cost of a single linear solve. This adjoint system is also the bridge between the reduced problem's KKT conditions and MPCC S-stationarity.
What would settle it
Find a bilevel instance satisfying the regularity assumptions and MPEC-LICQ for which the algorithm returns a KKT point of the reduced problem that fails the MPCC S-stationarity sign conditions (e.g., a negative multiplier for an active lower-level constraint). Theorem 3.2 declares such an instance impossible; exhibiting one — or running the check on a battery of degenerate benchmarks — would directly test the central equivalence claim.
Extended reading notes
Core claim
The central claim is that the implicit reduced problem min_x F(x, y-bar(x)) can be minimized efficiently and reliably by combining parametric sensitivity analysis with an augmented Lagrangian framework. The paper's main theoretical contribution is Theorem 3.2: assuming lower-level LICQ, the second-order sufficient condition, strict complementarity, and MPEC-LICQ, a KKT point of the reduced problem is exactly an S-stationary point of the KKT-based MPCC reformulation. The proof constructs adjoint variables from the sensitivity system and shows they satisfy the MPCC stationarity conditions, establishing a two-way equivalence. The numerical section demonstrates the method on standard benchmarks,
Load-bearing premise
The entire theory assumes the lower-level solution y-bar(x) stays continuously differentiable at every point the algorithm visits — i.e., LICQ, the second-order sufficient condition, and strict complementarity all hold at each lower-level solution, and the active set never changes.
Editorial extensions
If this is right
- A KKT point found by the algorithm is automatically an S-stationary point of the MPCC reformulation, so the method offers the strongest local optimality guarantee for the single-level formulation.
- Gradient evaluation cost becomes independent of the upper-level dimension, enabling the method to scale to larger leader problems than forward sensitivity approaches.
- The framework decouples the two levels, allowing any reliable NLP solver for the lower level and any bound-constrained quasi-Newton solver for the inner upper-level subproblem.
- LP lower-level problems can be handled by a small epsilon-regularization, extending the approach to linear-follower bilevel problems without changing the algorithm.
- The dual-criterion stopping rule turns the asymmetric primal-dual convergence typical of augmented Lagrangian methods into a practical advantage, avoiding excessive iterations on problems like AiyoshiShimizu1984Ex2.
Reading between the lines
- One implication not spelled out: the adjoint equivalence could be used as a cheap validation check inside a solver — after convergence, solving the adjoint system recovers candidate MPCC multipliers, so dual feasibility of those multipliers can certify (or refute) S-stationarity numerically.
- The factor-n cost reduction suggests the method may be most attractive in problems with a low-dimensional follower and a high-dimensional leader; the benchmark set here is too small to demonstrate that scaling, but it is a testable prediction.
- Because the method's guarantees require differentiability at every iterate, extending it to nonsmooth kinks (as in ClarkWesterberg1990 at x=2 and x=4) would require a bundle-type or lexicographic derivative treatment; the paper leaves that as heuristic territory.
- The multi-start benchmarking hints that the method should be paired with a global search shell for nonconvex upper levels, but the paper does not propose a particular globalisation strategy.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proposes a sensitivity-based augmented Lagrangian method for continuous optimistic bilevel programs with convex lower-level problems. The lower-level solution is treated as an implicit differentiable function of the upper-level variables; total derivatives are computed via a sensitivity system, and upper-level updates are performed by an L-BFGS-B inexact solver. The paper claims convergence to KKT points of the reduced problem (Theorem 3.1) and equivalence of these points to S-stationary points of the MPCC reformulation under MPEC-LICQ (Theorem 3.2). It also claims computational savings from replacing the sensitivity Jacobian with a single adjoint solve per iteration. Numerical experiments on selected BOLIB benchmarks are reported.
Significance. If the theoretical results were correct, the paper would offer a reformulation-free, gradient-based solver for an important class of bilevel problems, with a rigorous stationarity characterization and a claimed reduction in gradient cost. The computational experiments support basic correctness on simple benchmarks. However, the central equivalence theorem is false as stated, and the algorithm as presented does not implement the claimed adjoint-based gradient computation. These are load-bearing flaws that invalidate the main theoretical and computational claims.
major comments (3)
- [§3.6, Theorem 3.2] The forward direction of Theorem 3.2 is false. The proof asserts that the sign conditions π_A≥0 and ξ_I≥0 'follow from optimality' without a derivation, but this is not generally true. Counterexample: minimize F=(x−2)²−y over x∈[0,3], with follower min_y {0.5y²−xy : −y≤0}. For x>0, ybar(x)=x, λ=0, so the reduced objective is x²−5x+4 with a minimum at x*=2.5. All assumptions, including MPEC-LICQ, hold at (2.5,2.5,0). The MPCC stationarity system (28) gives ν=1, π=0, and ξ=−1. Since g=−y<0 and λ=0 lie in I_−, S-stationarity requires ξ≥0, which is violated. Thus a KKT point of the reduced problem need not be S-stationary under the stated assumptions.
- [§3.4, Algorithm 2; §3.3 Eq. (12); Abstract] The abstract and introduction claim that the method 'replaces explicit construction of the sensitivity Jacobian with a single linear adjoint solve per iteration.' However, Algorithm 2, step 5 explicitly says 'Compute sensitivity dy/dx and total gradients (12)', and Eq. (12) uses the full sensitivity matrix dy/dx. The adjoint system (31) appears only in the proof of Theorem 3.2, not in the algorithm or its implementation description. This is a direct inconsistency between the claimed computational contribution and the actual method, and it undermines the stated cost reduction by a factor of the upper-level dimension.
- [§3.5, Theorem 3.1] The convergence proof is only a sketch and contains several unaddressed gaps. Assumption (b) assumes bounded multipliers and compactness a priori, which are not guaranteed by Algorithm 2. More importantly, the inner subproblems are solved inexactly with tolerance ε_inner>0, yet Eq. (25) states that the gradient norm converges to zero. With a fixed positive ε_inner, the gradient norm need only be bounded by ε_inner, not converge to 0. Additionally, inequality (24) is asserted across outer iterations, but the augmented Lagrangian value can increase when multipliers are updated to μ_{k+1} before the next subproblem. These issues make the stated KKT convergence theorem conditional on assumptions that are neither verified nor proven.
minor comments (3)
- [§4.2, ClarkWesterberg1990] Figure 4 explicitly shows nondifferentiable kinks at x=2 and x=4, which violate Assumption 3.1(c) (SCC and differentiability of ybar). The paper presents this problem as a successful test case but does not explain how the convergence theory applies, or whether the behavior across kinks is heuristic. This should be stated as a limitation.
- [§5] The concluding section contains a typo: 'extending extending'. Please correct.
- [§3.6, sign rules] The index set I_− is defined as {i: g_i≤0, λ_i=0}, which overlaps with I_0={i: g_i=0, λ_i=0}. In the proof of Theorem 3.2, I is instead defined as {i: g_i<0, λ_i=0}, relying on SCC to exclude the biactive case. This inconsistency between the definition and the proof should be reconciled.
Circularity Check
No circular derivation: the sensitivity/adjoint and augmented-Lagrangian derivations are self-contained, and benchmark validation is external; the Theorem 3.2 sign-condition gap is a correctness/proof issue rather than circularity.
full rationale
Walking the derivation chain: the reduced problem (8) is the definition of the optimistic bilevel problem with a single-valued lower-level solution; the sensitivity system (11) follows from the implicit function theorem under Assumption 3.1; the total gradients (12) are straightforward chain-rule applications; Algorithm 2 uses these gradients inside a standard augmented-Lagrangian framework; and Theorem 3.1 is a standard ALM convergence argument adapted to this setting. None of these steps fits a parameter, imports a load-bearing result from the authors' own prior work, or renames an empirical pattern as a derivation. The benchmarks are taken from the external BOLIB library and the Clark-Westerberg paper, and the reported objective values are compared against known literature values; matching an externally supplied optimum is validation, not circular construction. The main weakness is in Theorem 3.2: the proof asserts that the S-stationarity sign conditions 'πA≥0 and ξI≥0 follow from the optimality of the KKT point' without a derivation, and the skeptical counterexample suggests the claimed equivalence may be false. However, an unjustified or even false step is a correctness risk, not circularity: the theorem's conclusion is not assumed as an input, not fitted to data, and not imported through a self-citation. There is also an internal inconsistency between the abstract's claim of a single adjoint solve per iteration and Algorithm 2's line 5, which says to 'Compute sensitivity d̄y/dx and total gradients (12)' (i.e., the full sensitivity matrix); that is a performance/implementation concern and not circularity. Overall, no load-bearing circular step is present, so the honest finding is no significant circularity.
Assumptions & free parameters
free parameters (6)
- KKT tolerance epsilon =
1e-5
- inner gradient tolerance epsilon_inner =
unspecified (>0)
- penalty growth factor gamma =
unspecified (>1)
- feasibility improvement ratio c =
unspecified (in (0,1))
- LP regularization epsilon =
1e-6 (example)
- stall tolerance =
1e-5
assumptions (6)
- domain assumption Assumption 3.1: F,G,f,g twice continuously differentiable; lower level strictly convex; LICQ, SOSC, SCC hold at lower-level solutions along the iterate path.
- domain assumption IPOPT reliably returns the global minimizer of the convex parametric lower-level problem at each x_k.
- ad hoc to paper The multiplier sequence {mu_k} is bounded and {x_k} lies in a compact set (Theorem 3.1(b)).
- domain assumption MPEC-LICQ holds at the limit point (Theorem 3.2).
- ad hoc to paper A KKT point of the implicit problem is a local minimum, so sign conditions on MPCC multipliers follow (used in Thm 3.2 forward direction).
- domain assumption Wolfe line search and standard ALM theory for smooth problems transfer to the implicit, nonsmooth reduced problem.
Cite this review
Pith. "Pith review of A sensitivity-based method for bilevel optimization problems: Theoretical analysis and computational performance." pith.science (2026). https://pith.science/paper/Z5QBDNQ6
@misc{pith2026251001487,
author = {Pith},
title = {Pith review of: A sensitivity-based method for bilevel optimization problems: Theoretical analysis and computational performance},
year = {2026},
howpublished = {\url{https://pith.science/paper/Z5QBDNQ6}},
note = {Machine review of arXiv:2510.01487}
}
read the original abstract
Bilevel optimization provides a powerful framework for modelling hierarchical decision-making systems. This work presents a sensitivity-based algorithm that addresses the bilevel structure directly by treating the lower-level optimal solution as an implicit, locally differentiable function of the upper-level variables, thereby avoiding classical single-level reformulations. Under standard regularity assumptions on the lower level, an adjoint-based representation of the reduced upper-level gradient is derived, replacing explicit construction of the sensitivity Jacobian with a single linear adjoint solve per iteration and reducing gradient evaluation cost by a factor equal to the upper-level dimension. The reduced problem is solved within an Augmented Lagrangian framework, with inner subproblems managed by an L-BFGS-B quasi-Newton solver. Convergence to KKT points of the reduced problem is established, and these points are shown to be equivalent to S-stationary solutions of the associated mathematical programme with complementarity constraints under MPEC-LICQ. Computational experiments on benchmark bilevel problems validate the method's correctness and robustness, and demonstrate the effectiveness of a pragmatic dual-criterion stopping condition in handling the asymmetric primal-dual convergence rates characteristic of augmented Lagrangian methods.
Figures
Figures from the paper (2 more)
Reference graph
Works this paper leans on
-
[1]
Joel A. E. Andersson, Joris Gillis, Greg Horn, James B. Rawlings, and Moritz Diehl. CasADi: a software framework for nonlinear optimization and optimal control . Mathematical Programming Computation, 11 0 (1): 0 1--36, mar 2019. ISSN 1867-2949. doi:10.1007/s12532-018-0139-4. URL http://link.springer.com/10.1007/s12532-018-0139-4
-
[2]
Mathematical Programs with Optimization Problems in the Constraints
Jerome Bracken and James T Mcgill. Mathematical Programs with Optimization Problems in the Constraints . Mathematical Programming, 21 0 (1): 0 37--44, 1973
1973
-
[3]
Byrd, Peihuang Lu, Jorge Nocedal, and Ciyou Zhu
Richard H. Byrd, Peihuang Lu, Jorge Nocedal, and Ciyou Zhu. A Limited Memory Algorithm for Bound Constrained Optimization . SIAM Journal on Scientific Computing, 16 0 (5): 0 1190--1208, sep 1995. ISSN 1064-8275. doi:10.1137/0916069. URL http://epubs.siam.org/doi/10.1137/0916069
doi:10.1137/0916069 1995
-
[4]
P. A. Clark and A. W. Westerberg. Bilevel programming for steady-state chemical process design-I. Fundamentals and algorithms . Computers and Chemical Engineering, 14 0 (1): 0 87--97, jan 1990. ISSN 00981354. doi:10.1016/0098-1354(90)87007-C. URL https://linkinghub.elsevier.com/retrieve/pii/009813549087007C
arXiv 1990
-
[5]
Foundations of Bilevel Programming , volume 61 of Nonconvex Optimization and Its Applications
Stephan Dempe. Foundations of Bilevel Programming , volume 61 of Nonconvex Optimization and Its Applications. Kluwer Academic Publishers, Dordrecht, 2002
2002
-
[6]
P \' e rez-Vald \' e s, and Nataliya Kalashnykova
Stephan Dempe, Vyacheslav Kalashnikov, Gerardo A. P \' e rez-Vald \' e s, and Nataliya Kalashnykova. Bilevel Programming Problems . Springer Berlin Heidelberg, 2015
2015
-
[7]
Discretization-based algorithms for generalized semi-infinite and bilevel programs with coupling equality constraints
Hatim Djelassi, Moll Glass, and Alexander Mitsos. Discretization-based algorithms for generalized semi-infinite and bilevel programs with coupling equality constraints . Journal of Global Optimization, 75 0 (2): 0 341--392, 2019
2019
-
[8]
Pablo Garcia-Herreros, Lei Zhang, Pratik Misra, Erdem Arslan, Sanjay Mehta, and Ignacio E. Grossmann. Mixed-integer bilevel optimization for capacity planning with rational markets . Computers and Chemical Engineering, 86: 0 33--47, 2016. ISSN 00981354. doi:10.1016/j.compchemeng.2015.12.007
Show all 29 references
-
[9]
G \" u m \" u ş and C.A
Z.H. G \" u m \" u ş and C.A. Floudas. Global Optimization of Nonlinear Bilevel Programming Problems . Journal of Global Optimization, 20: 0 1--31, 2001
2001
-
[10]
Hestenes
Magnus R. Hestenes. Multiplier and gradient methods . Journal of Optimization Theory and Applications, 4 0 (5): 0 303--320, nov 1969. ISSN 0022-3239. doi:10.1007/BF00927673. URL http://link.springer.com/10.1007/BF00927673
1969 doi
-
[11]
Kleniati and Claire S
Polyxeni M. Kleniati and Claire S. Adjiman. A generalization of the Branch-and-Sandwich algorithm: From continuous to mixed-integer nonlinear bilevel problems . Computers and Chemical Engineering, 72: 0 373--386, 2015. ISSN 00981354. doi:10.1016/j.compchemeng.2014.06.004
2015 doi
-
[12]
Polyxeni-Margarita Kleniati and Claire S. Adjiman. Branch-and-Sandwich: a deterministic global optimization algorithm for optimistic bilevel programming problems. Part I: Theoretical development . Journal of Global Optimization, 60 0 (3): 0 425--458, 2014
2014
-
[13]
Michal Ko c vara and Jiř \' i V. Outrata. Optimization problems with equilibrium constraints and their numerical solution . Mathematical Programming, 101 0 (1): 0 119--149, 2004. ISSN 0025-5610
2004
-
[14]
Lucchetti, F
R. Lucchetti, F. Mignanego, and G. Pieri. Existence theorems of equilibrium points in stackelberg . Optimization, 18 0 (6): 0 857--866, jan 1987. ISSN 0233-1934. doi:10.1080/02331938708843300. URL http://www.tandfonline.com/doi/abs/10.1080/02331938708843300
1987 doi
-
[15]
Mathematical Programs with Equilibrium Constraints
Zhi-Quan Luo, Jong-Shi Pang, and Daniel Ralph. Mathematical Programs with Equilibrium Constraints . Cambridge University Press, nov 1996. ISBN 9780521572903. doi:10.1017/CBO9780511983658. URL https://www.cambridge.org/core/product/identifier/9780511983658/type/book
1996
-
[16]
J. A. Mirrlees. The Theory of Moral Hazard and Unobservable Behaviour: Part I . Review of Economic Studies, 66 0 (1): 0 3--21, jan 1999. ISSN 0034-6527
1999
-
[17]
Global solution of nonlinear mixed-integer bilevel programs
Alexander Mitsos. Global solution of nonlinear mixed-integer bilevel programs . Journal of Global Optimization, 47 0 (4): 0 557--582, aug 2010. ISSN 0925-5001
2010
-
[18]
Alexander Mitsos, Panayiotis Lemonidis, and Paul I. Barton. Global solution of bilevel programs with a nonconvex inner program . Journal of Global Optimization, 42 0 (4): 0 475--513, 2008
2008
-
[19]
Bollas, and Paul I
Alexander Mitsos, George M. Bollas, and Paul I. Barton. Bilevel optimization formulation for parameter estimation in liquid–liquid phase equilibrium problems . Chemical Engineering Science, 64 0 (3): 0 548--559, feb 2009. ISSN 00092509. doi:10.1016/j.ces.2008.09.034. URL https...
2009 doi
-
[20]
Numerical Optimization
Jorge Nocedal and Stephen Wright. Numerical Optimization . Springer Series in Operations Research and Financial Engineering, chapter 13, page 664. Springer New York, 2 edition, 2006. ISBN 978-0-387-30303-1. doi:10.1007/978-0-387-40065-5
2006 doi
-
[21]
J. V. Outrata. On the numerical solution of a class of Stackelberg problems . ZOR-Math. Operations Research Methods and Models of Operations Research, 34 0 (4): 0 255--277, 1990
1990
-
[22]
M. J. D. Powell. A method for nonlinear constraints in minimization problems . In R. Fletcher, editor, Optimization, pages 283--298. Academic Press, New York, 1969
1969
-
[23]
R. T. Rockafellar. The multiplier method of Hestenes and Powell applied to convex programming . Journal of Optimization Theory and Applications, 12 0 (6): 0 555--562, dec 1973. ISSN 0022-3239. doi:10.1007/BF00934777. URL http://link.springer.com/10.1007/BF00934777
1973 doi
-
[24]
Mathematical Programs with Complementarity Constraints: Stationarity, Optimality, and Sensitivity
Holger Scheel and Stefan Scholtes. Mathematical Programs with Complementarity Constraints: Stationarity, Optimality, and Sensitivity . Mathematics of Operations Research, 25 0 (1): 0 1--22, 2000
2000
-
[25]
Marktform und Gleichgewicht
Heinrich von Stackelberg. Marktform und Gleichgewicht . Technical report, Berlin, 1934
1934
-
[26]
Andreas W \" a chter and Lorenz T. Biegler. On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming . Mathematical Programming, 106 0 (1): 0 25--57, mar 2006. ISSN 0025-5610. doi:10.1007/s10107-004-0559-y. URL http://link.s...
2006 doi
-
[27]
BOLIB: Bilevel optimisation library for benchmarking
Samuel Ward, Alain Zemkoho, Jordan Fisher, David Benfield, and Yaru Qian. BOLIB: Bilevel optimisation library for benchmarking . Technical report, University of Southampton, 2025
2025
-
[28]
Pessimistic Bilevel Optimization
Wolfram Wiesemann, Angelos Tsoukalas, Polyxeni-Margarita Kleniati, and Ber c Rustem. Pessimistic Bilevel Optimization . SIAM Journal on Optimization, 23 0 (1): 0 353--380, 2013
2013
-
[29]
Game-theoretic modeling and optimization of multi-echelon supply chain design and operation under Stackelberg game and market equilibrium
Dajun Yue and Fengqi You. Game-theoretic modeling and optimization of multi-echelon supply chain design and operation under Stackelberg game and market equilibrium . Computers and Chemical Engineering, 71: 0 347--361, 2014. ISSN 00981354. doi:10.1016/j.compchemeng.2014.08.010
2014 doi
Reviewed August 4, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.