S. V. Ivanov, A. I. Kibzun. Sample average approximation in the two-stage stochastic linear programming problem with quantile criterion ... P. 134-143.

The two-stage problem of stochastic linear programming with quantile criterion is considered. In this problem, the first stage strategy is deterministic and the second stage strategy is chosen when a realization of the random parameters is known. The properties of the problem are studied, a theorem on the existence of its solution is proved, and a sample average approximation of the problem is constructed. The sample average approximation is reduced to a mixed integer linear programming problem, and a theorem on their equivalence is proved. A procedure for finding an optimal solution of the approximation problem is suggested. A theorem on the convergence of discrete approximations with respect to the value of the objective function and to the optimization strategy is given.

We also consider some cases not covered in the theorem.

Keywords: stochastic programming, quantile criterion, sample average approximation, mixed integer linear programming.

The paper was received by the Editorial Office on May 19, 2017.

Sergei Valer'evich Ivanov, Cand. Sci. (Phys.-Math.), Moscow Aviation Institute (National Research University), Moscow, 125993 Russia, e-mail: sergeyivanov89@mail.ru

Andrei Ivanovich Kibzun, Dr. Phys.-Math. Sci., Prof., Head of a department, Moscow Aviation Institute (National Research University), Moscow, 125993 Russia, e-mail: kibzun@mail.ru

REFERENCES

1.   Shapiro A., Dentcheva D., RuszczyДnski A. Lectures on stochastic programming: Modeling and theory. MPS/SIAM Series on Optimization. 9. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM), 2009, 436 p. ISBN: 9780898716870 .

2.   Kibzun A.I., Naumov A.V. A two-stage quantile linear programming problem. Autom. Remote Control, 1995, vol. 56, iss. 1, pp. 68–76.

3.   Norkin V.I., Kibzun A.I., Naumov A.V. Reducing two-stage probabilistic optimization problems with discrete distribution of random data to mixed-integer programming problems. Cybern. Syst. Anal., 2014, vol. 50, pp. 679–692. doi: 10.1007/s10559-014-9658-9 .

4.   Artstein Z., Wets R.J.-B. Consistency of minimizers and the SLLN for stochastic programs. J. Convex Anal., 1996, vol. 2, iss. 1/2, pp. 1–17.

5.   Pagnoncelli B.K., Ahmed S., Shapiro A. Sample average approximation method for chance constrained programming: Theory and applications. J. Optim. Theory Appl., 2009, vol. 142, pp. 399–416.
doi: 10.1007/s10957-009-9523-6 .

6.   Kibzun A.I., Ivanov S.V. Convergence of discrete approximations of stochastic programming problems with probabilistic criteria. Proc. 9th Internat. Conf. DOOR 2016 (Vladivostok, 2016), eds. Kochetov, Yu. et all., Ser. Theoretical Computer Science and General Issues, vol. 9869, pp. 525–537, Heidelberg: Springer, 2016. doi: 10.1007/978-3-319-44914-2 .

7.   Rockafellar R.T., Wets R.J.-B. Variational analysis. Berlin: Springer, 2009, 736 p.
doi: 10.1007/978-3-642-02431-3 .

8.   Eremin I.I. Lineinaya optimizatsiya i sistemy lineinykh neravenstv [Linear optimization and systems of linear inequalities]. Moscow, Akademiya Publ., 2007, 256 p. ISBN: 978-5-7695-2963-4 .

9.   Kan Yu. S., Kibzun A.I. Zadachi stokhasticheskogo programmirovaniya s veroyatnostnymi kriteriyami [Problems in stochastic programming with probabilistic criteria]. Moscow, Fizmatlit Publ., 2009, 372 p. ISBN: 978-5-9221-1148-5/hbk .

10.   Lepp R. Approximate solution of stochastic programming problems with recourse. Kybernetika, 1987, vol. 23, iss. 6, pp. 476–482.