Теория выпуклых продолжений в задачах комбинаторной оптимизации

• Published in: Доповіді НАН України
• Date: 2017
• Main Author: Яковлев, С.В.
• Format: Article
• Language: Russian
• Published: Видавничий дім "Академперіодика" НАН України 2017
• Subjects: Інформатика
• Online Access: https://nasplib.isofts.kiev.ua/handle/123456789/126837
• Journal Title: Digital Library of Periodicals of National Academy of Sciences of Ukraine
• Cite this: Теория выпуклых продолжений в задачах комбинаторной оптимизации / С.В. Яковлев // Доповіді Національної академії наук України. — 2017. — № 8. — С. 20-26. — Бібліогр.: 15 назв. — рос.

Для задач евклидовой комбинаторной оптимизации выделены классы вершинно расположенных и полиэдрально-сферических множеств, для которых обобщены результаты теории выпуклых продолжений. На
 основе теорем о существовании дифференцируемых выпуклых продолжений для вершинно расположенных
 множеств сформулирована эквивалентная задача дискретной оптимизации выпуклой функции при выпуклых функциональных ограничениях. Описаны свойства релаксационных задач как задач выпуклого программирования. Для задач евклідової комбінаторної оптимізації виділені класи вершинно розташованих і поліедрально-
 сферичних множин, для яких узагальнено результати теорії опуклих продовжень. З використанням теорем про існування диференційованих опуклих продовжень для вершинно розташованих множин сформульовано еквівалентну задачу дискретної оптимізації опуклої функції при опуклих функціональних обмеженнях. Описано властивості релаксаційних задач опуклого програмування, що виникають. 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.