Теорія опуклих продовжень в задачах комбінаторної оптимізації
DOI:
https://doi.org/10.15407/dopovidi2017.08.020Ключові слова:
вершинно розташована множина, комбінаторна оптимізація, комбінаторний багатогранник, опукле продовженняАнотація
Для задач евклідової комбінаторної оптимізації виділені класи вершинно розташованих і поліедральносферичних множин, для яких узагальнено результати теорії опуклих продовжень. З використанням теорем про існування диференційованих опуклих продовжень для вершинно розташованих множин сформульовано еквівалентну задачу дискретної оптимізації опуклої функції при опуклих функціональних обмеженнях. Описано властивості релаксаційних задач опуклого програмування, що виникають.
Завантаження
Посилання
Sergienko, I. V. & Shilo, V. P. (2003). Discrete optimization problem. Kiev: Naukova Dumka (in Russian).
Korte, B. & Vygen, J. (2002). Combinatorial Optimization: Theory and Algorithms. Heidelberg etc.: Springer. https://doi.org/10.1007/978-3-662-21711-5
Hulianytskyi, L. F. & Mulesa, O. Y. (2016). Applied methods of combinatorial optimization. Kiev: Kyiv University Press (in Ukrainian).
Stoyan, Y. G. & Yakovlev, S. V. (1986). Mathematical models and optimization methods of geometric design. Kiev: Naukova Dumka (in Russian).
Yakovlev, S. V. (1994). Theory of convex extensions of functions on the vertices of a convex polyhedron. J. Comp. Math. and Math. Phys. 34 (7), pp. 1112-1119 (in Russian).
Sergienko, I. V., Hulianytskyi, L. F. & Sirenko, S. I. (2009). Classification of applied methods of combinatorial optimization. Cybernetics and system analysis, No. 5, pp. 71-83 (in Russian). https://doi.org/10.1007/s10559-009-9134-0
Hulianytskyi, L. F. & Sergienko, I. V. (2007). Metaheuristic method of deformed polyhedron in combinatorial optimization. Cybernetics and system analysis, No. 6, pp. 70-79 (in Russian).
Yakovlev, S. V., Gil, N. &. Komyak, V. M., et. al. (1995). Elements of the theory of geometric design. Kiev: Naukova Dumka (in Russian).
Grichik, V. V., Kiselyova, O. M. & Yakovlev, S. V., et. al. (2012). Mathematical methods of optimization and intelligent computer technologies for modeling complex systems with consideration of spatial shapes of objects. Donetsk: Nauka and Osvita (in Ukrainian).
Emelichev, V. A., Kovalev, M. M. & Kravtsov, M. K. (1981). Polytopes, graphs, optimization (combinatorial theory of polytopes). Moscow: Nauka (in Russian).
Pichugina, O. S. & Yakovlev, S. V. (2016). On continuous representations and functional continuations in combinatorial optimization. Cybernetics and system analysis. 52, No. 6, pp. 102-113 (in Russian). http://link.springer.com/article/10.1007/s10559-016-9894-2 https://doi.org/10.1007/s10559-016-9894-2
Pichugina, O. & Yakovlev, S. (2016). Convex extensions and continuous functional representations in optimization with their applications. J. Coupled Syst. Multiscale Dyn., 4 (2), pp. 129-152 (in Russian). http://link.springer.com/article/10.1007/s10559-016-9894-2
http://www.ingentaconnect.com/contentone/asp/jcsmd/2016/00000004/0000000.
Stoyan, Yu. G. & Yakovlev, S. V. (1988). Construction of convex and concave functions on the permutation polyhedron. Doklady Academy of Science USSR, Ser. A. No. 5, pp. 66-68 (in Russian).
Stoyan, Yu. G., Yakovlev, S. V., Yemets, O. A. & Valuyskaya, O. A. (1995). Construction of convex continuations for functions defined on hypersphere. Cybernetics and system analysis. No. 2, pp. 27-36 (in Russian).
Yakovlev, S. V. (1989). Estimates of the minimum of convex functions on Euclidean combinatorial sets. Cybernetics. No. 3, pp. 89-97 (in Russian).
##submission.downloads##
Опубліковано
Як цитувати
Номер
Розділ
Ліцензія
Авторське право (c) 2024 Доповіді Національної академії наук України
Ця робота ліцензується відповідно до Creative Commons Attribution-NonCommercial 4.0 International License.
