The theory of convex extensions in combinatorial optimization problems

TitleThe theory of convex extensions in combinatorial optimization problems
Publication TypeJournal Article
Year of Publication2017
AuthorsYakovlev, SV
Abbreviated Key TitleDopov. Nac. akad. nauk Ukr.
SectionInformation Science and Cybernetics
Date Published8/2017

The results of the theory of convex extensions for vertex located and polyhedral-spherical sets are summarized. In view of the theorems of existence of convex differentiable extensions, the problem is equivalent to a discrete optimization problem of convex functions under convex functional constraints. The convex nonlinear relaxation problem is considered.

Keywordscombinatorial optimization, combinatorial polyhedron, convex extension, vertex located set
  1. Sergienko, I. V. & Shilo, V. P. (2003). Discrete optimization problem. Kiev: Naukova Dumka (in Russian).
  2. Korte, B. & Vygen, J. (2002). Combinatorial Optimization: Theory and Algorithms. Heidelberg etc.: Springer.
  3. Hulianytskyi, L. F. & Mulesa, O. Y. (2016). Applied methods of combinatorial optimization. Kiev: Kyiv University Press (in Ukrainian).
  4. Stoyan, Y. G. & Yakovlev, S. V. (1986). Mathematical models and optimization methods of geometric design. Kiev: Naukova Dumka (in Russian).
  5. 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).
  6. 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).
  7. 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).
  8. Yakovlev, S. V., Gil, N. &. Komyak, V. M., et. al. (1995). Elements of the theory of geometric design. Kiev: Naukova Dumka (in Russian).
  9. 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).
  10. Emelichev, V. A., Kovalev, M. M. & Kravtsov, M. K. (1981). Polytopes, graphs, optimization (combinatorial theory of polytopes). Moscow: Nauka (in Russian).
  11. 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).
  12. 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).
  13. 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).
  14. 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).
  15. Yakovlev, S. V. (1989). Estimates of the minimum of convex functions on Euclidean combinatorial sets. Cybernetics. No. 3, pp. 89-97 (in Russian).