DOI: https://doi.org/10.15407/kvt179.01.035
Kibern. vyčisl. teh., 2015, Issue 179, pp 35-42.
Norkin Bogdan V., PhD (Phys. & Math.), Researcher of the Department of Methods for Discrete Optimization of Mathematical Modeling for Analysis of Complex Systems of the Glushkov Institute of Cybernetics of the National Academy of Sciences of Ukraine, Acad.Glushkov ave., 40, Kiev, 03187, Ukraine, email: bogdan.norkin@gmail.com
ON THE APPROXIMATION OF VECTOR OPTIMIZATION PROBLEMS
Introduction. Vector optimization has a great variety of applications. Such problems naturally appear in stochastic optimization, where the optimization problem contains random parameters. In the latter case the vector objective function may include mean value, median, variance, quantiles and other characteristics of the random objective function. The difficulty is that these quantities usually cannot be calculated exactly and are non-convex as functions of variable parameters. These circumstances set additional difficulties for solving corresponding vector optimization problems.
The purpose of this paper is to study conditions for convergence of the approximation method when the objective functions and the feasible set are replaced by their more and more fine approximations.
Results. We consider an approximation approach to solving vector optimization problems. The standard approach to such problems is to optimize one criterion under constraints on the others or to scalarize the problem, i.e. to combine all criteria into one scalar criterion. This paper describes a completely different approach, where the feasible set is approximated by a discrete grid (deterministic or random) and the vector function is approximately calculated on this grid. The obtained discrete problem is exactly solved by Pareto type optimization.
Conclusions. Sufficient conditions are established for Pareto-optimal solutions of the approximate problems to converge in set convergence sense to the Pareto optimal solution of the original problem (with some accuracy). Namely, it is required for the approximate functions to converge uniformly to the original function and for the feasible set approximations (possibly discrete) to converge to elements of the original feasible set, at least, in the vicinity of the solution. The result confirms a natural hypothesis that the approximation accuracy should increase when approaching to the solution.
Keywords: vector optimization, stochastic multicriteria optimization, Pareto optimality, discrete approximation, epsilon-dominance.
References
1 Miettinen K. Nonlinear multiobjective optimization. Boston,London,Dordrecht: Kluwer Academic Publishers, 1999. 298 p.
2 Sobol I.M., Statnikov R.B. Vybor optimalnyh parametrov v zadachah so mnogimi kriteriyami (Selection of optimal parameters in problems with multiple criteria). 2-nd ed, revised and supplemented. Moscow: Drofa, 2006. 176 p. (In Russian).
3 Deb K. Multi-objective optimization using evolutionary algorithms. Chichester: John Willey & Sons, 2001. 497 p.
4 Hanne T. On the convergence of multiobjective evolutionary algorithms. European J. of Operational Research. 1999. 117. P. 553–564. https://doi.org/10.1016/S0377-2217(98)00262-8
5 Li Z., Li Zhe, Rudolph G. On the convergence properties of quantum-inspired multi-objective evolutionary algorithms. In: Advanced intelligent computing theories and applications. With aspects of contemporary intelligent computing techniques. Berlin, Heidelberg: Springer, 2007. P. 245–255. https://doi.org/10.1007/978-3-540-74282-1_28
6 Laumanns M., Zenklusen R. Stochastic convergence of random search methods to fixed size Pareto front approximations. European J. of Operational Research. 2011. 213. P. 414–421. https://doi.org/10.1016/j.ejor.2011.03.039
7 Ben Abdelaziz F. Solution approaches for the multiobjective stochastic programming. European J. of Operational Research. 2012. 216. P. 1–16. https://doi.org/10.1016/j.ejor.2011.03.033
8 Gutjahr W., Pichler A. Stochastic multi-objective optimization: a survey on non-scalarizing methods. Annals of Operations Research. 2013. P. 1–25.
9 Shapiro A., Dentcheva D., Ruszczycnski A. Lectures on stochastic programming: Modeling and theory. Second Edition. Philadelphia: SIAM, 2014. 494 p.
10 Koenker R. Quantile Regression. Cambridge, New York: Cambridge University Press, 2005. https://doi.org/10.1017/CBO9780511754098
11 Ermoliev Y.M. Metody stochasticheskogo programmirovaniya (Methods of stochastic programming). Moscow: Nauka, 1976. 240 p. (in Russian).
12 Rockafellar R.T., Wets R.J-B. Variational Analysis. Berlin: Springer, 1998 (3rd Printing in 2009). 734 p. https://doi.org/10.1007/978-3-642-02431-3
13 Norkin B.V. Sample approximations of multiobjective stochastic optimization problems. www://optimization-online.org. Electronic preprint. November 2014. Access: http://www.optimization-online.org/DB_HTML/2014/11/4655.html
Received 12.12.2014