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


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

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

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

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

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

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

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

Векторы 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) + l1s(1)) = min f(x(1) + ls(1)), (*)

l Î E1

f(z(2)) = f(x(2) + l2s(2)) = min f(x(2) + ls(2)). (**)

l Î E1

Тогда направления 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 + ls). l Î E1

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

Пусть заданы квадратическая функция 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) = (x1(0), x2(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 + ls),

l Î E1

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

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

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



Дата добавления: 2021-07-22; просмотров: 548;


Поиск по сайту:

Воспользовавшись поиском можно найти нужную информацию на сайте.

Поделитесь с друзьями:

Считаете данную информацию полезной, тогда расскажите друзьям в соц. сетях.
Poznayka.org - Познайка.Орг - 2016-2024 год. Материал предоставляется для ознакомительных и учебных целей.
Генерация страницы за: 0.009 сек.