Критерии точности SDP-релаксаций квадратичных экстремальных задач

• Veröffentlicht in: Кибернетика и системный анализ
• Datum: 2016
• 1. Verfasser: Березовский, О.А.
• Format: Artikel
• Sprache: Russisch
• Veröffentlicht: Інститут кібернетики ім. В.М. Глушкова НАН України 2016
• Schlagworte: Системный анализ
• Online Zugang: https://nasplib.isofts.kiev.ua/handle/123456789/142061
• Назва журналу: Digital Library of Periodicals of National Academy of Sciences of Ukraine
• Zitieren: Критерии точности SDP-релаксаций квадратичных экстремальных задач / О.А. Березовский // Кибернетика и системный анализ. — 2016. — Т. 52, № 6. — С. 95-101. — Бібліогр.: 14 назв. — рос.

Исследованы условия получения точных решений квадратичных экстремальных задач общего вида с помощью SDP-релаксаций. На основе известных результатов относительно точности двойственных оценок (лагранжевых релаксаций) и их взаимосвязи с SDP-релаксациями сформулирован ряд условий, при которых оптимальные значения целевых функций квадратичной экстремальной задачи и ее SDP-релаксации равны. Досліджено умови отримання точних розв’язків квадратичних екстремальних задач загального вигляду за допомогою SDP-релаксацій. На основі відомих результатів стосовно точності двоїстих оцінок (лагранжевих релаксацій) і їхнього взаємозв’язку з SDP-релаксаціями сформульовано ряд умов, при яких оптимальні значення цільових функцій квадратичної екстремальної задачі та її SDP-релаксації рівні. The author analyzes the conditions of obtaining exact solutions to quadratic extremum problems of general type by using SDP-relaxations. Based on the known results for exactness of dual bounds (lagrangian relaxations) and their relationship with SDP-relaxations, several conditions are formulated, under which the values of optimal objective function of the quadratic extremal problem and its SDP-relaxation are equal.