Probabilistic solutions of conditional optimization problems

G. A. Timofeeva

Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 26 (2020) no. 1, pp. 198-211

Résumé

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.

Détail

Keywords: probabilistic optimization, stochastic optimization, multicriteria optimization, linear convolution of criteria, consumer choice, preference function, securities portfolio problem.
Mots-clés : probabilistic solution, route selection

Bibliographie

[1] Prekopa A., Stochastic programming, Mathematics and Its Applications, 324, Springer, Dordrecht, 1995, 600 pp. | DOI | MR

[2] Popova O.A., “Zadacha lineinogo programmirovaniya so sluchainymi vkhodnymi dannymi”, Vestn. SGUTU, 41:2 (2013), 19–23

[3] Popova O.A., “Optimization problems with random data”, Zhurn. Sib. federal. un-ta. Ser.: Matematika i fizika, 6:4 (2013), 506–515 | MR

[4] Calafiore G., Campi M.C., “Uncertain convex programs: randomized solutions and confidence levels”, Math. Program. Ser. A, 102 (2005), 25–46 | DOI | MR | Zbl

[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, no. 1, 2936317-2 | DOI | MR

[6] Kuo-Chen Hung, Shu-Cheng Lin, Chun-Hsiao Chu, “Note on solving probabilistic programming problems involving multi-choice parameters”, J. Interdisciplinary Math., 18:5 (2015), 617–627 | DOI

[7] Podinovskii V.V., “Potentsialnaya optimalnost v mnogokriterialnoi optimizatsii”, Zhurn. vychisl. matematiki i mat. fiziki, 54:3 (2014), 415–424 | DOI

[8] Zhukovskii V.I., Molostvov V.S., Mnogokriterialnaya optimizatsiya sistem v usloviyakh nepolnoi informatsii, MNIIPU, M., 1990, 112 pp.

[9] Kurzhanskii A.B., Komarov Yu.A., “Gamiltonov formalizm dlya zadachi upravleniya dvizheniem s vektornym kriteriem”, Dokl. AN, 480:4 (2018), 408–412 | DOI

[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, 51, no. 32, 2018, 496–498 | DOI

[11] Powell W.B., “A unified framework for stochastic optimization”, European J. Oper. Research, 275:3 (2019), 795–821 | DOI | MR | Zbl

[12] Polyak B.T., Vvedenie v optimizatsiyu, Nauka, M., 1983, 383 pp.

[13] Robbins H., Monro S., “A stochastic approximation method”, The Annals Math. Stat., 22:3 (1951), 400–407 | DOI | MR | Zbl

[14] Ermoliev Y., “Stochastic quasigradient methods and their application to system optimization”, Stochastics. Ser. B, 9:1–2 (1983), 1–36 | DOI | MR | Zbl

[15] Bertsekas D.P., Tsitsiklis J.N., “Gradient convergence in gradient methods with errors”, SIAM J. Optim., 10:3 (2000), 627–642 | DOI | MR | Zbl

[16] Rosasco L., Villa S., Vu B.C., “Convergence of stochastic proximal gradient algorithm”, Appl. Math. Optim., 18 (2019), 1–27 | DOI

[17] Lai T.L., Xing H., Chen Z., “Mean-variance portfolio optimization when means and covariances are unknown”, Annals Appl. Stat., 5:2A (2011), 798–823 | DOI | MR | Zbl

[18] Markowitz H.M., Portfolio selection: efficient diversification of investments, 2nd edt., B. Blackwell, Cambridge, Mass., 1991, 384 pp. | MR

[19] Kan Yu.S., Kibzun A.I., Zadachi stokhasticheskogo programmirovaniya s veroyatnostnymi kriteriyami, Fizmatlit, Moskva, 2009, 372 pp.

[20] Lejeune M.A., Prekopa A., “Relaxations for probabilistically constrained stochastic programming problems: review and extensions”, Annals Oper. Research, 2018 | DOI

[21] Dentcheva D., Martinez G., “Regularization methods for optimization problems with probabilistic constraints”, Math. Programming, 138:1 (2013), 223–251 | DOI | MR | Zbl

[22] Genz A., “Numerical computation of multivariate normal probabilities”, J. Comput. Graphical Stat., 1992, no. 1, 141–149 | MR

[23] Henrion R., Moller A., “A gradient formula for linear chance constraints under Gaussian distribution”, Math. Oper. Research, 37 (2012), 475–488 | DOI | MR | Zbl

[24] Materon Zh., Sluchainye mnozhestva i integralnaya geometriya, Mir, M., 1978, 318 pp.

[25] Varian H.R., Intermediate. Microeconomics. A Modern approach, 8th edt., University of California at Berkeley, N Y, 2009, 739 pp.

[26] Dixit A.K., Stiglitz J.E., “Monopolistic competition and optimum product diversity”, The American Economic Review, 67:3 (1977), 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, 56:1 (1989), 21-35 | DOI | MR | Zbl

[28] Timofeeva G., “Investigation of mathematical model of passenger preferences”, AIP Conf. Proc., 2172 (2019), 080001 | DOI

[29] Kan Yu.S., Tuzov N.V., “Minimizatsiya kvantili normalnogo raspredeleniya bilineinoi funktsii poter”, Avtomatika i telemekhanika, 1998, no. 11, 82–92 | Zbl

[30] Kats I.Ya., Timofeeva G.A., “Bikriterialnaya zadacha stokhasticheskoi optimizatsii”, Avtomatika i telemekhanika, 1997, no. 3, 116–123 | Zbl