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

Abstract

Для задач евклидовой комбинаторной оптимизации выделены классы вершинно расположенных и полиэдрально-сферических множеств, для которых обобщены результаты теории выпуклых продолжений. На основе теорем о существовании дифференцируемых выпуклых продолжений для вершинно расположенных множеств сформулирована эквивалентная задача дискретной оптимизации выпуклой функции при выпуклых функциональных ограничениях. Описаны свойства релаксационных задач как задач выпуклого программирования.

Для задач евклідової комбінаторної оптимізації виділені класи вершинно розташованих і поліедрально- сферичних множин, для яких узагальнено результати теорії опуклих продовжень. З використанням теорем про існування диференційованих опуклих продовжень для вершинно розташованих множин сформульовано еквівалентну задачу дискретної оптимізації опуклої функції при опуклих функціональних обмеженнях. Описано властивості релаксаційних задач опуклого програмування, що виникають.

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.