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

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

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

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

Методы Пауэла, Флетчера-Ривса, Девидона-Флетчера-Пауэла

43. Методы случайного поиска.

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

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

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

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

Алгоритм с возвратом при неудачном шаге

1. Задать начальный шаг h⁰, число проб s  n и точность .

2. Сгенерировать или задать начальную точку X⁰ и вычислить в ней функцию f; положить i=1 (i – счетчик проб).

3. Сгенерировать случайный вектор направления  .

4. На направлении определить точку X^k+1 = X^k + h^k^k и вычислить в ней функцию f.

5. П роверить: а) если f(X^k+1)<f(X^k), положить k=k+1, i=1 и вернуться на 3; б) если f(X^k+1)f(X^k) и i<s, положить i= i+1 и вернуться на 3; в) если f(X^k+1)f(X^k), i=s и h^k >, положить h^k= h^k/2, i=1 и вернуться на 3. г) если f(X^k+1)f(X^k), i=s и h^k, поиск закончить, приняв X^k за точку минимума.

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