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

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

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

Рассмотрим сначала проблему поиска точки минимума сильно выпуклой квадратичной функции двух переменных. Ее линиями уровня являются эллипсы (рис. 3.11). Пусть р¹ и р² — направления главных осей этих эллипсов (они могут быть найдены как ортонормированный базис из собственных векторов матрицы A квадратичной функции). Ес­ли из произвольной точки х⁰Î E ₂ выполнить итерационную процедуру х ^k = х + a _k р ^k, k = l, 2, где величина шага a _k находится из условия исчерпывающего спуска, то, очевидно, потребуется не более двух ша­гов для отыскания точки х^*.

Рис. 3.11. Минимазация строго выпуклой квадратичной функции двух переменных по направлениям главных осей методом наискорейшего спуска.

Такого же результата можно достичь и другим способом. Выберем некоторое направление р¹ и две точки х⁰ и у⁰ такие, чтобы векторы х⁰ - у⁰ и р¹ были неколлинеарны (рис. 3.12). Выполнив исчерпывающий спуск из точек х⁰ и у⁰ в направлении р¹, получим точки х¹ и у¹. По свойству исчерпывающего спуска в точках х¹ и у¹ имеет место касание соответствующих прямых (направлений убывания) и эллипсов (линий уровня целевой функции). Так как эллипсы различаются гомотетией с центром в точке х^*, то точки х^*, х¹ и у¹ расположены на одной пря­мой. Поэтому, полагая р² = х¹-у¹ и решая задачу f(х¹ + aр²) ® min, мы находим точку х^*. Таким образом, и в этом случае решение задачи ми­нимизации квадратичной сильно выпуклой функции будет получено за конечное число шагов.

Рис 3.12. Определение направления p² в процессе минимзации сильно выпуклой квадратичной функции двух переменных

Рассмотренному способу минимизации квадратичных функций двух переменных соответствует, например, такой алгоритм.

Шаг 0. Выбрать начальную точку х⁰ Î Е ₂.

Шаг 1. Положить р¹ =е¹. Найти точку х¹ с помощью исчерпывающего спуска из точки х⁰ по направлению р¹: f(х¹) = .

Шаг 2. а) положить у=х +с;

б) найти точку у из условия исчерпывающего спуска из точки у⁰ по направлению р¹: f(y¹) = ;

в) положить р² = х¹-у¹, найти точку x² из условия f(х²)= , вычисления закончить, положив х^*= x².

Графическая иллюстрация работы алгоритма представлена на рис. 3.13. Поиск точки минимума доводится по так называемым сопряженным направлениям.

Определение 3.8. Ненулевые векторы р¹,..,р ^k называются сопряженными относительно матрицы A размера (п´ п) (А-ортогональными), если

<Ap ⁱ, p ^j > = 0, i ¹ j, i, j = 1, …, k. (3.42)

Пример 3.8. Направления р¹ и р², использованные в описанном выше алгоритме минимизации квадратичной функции двух переменных, являются A-ортогонaльными.

Рассмотрим скалярное произведение

<Ap²,p¹>=<A(x¹-y¹), p¹>=<f ¢(x¹) - f ¢(y¹), p¹> = < f ¢(x¹), p¹> - <f ¢(y¹), p¹>.

Так как точки х¹ и у¹ получены в результате исчерпывающего спуска по направлению р¹, то оба скалярных произведения < f ¢(x¹), p¹> и <f ¢(y¹), p¹> равны нулю (см. (3.34)), поэтому <Ap², p¹> = 0.

Лемма 3.1. Система из п векторов р¹,.., р ⁿ, сопряженных относительно положительно определенной матрицы A, линейно незaвисимa.

Предположим противное, т.е. что существует линейная комби­нация, равная нулю:

, (3.43)

где не все g _i = 0, например g _k ¹ 0. Умножим обе части равенства (3.43) скалярно на вектор A р ^k. Тогда, с учетом свойства (3.42), полу­чим g _k < A р ^k, р ^k >=0. В силу положительной определенности матрицы A для ненулевого вектора р ^k квадратичная форма < A р ^k, р ^k > прини­мает положительное значение и, следовательно, g _k = 0. Полученное противоречие доказывает лемму.

Таким образом, п ненулевых A -ортогональных векторов образуют базис в E _n.

Рассмотрим минимизацию в E _n квадратичной функции

f(х) = 1/2< A х, х >+< b, х >+с

с положительно определенной матрицей A с помощью итерационного процесса

x ^k = x ^{k- 1} + a _k p ^k, k =1, 2, …, (3.44)

где векторы р ^k A -ортогональны.

Лемма 3.2. Если в итерационном процессе (3.44) нa кaждом шaге используется исчерпывaющий спуск, то величинa шaгa a_k будет

, k =1, 2, …, (3.45)

Раскрывая рекуррентную формулу (3.44), получаем

. (3.46)

Из формулы (3.46), учитывая выражение для градиента квадратичной функции f '(x) = A х + b, находим

.

(Умножая обе части этого равенства скалярно на вектор р ^k и учитывая условие исчерпывающего спуска по направлению р ^k (< f ¢(x ^k), р ^k > = 0) и A -ортогональность векторов (3.42), получаем

< f ¢(x⁰), р ^k > + a _k < A р ^k,р ^k > = 0.

Так как матрица A положительно определена, квадратичная форма < A р ^k,р ^k >>0 и для величины шага a _k получаем выражение (3.45).

Теорема 3.9. Последовaтельный исчерпывающий спуск по A-ортогонaльным нaпрaвлениям (3.44) приводит к точке минимумa квaдрaтичной функции не более чем зa п шaгов.

Согласно лемме 3.1 векторы р¹,..,р ⁿ образуют базис в E _n, поэтому будем искать точку минимума х^* в виде

, (3.47)

где х⁰ — произвольная точка E _n. Подставим выражение (3.47) в необходимое и достаточное условие минимума сильно выпуклой квадратной функции f '(х^*) = A х^* + b = 0:

A x⁰ + b + .

Умножая это равенство скалярно на вектор р ^k, находим

< f ¢(x⁰), р ^k > + u_k < A р ^k,р ^k > = 0.

или

.

Коэффициенты разложения u_k точки х ^*- х по базису р¹, совпадают с длинами шагов a _k исчерпывающего спуска (3,45) в итерационном процессе (3.44). Поэтому определение точки х^* из (3.47) можно рассматривать как результат п шагов итерационного процесса (3.44), где a _k = u_k.

Таким образом, точка минимума квадратичной функции будет найдена не более чем за п шагов.

Вопрос о нахождении базиса из A -ортогональных векторов в пространстве Е _n решается неоднозначно. В качестве такого базиса можно, например, взять ортогональный базис из собственных векторов матрицы A. Однако их поиск особенно при п > 2 представляет собой само­стоятельную довольно сложную задачу.

Итерационный процесс (3.44) последовательной одномерной ми­нимизации по сопряженным направлениям р ^k можно организовать и без предварительного построения векторов р¹,.., р ⁿ, последователь­но находя их в процессе минимизации, как это было сделано выше для функции двух переменных.

Опишем процедуру метода сопряженных направлений для мини­мизации функции п переменных, обобщающую приведенный выше ал­горитм для п = 2.

Шаг 0. Выбрать начальную точку х⁰ Î Е _n.

Шаг 1. Положить р¹=е¹ . Найти точку х¹ из условия f(х¹)= .

Шаг 2. а) положить у⁰ =х¹ + е²;

б) найти точку у¹ из условия f(у¹)= ;

в) положить р¹ = х¹ - у¹, найти точку х² из условия f(х²)= .

Шаг 3. а) положить у¹ = х² + е³;

б) найти у², минимизируя f (x) последовательно по направлениям р¹ и р², начиная из точки у¹;

в) положить р³ = х² - у² найти точку х³ из условия f(х³)= .

Шаг n. а) положить у ^{n- 1} = х ^{n -1} + е ⁿ;

б) найти точку у ⁿ, минимизируя f(х) последовательно по направ­лениям

р¹,.., р ^{n -1}, начиная из точки у ^{n- 1}.

в) положить р ⁿ = х ^{n -1} – у ^{n- 1}, найти точку х ⁿ из условия f(х ⁿ)= .

Замечание. Как и в двумерном случае, можно показать, что направления р¹,.., р ⁿ, построенные при выполнении этого алгоритма, являются A -ортогональными. Поэтому, если f(х) является квадратичной функцией с положительно определенной матрицей A и все задачи одномерной минимизации решаются точно, то х^* = х ⁿ и вычисления на этом завершаются. Если же f(х) не является квадратичной фунцией или вспомогательные задачи одномерной минимизации решаются приближенно, то необходимо перейти к следующему шагу.

Шаг n + 1. (проверка условия останова). Если ||x⁰-x ⁿ || £ e, где e - параметр точности, то поиск завершить, полагая х^* = х ⁿ, иначе — положить х⁰ = х ⁿ и перейти к шагу 1.

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