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

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

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

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

Рассмотрим сначала проблему поиска точки min-ма сильно выпуклой квадратичной функции двух переменных. Ее линиями уровня являются эллипсы.

Пусть pи p- направления главных осей эллипсов. Если из произвольной точки хЄЕвыполнить итерационную процедуру х=х+p, k=1,2, где величина шага - находится из условия исчерпывающего спуска, то, очевидно, потребуется не более двух шагов для отыскания х*.

Того же результата можно достичь и другим способом. Выберите некоторое направление pи две точки хи утакие, чтобы векторы х-уи pбыли неколлинеарны. Выполнив исчерпывающий спуск из точек хи ув направлении p, получив точки хи у.

По свойству исчерпывающего спуска в точках хи уимеет место касание соответствующих прямых (направлений убывания) и эллипсов (линий уровня целевой функции). Точки х*, хи урасположены на одной прямой.

Поэтому, полагая p=х-уи решая задачу f(х+p)→min, мы находим точку х*. Таким образом, и в этом случае решение задач min-ии квадратичной сильно выпуклой функции будет получено законченное число шагов.

Определение направления pв процессе min-ии сильно выпуклой квадратичной функции двух переменных:

Рассмотренному методу min-ии квадратичной функции двух переменных соответствует алгоритм:

ШАГ 0:

Выбрать начальную точку хЄЕ.

ШАГ1:

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

f(х)=minf(х+p)

ШАГ2:

а) положить у=х+ е;

б) найти точку уиз условия исчерпывающего спуска из точки упо направлению p:

f(у)=minf(у+p);

в) положить p=х-у, найти точку хиз условия f(х)=minf(х+p), вычисления закончить, положив х*=х

В данном алгоритме поиск точки min-ма проводится по так называемым сопряженным направлениям.

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

Ненулевые векторы p…pназывается сопряженным относительно матрицы А размера (n*n), если

<Аp, p>=0, i=j; I,j=1,…,k (2)

Лемма 1: Система из n векторов p…p, сопряженных относительной положительно определенной матрицы А, линейно независима (или назыв. А – ортогональными).

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

Рассмотрим min-ию в Еn квадратичной функции f(x)=<Ax,x>+<b,x>+c с положительно определенной матрицей А с помощью итерационного процесса

х=х+p, k=1,2… (3)

где векторы pА – ортогональны.

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

=-, k=1,2,… (4)

Теорема:

Последний исчерпывающий спуск по А-ортогональным направлениям (3) приводит к точке min-ма квадратичной функции не более чем за n-шагов.

Вопрос о нахождении базиса из А-ортогональных векторов в пространстве Еn решается неоднозначно. В качестве такого базиса можно взять ортогональный базис из собственных векторов матрицы А.

Однако поиск особенно при n>2 представляет собой самостоятельную довольно сложную задачу.

Итерационный процесс (1) можно организовать и без предварительного построения векторов p…p, последовательно находя их в процессе min-ии.

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

ШАГ 0:

Выбрать начальную точку хЄЕ.

ШАГ1:

Положить p=е. Найти точку хиз условия

f(х)=minf(х+p)

ШАГ2:

а) положить у=х+ е;

б) найти точку уиз условия:

f(у)=minf(х+p);

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

ШАГ3:

а) положить у=х+ е;

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

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

ШАГn:

а) положить у=х+е;

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

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

Замечание:

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

ШАГn+1 (проверка):

Если ||х-х||, где - параметр точности, то поиск завершить, полагая х*=х, иначе положить х=хи перейти к шагу 1.

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

Дата добавления: 2014-01-07