arxiv: 2604.23487 · v1 · submitted 2026-04-26 · 🧮 math.OC

Optimality Conditions and Numerical Algorithms for a Class of Minimax Bilevel Optimization Problems

Yaling Hu , Jiani Wang , Yu-Hong Dai , Xiaojiao Tong This is my paper

Pith reviewed 2026-05-08 05:54 UTC · model grok-4.3

classification 🧮 math.OC

keywords minimax bilevel optimizationoptimality conditionspenalty methodprojected gradient methodconvergence analysisKKT conditionspower systemsStackelberg games

0 comments

The pith

A penalty reformulation of minimax bilevel problems yields a single-level minimax problem solvable by projected gradient ascent-descent to ε-KKT accuracy in O(ε^{-3} log(ε^{-1})) iterations.

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

This paper studies minimax bilevel optimization problems in which an upper-level minimax objective is constrained by the solution of a separate lower-level optimization problem. The authors first derive optimality conditions by replacing the lower-level problem with its KKT conditions and value function. They then apply a penalty method to convert the resulting problem into an equivalent single-level minimax problem. A projected gradient multi-step ascent-descent algorithm is designed for this reformulated problem and shown to produce an ε-KKT point of the original bilevel problem in the stated number of iterations, with an accelerated Nesterov variant preserving the same rate. The methods are tested on synthetic minimax bilevel instances and a bilevel economic dispatch model from power systems.

Core claim

By reconstructing the lower-level problem through its KKT conditions and value function, optimality conditions for the minimax bilevel problem are obtained. These conditions support a penalty framework that produces a single-level minimax problem. The projected gradient multi-step ascent-descent method applied to the penalized problem locates an ε-KKT solution of the original problem after O(ε^{-3} log(ε^{-1})) iterations, and the Nesterov acceleration maintains this complexity bound.

What carries the argument

The penalty method framework that substitutes lower-level KKT conditions and value function to create a single-level minimax problem, solved via the projected gradient multi-step ascent-descent method.

If this is right

The same penalty-plus-gradient approach applies to any minimax bilevel problem whose lower level satisfies the KKT substitution assumption, including Stackelberg games and constrained machine learning models.
The Nesterov acceleration improves practical speed while keeping the worst-case iteration bound unchanged.
Numerical results on power-system economic dispatch confirm that the method produces feasible and stationary solutions for realistic constraint sets.
The ε-KKT guarantee extends directly to the original bilevel problem once the penalty parameter is driven to zero.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The framework could be tested on other bilevel structures such as standard (non-minimax) bilevel programs by replacing the upper-level minimax with a single objective.
Scalability experiments on large-scale power networks would show whether the O(ε^{-3} log(1/ε)) rate remains practical when the lower-level KKT system grows in size.
Similar multi-step gradient schemes might combine with other single-level reformulations, such as value-function or implicit-gradient approaches, to handle cases where KKT substitution is unavailable.

Load-bearing premise

The lower-level problem admits a KKT representation that can be substituted into the upper-level minimax problem without destroying equivalence or introducing non-convexity that invalidates the penalty and gradient analysis.

What would settle it

A concrete minimax bilevel instance in which substituting the lower-level KKT system produces a problem whose penalty reformulation fails to recover original stationary points, or whose iteration count to ε-KKT visibly exceeds the predicted bound.

read the original abstract

In many applications, including Stackelberg games, machine learning, and power systems \cite{Mackay2018Selftuning,Heinrich1952The,Wang2021Bi-Level}, the decisions in a minimax optimization problem can be constrained by a solution to an optimization problem. In this paper, we introduce optimality conditions of this novel minimax bilevel optimization problem and develops efficient first-order algorithms for this class of problems. Firstly, we establish the optimality conditions for minimax bilevel problems by reconstructing the lower-level problem through its Karush-Kuhn-Tucker (KKT) conditions and value function. Secondly, we develop a penalty method framework to approximately solve the minimax bilevel problem by transforming it into a single-level minimax problem. Thirdly, we design a projected gradient multi-step ascent descent method to solve the resulting minimax problem, which can find an $\epsilon$-KKT solution for the original minimax bilevel problem within $\mathcal{O}(\epsilon^{-3} \log(\epsilon^{-1}))$ iterations. To improve {the convergence rate} of the algorithm, we provide its Nesterov accelerated extension with $\mathcal{O}(\epsilon^{-3} \log(\epsilon^{-1}))$ iteration complexity. Finally, we demonstrate the effectiveness of our model and algorithms through numerical experiments on various minimax bilevel optimization problems and a bilevel economic dispatch in the power system.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper gives a KKT-plus-value-function reformulation and multi-step projected gradient method for a structured class of minimax bilevel problems, with an explicit O(ε^{-3} log(1/ε)) complexity claim, but the equivalence step requires lower-level convexity that is not stressed in the abstract.

read the letter

The main point to know is that the authors reformulate a minimax bilevel problem by replacing the lower level with its KKT conditions and value function, apply a penalty to make it single-level, and then solve it with a multi-step projected gradient ascent-descent scheme that they claim reaches an ε-KKT point in O(ε^{-3} log(ε^{-1})) iterations. They also give a Nesterov-accelerated version with the same bound.

Referee Report

2 major / 2 minor

Summary. The paper claims to establish optimality conditions for minimax bilevel optimization problems by reconstructing the lower-level problem via its KKT conditions and value function, to develop a penalty method that transforms the problem into a single-level minimax problem, and to propose a projected gradient multi-step ascent-descent method (with a Nesterov-accelerated variant) that finds an ε-KKT solution of the original problem in O(ε^{-3} log(ε^{-1})) iterations. Numerical experiments on synthetic minimax bilevel problems and a bilevel economic dispatch application in power systems are included to illustrate the approach.

Significance. If the equivalence between the original bilevel problem and the KKT-reconstructed single-level problem holds, the explicit iteration complexity for a first-order method and the penalty framework constitute a useful contribution to bilevel and minimax optimization. The work targets relevant applications in Stackelberg games, machine learning, and power systems, and the provision of both standard and accelerated algorithms strengthens its practical value. The numerical validation on a real-world power system example is a positive aspect.

major comments (2)

[§3] §3 (Optimality Conditions): The reconstruction of the lower-level problem through its KKT conditions and value function is asserted to produce an equivalent single-level minimax problem. This equivalence requires the lower-level problem to be convex and to satisfy a constraint qualification (such as MFCQ or LICQ). These assumptions are not explicitly stated for the 'class' of problems considered. This is load-bearing because the subsequent penalty exactness argument and the claim that the algorithm solves the original minimax bilevel problem both depend on it.
[§4] §4 (Algorithm and Complexity Analysis): The O(ε^{-3} log(ε^{-1})) iteration bound for the projected gradient multi-step ascent-descent method to reach an ε-KKT point of the original bilevel problem relies on the equivalence established via KKT substitution in §3. Without the convexity and CQ assumptions, the bound applies only to the penalized single-level problem and may not guarantee solutions to the original bilevel formulation, as extraneous stationary points could be introduced.

minor comments (2)

[Abstract] Abstract: The phrasing 'we introduce optimality conditions ... and develops efficient first-order algorithms' contains a subject-verb agreement error ('develops' should be 'develop').
[Numerical Experiments] Numerical Experiments section: Additional details on the specific formulation of the bilevel economic dispatch problem (e.g., how the minimax structure is defined and the choice of penalty parameters) would improve reproducibility and clarity.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the thorough review and insightful comments, which have helped us identify areas for clarification. We agree that the assumptions underlying the KKT reconstruction need to be stated explicitly and will revise the manuscript accordingly to strengthen the presentation of the optimality conditions and complexity results.

read point-by-point responses

Referee: §3 (Optimality Conditions): The reconstruction of the lower-level problem through its KKT conditions and value function is asserted to produce an equivalent single-level minimax problem. This equivalence requires the lower-level problem to be convex and to satisfy a constraint qualification (such as MFCQ or LICQ). These assumptions are not explicitly stated for the 'class' of problems considered. This is load-bearing because the subsequent penalty exactness argument and the claim that the algorithm solves the original minimax bilevel problem both depend on it.

Authors: We agree that the equivalence holds only when the lower-level problem is convex and satisfies a constraint qualification such as MFCQ. These conditions were used in our derivations but not stated explicitly as part of the problem class. In the revision, we will add a dedicated paragraph at the start of Section 3 listing the standing assumptions (lower-level convexity and MFCQ) and will restate that all subsequent results, including the penalty exactness, are valid under these conditions. revision: yes
Referee: §4 (Algorithm and Complexity Analysis): The O(ε^{-3} log(ε^{-1})) iteration bound for the projected gradient multi-step ascent-descent method to reach an ε-KKT point of the original bilevel problem relies on the equivalence established via KKT substitution in §3. Without the convexity and CQ assumptions, the bound applies only to the penalized single-level problem and may not guarantee solutions to the original bilevel formulation, as extraneous stationary points could be introduced.

Authors: The complexity analysis in Section 4 is derived for the single-level penalized problem after KKT reconstruction; the transfer to the original bilevel problem requires the equivalence shown in Section 3. Once the convexity and CQ assumptions are stated explicitly (as planned), the ε-KKT guarantee for the original problem will be correctly qualified. We will add a short remark in Section 4 referencing the assumptions from Section 3 and will adjust the theorem statements to make the dependence clear. revision: yes

Circularity Check

0 steps flagged

No circularity: standard KKT reformulation and penalty analysis are external to the paper

full rationale

The derivation chain begins with the standard substitution of lower-level KKT conditions plus value function to obtain an equivalent single-level minimax problem, followed by a penalty reformulation and a projected multi-step ascent-descent algorithm whose iteration complexity is obtained by direct analysis of the method's descent properties. None of these steps reduces by construction to a fitted parameter, a self-definition, or a load-bearing self-citation; the KKT and penalty steps invoke well-known external results whose validity is independent of the present paper's claims. The O(ε^{-3} log(ε^{-1})) bound follows from the algorithm's convergence proof rather than from renaming or re-using the input data.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claims rest on the applicability of KKT conditions to the lower-level problem and on standard properties of penalty methods for converting bilevel to single-level problems.

axioms (1)

domain assumption Lower-level problem satisfies constraint qualifications allowing KKT conditions to fully characterize its solutions
Invoked when the lower-level problem is reconstructed via its KKT system and value function.

pith-pipeline@v0.9.0 · 5563 in / 1289 out tokens · 29700 ms · 2026-05-08T05:54:26.807353+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

9 extracted references · 2 canonical work pages · 1 internal anchor

[1]

[1]M. M. Ahmadi and E. Yazdandoost Hamedani,Single-loop projection-free and projected gradient-based algorithms for nonconvex-concave saddle point problems with bilevel struc- ture, J. Sci. Comput., 103 (2025), p

2025
[2]

[2]G. B. Allende and G. Still,Solving bilevel programs with the KKT-approach, Math. Pro- gram., 138 (2013), pp. 309–332. [3]M. J. Alves and C. H. Antunes,A semivectorial bilevel programming approach to optimize electricity dynamic time-of-use retail pricing, Comput. Oper. Res., 92 (2018), pp. 130–144. [4]X. Bai, S. Zeng, J. Zhang, and L. Zhang,Alternating...

work page internal anchor Pith review arXiv 2013
[3]

Bernhard and A

[6]P. Bernhard and A. Rapaport,On a theorem of danskin with an application to a theorem of von neumann-sion, Nonlinear Anal. Theory Methods Appl., 24 (1995), pp. 1163–1181. [7]W. Bian and X. Chen,Nonsmooth convexconcave saddle point problems with cardinality pen- alties, Math. Program., (2024). [8]X. Chen, T. Xiao, and K. Balasubramanian,Optimal algorithm...

1995
[4]

Dai and L

[12]Y. Dai and L. Zhang,Optimality conditions for constrained minimax optimization, CSIAM Trans. Appl. Math., 1 (2020), pp. 296–315. [13]Y. Dai and L. Zhang,The rate of convergence of augmented lagrangian method for mini- max optimization problems with equality constraints, J. Oper. Res. Soc. China, 12 (2024), pp. 265–297. [14]E. Delage and Y. Ye,Distribu...

2020
[5]

[23]Q. Hu, Y. Zhong, and T. Yang,Multi-block min-max bilevel optimization with applications in multi-task deep auc maximization, in Advances in Neural Information Processing Systems, vol. 35, 2022, pp. 29552–29565. [24]Y. Huang, H. Lu, C. Gao, X. Rong, G. Li, and Z. Bie,Defenderattackerdefender model for power system resilience enhancement with protection...

2022
[6]

[37]J. Nie, L. W ang, J. J. Ye, and S. Zhong,A lagrange multiplier expression method for bilevel polynomial optimization, SIAM J. Optim., 31 (2021), pp. 2368–2395. [38]J. V. Outrata,On the numerical solution of a class of stackelberg problems, Z. Oper. Res., 34 (1990), pp. 255–277. [39]J. S. Pang,Error bounds in mathematical programming, Math. Program., 7...

2021
[7]

[40]S. M. Robinson,Some continuity properties of polyhedral multifunctions, Math. Program. Stud., 14 (1981), pp. 206–214. [41]H. Sadeghi and M. Esmaeili,On the quasiconcave multilevel programming problems, Asia Pac. J Oper. Res., 39 (2022), p. 2150026. [42]R. Sato, M. Tanaka, and A. Takeda,A gradient method for multilevel optimization, in Advances in Neur...

1981
[8]

Shafiei, V

[44]A. Shafiei, V. Kungurtsev, and J. Marecek,Trilevel and multilevel optimization us- ing monotone operator theory, Math. Meth. Oper. Res., 99 (2024), pp. 77–114. [45]H. V. Stackelberg,The theory of the market economy, Oxford University Press, Oxford. England,

2024
[9]

Tsaknakis, M

[46]I. Tsaknakis, M. Hong, and S. Zhang,Minimax problems with coupled linear constraints: Computational complexity and duality, SIAM J. Optim., 33 (2023), pp. 2675–2702. [47]K. Tu, Z. Chen, and M.-C. Yue,A max-min-max algorithm for large-scale robust optimiza- tion, (2024), https://arxiv.org/abs/2404.05377. [48]L. W ang, Z. Zhu, C. Jiang, and Z. Li,Bi-lev...

work page arXiv 2023