Existence of solutions and solving method of lexicographic problem of convex optimization with the linear criteria functions

1Semenova, NV
Lomaha, MM
2Semenov, VV
1V.M. Glushkov Institute of Cybernetics of the NAS of Ukraine, Kyiv
2V.М. Glushkov Institute of Cybernetics of the NAS of Ukraine, Kyiv
Dopov. Nac. akad. nauk Ukr. 2020, 12:19-27
https://doi.org/10.15407/dopovidi2020.12.019
Section: Information Science and Cybernetics
Language: Ukrainian
Abstract: 

Among vector problems, the lexicographic ones constitute a broad significant class of problems of optimization. Lexicographic ordering is applied to establish rules of subordination and priority. Hence, a lot of problems including the ones of complex system optimization, of stochastic programming under a risk, of the dynamic character, etc. may be presented in the form of lexicographic problems of optimization. We have revealed the conditions of existence of solutions of multicriteria of lexicographic optimization problems with an unbounded set of feasible solutions on the basis of applying the properties of a recession cone of a con vex feasible set, the cone which puts it in order lexicographically with respect to optimization criteria. The obtained conditions may be successfully used while developing algorithms for finding the optimal solutions of the mentioned problems of lexicographic optimization. A method of finding the optimal solutions of convex lexico graphic problems with the linear functions of criteria is built and grounded on the basis of ideas of the method of linearization and the Kelley cutting plane method.

Keywords: cutting plane method, existence of solutions, lexicographic optimization, method of linearization, vector criterion
References: 

1. Podinovskyi, V. V. & Gavrilov, V. M. (1975). Optimization on the consistently applied criteria. Moscow: Sov. radio (in Russian).
2. Chervak, Yu. Yu. (2002). Optimization. Unimprovable choice. Uzhgorod: Nat. Univ., Uzhgorod (in Ukrainian).
3. Podinovskyi, V. V. & Nogin, V. D. (2007). Pareto-optimal solutions of multicriteria problems. 2-th publ. Moscow: Fizmatlit (in Russian).
4. Lomaha, M. M. & Semenov, V. V. (2013). Quadratic problems of lexicographic optimization: properties and solving. Komp’yuterna mathematica. No 2, pp. 134-143 (in Ukrainian).
5. Semenova, N. V., Lomaha, M. M. & Semenov, V. V. (2014). Algorithm of solving of multicriteria lexicographic optimization problems with the convex functions of criteria. Int. J. Inform. Theories and Applications, 21, No. 3, pp. 254-262 (in Russian).
6. Lomaha, M. M. (2015). Solving lexicographic optimization problems with linear functions of criteria on a convex set. Uzhgorod Univ. Scientific Bulletin. Series: Mathematics and Informatics. No. 2 (27), pp. 70-75 (in Ukrainian).
7. Lomaha, M. M. & Semenova, N. V. (2019). Quadratic lexicographic problems of optimization and Lagrange’s reflection. Uzhgorod Univ. Scientific Bulletin. Series: Mathematics and Informatics. No. 2 (35), pp. 127-133 (in Ukrainian).
8. Rockafellar, R. (1973) Convex analysis, Moscow: Mir (in Russian).
9. Sergienko, T. I., Kozeratskya, L. N. & Lebedeva, T. T. (1995). Investigation of stability and parametric analysis of discrete optimization problems. Kyiv: Naukova Dumka (in Russian). 171 с.
10. Sergienko, I. V., Kozeratskaya, L. N. & Kononova, A. A. (1997). Stability and unboundedness of vector optimization problems. Cybernetics and Systems Analysis. 33, No. 1, pp. 1-7.
11. Sergienko, I. V., Lebedeva, T. T. & Semenova, N. V. (2000). Existence of solutions in vector optimization problems. Cybernetics and Systems Analysis. 36, No. 6, pp. 823-828.
12. Sergienko, T. I. (2015). Existence of Pareto-optimal solutions to the vector optimization problem with an unbounded feasible set. Dopov. Nac. akad. nauk. Ukr., No. 10, pp. 27-31 (in Ukrainian).
13. Lebedeva, Т. Т., Semenova, N. V. & Sergienko, Т. I. (2003). Optimality and solvability conditions in linear vector optimization problems with convex feasible region. Dopov. Nac. akad. nauk. Ukr., No. 10, pp. 80-85 (in Ukrainian).
14. Kelley, I. E. (1960). The cutting plane method for solving convex programs. SIAM J. 8, pp. 703-712.