1.5.2 Метод Вольфа

Метод Вольфа [35] основывается на построении начального n+1 - мерного симплекса, расчета в вершинах симплекса значений целевой функции и градиента и вычисления новой вершины симплекса по квадратичной аппроксимации целевой функции. Алгоритм метода Вольфа следующий.

{{{ Начало алгоритма.

1) Относительно начальной точки X_init случайным образом определяются n+1 вершины симплекса в гиперкубе с ребром X_init. В вершинах этого симплекса вычисляются значения целевой функции и градиента: J(X_k), _xJ(X_k), k=1..n+1.

2) Решается относительно параметров _k следующая система линейных алгебраических уравнений n+1 порядка:

(1.5.2)

Определяется новая вершина симплекса

(1.5.3)

Среди всех старых вершин симплекса находится такая с номером j в которой значение целевой функции максимально, т.е.

J(X_j)>J(X_k), k=1..n+1. (1.5.4)

Если J(X_new)>J(X_j), то полагаем и переходим к пункту 1), иначе заменяем j-ю вершину на новую X_j=X_new и переходим к следующему пункту.

3) Если , то переходим к пункту 2), иначе поиск заканчивается.

}}} Конец алгоритма.

Для доказательства правомерности формулы (1.5.3), представим квадратичную целевую функцию в виде следующего ряда Тейлора относительно точки X_new, в которой мы предполагаем находится минимум целевой функции:

J(X_k)=J(X_new)+(X_k-X_new)^TG(X_k-X_new)/2. (1.5.5)

Градиент в точке X_k определяется как

_xJ(X_k)=G(X_k-X_new). (1.5.6)

Подставив (1.5.6) в (1.5.2) получим:

Считая, что G ненулевая матрица и учитывая соотношение (1.5.2), получаем искомую формулу (1.5.3), которая указывает на точку минимума квадратичной целевой функции.

Метод Вольфа хорошо сходится, как и метод Ньютона, на функциях близких к квадратичным, на не квадратичных функциях метод Вольфа неустойчив. Его можно, как и метод Ньютона, модифицировать, введя процедуру поиска минимума вдоль направления P=X_new-X_j в пункт 2) алгоритма метода Вольфа. Можно ожидать, что такое дополнение улучшит устойчивость метода Вольфа, как это наблюдается в методе Ньютона-Рафсона.

1.5.3 Методы с переменной метрикой

В методах с переменной метрикой заложена идея метода Ньютона, а именно в них итерационным способом находится матрица, обратная матрице вторых производных, т.е. G^-1 ~ H_k, где H_k - матрица порядка nn, которая носит название метрики. Поисковое направление определяется по формуле:

(1.5.7)

Методы поиска вдоль направлений, определяемых этой формулой, называются методами с переменной метрикой, поскольку матрица H_k изменяется на каждой итерации. С другой стороны методы с переменной метрикой представляют собой квази-ньютоновские методы, если в соответствии с ними перемещение текущей точки удовлетворяет условию, следующему из формул (1.1.6) и (1.4.3):

X=G^-1g (1.5.8)

Для аппроксимации матрицы, обратной матрице Гессе, воспользуемся следующим рекуррентным соотношением:

H_k+1=H_k+E_k, (1.5.9)

где E_k - корректирующая матрица.

Исходя из важного свойства квадратичной функции (1.5.8), можно потребовать, чтобы новое приближение H_k+1 удовлетворяло соотношению:

H_k+1y_k=s_k , (1.5.10)

где y_k=g_k+1-g_k, s_k=X_k+1-X_k.

Выражение (1.5.10) можно переписать в виде:

H_ky_k+E_ky_k=s_k. (1.5.11)

Решение уравнения (1.5.11) для корректирующей матрицы E_k является не однозначным и может иметь следующий вид:

Здесь v_k и w_k - произвольные вектора, т.е. формула (1.5.12) определяет некоторое семейство решений. Если положить

v_k=s_k и w_k =H_ky_k , (1.5.13)

то получим формулу, реализующую известный и широко применяемый метод Давидона-Флетчера-Пауэлла [16 ]:

(1.5.14)

Можно показать, что формула (1.5.14) сохраняет свойства симметрии и положительной определенности матрицы H_k. Поэтому, если H₀ - симметрическая и положительно определенная матрица, то матрицы H₁, H₂, ... также будут симметричными и положительно определенными при отсутствии ошибок округления; обычно полагают H₀=I, где I - единичная диагональная матрица.

Первая вариация J(X) равна

J(X)=g_k^TX.

Используя формулы (1.5.7) и (1.1.1), получим

J(X)=-_kg_k^TH_kg_k.

Из (1.5.16) видно, что неравенство J(X_k+1)<J(X_k) выполняется при

любых значениях _k>0 , если H_k - положительно определенная матрица. Таким образом, алгоритм обеспечивает убывание целевой функции при переходе от итерации к итерации.

В силу того, что существует определенный произвол в выборе векторов v и w в (1.5.12), то можно учесть какие-то дополнительные условия, улучшающие работу методов с переменной метрикой. Например, в методе Гольдфарба [19] накладывается дополнительное требование минимальности нормы корректирующей матрицы:

(1.5.17)

где Q_i={0,0,..,0,1_i,0,..,0}^T . Это приводит к повышению устойчивости метода к ошибкам вычислений значений целевой функции, градиента и минимума в поисковом направлении. Так практически на тестовых примерах и задачах оптимизации процессов в электронных приборах было установлено, что алгоритм Гольдфарба оказался существенно более устойчивым к ошибкам вычислений, чем алгоритм Давидона-Флетчера-Пауэлла. Корректирующая матрица алгоритма Гольдфарба рассчитывается по формуле:

(1.5.18)

В приложении 1 приведены основные алгоритмы расчета корректирующих матриц для наиболее известных методов с переменной метрикой.

Алгоритм методов с переменной метрикой следующий.

{{{ Начало алгоритма.

1 0....0)

1) Полагаем k=1, X_k=X_init,

Рассчитываем J(X_k), g_k=_xJ(X_k).

2) Определяем поисковое направление

P_k= - H_kg_k и находим минимум в этом направлении:

_k: min_(J(X_k+_kP_k )

Новое приближение вектора поисковых параметров находится как

X_k+1=X_k+_kP_k.

3) Если |_kP_k|<, то процесс оптимизации окончен, иначе переходим к следующему пункту.

4) Рассчитываем в новой точке J(X_k+1) и g_k+1.

Пересчитываем метрику H_k+1=H_k+E_k по одной из формул приложения 1, увеличиваем k на единицу k=k+1 и переходим опять к пункту 2).

}}} Конец алгоритма.

Работа метода с переменной метрикой показана на рис.1.5.2

Методы с переменной метрикой, как и ожидалось, хорошо себя показали на только на функциях близких к квадратичным, но и на сложных более высокого порядка функциях. Это можно объяснить тем, что в методах с переменной метрикой на каждой итерации находится очередное приближение обратной матрицы Гессе, которая дает квадратичную аппроксимацию целевой функции около текущей поисковой точки. В процессе оптимизации это приближение меняется в соответствии с изменением рельефа целевой функции, при этом рассчитываются только первые производные, что существенно проще и быстрее сделать, чем рассчитывать вторые производные, как в методе Ньютона. Пересчет матрицы H_k на каждой итерации приводит к адаптации метода к текущему рельефу целевой функции, что и позволяет ему успешно работать на функциях далеких от квадратичных. Как показали тестовые испытания методы с переменной метрикой оказались более быстродействующими даже по сравнению с методом Ньютона-Рафсона при численном расчете производных.

Рис.1.5.2

Поиск минимума методом с переменной метрикой

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

Следует отметить также, что методы с переменной метрикой позволяют получить, как побочный результат, квадратичную аппроксимацию целевой функции вблизи точки минимума:

J(X)=J(X_min)+g^T(X_min)(X-X_min)+(X-X_min)^TG(X-X_min)/2. (1.5.19)