Volume 2008
http://edoc.hu-berlin.de/18452/365
2021-09-23T12:56:59ZStochastic Nash Equilibrium Problems: Sample Average Approximation and Applications
http://edoc.hu-berlin.de/18452/9050
Stochastic Nash Equilibrium Problems: Sample Average Approximation and Applications
Xu, Huifu; Zhang, Dali
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
This paper presents a Nash equilibrium model where the underlying objective functionsinvolve uncertainties and nonsmoothness. The well known sample average approximationmethod is applied to solve the problem and the ﬁrst order equilibrium conditions are characterized in terms of Clarke generalized gradients. Under some moderate conditions, it is shown that with probability one, a statistical estimator obtained from sample average approximateequilibrium problem converges to its true counterpart. Moreover, under some calmness conditions of the generalized gradients and metric regularity of the set-valued mappings whichcharacterize the ﬁrst order equilibrium conditions, it is shown that with probability approaching one exponentially fast with the increase of sample size, the statistical estimatorconverge to its true counterparts. Finally, the model is applied to an equilibrium problem inelectricity market.
2008-12-19T00:00:00ZApproximations and contamination bounds for probabilistic programs
http://edoc.hu-berlin.de/18452/9049
Approximations and contamination bounds for probabilistic programs
Branda, Martin; Dupacova, Jitka
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
In this paper we aim at output analysis with respect to changes of the probability distribution for problems with probabilistic (chance) constraints. The perturbations are modeled via contamination of the initial probability distribution. Dependence of the set of solutions on the probability distributionrules out the straightforward construction of the convexity-based global contamination bounds for the perturbed optimal value function whereas localresults can be still obtained. To get global bounds we shall explore several approximations and reformulations of stochastic programs with probabilistic constraints by stochastic programs with suitably chosen recourse or penaltytype objectives and ﬁxed constraints.
2008-09-16T00:00:00ZConvergence Analysis of a Weighted Barrier Decomposition Algorithm for Two Stage Stochastic Programming
http://edoc.hu-berlin.de/18452/9048
Convergence Analysis of a Weighted Barrier Decomposition Algorithm for Two Stage Stochastic Programming
Mehrotra, Sanjay; Ozevin, M. Gokhan
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
Mehrotra and Ozevin [7] computationally found that a weighted primal barrier decomposition algorithm signiﬁcantly outperforms the barrier decomposition proposed and analyzed in [11; 6; 8]. Thispaper provides a theoretical foundation for the weighted barrier decomposition algorithm (WBDA)in [7]. Although the worst case analysis of the WBDA achieves a ﬁrst-stage iteration complexitybound that is worse than the bound shown for the decomposition algorithms of [11] and [6; 8],under a probabilistic assumption we show that the worst case iteration complexity of WBDA isindependent of the number of scenarios in the problem. The probabilistic assumption uses a novelconcept of self-concordant random variables.
2008-07-05T00:00:00ZNumerical Evaluation of Approximation Methods in Stochastic Programming
http://edoc.hu-berlin.de/18452/9047
Numerical Evaluation of Approximation Methods in Stochastic Programming
Küchler, Christian; Vigerske, Stefan
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
We study an approach for the evaluation of approximation and solution methodsfor multistage linear stochastic programs by measuring the performance of the obtained solutions on a set of out-of-sample scenarios. The main point of the approachis to restore the feasibility of solutions to an approximated problem along the out-of-sample scenarios. For this purpose, we consider and compare different feasibilityand optimality based projection methods. With this at hand, we study the quality of solutions to different test models based on classical as well as recombiningscenario trees.
2008-07-02T00:00:00Z