Gaining traction: on the convergence of an inner approximation scheme for probability maximization
Open Access
- 17 July 2020
- journal article
- research article
- Published by Springer Nature in Central European Journal of Operations Research
- Vol. 29 (2) , 491-519
Abstract
We analyze an inner approximation scheme for probability maximization. The approach was proposed in Fábián et al. (Acta Polytech Hung 15:105–125, 2018), as an analogue of a classic dual approach in the handling of probabilistic constraints. Even a basic implementation of the maximization scheme proved usable and endured noise in gradient computations without any special effort. Moreover, the speed of convergence was not affected by approximate computation of test points. This robustness was then explained in an idealized setting. Here we work out convergence proofs and efficiency arguments for a nondegenerate normal distribution. The main message of the present paper is that the procedure gains traction as an optimal solution is approached.Keywords
Funding Information
- Hungarian Government co-financed by European Social Fund (EFOP-3.6.1-16-2016-00006)
This publication has 19 references indexed in Scilit:
- Level bundle methods for oracles with on-demand accuracyOptimization Methods and Software, 2014
- Regularization methods for optimization problems with probabilistic constraintsMathematical Programming, 2012
- Probabilistic Analysis of Simplex Algorithms2008
- Dual methods for probabilistic optimization problems*Mathematical Methods of Operations Research, 2004
- Smoothed analysis of algorithmsJournal of the ACM, 2004
- Concavity and efficient points of discrete distributions in probabilistic programmingMathematical Programming, 2000
- Programming Under Probabilistic Constraint with Discrete Random Variable1998
- A Practical Geometrically Convergent Cutting Plane AlgorithmSIAM Journal on Numerical Analysis, 1995
- Conjugation and second-order properties of convex functionsJournal of Mathematical Analysis and Applications, 1991
- Dual method for the solution of a one-stage stochastic programming problem with random RHS obeying a discrete probability distributionMathematical Methods of Operations Research, 1990