Минимизация функции методом Нелдера-Мида

В лабораторных предыдущих работах описаны градиентные методы отыскания локального минимума функции нескольких переменных. В настоящей работе рассматривается один из методов минимизации, в котором в отличие от методов гради­ентного спуска не требуется вычислять градиент целевой функции [10].

Методы минимизации, не требующие вычисления производных, называются методами поиска [10].

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

В данной лабораторной работе для минимизации целевой функции используется метод Нелдера—Мида. Основу стра­тегии Нелдера—Мида проще всего понять на примере минимизации в двумерном случае.

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

Рис. 2.9

Вычислим значения функции в вершинах А, В и С треугольника. Выберем точку с максимальным значением функции. Пусть, например, это точка А. Построим точку А', симметричную точке А относи­тельно противолежащей стороны СВ тре­угольника. Теперь вычислим значение фун­кции в точке А'. Из трех точек А', В, С выберем ту, в которой функция мак­симальна, и опять найдем ее «зеркальное изображение» относительно противолежа­щей стороны. Если после некоторого числа таких шагов функция перестанет уменьшаться, то следует уменьшить, например, в два раза сторону треугольника и продолжить процесс от вершины с наименьшим значением целевой функции. Процесс можно закончить, когда размеры треугольника станут настолько малыми, что все три его вершины можно будет считать неразличимыми.

Если минимизируемая функция имеет «овражные» особенности, то описанный алгоритм неэффек­тивен, так как не реагирует на «топографические» особенности исследуемой функции. Нелдер и Мид усовершенствовали рас­сматриваемый алгоритм. Основная идея усовершенствования состоит в деформации треугольника в зависимости от особен­ностей функции. Те стороны треугольника, которые ориен­тированы преимущественно вдоль «оврага», растягиваются, а те, которые ориентированы «поперек», - сжимаются. Это позволяет повысить быстродействие алгоритма [10].

Задание.

Найти методом Нелдера-Мида экстремум заданной функции.