2015-04-01
434
| Векторы s (1) Î En и s (2) Î En являются H -сопряженными (или H -ортогональными), где H – квадратная n´ n матрица, если выполнено условие (Hs (1), s (2)) = 0. (2.2.1) |
Если H = I (где I – единичная n ´ n матрица), то понятие
H- сопряженности векторов (Hs (1), s (2)) = 0 эквивалентно ортогональности векторов s (1) и s (2). Отметим также, что общее число H- сопряженных векторов для неособенной n ´ n матрицы H равно n.
Квадратические функции (для случая двух переменных) обладают так называемым свойством "параллельного подпространства", суть которого заключается в следующем. Пусть даны две произвольные точки x (1) Î E2 и x (2) Î E2 и квадратическая функция f (x) с положительно определенной матрицей Гессе. Выберем произвольное направление s (1) Î E2 и найдем z (1) Î E2 и z (2) Î E2, решив две одномерные оптимизационные задачи:
f (z (1)) = f (x (1) + l1 s (1)) = min f (x (1) + l s (1)), (*)
l Î E 1
f (z (2)) = f (x (2) + l2 s (2)) = min f (x (2) + l s (2)). (**)
l Î E 1
Тогда направления s (1) и s (2)= z (2) – z (1) будут H- сопряженными и одномерный поиск для f (x) из z (1) или z (2) в направлении, задаваемом вектором
s (2)= z (2) – z (1), дает искомый минимум исследуемой функции.
|
|
|
| Термин "одномерный поиск" для f (x) из точки х в направлении s здесь и далее означает определение точки х * и (или) числа l* из решения одномерной оптимизационной задачи вида f (х *) = f(x + l* s) = min f (x + l s). l Î E 1 |
Для квадратических функций с тремя и более переменными имеет место обобщенное свойство "параллельного подпространства", которое можно сформулировать следующим образом.
| Пусть заданы квадратическая функция f (x), x Î En, две точки x (1) Î En и x (2) Î En, а также известны m (m < n) попарно H -сопряженных направлений s (1), s (2), s (3), …, s ( m ), где H – матрица Гессе для функции f (x). Пусть точка z (1) найдена в результате последовательно проводившихся из точки x (1) одномерных поисков вдоль каждого направления s (1), s (2), s (3), …, s ( m ), а точка z (2) получена аналогичным образом из точки x (2). Тогда направление z (2) – z (1) будет H -сопряженным по отношению к каждому направлению s (1), s (2), s (3), …, s ( m ). |
Теперь сформулируем метод сопряженных направлений для минимизации квадратической функции f (x), x Î En. Предположим, что матрица Гессе функции f(x) положительно определенная. Тогда метод можно записать в виде следующего алгоритма:
1. Начать с точки x (0) = (x 1(0), x 2(0), …, xn (0))т и n -линейно независимых направлений s (i), i = 1, 2, …, n, которые могут быть выбраны, например, совпадающими с координатными направлениями e (i), i = 1, 2, …, n. Положить k = 1.
2. Начиная с точки x (0) осуществить одномерный поиск для функции f (x) в направлении s (n) и определить точку z (1).
3. Начиная с точки z (1) осуществить последовательно n – 1 одномерный поиск для f (x) сначала в направлении s (1), а затем из полученной точки в направлении s (2) и т. д. до одномерного поиска в направлении s (n – 1) включительно. В результате этих действий будет определена точка x (2).
|
|
|
4. Начиная с точки x (2) осуществить одномерный поиск для f (x) в направлении s (n) и определить точку z (2).
Согласно обобщенному свойству "параллельного подпространства" направление s ( n + 1) = z (2) – z (1) будет сопряженным по отношению к направлениям s(n ), s ( n – 1), …, s ( n – k + 1) (для k = 1 – только к направлению s ( n )).
5. Начиная с точки z (2) осуществить поиск в направлении s ( n + 1)
и определить x *.
6. Положить k: = k + 1. Если k = n, перейти к выполнению п. 8.
7. Положить z (1): = x * и s ( i ): = s ( i + 1), i = 1, 2, …, n. и перейти к выполнению п. 2.
8. Процесс вычислений завершен: x * – точка минимума функции f (x).
Отметим некоторые важные свойства метода сопряженных направлений:
1. Как следует из описания метода, он позволяет отыскать минимум квадратической функции f (x), x Î En с положительно определенной матрицей Гессе при решении конечного числа одномерных задач минимизации вида
min f (x + l s),
l Î E 1
а именно решения n2 таких задач.
2. Для решения одномерных задач может быть использован любой из методов одномерной оптимизации, рассмотренных в гл. 1. При этом необходимо учитывать, что метод сопряженных направлений предъявляет высокие требования к точности проводимых одномерных поисков.
3. Если функция f (x) не является квадратической, то процесс вычислений после решения n2 одномерных задач не завершается и его необходимо продолжать до выполнения того или иного критерия окончания процесса. При этом предусматриваются некоторые дополнительные правила, позволяющие гарантировать сходимость метода сопряженных направлений. Отметим также, что применительно к неквадратическим функциям этот метод при определенных предположениях сходится со сверхлинейной скоростью.
