Метод сопряженных направлений
Метод сопряженных направлений относится к методам нулевого порядка и ориентирован прежде всего на минимизацию квадратических функций, так как использует специфические свойства последних.
Напомним, что квадратические функции могут быть представлены
в виде
f(x) = (1/2)(Hx, x) + (b, x) + c, (2.2.1)
где H – квадратная n ´ n матрица; b Î En, x Î En – n-мерные векторы;
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;