Основы теории оптимизации (стр. 44 )

1. Квазиньютоновские методы. Эти методы имеют общую структуру:

(1)

где матрица Нk пересчитывается рекуррентным способом на основе информации, полученной на k-й итерации, так что

.

Таким образом, методы в пределе пере­ходят в ньютоновский, что и объясняет их название. Отметим некоторые общие свойства методов такого типа. Доказатель­ство приводимых ниже лемм может быть без труда получено с использованием описанной ранее техники.

Лемма 1. Пусть дифференцируема, f(х)

удовлетворяет условию Липшица и

(2)

Тогда в методе (1) с γk≡γ, где γ > 0 достаточно мало, будет

Лемма 2. Пусть х*— невырожденная точка минимума f(x), f(x) дважды непрерывно дифференцируема в окрестности х* и

(3)

Тогда метод (1) с γk = 1 локально сходится к х* быстрее лю­бой геометрической прогрессии.

Таким образом, при любых равномерно положительно опре­деленных Hk метод (1) обладает глобальной сходимостью, а при условии (3) в окрестности минимума метод сходится со сверхлинейной скоростью.

Перейдем к вопросу о способах построения матриц Hk, ап­проксимирующих В принципе их можно формиро­вать с помощью конечно-разностной аппроксимации. Именно, из точки xk можно сделать п «пробных шагов» длины αk по ко­ординатным осям и вычислить в этих точках градиенты. Соответствующая разностная аппроксимация будет искомой, если .

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

(4)

Тогда для квадратичной фукции

имеем

(5)

Поэтому для нового приближения естественно потребовать выполнения так называемого квазиньюто-новского условия

(6)

Кроме того, удобно получать Hk+1 как поправку к Hk с по­мощью матриц первого или второго ранга. Наконец, эти по­правки должны быть такими, чтобы для квадратичного случая оказалось Нп = А-1.

Основным техническим инструментом анализа подобных ме­тодов является следующая лемма об обращении матриц.

Лемма 3. Пусть В — матрица п×п, для которой В-1 существует, a, b — векторы из Rп,

Тогда

(7)

Лемма доказывается прямой проверкой.

Таким образом, если известна матрица, обратная к В, a матрица А получена из В добавлением матрицы ранга 1, то обратная к А находится без труда.

Приведем примеры формул пересчета матриц Hk:

а) метод Давидона — Флетчера — Пауэлла (ДФП):

(8)

б) метод Бройдена:

(9)

в) метод Бройдена — Флетчера — Шенно (БФШ):

(10)

Оказывается, для всех формул (8) — (10) выполнено квази­ньютоновское условие (6). А если γk > 0 — произвольные числа, pk — произвольные, линейно независимые векторы, yk удовле­творяют соотношению (5) с А-1 > 0, то при любом Н0 > 0 бу­дет Нп = А-1. Отсюда следует

Теорема 1. При любых х0, Н0 > 0 метод (1), (4) с любой из формул пересчета (8), (9), (10) и γk = argmin f(xk+ γpk)

γ

для f(x) = (Ax, х)/2 — (b, х), А > 0, будет конечным: хп =х*= А-1b.

Более того, можно показать, что, несмотря на различие формул пересчета, последовательности xk, генерируемые каж­дым вариантом метода, для квадратичной функции f(x) сов­падают.

Для неквадратичных функций квазиньютоновские методы в записанной выше форме применимы, но они пере­стают быть конечными. В связи с этим при k > п можно либо продолжать счет по этим же формулам, либо ввести процедуру обновления (заменять матрицу Hk на H0 через каждые п ите­раций).

Доказана сверхлинейная (или квадратич­ная) скорость сходимости многих вариантов квазиньютоновских методов в окрестности невырожденной точки минимума.

Эти результаты выглядят естественными в свете утвержде­ний лемм 1 и 2 и теоремы 1, однако их полное доказательство весьма громоздко.

Квазиньютоновские методы чрезвычайно популярны, им по­священ огромное количество работ. Такое внимание объясняется упоминавшимися выше достоинствами методов — они требуют лишь одного вычисления градиента на каждом шаге, в них не нужно обращать матрицу или решать систему линейных уравнений, они обладают глобальной сходимостью, в окрестности решения скорость сходимости высока (часто квадратична) и т. п. Однако они имеют и дефекты по сравнению, например, с методом сопряженных градиентов. Главный из них заключается в необходимости хранить и пересчитывать матрицу Hk размер­ности п×п, что для больших п требует значительного объема памяти ЭВМ.

При численной проверке методов обычно наилучшие резульаты дает вариант (10).

2. Методы переменной метрики и методы сопряженных на­правлений. Выше квазиныотоновскне методы были получены как приближения к методу Ньютона. Однако на них можно посмотреть и с другой точки зрения.

Выясним прежде всего, как влияет выбор метрики на вид и свойства градиентного метода. Пусть в пространстве Rn наряду с исходным скалярным произведением (х, у) задано с помощью матрицы A > 0 другое скалярное произведение

(11)

В этом случае А задает новую метрику в Rn:

(12)

Выпишем градиент дифференцируемой функции f(x) в но­вой метрике:

В соответствии с определением вектор а есть градиент f(x) в пространстве со скалярным произведением (11). Итак,

(13)

В новой метрике градиентный метод приобретает вид

(14)

и отличается от исходного градиентного метода наличием ма­трицы А-1 Иными словами, градиентный метод не инвариантен к выбору метрики пространства. Естественно попытаться вы­брать метрику так, чтобы ускорить сходимость метода. Для ква­дратичной функции

(15)

скорость сходимости (14) определяется знаменателем прогрес­сии q — (L— l)/(L+l), где L, I — наибольшее и наименьшее собственные значения матрицы А-1В. Чем ближе эта матрица к единичной, тем меньше q. Наилучший способ — выбрать А = В, тогда А-1В = I, q = 0, т. е. если задать метрику с помощью матрицы В, то градиентный метод (с γk≡1) даст точное реше­ние за 1 шаг. Это не удивительно, так как в этой метрике т. е. линии уровня f(x) — сферы, а обусловленность μ равна единице.

Для неквадратичной функции метод

(16)

может рассматриваться как градиентный в метрике

(17)