Optimization problems with random parameters are studied. The traditional approach to their solution consists in finding a deterministic solution satisfying a certain criterion: optimization of the expected value of the objective function, optimization of the probability of attaining a certain level, or optimization of the quantile. In this review paper, we consider a solution of a stochastic optimization problem in the form of a random vector (or a random set). This is a relatively new class of problems, which is called “probabilistic optimization problems.” It is noted that the application of probabilistic solutions in problems with random parameters is justified in the cases of multiple decision makers. Probabilistic optimization problems arise, for example, in the analysis of multicriteria problems; in this case, the weight coefficients of the importance of criteria are regarded as a random vector. We consider important examples of economic–mathematical models, which are optimization problems with a large number of decision makers: the problem of optimal choice based on the consumer’s preference function, the route selection problem based on the optimization of the generalized cost of the trip, and the securities portfolio problem with a distribution of the investors’ risk tolerance. Mathematical statements of these problems are given in the form of problems of probabilistic optimization. Some properties of the constructed models are studied; in particular, the expected value of the probabilistic solution of an optimization problem is analyzed.
Keywords: probabilistic optimization, stochastic optimization, probabilistic solution, multicriteria optimization, linear convolution of criteria, consumer choice, preference function, route selection, securities portfolio problem
Received December 2, 2019
Revised February 10, 2020
Accepted February 17, 2020
Galina Adol’fovna Timofeeva, Dr. Phys.-Math. Sci., Prof., Ural State University of Railway Transport, Yekaterinburg, 620034 Russia; Ural Federal University, Yekaterinburg, 620083 Russia, e-mail: Gtimofeeva@usurt.ru
REFERENCES
1. Prekopa A. Stochastic programming. Ser. Mathematics and Its Applications, vol. 324, Dordrecht: Springer, 1995, 600 p. doi: 10.1007/978-94-017-3087-7
2. Popova O.A. Linear programming problem with random input data. Vestn. VSGUTU, 2013, vol. 41, no. 2, pp. 19–23 (in Russian).
3. Popova O.A. Optimization problems with random data. J. Siberian Federal Univ. Math. Phys., 2013, vol. 6, no. 4, pp. 506–515.
4. Calafiore G., Campi M.C. Uncertain convex programs: randomized solutions and confidence levels. Math. Program., Ser. A, 2005, vol. 102, pp. 25–46. doi: 10.1007/s10107-003-0499-y
5. Bonami P., Lejeune M.A. An exact solution approach for portfolio optimization problems under stochastic and integer constraints. Stochastic Programming E-print Series (SPEPS), 2007, iss. 1, no. 2936317-2. doi: 10.18452/8373
6. Kuo-Chen Hung, Shu-Cheng Lin, Chun-Hsiao Chu Note on solving probabilistic programming problems involving multi-choice parameters. J. Interdisciplinary Math., 2015, vol. 18, no. 5, pp. 617–627. doi: 10.1080/09720502.2015.1047606
7. Podinovski V.V. Potential optimality in multicriterial optimization. Comput. Math. Math. Phys., 2014, vol. 54, no. 3, pp. 429–438. doi: 10.1134/S0965542514030154
8. Zhukovskii V.I., Molostvov V.S. Mnogokriterial’naya optimizatsiya sistem v usloviyakh nepolnoi informatsii [Multicriterion Optimization of Systems in Conditions of Incomplete Information]. Moscow: MNIIPU Publ., 1990, 112 p.
9. Komarov Yu.A., Kurzhanski A.B. Hamiltonian formalism for the problem of optimal motion control under multiple criteria. Dokl. Math., 2018, vol. 97, no. 3, pp. 291–294. doi: 10.1134/S1064562418030134
10. Timofeeva G., Martynenko A., Zavalishchin D. Probabilistic modeling of passengers and carriers preferences via bicriterial approach. In: 17th IFAC Workshop on Control Applications of Optimization (CAO 2018), IFAC-PapersOnLine, 2018, vol. 51, no. 32, pp. 496–498. doi: 10.1016/j.ifacol.2018.11.469
11. Powell W.B. A unified framework for stochastic optimization. European J. Operational Research, 2019, vol. 275, no. 3, pp. 795–821. doi: 10.1016/j.ejor.2018.07.014
12. Polyak B. Introduction to optimization. New York: Optimization Software, 1987. ISBN: 9780911575149 . Original Russian text published in Polyak B.T. Vvedenie v optimizatsiyu. Moscow: Nauka Publ., 1983, 383 p.
13. Robbins H., Monro S. A stochastic approximation method. The Annals Math. Stat., 1951, vol. 22, no. 3, pp. 400–407. doi: 10.1214/aoms/1177729586
14. Ermoliev Y. Stochastic quasigradient methods and their application to system optimization. Stochastics Ser. B, 1983, vol. 9, no. 1–2, pp. 1–36. doi: 10.1080/17442508308833246
15. Bertsekas D.P., Tsitsiklis J.N. Gradient convergence in gradient methods with errors. SIAM J. Optim., 2000, vol. 10, no. 3, pp. 627–642. doi: 10.1137/S1052623497331063
16. Rosasco L., Villa S., V~u B.C. Convergence of stochastic proximal gradient algorithm. Appl. Math. Optim., 2019, vol. 18, pp. 1–27. doi: 10.1007/s00245-019-09617-7
17. Lai T.L., Xing H., Chen Z. Mean-variance portfolio optimization when means and covariances are unknown. Annals Appl. Stat., 2011, vol. 5, no. 2A, pp. 798–823. doi: 10.1214/10-AOAS422
18. Markowitz H.M. Portfolio selection: efficient diversification of investments (2nd ed.) Cambridge, Mass.: B. Blackwell, 1991, 384 p. ISBN: 9781557861085 .
19. Kibzun A.I., Kan Yu.S. Stochastic programming problems with probability and quantile functions. N Y: Wiley, 1996, 316 p. ISBN: 9780471958154 . Original Russian text published in Kan Yu.S., Kibzun A.I. Zadachi stokhasticheskogo programmirovaniya s veroyatnostnymi kriteriyami. Moscow: Fizmatlit Publ., 2009, 372 p. ISBN: 978-5-9221-1148-5 .
20. Lejeune M.A., Prekopa A. Relaxations for probabilistically constrained stochastic programming problems: review and extensions. Annals Oper. Research, 2018. doi: 10.1007/s10479-018-2934-8
21. Dentcheva D., Martinez G. Regularization methods for optimization problems with probabilistic constraints. Math. Program., 2013, vol. 138, no. 1, pp. 223–251. doi: 10.1007/s10107-012-0539-6
22. Genz A. Numerical computation of multivariate normal probabilities. J. Comput. Graphical Stat., 1992, vol. 1, no. 2, pp. 141–149. doi: 10.2307/1390838
23. Henrion R., MЈoller A. A gradient formula for linear chance constraints under Gaussian distribution. Mathematics of Operations Research, 2012, vol. 37, no. 3, pp. 475–488. doi: 10.1287/moor.1120.0544
24. Matheron G. Random sets and integral geometry. N Y: Wiley, 1975, 261 p. ISBN: 978-0-471-57621-1 . Translated to Russian under the title Sluchainye mnozhestva i integral’naya geometriya. Moscow: Mir Publ., 1978, 318 p.
25. Varian H.R. Intermediate. Microeconomics. A modern approach. (8th edn.) N Y: University of California at Berkeley, 2009. 739 p. ISBN: 978-0393934243 .
26. Dixit A.K., Stiglitz J.E. Monopolistic Competition and Optimum Product Diversity. The American Economic Review, 1977, vol. 67, no. 3, pp. 297–308. doi: 10.7916/D8S75S91
27. Anderson S.P., De Palma A., Thisse J.-F. Demand for differentiated products, discrete choice models, and the characteristics approach. Review of Economic Studies, 1989, vol. 56, no. 1, pp. 21–35. doi: 10.2307/2297747
28. Timofeeva G. Investigation of mathematical model of passenger preferences. AIP Conf. Proc., 2019, vol. 2172, art. no. 080001. doi: 10.1063/1.5133559
29. Kan Yu.S., Tuzov N.V. Quantile minimization of the normal distribution of a bilinear loss function. Autom. Remote Control, 1998, vol. 59, no. 11, pp. 1568–1576.
30. Kats I.Ya., Timofeeva G.A. Bicriteria problem of stochastic optimization. Autom. Remote Control, 1997, vol. 58, no. 3, pp. 422–428.
Cite this article as: G.A. Timofeeva. Probabilistic solutions of conditional optimization problems, Trudy Instituta Matematiki i Mekhaniki URO RAN, 2020, vol. 26, no. 1, pp. 198–211.
