Введение 3
Постановка задачи 5
Глава 1. Обзор литературы 6
Глава 2. Теоретическая часть 9
2.1. Эвристические алгоритмы 9
2.2. Метод заряженных шариков 11
Глава 3. Практическая часть 17
3.1. Итоговый алгоритм 17
3.2. Результаты работы алгоритма 17
Выводы 22
Заключение 23
Список литературы 24
Приложение 25
В общем смысле совокупность методов, ориентированных на нахождение наибольших и наименьших значений величин, называют теорией оптимизации. Основным разделом теории оптимизации является нелинейное программирование (НЛП), задача которого охватывает мириады форм и возникает в физических, естественных, математических, экономических науках и в инженерной деятельности.
Так, в экономике — это основная экономическая задача, связанная с распределением ограниченных ресурсов. Также решение задачи НЛП используется в управлении государством, когда нужно минимизировать затраты при условии, что благосостояние государства должно находиться выше некоторого минимального значения.
В стандартной задаче НЛП требуется минимизировать целевую нелинейную функцию нескольких переменных f:X→R при заданном допустимом множестве 〖X={x|g〗_i (x)≤0,i=(1,m) ̅}∈R^n:
{█(f(x)→min@x∈X )┤ (1)
Для их решения применяются итеративные методы, идеей которых является движение от заданной начальной точки x_0∈X вдоль генерируемой последовательности точек x_1,x_2,…,x_k,x_(k+1),… , приближающейся к некоторому «оптимальному» решению данной задачи. Переход от x_k к x_(k+1) называется итерацией. Обычно она строится по схеме
x_(k+1)=x_k+δ_k (ρ_k ) ⃗,k=0,1,…
где вектор (ρ_k ) ⃗ — направление в точке x_k, а число δ_k — длина шага. Итеративные методы отличаются друг от друга способом вычисления δ_k.
Правила остановки итеративного процесса задаются различными способами с заданной точностью ε>0 решения исходной задачи:
||x_(k+1)-x_k ||≤ε,|f(x_(k+1) )-f(x_k ) |≤ε,||∇f(x_k )||≤ε
Эффективность процесса оптимизации, с одной стороны, зависит от умения использовать результаты таких наук, как теория алгоритмов, функциональный анализ, математический анализ и линейная алгебра.
С другой стороны, решения оптимизационной задачи в некоторых случаях требуют больших затрат временных и вычислительных ресурсов. Из-за этого такие задачи в первую очередь направлены на реализацию на вычислительной технике.
Одними из наиболее исследованных являются задачи выпуклого программирования. Этот раздел оптимизации занимается минимизацией выпуклых функций на выпуклых множествах. И это не случайно, ведь свойство выпуклости чрезвычайно важно не только в теоретическом плане (единственность решения, выполнение условий регулярности и т.д.), так и в практическом (существует большое количество методов разработанных для выпуклых задач и учитывающих их специфику). Однако, как правило, задачи, возникающие на практике, являются невыпуклыми.
В данной работе рассматривается задача нахождения ближайшей к нулю точки невыпуклого множества. Рассматривается алгоритм поиска глобального решения поставленной задачи. Он основан на совместном применении метода заряженных шариков, изначально предлагавшегося для поиска ортогональной проекции точки на выпуклое множество, а также эвристических вероятностных алгоритмов. Последние используются для поиска исходной точки в окрестности глобального решения, из которой далее запускается метод заряженных шариков.
Отметим, что, вообще говоря, задача получения начальной точки является самостоятельной важной задачей, которая особенно важна в алгоритмах глобальной оптимизации.
Рассмотренная ниже задача имеет множество практических приложений и возникает, например, при моделировании освещения в компьютерной графике, робототехнике, астрономии и т.д.
Постановка задачи
Пусть x∈X — произвольная точка множества X={x∈R^n ┤| f(x)≤0}, где f∶ R^n→R — непрерывно дифференцируемая функция.
Требуется найти ближайшую к нулю точку множества X:
{█(‖x‖→min@ x∈X )┤ (2)
Следует отметить, что задачу (2) можно расширить на случай нахождения минимального расстояния между множеством X и любой точкой x ̃∈R^n, при помощи преобразования (сдвига) координат, приняв за x ̃=0_n.
Очевидно, что X — замкнутое множество. Для любого x∈X минимум будет достигаться на множестве X∩S_‖x‖ , где S_‖x‖ — замкнутый шар радиуса ‖x‖ с центром в начале координат. Это множество замкнуто как пересечение двух замкнутых множеств, и ограничено как пересечение множеств, одно из которых ограничено. Исходя из вышесказанного, по теореме Вейерштрасса существует такая точка x_*∈X, на которой достигается минимальное значение целевой функции ‖x‖. Отметим, что в отличие от [1] мы не требуем выпуклости Х.
Ожидается, что решение задачи (2) будет найдено для любой заданной точности ε>0.
В работе была рассмотрена задача нахождения ближайшей к нулю точки невыпуклого множества с гладкой границей и предложен алгоритм для ее решения. Данный алгоритм был построен на основе недавно предложенных эвристических алгоритмах и методе заряженных шариков. Проведенные вы-числительные эксперименты показали возможность практического применения предложенного подхода в различных задачах, и в некоторых случаях до-казали его эффективность по сравнении с уже существующими алгоритмами, используемыми для решения аналогичных задач.
