logo
ОИТ_Учебник

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

Этот метод использует свойство квадратичной функции, заключающееся в том, что любая прямая, которая проходит через точку минимума функции х*,пересекает под равными углами касательные к поверхностям равного уровня функции в точках пересечения (рис. 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шагов они окажутся взаимно сопряженными.