Сопряженные направления. 
Методы поиска минимума функции многих переменных

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

• (3.12)
• (где r есть n-мерный вектор) с симметричной положительно определенной матрицей, А процесс спуска сойдется точно к минимуму за конечное число шагов.

Положительно определенная матрица позволяет ввести норму вектора следующим образом:

(3.13).

Определение (3.13) означает, что под скалярным произведением двух векторов x и у теперь подразумевается величина (х, Ау). Векторы, ортогональные в смысле этого скалярного произведения.

(х, Ау) = 0 (3.14).

называют сопряженными (по отношению к данной матрице А).

На этом основана большая группа методов: сопряженных градиентов, сопряженных направлений, параллельных касательных и другие.

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

Сначала рассмотрим, как применяется этот метод к квадратичной форме (3.12). Для этого нам потребуются некоторые свойства сопряженных векторов.

Пусть имеется некоторая система попарно сопряженных векторов х_i. Нормируем каждый из этих векторов в смысле нормы (3.14), тогда соотношения между ними примут вид.

(3.15).

Докажем, что взаимно сопряженные векторы линейно-независимы. Из равенства.

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

Пусть нашли некоторый спряженный базис х_i, 1 in. Выберем произвольную точку r₀. Любое движение из этой точки можно разложить по сопряженному базису.

(3.16).

Подставляя это выражение в правую часть формулы (3.12), преобразуем ее с учетом сопряженности базиса (3.15) к следующему виду:

(3.17).

Последняя сумма состоит из членов, каждый из которых соответствует только одной компоненте суммы (3.16). Это означает, что движение по одному из сопряженных направлений х_i меняет только один член суммы (3.17), не затрагивая остальных.

Совершим из точки r₀поочередные спуски до минимума по каждому из сопряженных направлений x_i. Каждый спуск минимизирует свой член суммы (3.17), так что минимум квадратичной функции точно достигается после выполнения одного цикла спусков, то есть за конечное число действий.

Сопряженный базис можно построить способом параллельных касательных плоскостей.

Пусть некоторая прямая параллельна вектору х, а квадратичная функция достигает на этой прямой минимального значения в точке r₀. Подставим уравнение этой прямой r = r₀ + бx в выражение (3.12) и потребуем выполнения условия минимума функции ц (б) = Ф (r₀) + б² + б (x, 2Аr₀ + b),.

и положим (dц/dб)_б-0 = 0. Отсюда следует уравнение, которому удовлетворяет точка минимума:

(х, 2Аr₀ + b) = 0. (3.18).

Пусть на какой-нибудь другой прямой, параллельно первой, функция принимает минимальное значение в точке r₁;тогда аналогично найдем (х, 2Аr₁ + b) = 0. Вычитая это равенство из (3.18), получим.

(х, А (r₁r₀)) = 0. (3.19).

Следовательно, направление, соединяющее точки минимума на двух параллельных прямых, сопряжено направлению этих прямых.

Таким образом, всегда можно построить вектор, сопряженный произвольному заданному вектору х. Для этого достаточно провести две прямые, параллельные х, и найти на каждой прямой минимум квадратичной формы (3.12). Вектор r₁r₀, соединяющий эти минимумы, сопряжен х. Заметим, что прямая касается линии уровня в той точке, где функция на данной прямой принимает минимальное значение; с этим связано название способа.

Пусть имеются две параллельные m-мерные плоскости, порожденные системой сопряженных векторов х_i, 1 imn. Пусть квадратичная функция достигает своего минимального значения на этих плоскостях соответственно в точках r₀и r₁. Аналогичными рассуждениями можно доказать, что вектор r₁r₀, соединяющий точки минимума, сопряжен всем векторам х_i. Следовательно, если задана неполная система сопряженных векторов х_i, то этим способом всегда можно построить вектор r₁r₀, сопряженный всем векторам этой системы.

Рассмотрим один цикл процесса построения сопряженного базиса. Пусть уже построен базис, в котором последние m векторов взаимно сопряжены, а первые n-m векторов не сопряжены последним. Найдем минимум квадратичной функции (3.12) в какой-нибудь m-мерной плоскости, порожденной последними mвекторами базиса. Поскольку эти векторы взаимно сопряжены, то для этого достаточно произвольно выбрать точку r₀и сделать из нее спуск поочередно по каждому из этих направлений (до минимума). Точку минимума в этой плоскости обозначим через r₁.

Теперь из точки r₁сделаем поочередный спуск по первым n — m векторам базиса. Этот спуск выведет траекторию из первой плоскости и приведет ее в некоторую точку r₂. Из точки r₂ снова совершим по последним m направлениям спуск, который приведет в точку r₃. Этот спуск означает точное нахождение минимума во второй плоскости, параллельной первой плоскости. Следовательно, направление r₃ — r₁сопряжено последним m векторам базиса.

Если одно из несопряженных направлений в базисе заменить направлением r₃ — r₁, то в новом базисе уже m + 1 направление будет взаимно сопряжено.

Начнем расчет циклов с произвольного базиса; для него можно считать, что m=1. Описанный процесс за один цикл увеличивает на единицу число сопряженных векторов в базисе. Значит, за n — 1 цикл все векторы базиса станут сопряженными, и следующий цикл приведет траекторию в точку минимума квадратичной функции (3.12).

Хотя понятие сопряженного базиса определено только для квадратичной функции, описанный выше процесс построен так, что его можно формально применять для произвольной функции. Разумеется, что при этом находить минимум вдоль направления надо методом парабол, не используя нигде формул, связанных с конкретным видом квадратичной функции (3.12).

В малой окрестности минимума приращение достаточно гладкой функции обычно представило в виде симметричной положительно определенной квадратичной формы типа (3.2). Если бы это представление было точным, то метод сопряженных направлений сходился бы за конечное число шагов. Но представление приближенно, поэтому число шагов будет бесконечным; зато сходимость этого метода вблизи минимума будет квадратичной.

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

Метод сопряженных направлений является, по-видимому, наиболее эффективным методом спуска. Он неплохо работает и при вырожденном минимуме, и при разрешимых оврагах, и при наличии слабо наклонных участков рельефа — «плато», и при большом числе переменных — до двух десятков[2].