Методы сопряженных направлений

Как и метод Ньютона, методы сопряженных направлений основаны на свойствах квадратичных функций. В связи с этим говорят о сопряженных направлениях относительно квадратичной функции. Пусть дана матрица Н n´n. Направления d1, d2,..., dk (k £ n) называются сопряженными или Н-сопряженными, если они линейно независимы и .

Эти векторы определяют сопряженные направления. Для квадратичной функции двух переменных сопряженные направления получаются следующим образом. Возьмем произвольное направление d ₁ и на нем найдем минимум, двигаясь из точки X¹. Повторим поиск минимума на d ₁ из точки X²¹ X¹ . Направление d ₂, определяемое прямой, проходящей через найденные минимумы, является сопряженным с направлением d ₁. При этом направление d ₂ проходит через искомый минимум функции f. Следовательно, при любой начальной точке минимум квадратичной функции двух переменных достигается за два одномерных поиска вдоль сопряженных направлений.

Пример: Используя сопряженные направления, найти минимум функции (точка минимума X^*=(2,4)). Запишем матрицу Гессе . Возьмем . . Пусть а = 1, получаем

b = 2 и . Возьмем начальную точку X⁰=(-1;1). Найдем минимум на направлении d ₁. Для этого подставим в функцию X = X⁰+ h d ₁, то есть x ₁= x ₁⁰+ h = -1+ h, x ₂= x ₂⁰=1. Тогда f = h ²-3 h -3 и минимум по h будет при h ^*=1,5. Следовательно, минимум на d ₁ достигается в точке X¹=(0,5;1). Приняв ее за начальную для поиска вдоль d ₂ и подставляя в функцию x ₁= 0,5+ h, x ₂=1+2 h, получаем f = 3 h ²-9 h -5,25. Находим h ^*=1,5 и соответствующую новую точку X²=(2;4). Как видим, второй одномерный поиск привел в точку искомого минимума f.

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

Методы, основанные на концепции сопряженных направлений, различаются способами построения таких направлений.

Методы Пауэла, Флетчера-Ривса, Девидона-Флетчера-Пауэла
43. Методы случайного поиска.

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

Случайный механизм выбора направления реализуется с помощью датчика случайных чисел b, равномерно распределенных на интервале [- b, b ]. Направление задается случайным вектором X = (x ₁, x ₂, x ₃,..., x _n), компоненты которого вычисляются по формуле:

,где n случайных чисел b_i генерируются датчиком. Такой случайный вектор имеет единичную длину и определяет только направление. При этом все направления равновероятны.

Приведем несколько простых алгоритмов случайного поиска.