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

и «оптимальным» выбором метрики является Иными словами, квазиньютоновские методы могут трактоваться как градиентные, в которых на каждом шаге выбирается новая метрика, по возможности близкая к наилучшей. В связи с этим часто употребляют термин методы переменной метрики как си­ноним квазиныотоновских методов.

Такая интерпретация полезна и как эвристический способ построения новых вариантов квазиньотоновских методов. На­пример, можно получить новую метрику путем «растяжения» пространства в направлении последнего градиента или в на­правлении разности двух последовательных градиентов и т. п. Мы остановимся на таких методах подробнее в последующих разделах.

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

(18)

можно найти минимум квадратичной функции за п одномерных минимизаций:

(19)

Тогда при любом х0 будет хп = х* = A-1b. Один способ построе­ния сопряженных направлений использовался в методе сопря­женных градиентов — в нем процессу А-ортогонализации под­вергались последовательно вычисляемые градиенты. Однако возможны и другие способы.

Пусть —уже построенные сопряженные

векторы,

(20)

a xk — соответствующие им точки в методе (19). Следующий вектор pk+1 должен удовлетворять соотношению

Поскольку

то это эквивалентно условию

(pk+1, yi)=0, i=1,…, k. (21)

Итак, новое сопряженное направление pk+1должно удовлетво­рять условиям ортогональности (21). Подвергая такому про­цессу ортогонализации любой набор линейно независимых век­торов, получим различные наборы сопряженных направлений. Этот же процесс может быть применен к неквадратичной функции:

(22)

Обычно при этом ищут pk+1 в виде

(23)

и вместо непосредственного запоминания векторов уi, i= 1, ..., k, запоминают матрицу Нk. Таким образом, методы прини­мают ту же форму (1), что и квазиньютоновские. Разница лишь в том, что при этом не обязательно Нk→[2f(xk)]-1; в некото­рых вариантах метода оказывается (для квадратичной функ­ции) Нп=0. Поэтому в таких методах обязательно должно осуществляться обновление.

Выпишем алгоритм одного из простейших методов данного

класса:

(24)

Оказывается, что для квадратичной функции в методе (24) рk являются сопряженными направлениями, Hk ≥ 0 для всех k ≤ п, Нп = 0. Для неквадратичных функций доказана квадра­тичная локальная сходимость методов данного класса в окрест­ности невырожденного минимума.

3. Метод секущих. Одним из простейших и наиболее распро­страненных методов решения одномерного уравнения

g(x) = 0 (25)

является метод секущих, сущность которого видна из рис. 1.

Рис. 1. Метод секущих

Его можно обобщить на многомерный случай — если g: Rn→Rn, то можно вычислить g в п+1 точках, построить линейную ап­проксимацию и найти ее корень, который является очередным приближением к решению (25).

Применительно к задаче минимизации f(x) в Rn, т. е. к за­даче решения уравнения f(x) = 0, метод принимает следую­щий вид. Пусть xk, xk-1x.....xk-n — n+ 1 точек в Rn, f(xk),......, f(xk-n) — вычисленные в них градиенты. Решим систему п+1 линейных уравнений с п+1 переменными λ0, λ1 ,…, λп:

(26)

и построим точку

(27)

Далее процесс повторяется для п + 1 последних точек xk+1, xk, ..., xk-n+1 и т. д. Нетрудно проверить, что для п— 1 такой метод совпадает с методом секущих для решения уравнения f(x) = 0.

Теорема 2. Если векторы х1 — х0, х2 — х0, ..., хп — х0 линейно незави­симы, a f(x) квадратична с 2f(x)≡А > 0, то хп+1 — точка минимума f(x).

В системе линейных уравнений (26) на каждой итерации меняется лишь один столбец, поэтому нет необ­ходимости решать ее каждый раз за­ново, а можно воспользоваться сле­дующим результатом.

Лемма 4. Пусть В — квадратная матрица n × п со столбцами b1,..., bп, а В отличается от нее первым столбцом (b1 заменено на ). Тогда

(28)

где сi — строки В-1,1 — строки .

Для доказательства достаточно представить в виде = + (— b1)ет, где е = (1, 0, ..., 0), и воспользоваться лем­мой 3.

Однако в описанной выше форме метод секущих не является удовлетворительным. Так, он не обладает свойством глобальной сходимости. Для устранения этого недостатка можно применять стандартные средства, например регулировку длины шага (из xk делается шаг по направлению ). Вторым дефектом

метода является его склонность к вырождению — в процессе счета последовательные приближения оказываются лежащими (приближенно) в подпространстве пространства Rn. Соответ­ствующая система линейных уравнений (26) плохо обусловлена и ее решение неустойчиво. Для преодоления этого недостатка можно модифицировать метод с тем, чтобы система базисных точек была заведомо невырожденной. Например, можно до­бавлять на каждой итерации точку, делая шаг по координат­ным осям (в циклическом порядке). Для модифицирован­ных подобным образом методов можно доказать сверхлинейную сходимость.

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

В связи с этим целесообразно использовать другие модели функции, отличные от квадратичной. На первый взгляд есте­ственно попытаться строить полиномиальные модели на основе старших производных — следующих членов ряда Тейлора. Такие попытки делались, однако они вряд ли перспективны. Во-пер­вых, прямое вычисление старших производных в многомерных задачах обычно требует слишком громоздких вычислений и большого объема памяти, а их восстановление по младшим производным предполагает вычисление последних в огромном числе точек. Во-вторых, решение вспомогательных задач мини­мизации полиномиальных функций, за редкими исключениями, не может быть осуществлено в аналитической форме.

Простой и важный класс представляют модели, основанные на аппроксимации функции однородной. Функция f(x), x Rn, называется однородной относительно точки х* с показателем γ > 0, если