Лекция: МЕТОД СОПРЯЖЕННЫХ НАПРАВЛЕНИЙ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

<Api, pj> = 0, i ¹j, i,j = 1, …, k. (3.42)

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

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

<Ap2,p1>=<A(x1-y1), p1>=<f ¢(x1) — f ¢(y1), p1> = < f ¢(x1), p1> — <f ¢(y1), p1>.

Так как точки х1 и у1 получены в результате исчерпывающего спуска по направлению р1, то оба скалярных произведения < f ¢(x1), p1> и <f ¢(y1), p1> равны нулю (см. (3.34)), поэтому <Ap2, p1> = 0.

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

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

, (3.43)

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

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

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

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

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

xk = xk-1 + ak pk, k=1, 2, …, (3.44)

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

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

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

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

. (3.46)

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

.

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

< f ¢(x0), рk > + ak <Aрk, рk> = 0.

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

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

Согласно лемме 3.1 векторы р1 ,…, рn образуют базис в En, поэтому будем искать точку минимума х* в виде

, (3.47)

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

Ax0+ b + .

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

< f ¢(x0), рk > + uk <Aрk, рk> = 0.

или

.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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