![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
В лабораторных предыдущих работах описаны градиентные методы отыскания локального минимума функции нескольких переменных. В настоящей работе рассматривается один из методов минимизации, в котором в отличие от методов градиентного спуска не требуется вычислять градиент целевой функции [10].
Методы минимизации, не требующие вычисления производных, называются методами поиска [10].
Как правило, при решении задач нелинейного программирования без ограничений градиентные методы сходятся быстрее, чем методы поиска. Однако встречаются задачи, в которых вычисление частных производных сопряжено с некоторыми трудностями (например, очень громоздкие аналитические выражения для частных производных или невозможность получить их в явном виде). Правда, точные значения частных производных можно заменить их разностными аппроксимациями, но такие методы, как правило, «плохо работают» вблизи точки экстремума. Кроме того, может возникнуть необходимость минимизировать недифференцируемые или даже разрывные функции. Для решения подобных задач и применяются методы поиска.
В данной лабораторной работе для минимизации целевой функции используется метод Нелдера—Мида. Основу стратегии Нелдера—Мида проще всего понять на примере минимизации в двумерном случае.
Пусть требуется минимизировать функцию двух переменных f(x, у). В плоскости (х, у) выберем начальную точку (нулевое приближение) и построим равносторонний треугольник с вершиной в этой точке (рис. 2.9).
Рис. 2.9
Вычислим значения функции в вершинах А, В и С треугольника. Выберем точку с максимальным значением функции. Пусть, например, это точка А. Построим точку А', симметричную точке А относительно противолежащей стороны СВ треугольника. Теперь вычислим значение функции в точке А'. Из трех точек А', В, С выберем ту, в которой функция максимальна, и опять найдем ее «зеркальное изображение» относительно противолежащей стороны. Если после некоторого числа таких шагов функция перестанет уменьшаться, то следует уменьшить, например, в два раза сторону треугольника и продолжить процесс от вершины с наименьшим значением целевой функции. Процесс можно закончить, когда размеры треугольника станут настолько малыми, что все три его вершины можно будет считать неразличимыми.
Если минимизируемая функция имеет «овражные» особенности, то описанный алгоритм неэффективен, так как не реагирует на «топографические» особенности исследуемой функции. Нелдер и Мид усовершенствовали рассматриваемый алгоритм. Основная идея усовершенствования состоит в деформации треугольника в зависимости от особенностей функции. Те стороны треугольника, которые ориентированы преимущественно вдоль «оврага», растягиваются, а те, которые ориентированы «поперек», - сжимаются. Это позволяет повысить быстродействие алгоритма [10].
Задание.
Найти методом Нелдера-Мида экстремум заданной функции.
Дата публикования: 2014-11-04; Прочитано: 1187 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!