В предыдущем методе задача минимизации функции без ограничений решалась методом наискорейшего спуска, который, однако, как и другие градиентные методы, медленно сходится в тех случаях, когда поверхности уровня функции f(х) сильно вытянуты. Этот факт известен в литературе как «эффект оврагов». Суть эффекта в том, что небольшие изменения одних переменных приводят к резкому изменению значений функции – эта группа переменных характеризует «склон оврага», а по остальным переменным, задающим направление «дна оврага», функция меняется незначительно. На рис. 2.8 изображены линии уровня «овражной» функции двух переменных. Для овражных функций траектория градиентного метода, как видно из рис. 2.8, характеризуется довольно быстрым спуском на «дно оврага», и затем медленным зигзагообразным движением в точку минимума. Например, для минимизации «овражной» функции
программе Minim потребовалось совершить более 100 итераций. Спуск начинался из точки (0.1; 0.1) с начальным шагом a = 1 и e = 0.000001. Такое число итераций очень велико, особенно если учесть, что минимум функции f(x1, х2) находится в точке (1, 1), т. е. совсем недалеко от начального приближения. Применение в таких случаях метода сопряженных градиентов позволяет существенно ускорить процедуру поиска минимума. Метод сопряженных градиентов обладает замечательным свойством: положительно определенная квадратичная форма п переменных минимизируется методом сопряженных градиентов не более чем за п шагов. Метод успешно применяется для минимизации и неквадратичных функций п переменных, так как в окрестности экстремума любая гладкая функция мало отличается от квадратичной. Конечно, в этом случае для достижения точного минимума потребуется бесконечное число шагов. Здесь для минимизации функции нескольких переменных принят вариант метода сопряженных градиентов, предложенный Флетчером и Ривсом. Опишем алгоритм Флетчера—Ривса [10].
1. Вычисляем S0 = - grad f(x0) в точке x0.
2. На k-м шаге (k = 1, 2, ...) решаем задачу минимизации по а функции f(xk+aSk), в результате чего определяем величину шага ak и точку хk+1=хk+akSk.
3. Вычисляем величины f(xk+1) и grad f(xk+1).
4. Если ||grad f(xk+1)|| < e, то точка xk+1 – решение задачи, в противном случае определяем коэффициент bk по формуле
Здесь I – множество индексов I = {0, п, 2п, Зп, ...}. Значения k, для которых bk = 0, называют моментами обновления метода. Таким образом, обновление метода происходит через каждые n шагов.
5. Вычисляем Sk+1 no формуле
При обновлении процесс повторяют с п. 1, в противном случае – с п. 2.
Задание.
Написать программу минимизации и минимизировать заданную целевую функцию.
Порядок выполнения лабораторной работы.
1. Выбрать значение начального приближения для x.
2. Составить подпрограмму вычисления grad f(x).
3. Написать программу минимизации целевой.
4. Провести вычисления.
Таблица 2.9
Варианты заданий.
Вар. | f(x, y) | Вар. | f(x, y) |
1 |
| 16 |
|
2 |
| 17 |
|
3 |
| 18 |
|
4 |
| 19 |
|
5 |
| 20 |
|
6 |
| 21 |
|
7 |
| 22 |
|
8 |
| 23 |
|
9 |
| 24 |
|
10 |
| 25 |
|
11 |
| 26 |
|
12 |
| 27 |
|
13 |
| 28 |
|
Продолжение табл. 2.9 | |||
Вар. | f(x, y) | Вар. | f(x, y) |
14 |
| 29 |
|
15 |
| 30 |
|
2.7.3. Минимизация функции методом Нелдера-Мида.
В лабораторных предыдущих работах описаны градиентные методы отыскания локального минимума функции нескольких переменных. В настоящей работе рассматривается один из методов минимизации, в котором в отличие от методов градиентного спуска не требуется вычислять градиент целевой функции [10].
Методы минимизации, не требующие вычисления производных, называются методами поиска [10].
Как правило, при решении задач нелинейного программирования без ограничений градиентные методы сходятся быстрее, чем методы поиска. Однако встречаются задачи, в которых вычисление частных производных сопряжено с некоторыми трудностями (например, очень громоздкие аналитические выражения для частных производных или невозможность получить их в явном виде). Правда, точные значения частных производных можно заменить их разностными аппроксимациями, но такие методы, как правило, «плохо работают» вблизи точки экстремума. Кроме того, может возникнуть необходимость минимизировать недифференцируемые или даже разрывные функции. Для решения подобных задач и применяются методы поиска.
В данной лабораторной работе для минимизации целевой функции используется метод Нелдера—Мида. Основу стратегии Нелдера—Мида проще всего понять на примере минимизации в двумерном случае.
Пусть требуется минимизировать функцию двух переменных f(x, у). В плоскости (х, у) выберем начальную точку (нулевое приближение) и построим равносторонний треугольник с вершиной в этой точке (рис. 2.9).
Рис. 2.9
Вычислим значения функции в вершинах А, В и С треугольника. Выберем точку с максимальным значением функции. Пусть, например, это точка А. Построим точку А', симметричную точке А относительно противолежащей стороны СВ треугольника. Теперь вычислим значение функции в точке А'. Из трех точек А', В, С выберем ту, в которой функция максимальна, и опять найдем ее «зеркальное изображение» относительно противолежащей стороны. Если после некоторого числа таких шагов функция перестанет уменьшаться, то следует уменьшить, например, в два раза сторону треугольника и продолжить процесс от вершины с наименьшим значением целевой функции. Процесс можно закончить, когда размеры треугольника станут настолько малыми, что все три его вершины можно будет считать неразличимыми.
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
Основные порталы (построено редакторами)