Теорема о сходимости метода покоординатного спуска.

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

Тогда спуск по координатам сходится к минимуму из данного начального приближения, причем линейно.

Все описанные до сих пор прямые методы 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(х )=min f(х + p )

ШАГ2:

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

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

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

в) положить p =х -у , найти точку х из условия f(х )=min f(х + 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(х )=min f(х + p )

ШАГ2:

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

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

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

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

ШАГ3:

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

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

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

ШАГn:

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

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

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

Замечание:

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

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

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

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