Основы теории оптимизации (стр. 72 )

где λ[j] - величина шага итерации по каждому из параметров хi;

si[j] - параметр выбора “направления”, который обычно определяется по итерационной формуле.

Данная формула обеспечивает сходимость исследуемой функции к некоторому решению при j→∞. Величина шага λ[j] на каждой j-й итерации определяется одним из методов оптимизации однопараметрической оптимизации, например методом деления отрезка пополам или методом “золотого сечения” или Фибоначчи.

Наискорейший подъем с использованием одномерного поиска

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

    ,  (6)

где λ- величина шага, значение которого определяются в направлении градиента.

Получив одномерный оптимум в направлении данного градиента, находят новый градиент и повторяют процесс до тех пор, пока следующие вычисления позволяют улучшать полученный результат. Главное преимущество этого метода заключается в том, что параметр λ можно использовать в качестве независимой переменной для поиска по методу Фибоначчи, и это обеспечивает высокую эффективность метода. Другое важное преимущество методов, которые рассматриваются, заключается в том, что они позволяют отходить от седловин точек поверхности, которая описывается целевой функцией (рис. 1).

 

Рис. 1. Бимодальная целевая функция

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

Алгоритм наискорейшего спуска

Данный алгоритм основан на использовании итерационной формулы

,

где

,

причем все производные вычисляются при λі =хі [j];

λ[j] - величина шага, значение которого изменяется (уменьшается или вычисляется) методом половинного деления.

Алгоритм метода наискорейшего спуска:

1. Выбираем начальные значения координат вектора

и начальные значения шага итерационного процесса λ, которые обычно выбираются из условий решаемой конкретной задачи. Хотя общих правил выбора нет, однако если есть дополнительная информация об области расположения минимума целевой функции, то выбираем в этой области.

2. Задаем номер итерации k = 1.

3. Вычисляем значение целевой функции в точке с координатами .

4. Вычисляем значение градиента si.

5. Вычисляем норму вектора градиента NG.

6. Если |NG| < заданной ε, то итерационный процесс заканчивается и оптимум найден.

7. Если условие |NG| < ε не выполняется, то определяются новые координаты вектора , которые получаются при движении к минимуму целевой функции с шагом λ (рис. 2).

8. Сравниваем два значения целевой функции в двух точках с координатами векторов и по формуле

   f()<f(),  (7)

Рис. 2. Последовательность движения к минимуму с заданным шагом λ.

9. Если условие не выполняется, то шаг был выбран неверно, т. е. с этим шагом перескочили через оптимум и шаг нужно уменьшить, например, в два раза λ=1/2 и переходим к пункту 7 (рис. 2).

10. Если условие (7) выполняется, то запоминаем координаты вектора и переходим к пункту 4.

Схема алгоритма описанного метода представлена на рис. 3.

  Рис. 3. Схема алгоритма метода наискорейшего спуска

6.8.3. Метод Флетчера – Ривса

Этот метод позволяет найти минимум нелинейной целевой функции многих переменных вида

при отсутствии ограничений. Метод основан на применении частных производных целевой функции по независимым переменным и переопределен для исследования унимодальних функций. С его помощью можно исследовать и мультимодальные функции, однако в этом случае следует брать несколько входных точек и проверять, одинаково или во всех случаях решение. Схема алгоритма метода Флетчера - Ривса представленная на рис.4.

 

  Рис. 4. Схема алгоритма метода Флетчера - Ривса

Выполняется он следующим образом. Вначале выбирается подходящая начальная точка пространства проектирования и путем вычисления компонент вектора градиента определяется направление наискорейшего спуска. Индекс k=1 соответствует входной точке. После этого в направлении наискорейшего спуска ведется одномерный поиск по формуле

, і = 1, 2, ..., N,

, і = 1, 2, ..., N,

где λ – смещение в направлении вектора градиента. Найдя минимум в этом направлении, определяют направления новых единичных векторов, которые несколько отличаются от направления нового вектора градиента и представляют собой линейные комбинации вектора градиента на данном шаге и вектора градиента, полученного на предыдущем шаге. Новые компоненты единичных векторов записываются в виде

  , і = 1, 2, ..., N,  (8)

где

  .  (9)

Индекс k указывает на последовательность вычислений в процессе итераций. Новые направления называются «сопряженными» и соответствуют текущей локальной квадратичной аппроксимации функции, а фактически представляют собой движение по дну оврага (рис. 5).

Рис. 5. Изменение направлений движения по дну оврага

После этого по новому направлению (другому склону оврага) проводят одномерный поиск и, найдя минимум, проверяют, достигнута ли необходимая степень сходимости. Если проверка показывает, что это так, то счет прекращается. В противном случае определяют новые сопряженные направления, k увеличивают на единицу и продолжают процесс до тех пор, пока не будет обеспечена сходимость или пока поиск не будет проведен по всему N +1 направлениям. Закончив цикл поиска по N +1 направлениям, начинают новый цикл, в котором опять используется направление наискорейшего спуска. Особенность этого алгоритма заключается в том, что он позволяет использовать преимущества градиентных методов, которые проявляются при исследовании целевой функции с прерывистыми производными. Так как N+1 направлений поиска второй совокупности отличаются от направлений единичных векторов градиента, то поиск не «зависает на перегибе», а идет вдоль линии, которая соединяет точки перегибов линии уровня, которая, как правило, проходит через точку оптимума. Вообще можно утверждать, что методы, основанные на определении новых направлений поиска на основе накопленных данных о локальном поведении функции, по самой своей природе более эффективны, чем методы, в которых направление поиска задается заранее. Именно поэтому метод Флетчера - Ривса обладает большими преимуществами по сравнению с методами наискорейшего спуска или подъема. Его недостаток заключается в том, что он является более сложным чем указанные методы, и требует разработки более сложных программ.

6.8.4. Метод Девидона – Флетчера – Пауэлла

Метод Девидона - Флетчера - Пауэлла представляет собой алгоритм оптимизации, приспособленный для отыскания безусловного минимума целевой функции, которая зависит от нескольких переменных и имеет вид

      (10)