УДК 519.8
MSC: 90C15, 90C29, 91B70, 91B16
DOI: 10.21538/0134-4889-2020-26-1-198-211
Полный текст статьи (Full text)
Традиционный подход к решению задач оптимизации со случайными параметрами состоит в нахождении детерминированного решения, удовлетворяющего тому или иному критерию: оптимизации среднего ожидаемого значения целевой функции, оптимизации вероятности достижения определенного уровня или оптимизации квантили. В данной обзорной работе рассматривается решение задачи стохастической оптимизации в форме случайного вектора (или случайного множества). Это относительно новый класс задач, который называют вероятностными задачами оптимизации. Отмечается, что применение вероятностных решений в задачах со случайными параметрами обосновано в тех случаях, когда лиц, принимающих решения, много. В числе прочих задачи вероятностной оптимизации возникают при анализе многокритериальных задач; в этом случае весовые коэффициенты важности критериев рассматриваются как случайный вектор. В статье представлены важные примеры экономико-математических моделей — задач оптимизации с большим числом принимающих решение лиц: задача об оптимальном выборе на основе функции предпочтения потребителей; задача о выборе маршрута на основе оптимизации обобщенной стоимости поездки; задача о портфеле ценных бумаг с учетом распределения склонности инвесторов к риску. Приведены математические формулировки этих задач в форме задач вероятностной оптимизации. Изучаются некоторые свойства построенных моделей, в том числе анализируется математическое ожидание вероятностного решения задачи оптимизации.
Ключевые слова: вероятностная оптимизация, стохастическая оптимизация, вероятностное решение, многокритериальная оптимизация, линейная свертка критериев, выбор потребителя, функция предпочтения, выбор маршрута, задача о портфеле ценных бумаг
СПИСОК ЛИТЕРАТУРЫ
1. Prekopa A. Stochastic programming. Dordrecht: Springer, 1995. 600 p. (Mathematics and Its Applications; vol. 324.) doi: 10.1007/978-94-017-3087-7
2. Попова О.А. Задача линейного программирования со случайными входными данными // Вестн. СГУТУ. 2013. Т. 41, № 2. С. 19–23.
3. Popova O.A. Optimization problems with random data // Журн. Сиб. федерал. ун-та. Сер.: Математика и физика. 2013. Т. 6. № 4. С. 506–515.
4. Calafiore G., Campi M.C. Uncertain convex programs: randomized solutions and confidence levels // Math. Program. Ser. A. 2005. Vol. 102. P. 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. P. 617–627. doi: 10.1080/09720502.2015.1047606
7. Подиновский В.В. Потенциальная оптимальность в многокритериальной оптимизации // Журн. вычисл. математики и мат. физики. 2014. T. 54, № 3. C. 415–424. doi: 10.7868/S004446691403017X
8. Жуковский В.И., Молоствов В.С. Многокритериальная оптимизация систем в условиях неполной информации. М.: МНИИПУ, 1990. 112 c.
9. Куржанский А.Б., Комаров Ю.А. Гамильтонов формализм для задачи управления движением с векторным критерием // Докл. АН. 2018. T. 480, № 4. C. 408–412. doi: 10.7868/S0869565218160053
10. Timofeeva G., Martynenko A., Zavalishchin D. Probabilistic modeling of passengers and carriers preferences via bicriterial approach // 17th IFAC Workshop on Control Applications of Optimization (CAO 2018): IFAC-PapersOnLine. 2018. Vol. 51, no. 32. P. 496–498. doi: 10.1016/j.ifacol.2018.11.469
11. Powell W.B. A unified framework for stochastic optimization // European J. Oper. Research. 2019. Vol. 275, no. 3. P. 795–821. doi: 10.1016/j.ejor.2018.07.014
12. Поляк Б.Т. Введение в оптимизацию. M.: Наука, 1983. 383 c.
13. Robbins H., Monro S. A stochastic approximation method // The Annals Math. Stat. 1951. Vol. 22, no. 3. P. 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. P. 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. P. 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. P. 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. 2 A. P. 798–823. doi: 10.1214/10-AOAS422
18. Markowitz H.M. Portfolio selection: efficient diversification of investments. 2nd edt. Cambridge, Mass.: B. Blackwell, 1991. 384 p.
19. Кан Ю.С., Кибзун А.И. Задачи стохастического программирования с вероятностными критериями. Москва: Физматлит, 2009. 372 с.
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. Programming, 2013. Vol. 138, no. 1, P. 223–251.
22. Genz A. Numerical computation of multivariate normal probabilities // J. Comput. Graphical Stat. 1992. No. 1. P. 141–149.
23. Henrion R., MЈoller A. A gradient formula for linear chance constraints under Gaussian distribution // Math. Oper. Research, 2012. Vol. 37. P. 475–488.
24. Матерон Ж. Случайные множества и интегральная геометрия. М.: Мир, 1978. 318 p.
25. Varian H.R. Intermediate. Microeconomics. A Modern approach. 8th edt. N Y: University of California at Berkeley, 2009. 739 p.
26. Dixit A.K., Stiglitz J.E. Monopolistic competition and optimum product diversity // The American Economic Review. 1977. Vol. 67, no. 3. P. 297–308.
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. Кан Ю.С., Тузов Н.В. Минимизация квантили нормального распределения билинейной функции потерь // Автоматика и телемеханика. 1998. № 11. С. 82–92.
30. Кац И.Я., Тимофеева Г.А. Бикритериальная задача стохастической оптимизации // Автоматика и телемеханика. 1997. № 3. C. 116–123.
Поступила 2.12.2019
После доработки 10.02.2020
Принята к публикации 17.02.2020
Тимофеева Галина Адольфовна
д-р физ.-мат. наук, профессор
зав. кафедрой
Уральский государственный университет путей сообщения;
профессор
Уральский федеральный университет
г. Екатеринбург
e-mail: Gtimofeeva@usurt.ru
Ссылка на статью: Г.А. Тимофеева. Вероятностные решения задач условной оптимизации // Тр. Ин-та математики и механики УрО РАН. 2020. Т. 26, № 1. C. 198-211.
English
G.A. Timofeeva. Probabilistic solutions of conditional optimization problems
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
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.
