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

<4 5 678 9 10 >

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

Напомним, что квадратические функции могут быть представлены
в виде

f(x) = (1/2)(Hx, x) + (b, x) + c, (2.2.1)

где H – квадратная n ´ n матрица; b Î E_n, x Î E_n – n-мерные векторы;
c – число. (Полезно отметить, что матрица H в (2.2.1) является матрицей Гессе для функции f(x)).

Предполагается положительная определенность матрицы Н. Для квадратической функции f(x) методом сопряженных направлений гарантированно находится решение задачи (2.1.1) за конечное число шагов. Однако с алгоритмической точки зрения этот метод реализуется как итерационный. Кроме того, он может быть использован с некоторыми модификациями и для минимизации неквадратических функций.

Введем понятие H-сопряженных векторов.

Определение 2.2.1

Векторы s⁽¹⁾ Î E_n и s⁽²⁾ Î E_n являются H-сопряженными (или H-ортогональными), где H – квадратная n´ n матрица, если выполнено условие (Hs⁽¹⁾, s⁽²⁾) = 0. (2.2.1)

Если H = I (где I – единичная n ´ n матрица), то понятие
H-сопряженности векторов (Hs⁽¹⁾, s⁽²⁾) = 0 эквивалентно ортогональности векторов s⁽¹⁾и s⁽²⁾. Отметим также, что общее число H-сопряженных векторов для неособенной n ´ n матрицы H равно n.

Квадратические функции (для случая двух переменных) обладают так называемым свойством "параллельного подпространства", суть которого заключается в следующем. Пусть даны две произвольные точки x⁽¹⁾ Î E₂ и x⁽²⁾ Î E₂ и квадратическая функция f(x) с положительно определенной матрицей Гессе. Выберем произвольное направление s⁽¹⁾ Î E₂ и найдем z⁽¹⁾ Î E₂ и z⁽²⁾ Î E₂, решив две одномерные оптимизационные задачи:

f(z⁽¹⁾) = f(x⁽¹⁾ + l₁s⁽¹⁾) = min f(x⁽¹⁾ + ls⁽¹⁾), (*)

l Î E₁

f(z⁽²⁾) = f(x⁽²⁾ + l₂s⁽²⁾) = min f(x⁽²⁾ + ls⁽²⁾). (**)

l Î E₁

Тогда направления s⁽¹⁾ и s⁽²⁾= z⁽²⁾ – z⁽¹⁾ будут H-сопряженными и одномерный поиск для f(x) из z⁽¹⁾ или z⁽²⁾ в направлении, задаваемом вектором
s⁽²⁾= z⁽²⁾ – z⁽¹⁾, дает искомый минимум исследуемой функции.

Термин "одномерный поиск" для f(x) из точки х в направлении s здесь и далее означает определение точки х^* и (или) числа l^* из решения одномерной оптимизационной задачи вида f(х^*) = f(x + l^*s) = min f(x + ls). l Î E₁

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

Пусть заданы квадратическая функция f(x), x Î E_n, две точки x⁽¹⁾ Î E_n и x⁽²⁾ Î E_n, а также известны m (m < n) попарно H-сопряженных направлений s⁽¹⁾, s⁽²⁾, s⁽³⁾, …, s⁽^m⁾, где H – матрица Гессе для функции f(x). Пусть точка z⁽¹⁾ найдена в результате последовательно проводившихся из точки x⁽¹⁾одномерных поисков вдоль каждого направления s⁽¹⁾, s⁽²⁾, s⁽³⁾, …, s⁽^m⁾, а точка z⁽²⁾ получена аналогичным образом из точки x⁽²⁾. Тогда направление z⁽²⁾ – z⁽¹⁾ будет H-сопряженным по отношению к каждому направлению s⁽¹⁾, s⁽²⁾, s⁽³⁾, …, s⁽^m⁾.

Теперь сформулируем метод сопряженных направлений для минимизации квадратической функции f(x), x Î E_n. Предположим, что матрица Гессе функции f(x) положительно определенная. Тогда метод можно записать в виде следующего алгоритма:

1. Начать с точки x⁽⁰⁾ = (x₁⁽⁰⁾, x₂⁽⁰⁾, …, x_n⁽⁰⁾)^т и n-линейно независимых направлений s⁽ⁱ⁾, i = 1, 2, …, n, которые могут быть выбраны, например, совпадающими с координатными направлениями e⁽ⁱ⁾, i = 1, 2, …, n. Положить k = 1.

2. Начиная с точки x⁽⁰⁾ осуществить одномерный поиск для функции f(x) в направлении s⁽ⁿ⁾ и определить точку z⁽¹⁾.

3. Начиная с точки z⁽¹⁾ осуществить последовательно n – 1 одномерный поиск для f(x) сначала в направлении s⁽¹⁾, а затем из полученной точки в направлении s⁽²⁾ и т. д. до одномерного поиска в направлении s^{(n – 1)} включительно. В результате этих действий будет определена точка x⁽²⁾.

4. Начиная с точки x⁽²⁾ осуществить одномерный поиск для f(x) в направлении s⁽ⁿ⁾ и определить точку z⁽²⁾.

Согласно обобщенному свойству "параллельного подпространства" направление s⁽ⁿ^{+ 1)} = z⁽²⁾ – z⁽¹⁾ будет сопряженным по отношению к направлениям s⁽ⁿ⁾, s⁽ⁿ^{– 1)}, …, s⁽ⁿ^–^k^{+ 1)} (для k = 1 – только к направлению s⁽ⁿ⁾).

5. Начиная с точки z⁽²⁾ осуществить поиск в направлении s⁽ⁿ^{+ 1)}
и определить x^*.

6. Положить k: = k + 1. Если k = n, перейти к выполнению п. 8.

7. Положить z⁽¹⁾: = x^* и s⁽ⁱ⁾: = s⁽ⁱ^{+ 1)}, i = 1, 2, …, n.и перейти к выполнению п. 2.

8. Процесс вычислений завершен: x^* – точка минимума функции f(x).

Отметим некоторые важные свойства метода сопряженных направлений:

1. Как следует из описания метода, он позволяет отыскать минимум квадратической функции f(x), x Î E_n с положительно определенной матрицей Гессе при решении конечного числа одномерных задач минимизации вида

min f(x + ls),

l Î E₁

а именно решения n² таких задач.

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

3. Если функция f(x) не является квадратической, то процесс вычислений после решения n² одномерных задач не завершается и его необходимо продолжать до выполнения того или иного критерия окончания процесса. При этом предусматриваются некоторые дополнительные правила, позволяющие гарантировать сходимость метода сопряженных направлений. Отметим также, что применительно к неквадратическим функциям этот метод при определенных предположениях сходится со сверхлинейной скоростью.