Метод параллельных касательных (метод Пауэлла)

Этот метод использует свойство квадратичной функции, заключающееся в том, что любая прямая, которая проходит через точку минимума функции х*, пересекает под равными углами касательные к поверхностям равного уровня функции в точках пересечения (рис. 7.7).

Этот метод использует свойство квадратичной функции, заключающееся в том, что любая прямая, которая проходит через точку минимума функции х*, пересекает под равными углами касательные к поверхностям равного уровня функции в точках пересечения (рис. 7.7).

Рис. 7.7 ‑ Геометрическая интерпретация метода Пауэлла

Суть метода такова. Выбирается некоторая начальная точка х[0] и выполняется одномерный поиск вдоль произвольного направления, приводящий в точку х[1] . Затем выбирается точка х[2], не лежащая на прямой х[0] - х[1], и осуществляется одномерный поиск вдоль прямой, параллельной х[0] - х[1],. Полученная в результате точка х[3] вместе с точкой х[1] определяет направление x[1] ‑ х[3] одномерного поиска, дающее точку минимума х^*. В случае квадратичной функции n переменных оптимальное значение находится за п итераций. Поиск минимума при этом в конечном счете осуществляется во взаимно сопряженных направлениях. В случае неквадратичной целевой функции направления поиска оказываются сопряженными относительно матрицы Гессе. Алгоритм метода параллельных касательных состоит в следующем.

1. Задаются начальной точкой x[0]. За начальные направления поиска р[1], ..., р[0] принимают направления осей координат, т. е. р [i] = е[i], i = 1, ..., n (здесь e[i]= (0, ..., 0, 1, 0, … 0)^T).

2. Выполняют n одномерных поисков вдоль ортогональных направлений р[i] , i = 1, ..., п. При этом каждый следующий поиск производится из точки минимума, полученной на предыдущем шаге. Величина шага а_k находится из условия

f(x[k] + а_kр[k]) = f(x[k] + ар[k]).

Полученный шаг определяет точку

х[k+1] = х[k] + а_kр[k] .

3. Выбирают новое направление p =‑x[n] ‑ х[0] и заменяют направления р[1], ..., р[n] на р[2], ..., р [n], р. Последним присваивают обозначения р[1], ..., р[n]

4. Осуществляют одномерный поиск вдоль направления р = р[n] = х[n] - х[0]. Заменяют х[0] на х[n+1] = х[n] + а_nр[п] и принимают эту точку за начальную точку х[0] для следующей итерации. Переходят к п. 1.

Таким образом, в результате выполнения рассмотренной процедуры осуществляется поочередная замена принятых вначале направлений поиска. В итоге после n шагов они окажутся взаимно сопряженными.