Решение задач безусловной и условной оптимизации методом Нелдера-Мида

Введение


Метод Нелдера — Мида — метод оптимизации (поиска минимума) функции от нескольких переменных. Простой и в тоже время эффективный метод, позволяющий оптимизировать функции без использования градиентов. Метод надежен и, как правило, показывает замечательные результаты, хотя и отсутствует теория сходимости.
Метод Нелдера-Мида является развитием симплексного метода Спендли, Хекста и Химсворта.
Выпуклая оболочка множества -й равноудаленной точки в -мерном пространстве называется регулярным симплексом. Эта конфигурация рассматривается в методе Спендли, Хекста и Химсворта.
В двухмерном пространстве регулярным симплексом является правильный треугольник, а в трехмерном - правильный тетраэдр. Идея метода состоит в сравнении значений функции в вершинах симплекса и перемещении симплекса в направлении оптимальной точки с помощью итерационной процедуры.
В симплексном методе, предложенном первоначально, регулярный симплекс использовался на каждом этапе. Нелдер и Мид предложили несколько модификаций этого метода, допускающих, чтобы симплексы были неправильными. В результате получился очень надежный метод прямого поиска, являющийся одним из самых эффективных при .
Главными особенностями алгоритма можно назвать следующие:
 Метод Нелдера-Мида не накладывает ограничений на гладкость функции
 Данный метод явялется эффективным при низкой скорости вычисления минимизируемой функции. Как правило, на каждой итерации происходит вычисление значения функции не более чем в 3 точках.
 Отсутствие теории сходимости. Алгоритм может расходиться даже на гладких функциях.
 
Описание оптимизационных задач

Оптимизационная задача – это задача нахождения экстремума (минимума или максимума) целевой функции в некоторой области конечномерного векторного пространства, ограниченной набором линейных и/или нелинейных равенств и/или неравенств.
Целевая функция представляет собой набор критериев качества, которые должны быть оптимизированы одновременно. В общем случае целевая функция состоит из управляемых и неуправляемых переменных. Условие поиска экстремума целевой функции записывается в следующем виде:

Методы решения оптимизационных задач изучает математическое программирование. Математическое программирование – это математическая дисциплина, изучающая теорию и методы решения задач по определению экстремумов функций на множествах конечномерного векторного пространства, определяемых набором линейных и/или нелинейных ограничений (равенствами и/или неравенствами). Математическое программирование представляет собой, как правило, многократно повторяющуюся вычислительную процедуру, приводящую к искомому оптимальному решению. Выбор метода математического программирования для решения оптимизационной задачи определяется видом зависимостей в математической модели, характером искомых переменных, категорией исходных данных и количеством критериев оптимальности:
• Методы линейного программирования используются в случае, если в математической модели имеются только линейные зависимости между переменными, для решения оптимизационной задачи.
• Методы нелинейного программирования используются в случае, если в математической модели имеются нелинейные зависимости между переменными, для решения оптимизационной задачи.
• Методы целочисленного или дискретного программирования используются в случае, если среди переменных имеются целочисленные или дискретные переменные, соответственно.
• Методы стохастического программирования используются в случае, если исходные данные или их часть являются случайными величинами.
• Математический аппарат теории игр используются в случае, если задана недетерминированная (неопределенная) исходная информация.
Решение задачи оптимизации осуществляется с помощью поисковых методов, использующих предшествующую информацию для построения улучшенного решения задачи (итерационные методы расчета). К настоящему времени разработано достаточно много методов локальной оптимизации для решения задач общего вида. Большинство из них используют принцип локального спуска, когда метод последовательно на каждом шаге переходит к точкам с существенно меньшими (большим) значениями целевой функции. Данные методы отличаются один от другого способом определения направления движения к оптимуму, размером шага и продолжительностью поиска вдоль найденного направления, а также критериями окончания поиска. Поиск оптимального значения в таких задачах может быть представлен в виде итерационного соотношения:

где переменная - это приращение вектора управляемых параметров. В зависимости от условия поиска (поиск максимального или минимального значения целевой функции) используется либо знак «+», либо знак «-».
Приращение вектора управляемых параметров в большинстве случаях вычисляется по формуле:

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

Другими словами, величина шага расчета вычисляется при решении следующего выражения:

В результате решения данного уравнение мы получим, что шаг расчета в символьном виде определяется следующим образом:

где - значение аргумента функции на k-ом шаге итерации;
n – количество неизвестных переменных, которые определяются в ходе решения задачи;
L – некоторая константа, которая определяется из определителя следующей матрицы:

В результате для определения оптимального шага расчета требуется выполнить большой объем вычислений целевой функции. Для снижения числа операций на практике используют другой подход: подбирают такие значения шага расчета , чтобы они удовлетворяли любому из представленных ниже условию.
• Первое условие (правило Армихо) является адаптивным методом поиска величины шага расчета, которое говорит о том, что функция не должна превышать значения некоторой убывающей линейной функции, равной в нуле:

где коэффициент , а шаг расчета определяется итеративно путем умножения первоначального шага на коэффициент до тех пор пока не будет выполняться условие.
Методика определения шага расчета оптимизационной задачи в соответствии с правилом Армихо заключается в следующем:
1.Задать коэффициент в диапазоне от 0 до 1.
2.Задать начальное значение шага .
Процедура поиска (проверка выполнения условия по правилу Армихо)
3. В случае если условие по правилу Армихо не выполняется, тогда необходимо скорректировать шаг расчета , где переменная может принимать любое значение от 0 до 1, по умолчанию примем, что переменная , а - текущий шаг поиска.
4. В случае если условие по правилу Армихо выполняется, тогда в качестве шага расчета можно принять , а процедура поиска завершается.
Данное правило требует однократного вычисления градиента, после чего небольшое количество итераций затрачивается на подбор подходящего шага. Каждая из таких вложенных итераций, в свою очередь, требует вычисления значения целевой функции без градиента, то есть проводимые испытания относительно легковесны. Следует отметить, что данное условие удовлетворяется для всех достаточно малых . Правило Армихо можно расширить на многокритериальный случай: неравенство 3.19 следует понимать покомпонентно.
• Второе условие (Правило Вольфе-Пауэлла - Wolfe. P) является модифицированным критерием, позволяет выбрать шаг расчета в случае выполнения двух условий:
- функция не должна превышать значения некоторой убывающей линейной функции, равной в нуле:

- величина скорости изменения функция в заданном направлении была в раз больше, чем скорость изменения функции в первоначальной точке