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

Індекс рубрикатора НБУВ: В173.113.2

Рубрики:

Квадратичне програмування

Шифр НБУВ: Ж29144 Пошук видання у каталогах НБУВ 

Індекс рубрикатора НБУВ: В173.113.2

Рубрики:

Квадратичне програмування

Шифр НБУВ: Ж61020 Пошук видання у каталогах НБУВ 

The paper briefly reviews the well-known partial results on the accuracy of dual bounds proposed by N. Z. Shor for quadratic extremal problems. The necessary and sufficient condition for the accuracy of the dual bound for a quadratic problem of general form is presented.

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

Рассмотрена общая задача минимизации квадратичной функции на квадратичных ограничениях. Приведено достаточное условие точности двойственной лагранжевой оценки, предложенной Н. З. Шором, для данной задачи.

Для нахождения минимального значения квадратичной функции на многогранном конусе применяются двойственные оценки с использованием функционально избыточных ограничений, полученых путем попарного перемноженыя исходных линейных ограничений. Сформулировано необходимое и достаточное условие, когда такой подход дает точное значение глобального минимума задачи.

Предложен ряд подходов для построения Ф-функций. В явном виде найдена нормализованная Ф-функция для описания взаимного расположения произвольно ориентированного эллипса и полуплоскости.

Рассмотрена задача упаковки одинаковых шаров в единичный куб в n-мерном пространстве. Исследована двойственная лагранжева оценка (верхняя оценка радиуса шаров) для классической квадратичной постановки задачи и ряда постановок, полученных путем ее расширения семействами функционально избыточных ограничений. В базовой постановке получено аналитическое выражение для двойственной оценки.

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

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

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

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

Рассмотрена двойственная оценка (лагранжева релаксация) для квадратичной экстремальной задачи общего вида. Сформулированы условия, при выполнении которых значение глобального экстремума квадратичной экстремальной задачи и значение ее двойственной оценки совпадают.

Індекс рубрикатора НБУВ: В173.112

Рубрики:

Дискретне програмування

Шифр НБУВ: Ж61020 Пошук видання у каталогах НБУВ 

Получено аналитическое выражение для двойственной оценки оптимального значения целевой функции квадратичной постановки задачи размещения точек в шаре. Этот результат справедлив также для оценки, получаемой в результате применения к данной постановке задачи SDP-релаксации.

Получено в матричном виде необходимое и достаточное условие точности двойственной лагранжевой оценки для общего случая квадратичной экстремальной задачи.

Для линейной задачи дополнительности рассмотрена эквивалентная постановка в виде квадратичной экстремальной задачи (КЭЗ), которая имеет точную двойственную оценку, если решение исходной задачи существует. Предложен путь нахождения приближения к одному из решений КЭЗ общего вида двойственным подходом в случае точной двойственной оценки.

Исследованы невыпуклые сепарабельные минимаксные задачи квадратичной оптимизации. Получено достаточное условие нахождения значения и точки глобального экстремума задачи данного класса путем нахождения двойственной оценки эквивалентной квадратичной экстремальной задачи.

Исследована невыпуклая сепарабельная минимаксная квадратичная оптимизационная задача. Изложено 2 подхода к ее решению: с помощью SOCP-релаксации и лагранжевой релаксации квадратичной экстремальной задачи-аналога. Получено условие, выполнение которого гарантирует нахождение значения и точки глобального экстремума задачи рассматриваемого класса вычислением двойственной оценки эквивалентной квадратичной экстремальной задачи.