pith. sign in

arxiv: 1907.04663 · v1 · pith:RJXH2M2Fnew · submitted 2019-07-08 · 🧮 math.OC

Bilevel Optimization under Uncertainty

Johanna Burtscheidt , Matthias Claus This is my paper

Pith reviewed 2026-05-25 00:50 UTC · model grok-4.3

classification 🧮 math.OC
keywords bilevel optimizationstochastic programmingrisk measuresstabilitydiscrete distributionscurse of dimensionalitylinear programming
0
0 comments X

The pith

Bilevel linear programs with stochastic lower-level right-hand sides admit risk-measure models that satisfy Lipschitz properties, existence conditions, optimality conditions, and stability results.

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

The paper considers bilevel linear problems in which the lower level has a stochastic right-hand side. The leader must choose without knowing the realization, while the follower observes it fully, so the leader's payoff becomes a random variable. This leads to a family of models that replace the random payoff with a coherent or convex risk measure or with stochastic dominance constraints. The authors derive Lipschitzian properties of the resulting problems, give conditions that guarantee existence and optimality, and prove stability with respect to changes in the distribution. When the distribution is finite and discrete they exhibit an equivalent deterministic bilevel program whose special structure can be exploited to ease computation.

Core claim

When the right-hand side of the lower level is stochastic, the leader's outcome is a random variable that can be optimized by coherent or convex risk measures or by stochastic dominance constraints. The resulting problems possess Lipschitzian properties, admit conditions for existence and optimality, and satisfy stability results. For finite discrete distributions the stochastic bilevel program is equivalent to a deterministic bilevel program whose special structure offers a route to mitigating the curse of dimensionality.

What carries the argument

The risk-measure reformulation of the leader's random outcome, together with the equivalent deterministic bilevel program obtained for finite discrete distributions.

If this is right

  • Existence of optimal solutions follows once the risk measure satisfies standard convexity and continuity requirements.
  • The objective function of the upper level is Lipschitz continuous with respect to the random right-hand side.
  • Small changes in the probability distribution produce only small changes in the optimal value and in the set of optimal solutions.
  • For finite discrete distributions the equivalent deterministic bilevel program inherits the same risk-measure objective while keeping the original bilevel constraint structure.

Where Pith is reading between the lines

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

  • The same Lipschitz and stability arguments would apply if the risk measure were replaced by a stochastic dominance constraint, because the paper derives these properties from the structure of the random payoff rather than from any particular risk measure.
  • The special structure identified for discrete distributions suggests that standard bilevel decomposition algorithms can be applied directly to the reformulated problem without first expanding the scenario set.
  • Stability with respect to distributional perturbations implies that the models remain well-behaved even when the support of the random right-hand side is approximated by a finite sample.

Load-bearing premise

The lower-level problem remains linear for every realization of the random right-hand side and the follower always knows the realized value exactly.

What would settle it

A concrete instance in which the lower-level problem is nonlinear for at least one realization of the right-hand side, showing that the risk-measure reformulation no longer recovers the correct leader decisions.

Figures

Figures reproduced from arXiv: 1907.04663 by Johanna Burtscheidt, Matthias Claus.

Figure 1
Figure 1. Figure 1: The bold line depicts the graph of Ψ(· ,(0, 0)), while the dotted lines correspond to the graphs of Ψ(· ,(±0.5, ±0.5)) and Ψ(· ,(∓0.5, ±0.5)). is law-invariant and coherent (cf. [20, Example 4.8]). This choice of R in (1) leads to the bilevel robust problem min x {Rmax[F(x)] | x ∈ X} . Note that Rmax does only depend on the so called uncertainty set Z(Ω) ⊆ R. Thus, bilevel robust problem can be formulated … view at source ↗
read the original abstract

We consider bilevel linear problems, where the right-hand side of the lower level problems is stochastic. The leader has to decide in a here-and-now fashion, while the follower has complete information. In this setting, the leader's outcome can be modeled by a random variable, which gives rise to a broad spectrum of models involving coherent or convex risk measures and stochastic dominance constraints. We outline Lipschitzian properties, conditions for existence and optimality, as well as stability results. Moreover, for finite discrete distributions, we discuss the special structure of equivalent deterministic bilevel programs and its potential use to mitigate the curse of dimensionality.

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.

Referee Report

0 major / 3 minor

Summary. The paper considers bilevel linear programs in which the lower-level right-hand side is stochastic. The leader must choose here-and-now while the follower observes the realization; the leader's random outcome is then modeled via coherent or convex risk measures or stochastic dominance constraints. The authors outline Lipschitzian properties, existence and optimality conditions, and stability results, and for finite discrete distributions they discuss the structure of equivalent deterministic bilevel programs and its use in mitigating the curse of dimensionality.

Significance. If the outlined results hold under the stated modeling assumptions, the work supplies a coherent risk-measure framework for stochastic bilevel problems together with computational structure for the discrete case. The manuscript explicitly builds on standard risk-measure axioms and highlights the deterministic-equivalent reformulation as a practical device.

minor comments (3)
  1. [Abstract and §1] The abstract and introduction state that Lipschitzian properties, existence/optimality conditions, and stability results are outlined, but the manuscript should add a short roadmap sentence indicating the section in which each outline appears.
  2. [Modeling section] Notation for the random lower-level right-hand side and the induced leader outcome random variable should be introduced once with a single consistent symbol before the risk-measure formulations are written.
  3. [Discrete-distribution section] When the deterministic equivalent for finite discrete distributions is presented, a brief remark on how the bilevel structure is preserved (or simplified) after the risk-measure reformulation would help readers assess the claimed mitigation of the curse of dimensionality.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive summary, significance assessment, and recommendation of minor revision. No major comments were provided in the report.

Circularity Check

0 steps flagged

No circularity; derivations rest on standard bilevel and risk-measure axioms under explicitly stated assumptions.

full rationale

The paper derives Lipschitzian properties, existence/optimality conditions, stability results, and deterministic equivalents from the problem class of linear lower-level problems with stochastic RHS where the follower has complete information. These follow from established theory in bilevel optimization and coherent/convex risk measures without any self-definitional loops, fitted parameters renamed as predictions, or load-bearing self-citations that reduce the claims to their own inputs. The finite-discrete case structure is presented as a direct consequence of the linearity assumption rather than a constructed equivalence. The derivation chain is self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract supplies no explicit free parameters, axioms, or invented entities; all modeling choices remain at the level of standard assumptions in bilevel and stochastic programming.

pith-pipeline@v0.9.0 · 5615 in / 1111 out tokens · 23844 ms · 2026-05-25T00:50:16.841009+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

54 extracted references · 54 canonical work pages · 1 internal anchor

  1. [1]

    Shapiro, D

    A. Shapiro, D. Dentcheva, A. Ruszczy´ nski, Lectures on Stochastic Pro- gramming: Modeling and Theory , MPS SIAM Series on Optimization 9, SIAM, Philadelphia, 2nd edn. (2014) Bilevel Optimization under Uncertainty 23

    work page 2014

  2. [2]

    Patriksson, L

    M. Patriksson, L. Wynter, Stochastic mathematical programs with equilib- rium constraints, Operations Res. Letters 25, 159–167 (1999)

    work page 1999

  3. [3]

    Christiansen, M

    S. Christiansen, M. Patriksson, L. Wynter, Stochastic bilevel programming in structural optimization , Struct. and Multidisciplinary Optim. 21, 361– 371 (2001)

    work page 2001

  4. [4]

    Werner, Bilevel stochastic programming problems: Analysis and app li- cation to telecommunications, PhD thesis, Norwegian University of Science and Technology (2005)

    A. Werner, Bilevel stochastic programming problems: Analysis and app li- cation to telecommunications, PhD thesis, Norwegian University of Science and Technology (2005)

    work page 2005

  5. [5]

    Carri´ on, J.M

    M. Carri´ on, J.M. Arroyo, A.J. Conejo, A Bilevel Stochastic Programming Approach for Retailer Futures Market Trading , IEEE Transact. on Power Syst. 24, 1446–1456 (2009)

    work page 2009

  6. [6]

    Dempe, V.V

    S. Dempe, V.V. Kalashnikov, G.A. P´ erez-Vald´ es, N.I. Kalashnykova, Natu- ral gas bilevel cash-out problem: Convergence of a penalty f unction method, European J. of Operations Res. 215, 532–538 (2011)

    work page 2011

  7. [7]

    Kosuch, P

    S. Kosuch, P. Le Bodic, J. Leung, A. Lisser, On a stochastic bilevel pro- gramming problem, Networks 59, 107–116 (2012)

    work page 2012

  8. [8]

    Kovacevic, G.C

    R.M. Kovacevic, G.C. Pflug, Electricity swing option pricing by stochastic bilevel optimization: a survey and new approaches , Euro. J. of Operational Res. 237, 389–403 (2013)

    work page 2013

  9. [9]

    A. Chen, J. Kim, Z. Zhou, P. Chootinan, Alpha reliable network design problem, Transportation Res. Record: J. of the Transportation Res. Bo ard. 2029, 49–57 (2007)

    work page 2029

  10. [10]

    M. Patriksson, On the applicability and solution of bilevel optimization models in transportation science: A study on the existence, stability and computation of optimal solutions to stochastic mathematic al programs with equilibrium constraints, Transportation Res. Part B: Methodological 42, 843–860 (2008)

    work page 2008

  11. [11]

    Henkel, An algorithm for global resolution of linear stochastic bil evel programs, PhD thesis, University of Duisburg-Essen (2014)

    C. Henkel, An algorithm for global resolution of linear stochastic bil evel programs, PhD thesis, University of Duisburg-Essen (2014)

    work page 2014

  12. [12]

    Alizadeh, P

    S.M. Alizadeh, P. Marcotte, G. Savard, Two-stage stochastic bilevel pro- gramming over a transportation network , Transportation Res. B 58, 92– 105 (2013)

    work page 2013

  13. [13]

    Eaves, On Quadratic Programming , Management Sci

    B.C. Eaves, On Quadratic Programming , Management Sci. 17, 698–711 (1971)

    work page 1971

  14. [14]

    Klatte, B

    D. Klatte, B. Kummer, Stability properties of infima and optimal solutions of parametric optimization problems , In: Nondifferentiable Optimization: Motivations and Applications, Proceedings of the IIASA Workshop, 215– 229, Sopron, Lect. Notes Econ. Math. Syst. 255, Springer, Berlin (1984) Bilevel Optimization under Uncertainty 24

    work page 1984

  15. [15]

    Beer, L¨ osung großer linearer Optimierungsaufgaben, Deutscher Verlag der Wiss., Berlin (1977)

    K. Beer, L¨ osung großer linearer Optimierungsaufgaben, Deutscher Verlag der Wiss., Berlin (1977)

    work page 1977

  16. [16]

    Klatte, G

    D. Klatte, G. Thiere, Error bounds for solutions of linear equations and inequalities, ZOR - Math. Methods of Operations Res. 41, 191–214 (1995)

    work page 1995

  17. [17]

    Ivanov, Bilevel stochastic linear programming problems with quant ile criterion, Automation and Remote Control 75, 107–118 (2014)

    S.V. Ivanov, Bilevel stochastic linear programming problems with quant ile criterion, Automation and Remote Control 75, 107–118 (2014)

    work page 2014

  18. [18]

    Artzner, F

    P. Artzner, F. Delbaen, J.-M. Eber, D. Heath, Coherent Measures of Risk , Math. Fin. 9, 203–228 (1999)

    work page 1999

  19. [19]

    F¨ ollmer, A

    H. F¨ ollmer, A. Schied, Convex measures of risk and trading constraints , Fin. and Stoch. 6, 429–447 (2002)

    work page 2002

  20. [20]

    F¨ ollmer, A

    H. F¨ ollmer, A. Schied, Stochastic Finance: an Introduction in Discrete Time, de Gruyter, Berlin, New York, 3rd edn. (2011)

    work page 2011

  21. [21]

    Claus, Advancing stability analysis of mean-risk stochastic prog rams: Bilevel and two-stage models , PhD thesis, University of Duisburg-Essen (2016)

    M. Claus, Advancing stability analysis of mean-risk stochastic prog rams: Bilevel and two-stage models , PhD thesis, University of Duisburg-Essen (2016)

    work page 2016

  22. [22]

    Pflug, Some Remarks on the Value-at-Risk and the Conditional Value-at-Risk, In: S.P

    G.C. Pflug, Some Remarks on the Value-at-Risk and the Conditional Value-at-Risk, In: S.P. Uryasev (eds.) Probabilistic Constrained Optimiza- tion - Methodology and Application., 272–281, Kluwer Academic Publish - ers, Dordrecht (2000)

    work page 2000

  23. [23]

    Rockafellar, S

    R.T. Rockafellar, S. Uryasev, Conditional Value-at-Risk for General Loss Distributions, J. of Bank. and Fin. 26, 1443–1471 (2002)

    work page 2002

  24. [24]

    Ben-Tal, L

    A. Ben-Tal, L. El Ghaoui, A. Nemirovski, Robust Optimization, Princeton University Press, Princeton, Oxford (2009)

    work page 2009

  25. [25]

    Ekeland, R

    I. Ekeland, R. Temam, Analyse convexe et probl` emes variationnels, Dunod, Paris (1974)

    work page 1974

  26. [26]

    Cheridito, T

    P. Cheridito, T. Li, Risk measures on orlicz hearts , Math. Fin. 18, 189–214 (2009)

    work page 2009

  27. [27]

    Inoue, On the worst case conditional expectation , J

    A. Inoue, On the worst case conditional expectation , J. Math. Anal. Appl. 286, 237–247 (2003)

    work page 2003

  28. [28]

    Belomestny, V

    D. Belomestny, V. Kr¨ atschmer, Central limit theorems for law-invariant coherent risk measures , J. Appl. Prob. 49, 1–21 (2012)

    work page 2012

  29. [29]

    Schultz, S

    R. Schultz, S. Tiedemann, Risk Aversion via Excess Probabilities in Stochastic Programs with Mixed-Integer Recourse , SIAM J. on Optim. 14, 115–138 (2003)

    work page 2003

  30. [30]

    Risk-Averse Models in Bilevel Stochastic Linear Programming

    J. Burtscheidt, M. Claus, S. Dempe, Risk-Averse Models in Bilevel Stochastic Linear Programming , Preprint, arXiv:1901.11349 [math.OC] (2019) Bilevel Optimization under Uncertainty 25

    work page internal anchor Pith review Pith/arXiv arXiv 1901

  31. [31]

    Gordan, ¨Uber die Aufl¨ osungen linearer Gleichungen mit reellen Coeffi - cienten, Math

    P. Gordan, ¨Uber die Aufl¨ osungen linearer Gleichungen mit reellen Coeffi - cienten, Math. Annalen 6, 238 (1873)

    work page

  32. [32]

    Robinson, Local epi-continuity and local optimization , Math

    S.M. Robinson, Local epi-continuity and local optimization , Math. Pro- gram. 37, 208–222 (1987)

    work page 1987

  33. [33]

    Billingsley, Convergence of Probability Measures , Wiley, New York (1968)

    P. Billingsley, Convergence of Probability Measures , Wiley, New York (1968)

    work page 1968

  34. [34]

    Claus, V

    M. Claus, V. Kr¨ atschmer, R. Schultz, Weak continuity of risk functionals with applications to stochastic programming , SIAM J. on Optim. 27, 91– 108 (2017)

    work page 2017

  35. [35]

    Kr¨ atschmer, A

    V. Kr¨ atschmer, A. Schied, H. Z¨ ahle,Qualitative and infinitesimal robust- ness of tail-dependent statistical functionals , J. of Multivariate Anal. 103, 35–47 (2012)

    work page 2012

  36. [36]

    Kr¨ atschmer, A

    V. Kr¨ atschmer, A. Schied, H. Z¨ ahle, Comparative and qualitative robust- ness for law-invariant risk measures , Fin. and Stoch. 18, 271–295 (2014)

    work page 2014

  37. [37]

    Kr¨ atschmer, A

    V. Kr¨ atschmer, A. Schied, H. Z¨ ahle,Domains of weak continuity of statis- tical functionals with a view on robust statistics , J. of Multivariate Anal. 158, 1–19 (2017)

    work page 2017

  38. [38]

    Berge, Espaces topologiques: fonctions multivoques , Coll

    C. Berge, Espaces topologiques: fonctions multivoques , Coll. Universitaire de math´ ematiques3, Paris, Dunod (1959)

    work page 1959

  39. [39]

    Rockafellar, R.J.-B

    R.T. Rockafellar, R.J.-B. Wets, Variational Analysis , Springer, Berlin (2009)

    work page 2009

  40. [40]

    Pollard, Convergence of Stochastic Processes , Springer, New York (1984)

    D. Pollard, Convergence of Stochastic Processes , Springer, New York (1984)

    work page 1984

  41. [41]

    Shorack, J.A

    G.R. Shorack, J.A. Wellner, Empirical Processes with Applications to Statistics, Wiley, New York (1986)

    work page 1986

  42. [42]

    Birge, R.J.-B

    J.R. Birge, R.J.-B. Wets, Designing approximation schemes for stochastic optimization problems, in particular for stochastic progr ams with recourse , Math. Program. Stud. 27, 54–102 (1986)

    work page 1986

  43. [43]

    P. Kall, A. Ruszczy´ nski, K. Frauendorfer, Approximation techniques in stochastic programming, In: Y. Ermoliev, R.J.-B. Wets (eds.), Numerical Techniques for Stochastic Optimization, 33–64, Springer, Berlin (1 988)

    work page

  44. [44]

    Pr´ ekopa, Stochastic Programming, Math

    A. Pr´ ekopa, Stochastic Programming, Math. and Its Applications 324, Kluwer Academic Publishers, Dordrecht (1995)

    work page 1995

  45. [45]

    Gollmer, F

    R. Gollmer, F. Neise, R. Schultz, Stochastic programs with first-order dom- inance constraints induced by mixed-integer linear recour se, SIAM J. Op- tim. 19, 552–571 (2008) Bilevel Optimization under Uncertainty 26

    work page 2008

  46. [46]

    Gollmer, U

    R. Gollmer, U. Gotzes, R. Schultz, A note on second-order stochastic dom- inance constraints induced by mixed-integer linear recour se, Math. Pro- gram. A 126, 179–190 (2011)

    work page 2011

  47. [47]

    Dempe, Foundations of Bilevel Programming , Springer, Berlin (2002)

    S. Dempe, Foundations of Bilevel Programming , Springer, Berlin (2002)

    work page 2002

  48. [48]

    Dempe, S.V

    S. Dempe, S.V. Ivanov, A. Naumov, Reduction of the bilevel stochastic optimization problem with quantile objective function to a mixed-integer problem, Applied Stoch. Models in Business and Industry 33, 544–554 (2017)

    work page 2017

  49. [49]

    J. Hu, J.E. Mitchell, J.-S. Pang, K.P. Bennett, G. Kunapuli, On the Global Solution of Linear Programs with Linear Complementarity Co nstraints, SIAM J. Optim. 19, 445–471 (2008)

    work page 2008

  50. [50]

    Tuy, Bilevel linear programming, multiobjective programming, and monotonic reverse convex programming , In: A

    H. Tuy, Bilevel linear programming, multiobjective programming, and monotonic reverse convex programming , In: A. Migdalas, P.M. Pardalos, P. V¨ arbrand (eds.) Multilevel Optimization: Algorithms and Applications, 295–314, Kluwer Academic Publishers, Dordrecht (1998)

    work page 1998

  51. [51]

    H. Tuy, A. Migdalas, P. V¨ arbrand, A quasiconcave minimization method for solving linear two-level programs , J. of Glob. Optim. 4, 243–263 (1994)

    work page 1994

  52. [52]

    Labb´ e, P

    M. Labb´ e, P. Marcotte, G. Savard, A bilevel model of taxation and its application to optimal highway pricing , Management Sci. 44, 1608–1622 (1998)

    work page 1998

  53. [53]

    Zhang, H

    J. Zhang, H. Xu and L. Zhang, Quantitative stability analysis for distribu- tionally robust optimization with moment constraints , SIAM J. on Optim. 26, 1855–1882 (2016)

    work page 2016

  54. [54]

    De Miguel, H

    V. De Miguel, H. Xu, A stochastic multiple-leader Stackelberg model: anal- ysis, computation, and application , Operations Res. 57, 1220–1235 (2009)

    work page 2009