Пусть решается задача J (х) → min, х ∈ R n, J ∈ (C 2(R n) с овражным… функционалом. Основной процедурой при реализации рассматриваемого далее класса методов обобщенного покоординатного спуска (ОПС) является процедура диагонализации матрицы J "(x) с последующим циклическим покоординатным спуском вдоль собственных векторов. Целесообразность такого подхода вытекает из геометрически очевидного факта, заключающегося в том, что оси наиболее рациональной системы координат при минимизации квадратичных функционалов (независимо от их выпуклости) методом покоординатного спуска совпадают с собственными векторами матрицы вторых производных, являющихся осями симметрии соответствующих поверхностей уровня. Эта идея неоднократно высказывалась в литературе, и даже строились соответствующие алгоритмы. Однако численные эксперименты показали низкую эффективность такого подхода. Существует и объяснение этих неудовлетворительных результатов. Оно основано на том, что при определении собственных векторов, соответствующих близким или кратным собственным значениям, возникают принципиальные вычислительные трудности. Аналогичные трудности, связанные с ограниченной точностью задания исходной информации, а также последующих вычислений, наблюдаются и при диагонализации плохо обусловленных матриц, имеющих относительно малые по модулю спектральные составляющие. Указанные обстоятельства, по-видимому, явились основным сдерживающим фактором, не позволившим внедрить изучаемые далее методы в вычислительную практику. Однако из дальнейшего изложения следует, что неудачи при численном экспериментировании были вызваны, по-видимому, особенностями реализации метода, рассчитанной на случай выпуклых функционалов. Как показано далее, для целей оптимизации, как в выпуклой ситуации, так и в невыпуклой, достаточно вычислить произвольный ортонормированный базис в инвариантном подпространстве, отвечающем каждой изолированной группе собственных значений. При этом собственные векторы могут быть вычислены со значительными погрешностями.
|
|
Отвечающие этим базисам линейные оболочки с высокой точностью совпадают с истинными подпространствами, определяемыми невозмущенной диагонализируемой матрицей.
Этот вывод в известной степени подтверждаются следующей теоремой.
Теорема 4.1. Пусть А — симметричная матрица п × п; { и i } — ортонормированные собственные векторы; λ i — собственные значения. Тогда при λ i ≠ λ j с точностью до величин второго порядка малости имеем
где dA — возмущение матрицы А; du i — соответствующее возмущение вектора ui.
|
|
Изложенное позволяет в качестве модели программ, реализующих различные методы диагонализации матрицы A, использовать оператор Λ(A), ставящий в соответствие произвольной симметричной матрице А ортогональную матрицу V, отличную, вообще говоря, от истинной матрицы U, состоящей из собственных векторов матрицы А. Оператор Л характеризуется тем, что если спектр матрицы А разделяется на р групп
«близких» между собой собственных чисел, то каждой группе соответствует набор столбцов { v it } матрицы V, задающий точное линейное многообразие, порожденное соответствующими столбцами { u i } точной матрицы U.
Рассмотрим квадратичную аппроксимацию
исходного функционала J (х) в окрестности точки х ∈ Q. Допустим, что известны матрица А и ортогональная матрица U, приводящая ее к диагональному виду U T AU = diag λ i. Тогда замена переменных х = Uy приводит квадратичный функционал к сепарабельному виду
где f i — квадратичные функции одной переменной (параболы). Таким образом достигается полная локальная декомпозиция исходной задачи, и последняя сводится к п независимым экстремальным задачам. В результате поиск оптимального вектора у * может осуществляться покомпонентно, так как связь между аргументами у i фактически исчезает. В указанной идеализированной ситуации явление заклинивания метода покоординатного спуска невозможно, и все вычислительные проблемы при применении покоординатных стратегий поиска оптимума, связанные с большими значениями η, формально снимаются.
В действительности бывает задана не матрица A, а возмущенная матрица А + dA, где dA отражает как неопределенность задания исходной матрицы A, так и последующие ошибки округления при проведении собственно процесса диагонализации. В связи с этим вместо точной матрицы U оказывается доступной некоторая матрица V = Λ(A). Замена переменных х = Vy уже не приводит к представлению (4.3). Для изучения создавшейся ситуации важное значение имеет следующая теорема.
Теорема 4.2. Пусть собственные значения { λ i } и отвечающие им ортонормированные собственные векторы { ui }, i ∈ [1: п ] некоторой симметричной матрицы А разделены произвольным образом на р групп так, что означают j -e собственное число и соответствующий собственный вектор группы t. Тогда, если в каждом линейном многообразии М t размерности с базисом задать иной ортонормированный базис связанный с исходным базисом линейным соотношением
то существует такая матрица Р перестановок столбцов, что:
1) преобразование подобия приводит матрицу А к блочно-диагональному виду с квадратными матрицами At на главной диагонали;
2) собственные значения матрицы At есть
Теорема 4.3. Пусть V= Λ(A), тогда
1) замена переменных x=Vy с точностью до нумерации компонентов вектора у приводит функционалах) (4.2) к блочно-сепарабельному виду
где
2) собственные значения матрицы равны
Следствие. Пусть собственные числа матрицы А удовлетворяют неравенствам λ1 ≥ … ≥ λ n – r >>| λ n – r + 1 | ≥ … ≥ | λ n |, тогда
1) замена переменных х = Vy, V = Λ(A), где V = (v 11,..., v 1 n – r, v 21,..., v 2 r)T;
с точностью до нумерации компонентов вектора у приводит f (x) к виду
fs (у) = f 1(y 1) + f 2(y 2), y = (y 1, у 2), (4.5)
где у 1= (у 1, ..., y п – r), у 2= (y п – r + 1, ..., y п);
2) η1<< η, η2<< η, где η i — показатели овражности задач fi → min, i = 1, 2.
Таким образом, исходная оптимизационная задача локально может быть сведена к двум эквивалентным задачам с существенно меньшими числами η i. Представление (4.5) реализует принцип частичной локальной декомпозиции и является аналогом идеализированного соотношения (4.3).
Если собственные числа матрицы квадратичного функционала разделяются более чем на две группы, то будет справедливо представление (4.5), содержащее соответствующее число слагаемых.
|
|
Согласно (4.5), появляется возможность независимого решения не связанных между собой оптимизационных задач для функционалов fi с невысокими показателями овражности.
Полученные результаты носят локальный характер и справедливы в рамках квадратичной аппроксимации исходного функционала J (х). Для неквадратичных функционалов приближенное выполнение соотношений типа (4.5) позволяет говорить о существенном ослаблении связей между различными группами переменных, что определяет достаточно высокую эффективность покоординатного спуска и в общем случае.