Тема: РАЗРАБОТКА И ЭКСПЕРИМЕНТАЛЬНОЕ ИССЛЕДОВАНИЕ МЕТОДА ВЕТВЕЙ И ГРАНИЦ ДЛЯ РЕШЕНИЯ ЗАДАЧИ ВОГНУТОГО ПРОГРАММИРОВАНИЯ НА ОСНОВЕ ИСКЛЮЧЕНИЯ ОГРАНИЧЕНИЙ ИЗ ДОПУСТИМОГО МНОЖЕСТВА

Как известно, к задачам невыпуклой глобальной оптимизации часто сводятся многие инженерные, экономические, физические задачи, задачи экологии, медицины и других наук. Сложность таких задач заключается в том, что они носят многоэкстремальный характер, т.е. предполагают возможность существования большого количества локальных решений и стационарных точек, которые могут быть далеки от глобального решения [1].
Широкое распространение имеет класс d.c. функций DС( Ш1п) , представимых в виде разности двух выпуклых функций. Этот класс обладает несколькими замечательными свойствами, благодаря которым любая непрерывная задача оптимизации на компакте К ■■ Ш1пможет быть аппроксимирована задачей оптимизации с d.c. функциями [1-3].
К прикладным задачам невыпуклой оптимизации относятся [1-5]:
• задача поиска равновесия по Нэшу в биматричной игре;
• задачи двухуровневого программирования (исследование сложноорганизованных систем управления);
• линейные задачи дополнительности (задача торможения, задача упругопластического кручения, задача об оптимальном постоянном основном капитале и т.д.);
• задачи молекулярной биологии и нанофизики (задача минимизации функционала полной энергии в модели переноса заряда в молекуле ДНК и т.п.);
• задачи целочисленного линейного программирования и др.
Ввиду распространенности задач невыпуклой оптимизации разрабатываются разнообразные алгоритмы и методы их решения, см. [6-8]. Рассмотрим основные подходы к решению данных задач:
1. Методы, основанные на разбиении допустимого множества, см. [6]. При данном подходе множество допустимых решений разбивается на подмножества, которые в объединении составляют исходное. На каждом из полученных подмножеств отыскивается решение исходной задачи, результаты сравниваются и решением задачи на исходном множестве является наилучший из сравниваемых результатов. Таким образом, множество решений сужается для каждой подзадачи, однако растет количество задач.
2. Методы отсекающих плоскостей. Эти методы характеризуются тем, что на каждой новой итерации сужается множество допустимых решений за счет отсечения некоторой его части, тем самым уменьшая окрестность оптимального решения. И на полученном множестве решается исходная задача. К достоинствам таких методов можно отнести то, что они не требуют неопределенного размера оперативной памяти для хранения дерева решений, однако при каждом отсечении плоскости увеличивается множество ограничений, кроме того, при приближении к решению отсекающие плоскости начинают практически совпадать, что затрудняет решение задачи.
3. Сеточный метод. На множество допустимых решений накладывается сетка, имеющая различную плотность, основанную на предположениях о положении глобального оптимума на допустимом множестве. В каждом узле рассчитывается значение целевой функции. Полученные значения сравниваются между собой, и наилучшее из них становится решением исходной задачи. Этот подход решения задач широко применяется на практике и дает возможность отыскания наиболее близкого решения задачи, однако, не всегда точного.
4. Метод ветвей и границ. В методах такого типа перебор организовывается таким образом, чтобы отбросить часть допустимых решений. Для этого метода необходимы две процедуры: ветвление и нахождение оценок, или границ. На этапе ветвления происходит последовательное разбиение множества допустимых значений на подмножества, к которым рекурсивно применяется та же процедура. Полученные подмножества являются узлами построенного дерева поиска. Для определения оценок необходимо найти верхнюю и нижнюю границы для решения задачи на подмножестве допустимых значений. Если решается задача минимизации, то проверка происходит путем сравнения нижней оценки значения целевой функции на данном подмножестве с верхней границей в узле. Действует правило отсева: если нижняя граница на подмножестве А дерева поиска больше, чем верхняя граница на каком-либо ранее просмотренном подмножестве, то множество А можно исключить из дальнейшего рассмотрения. Данный метод является одним из наиболее надежных при решении задач. Преимуществам данного метода является гарантированное получение решения задачи. К его недостаткам можно отнести необходимость полностью решать задачи в узлах дерева, что при достаточно большой размерности задачи требует значительных затрат времени, см. [7, 9].
Для повышения эффективности современные алгоритмы часто являются комбинацией вышеизложенных методов решения задач оптимизации, кроме того в некоторых применяются параллельные вычисления [6].
Целью данной работы является разработка метода, дающего точное решение задачи вогнутого программирования за приличное время. Задача заключалась в разработке метода и последующей его модернизации для сокращения временных затрат.
Замечание: тема моей научно-исследовательской работы частично совпадает с темой научно-исследовательской работы студентки группы 09-535 Корепановой Анны Алексеевны. На некоторых этапах работа проводилась совместно.

Купить

Были разработаны последовательные и параллельные алгоритмы МВиГ на основе исключения ограничений из допустимого множества, решающие задачу вогнутой минимизации дифференцируемой квадратичной функции: min f(x), XED
на непустом, замкнутом, выпуклом многограннике следующего вида:
D = {хЕ Вп|Лх С учетом проведенных экспериментов, стоит отметить, что, выбирая из МВиГ, основанных на исключении ограничений из допустимого множества, целесообразнее использовать описанные в данной работе последовательный или распределенный МВиГ с применением списка решенных задач, но без использования искусственных переменных при установлении порядка обхода дерева, т.к. они показывают лучшие результаты.

Купить