A Second-Order Sufficient Optimality Condition for Risk-Neutral Bi-level Stochastic Linear Programs
- PDF / 371,139 Bytes
- 17 Pages / 439.37 x 666.142 pts Page_size
- 15 Downloads / 138 Views
A Second-Order Sufficient Optimality Condition for Risk-Neutral Bi-level Stochastic Linear Programs Matthias Claus1 Received: 31 March 2020 / Accepted: 20 October 2020 © The Author(s) 2020
Abstract The expectation functionals, which arise in risk-neutral bi-level stochastic linear models with random lower-level right-hand side, are known to be continuously differentiable, if the underlying probability measure has a Lebesgue density. We show that the gradient may fail to be local Lipschitz continuous under this assumption. Our main result provides sufficient conditions for Lipschitz continuity of the gradient of the expectation functional and paves the way for a second-order optimality condition in terms of generalized Hessians. Moreover, we study geometric properties of regions of strong stability and derive representation results, which may facilitate the computation of gradients. Keywords Bi-level stochastic linear programming · Risk-neutral model · Second-order optimality conditions · Lipschitz gradients Mathematics Subject Classification 90C15 · 91A65
1 Introduction We study bi-level stochastic linear programs with random right-hand side in the lowerlevel constraint system. The sequential nature of bi-level programming motivates a setting where the leader decides nonanticipatorily, while the follower can observe the realization of the randomness. A discussion of the related literature is provided in the recent [1]. A central result of [1] states that evaluating the leader’s random outcome by taking the expectation leads to a continuously differentiable functional if the underlying probability measure is absolutely continuous w.r.t. the Lebesgue
Communicated by René Henrion.
B 1
Matthias Claus [email protected] University Duisburg-Essen, Essen, Germany
123
Journal of Optimization Theory and Applications
measure. This allows to formulate first-order necessary optimality conditions for the risk-neutral model. The main result of the present work provides sufficient conditions, namely boundedness of the support and uniform boundedness of the Lebesgue density of the underlying probability measure, that ensure Lipschitz continuity of the gradient of the expectation functional. Moreover, we show that the assumptions of [1] are too weak to even guarantee local Lipschitz continuity of the gradient. By the main result, second-order necessary and sufficient optimality conditions can be formulated in terms of generalized Hessians. As part of the preparatory work for the proof of the main result, we in particular show that any region of strong stability in the sense of [1, Definition 4.1] is a finite union of polyhedral cones. This representation is of independent interest, as it may facilitate the calculation or estimation of gradients of the expectation functional and thus enhance gradient descent-based approaches. The paper is organized as follows: The model and related results of [1] are discussed in Sect. 2, while the main result and a variation with weaker assumptions are formulated in Sect. 3. Section
Data Loading...
