Метод Ньютона

ВВЕДЕНИЕ

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

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

Реальные прикладные задачи оптимизации очень сложны. Современные методы оптимизации далеко не всегда справляются с решением реальных задач без помощи человека. Нет, пока такой теории, которая учла бы любые особенности функций, описывающих постановку задачи. Следует отдавать предпочтение таким методам, которыми проще управлять в процессе решения задачи.

1. ЗАДАЧА БЕЗУСЛОВНОЙ ОПТИМИЗАЦИИ

Итак, мы будем рассматривать задачу безусловной оптимизации

f (x)min, (1)

где f: RmR. Точка x* Rm называется решением задачи (1) (или точкой глобального безусловного минимума функции f), если

f (x*) f (x) (2)

при всех x Rm. Если неравенство (2) выполнено лишь для x, лежащих в некоторой окрестности Vx* точки x*, то точка x* называется локальным решением задачи (1), или точкой локального безусловного минимума функции f. Если неравенство (2) строгое при всех x x*, то говорят о строгом глобальном и, соответственно, строгом локальном минимумах. Решение задачи (1) иногда обозначают argmin f (x) (или, более полно, argmin Rm f (x); когда речь идет о задачах безусловной оптимизации в обозначениях argminx Rm f (x) и minx Rm f (x) мы будем всегда опускать индекс «x Rm»). Обычно из контекста ясно о каком минимуме (локальном, глобальном и т. д.) идет речь.

Аналогичные понятия (максимумов) определяются для задачи

f (x) max.

2. ГРАДИЕНТНЫЕ МЕТОДЫ

2.1 Общие соображения и определения Градиентные методы оптимизации относятся к численным методам поискового типа. Они универсальны, хорошо приспособлены для работы с современными цифровыми вычислительными машинами и в большинстве случаев весьма эффективны при поиске экстремального значения нелинейных функций с ограничениями и без них, а также тогда, когда аналитический вид функции вообще неизвестен. Вследствие этого градиентные, или поисковые, методы широко применяются на практике. Сущность указанных методов заключается в определении значений независимых переменных, дающих наибольшие изменения целевой функции. Обычно для этого двигаются вдоль градиента, ортогонального к контурной поверхности в данной точке. Различные поисковые методы в основном отличаются один от другого способом определения направления движения к оптимуму, размером шага и продолжительностью поиска вдоль найденного направления, критериями окончания поиска, простотой алгоритмизации и применимостью для различных ЭВМ. Техника поиска экстремума основана на расчетах, которые позволяют определить направление наиболее быстрого изменения оптимизируемого критерия.

Наиболее распространенные и эффективные методы приближенного решения задачи безусловной оптимизации

f (x) min, (1)

где f: Rm R, укладываются в следующую грубую схему. Начиная с некоторого x0 Rm, строится последовательность {xn} Rm такая, что

f (xn+1) < f (xn) (2)

при всех n N. Такие последовательности иногда называют релаксационными, а методы построения релаксационных последовательностей — итерационными методами или методами спуска. Последовательность, удовлетворяющую (2), строят в надежде, что уменьшая на каждом шаге (переходе от xn к xn+1) значение функции, мы приближаемся к минимуму (по крайней мере, локальному).

Мы будем говорить, что метод, начиная с данного x0 Rm,

а) условно сходится, если последовательность {xn} релаксационна и

f (xn) при n;

б) сходится, если

xn x* = argmin f (x) при n;

в) линейно сходится (или сходится со скоростью геометрической прогрессии, или имеет первый порядок сходимости), если при некоторых C > 0 и q [0, 1)

||xn? x*|| Cqn; (3)

г) сверхлинейно сходится, если для любого q (0, 1) и некоторого (зависящего от q) C выполнено неравенство (3);

д) квадратично сходится (или имеет второй порядок сходимости), если при некоторых C > 0 и q [0, 1) и всех n? N

||xn? x*|| Cq2n.

Если эти свойства выполняются только для x0 достаточно близких к x*, то как всегда добавляется эпитет «локально» .

2.2 Эвристические соображения, приводящие к градиентным методам Выше уже отмечалось, что если x не является точкой локального минимума функции f, то двигаясь из x в направлении, противоположном градиенту (еще говорят, в направлении антиградиента), мы можем локально уменьшить значение функции. Этот факт позволяет надеяться, что последовательность {xn}, рекуррентно определяемая формулой

xn+1 = xn? f (xn), (4)

где — некоторое положительное число, будет релаксационной.

К этой же формуле приводит и следующее рассуждение. Пусть у нас есть некоторое приближение xn. Заменим в шаре B (xn, ?) с центром в точке xn функцию fее линейным (вернее, афинным) приближением:

f (x) (x) f (xn) + (f (xn), x? xn)

(функция аппроксимирует f в окрестности точки xn с точностью o (x — xn)). Разумеется, (линейная) безусловная задача (x) min неразрешима, еслиf (xn) (см. задачу 1.3). В окрестности же B (xn,) функция имеет точку минимума. Эту точку естественно взять за следующее приближение xn+1.

2.3 Градиентный метод с постоянным шагом В общем случае число в формуле (4) может на каждом шаге (т. е. для каждого n) выбираться заново:

xn+1 = xn? nf (xn). (5)

Именно методы, задаваемые формулой (5), называются градентными. Если n = при всех n, то получающийся метод называется градиентным методом с постоянным шагом (с шагом.)

Поясним геометрическую суть градиентного метода. Для этого мы выберем способ изображения функции с помощью линий уровня. Линией уровня функции f (изолинией) называется любое множество вида {x Rm: f (x) = c}. Каждому значению c отвечает своя линия уровня (см. рис.).

Рис.

Геометрическая интерпретация градиентного метода с постоянным шагом изображена на рис. На каждом шаге мы сдвигаемся по вектору антиградиента, «уменьшенному в раз» .

Рис.

2.4 Один пример исследования сходимости Изучим сходимость градиентного метода с постоянным шагом на примере функции

f (x) = |x|p,

где p > 1 (случай p 1 мы не рассматриваем, поскольку тогда функция f не будет гладкой, а мы такой случай не исследуем). Очевидно, задача (1) с такой функцией f имеет единственное решение x* = 0. Для этой функции приближения xn градиентного метода имеют вид:

xn+1 = xn ?|xn|p?1sign xn. (6)

Пределом этой последовательности может быть только 0. Действительно, если x** = limn xn 0, то, переходя к пределу в (6) при n, получаем противоречащее предположению x** 0 равенство

x** = x** ?p|x**|p?1sign x**

откуда x** = 0. Очевидно также, что если x0 = 0, то и xn = 0 при всех n.

Покажем, что если p < 2, то при любом шаге > 0 и любом начальном приближении x0 (за исключением не более чем счетного числа точек) приближения (6)не являются сходящимися. Для этого заметим, что если 0 < |xn| < (2/p)½(2?p), то

|xn+1| > |xn|. (7)

Поэтому, если xn не обращается в нуль, то она не может сходиться к нулю и, следовательно, не может сходиться вообще.

Таким образом, осталось доказать (7). В силу (6)

|xn+1| = |xn ?p|xn|p?1 · sign xn| = |xn|· | 1 p|xn|p?2· sign xn|.

Остается заметить, что если 0 < |xn| < (2/p)1/(2?p), то, как нетрудно видеть, |1? |xn|p?2· sign xn| > 1, что и требовалось.

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

2.5 Теорема об условной сходимости градиентного метода с постоянным шагом Пусть в задаче (1) функция f ограничена снизу, непрерывно дифференцируема и, более того, f удовлетворяет условию Липшица:

||f (x)? f (y)|| ||x? y|| при всех x, y Rm.

Тогда при (0, 2/) градиентный метод с постоянным шагом условно сходится.

Доказательство.

Положим zn = ?f (xn) и обозначим f (xn + tzn) через (t). Тогда, как легко видеть,

(t) = (f (xn + tzn), zn)

и поэтому по формуле Ньютона — Лейбница для функции

f (xn+1)? f (xn) = f (xn + zn)? f (xn) = (1) ?(0) =1 0(s) ds = 1(f (xn+ szn), zn) ds.

Добавив и отняв (f (xn), zn) = 01(f (xn), zn) dsи воспользовавшись неравенством (x, y) ||x|| · ||y||, получим

f (xn+1)? f (xn) = (f (xn), zn) +1 0 (f (xn + szn)? f (xn), zn) ds

(f (xn), ?f (xn)) + 1||f (xn + szn)? f (xn)|| · ||zn|| ds.

Учитывая условие Липшица для f ?, эту цепочку можно продолжить:

f (xn+1)? f (xn) ||f (xn)||2 + ||zn||2 0s ds =||f (xn)||2 +2 2||f (xn)||2 = ?||f (xn)||2

Поскольку 1 /2 > 0, последовательность {f (xn)} не возрастает и, следовательно, релаксационность {xn} доказана. А так как в силу условий теоремы f еще и ограничена снизу, последовательность {f (xn)} сходится. Поэтому, в частности, f (xn+1)? f (xn) 0 при n. Отсюда и из (8) получаем

||f (xn)||2 ?1 1 — 2 -1 [f (xn)? f (xn+1)] 0 при n

2.6 Замечания о сходимости Подчеркнем, что теорема 3.5 не гарантирует сходимости метода, но лишь его условную сходимость, причем, локальную. Например, для функции f (x) =(1 + x2)?1 на R последовательность {xn} градиентного метода с постоянным шагом, начинающаяся с произвольного x0 стремится к.

Поскольку в теореме 3.5 градиент непрерывен, любая предельная точка последовательности {xn} является стационарной. Однако эта точка вовсе не обязана быть точкой минимума, даже локального. Например, рассмотрим для функции f (x) = x2sign x градиентный метод с шагом (0, ½). Тогда, как легко видеть, если x0 > 0, то xn 0 при n. Точка же x = 0 не является локальным минимумом функции f.

Заметим также, что описанный метод не различает точек локального и глобального минимумов. Поэтому для того, чтобы сделать заключение о сходимости xnк точке x* = argmin f (x) приходится налагать дополнительные ограничения, гарантирующие, в частности, существование и единственность решения задачи (1). Один вариант таких ограничений описывается ниже.

2.7 Теорема о линейной сходимости градиентного метода с постоянным шагом Пусть выполнены условия теоремы 3.5 и, кроме того, f дважды непрерывно дифференцируема и сильно выпукла с константой. Тогда при (0, 2/)градиентный метод с шагом? сходится со скоростью геометрической прогрессии со знаменателем q = max1 ?:

||xn? x*|| qn||x0? x*||.

Доказательство.

Решение x* = argmin f (x) существует и единственно в силу теорем 2.9 и 2.10. Для функции F (x) = f (x) воспользуемся аналогом формулы Ньютона — Лейбница

F (y) = F (x) + 1 0 °F [x + s (y? x)](y? x) ds,

или, для x = x* и y = xn, учитывая, что f (x*) = Q,

f (xn) = 1 0 f [x* + s (xn? x*)](xn? x*) ds

(здесь мы, как и выше, воспользовались задачей 2.3). Далее, в силу утверждения (2.5) из п. 2.3 f (x) при всех x Rm. Кроме того по условию f (x) при тех же x. Поэтому, так как

||h||2 (f [x* + s (xn ?x*)]h, h) ||h||2

выполнено неравенство

||h||2 1 f [x* + s (xn ?x*)] ds h, h ||h||2

Интеграл, стоящий в этом неравенстве, определяет линейный (симметричный в силу симметричности f) оператор на Rm, обозначим его Ln. Неравенство (10)означает, что Ln В силу (9) градиентный метод (4) записывается в виде

xn+1 = xn? Ln (xn? x*)

Но тогда ||xn+1? xn|| = ||xn ?x* Ln (xn? x*)|| = ||(I ?Ln)(xn? x*)|| ||I ?Ln|| ||xn? x*||.

Спектр (I ?Ln) оператора I? Ln состоит из чисел вида i = 1? i

где i (Ln). В силу (10) и неравенства (2.3)

и следовательно ||I? Ln|| max1? = q.

Таким образом, ||xn+1? xn|| q||xn? x*||.

2.8 Об оптимальном выборе шага Константа q, фигурирующая в теореме 2.7 и характеризующая скорость сходимости метода, зависит от шага ?. Нетрудно видеть, что величина

q = q () = max1 ?

минимальна, если шаг выбирается из условия |1 ?| = |1? | (см. рис. 7), т. е. если = * = 2/(+). При таком выборе шага оценка сходимости будет наилучшей и будет характеризоваться величиной q = q*

квадратичный градиентный линейный шаг Рис.

Напомним, что в качестве и могут выступать равномерные по x оценки сверху и снизу собственных значений оператора f (x). Если <<, тоq* 1 и метод сходится очень медленно. Геометрически случай << соответствует функциям с сильно вытянутыми линиями уровня (см. рис. 8). Простейшим примером такой функции может служить функция на R2, задаваемая формулой

f (x1, x2) = x21+ x22с <<

Рис.

Поведение итераций градиентного метода для этой функции изображено на рис. 8 — они, быстро спустившись на «дно оврага», затем медленно «зигзагообразно» приближаются к точке минимума. Число = / (характеризующее, грубо говоря, разброс собственных значений оператора f (x)) называютчислом обусловленности функции f. Если >> 1, то функции называют плохо обусловленными или овражными. Для таких функций градиентный метод сходится медленно.

Но даже для хорошо обусловленных функций проблема выбора шага нетривиальна в силу отсутствия априорной информации о минимизируемой функции. Если шаг выбирается малым (чтобы гарантировать сходимость), то метод сходится медленно. Увеличение же шага (с целью ускорения сходимости) может привести к расходимости метода. Мы опишем сейчас два алгоритма автоматического выбора шага, позволяющие частично обойти указанные трудности.

2.9 Градиентный метод с дроблением шага В этом варианте градиентного метода величина шага n на каждой итерации выбирается из условия выполнения неравенства

f (xn+1) = f (xn ?nf (xn)) f (xn) ?n||f (xn)||2

где (0, 1) — некоторая заранее выбранная константа.

Условие (11) гарантирует (если, конечно, такие n удастся найти), что получающаяся последовательность будет релаксационной. Процедуру нахождения такого n обычно оформляют так. Выбирается число (0, 1) и некоторый начальныйшаг 0. Теперь для каждого n полагают n = 0 и делают шаг градиентного метода. Если с таким n условие (11) выполняется, то переходят к следующему n. Если же (11) не выполняется, то умножают n на («дробят шаг») и повторяют эту процедуру до тех пор пока неравенство (9) не будет выполняться. В условиях теоремы 3.5 эта процедура для каждого n за конечное число шагов приводит к нужному n.

Можно показать, что в условиях теоремы 3.7 градиентный метод с дроблением шага линейно сходится. Описанный алгоритм избавляет нас от проблемы выбора на каждом шаге, заменяя ее на проблему выбора параметров, и 0, к которым градиентный метод менее чувствителен.

При этом, разумеется, объем вычислений возрастает (в связи с необходимостью процедуры дробления шага), впрочем, не очень сильно, поскольку в большинстве задач основные вычислительные затраты ложатся на вычисление градиента.

2.10 Метод наискорейшего спуска Этот вариант градиентного метода основывается на выборе шага из следующего соображения. Из точки xn будем двигаться в направлении антиградиента до тех пор пока не достигнем минимума функции f на этом направлении, т. е. на луче L = {x Rm: x = xn? f (xn); 0}:

n = argmin [0,)f (xn ?f (xn))

Рис.

Другими словами, n выбирается так, чтобы следующая итерация была точкой минимума функции f на луче L. Такой вариант градиентного метода называется методом наискорейшего спуска. Заметим, кстати, что в этом методе направления соседних шагов ортогональны. В самом деле, поскольку функция: f (xn ?f (xn)) достигает минимума при = n, точка n является стационарной точкой функции:

0 = (n) =d d f (xn ?f (xn)) = n = (f (xn nf (xn)), ?f (xn)) = ?(f (xn+1), f (xn)).

Метод наискорейшего спуска требует решения на каждом шаге задачи одномерной оптимизации (12). Такие задачи будут обсуждаться ниже. Практика показывает, что этот метод часто требует меньшего числа операций, чем градиентный метод с постоянным шагом.

В общей ситуации, тем не менее, теоретическая скорость сходимости метода наискорейшего спуска не выше скорости сходимости градиентного метода с постоянным (оптимальным) шагом.

3. МЕТОД НЬЮТОНА

3.1 Эвристические соображения, приводящие к методу Ньютона безусловной оптимизации Если исходить из того, что необходимым этапом нахождения решения задачи

f (x) min

где f: Rm R, является этап нахождения стационарных точек, т. е. точек, удовлетворяющих уравнению

F (x) f (x) = Q

(обозначение F для f? мы будем сохранять на протяжении всего параграфа), то можно попытаться решать уравнение (2) известным методом Ньютона решения нелинейных уравнений

xn+1 = xn? [F (xn)]?1F (xn)

Для задачи (1) этот метод называется методом Ньютона безусловной оптимизации и задается формулой

xn+1 = xn? [f (xn)]?1f (xn)

Формула (3) может быть выведена, исходя из следующих соображений. Пусть xn — некоторое приближенное решение уравнения (2). Тогда если заменить функцию F в уравнении (2) ее линейным приближением

F (x) (x) F (xn) + F (xn)(x? xn)

и взять в качестве следующего приближения решение уравнения то мы получим формулу (3).

Применительно к задаче (1) эти соображения выглядят так. Пусть так же, как и в п. 3.2 у нас уже есть некоторое приближенное решение xn задачи (1). Заменим в ней функцию f ее приближением второго порядка:

f (x) (x) f (xn) + (f (xn), x? xn) +1 2 (f (xn)(x? xn), x? xn)

и в качестве следующего приближения возьмем решение задачи

(x) min

Геометрическая интерпретация формул (3) и (4) приведена на рис. 10а и 10б.

Рис.

Метод Ньютона относится к методам второго порядка, поскольку для вычисления каждой итерации требуется знание второй производной функции f. По тем же соображениям градиентный метод относят к методам первого порядка. Подчеркнем, что здесь речь идет не о порядке сходимости метода, а о порядке используемых методом производных минимизируемой функции.

3.2. Теорема о локальной сверхлинейной сходимости метода Ньютона Пусть f дважды непрерывно дифференцируема, а x* — невырожденная стационарная точка. Тогда найдется окрестность Vx* точки x* такая, что приближения (4), начатые из произвольной начальной точки x0? Vx*, сверхлинейно сходятся к x*.

Доказательство.

Очевидно, F = f C1 и поэтому

Lim x x* ||F (x)? F (x*)|| = 0.

Поскольку F (x*) невырожден, в силу (7) при x достаточно близких к x* невырожден и оператор F ?(x) и более того,

Lim x x* ||[F ?(x)]?1? [F ?(x*)]?1|| = 0.

Поэтому, в частности, при x достаточно близких к x*

||[F (x)]?1|| C

Далее, в силу того, что F дифференцируема, а x* — стационарная точка,

F (x) = F (x*) + F (x*)(x? x*) + o (x — x*) = F ?(x*)(x? x*) + o (x — x*),

Но тогда в силу

x ?x* [F (x)]?1F (x) = [F (x)]?1 °F (x)(x? x*)? [F (x)]?1F (x) = [F (x)]?1[F (x)(x? x*) ?F (x)] = o (x? x*).

или

x? [F (x)]?1F (x)? x* = o (x? x*).

В частности, при x = xn

xn+1 x* = xn [F (xn)]?1F (xn) x* (xn x*) = o (xn x*)

Возьмем теперь в качестве Vx*, например, окрестность. В силу (9), очевидно, если x0 Vx*, то

||xn+1? x*|| 1

2||xn? x*|| … 1

2n+1 ||x0? x*||

и, следовательно, xn x* при n. Более того, для произвольного q (0, 1) найдется > 0 такое, что ||(x? x*)|| q||x? x*|| при ||x? x*||. Но тогда, если||xn? x*||, то ||xn+1? x*|| q||xn? x*||. Из последнего утверждения очевидным образом вытекает нужное соотношение ||xn? x*|| Cqn.

3.3 Обсуждение метода Ньютона Таким образом, метод Ньютона, с одной стороны, может сходиться с более высоким чем градиентный метод порядком, а, с другой стороны, для его сходимости требуются достаточно хорошие начальные приближения (по крайней мере так требуется в доказанной теореме).

Простой геометрический пример (см. рис.) подтверждает эту особенность метода (мы приводим пример для уравнения (2); соответствующий пример для задачи (1) получается «интегрированием»).

Рис.

Разумеется, как метод второго порядка, метод Ньютона требует большего объема вычислительной работы, поскольку приходится вычислять вторые производные функции f.

К этому сводятся основные преимущества (высокий порядок сходимости) и недостатки (локальный характер сходимости и больший объем вычислений) метода Ньютона.

Если функция f дополнительно сильно выпукла, то можно утверждать сходимость именно к решению задачи (1), а не только к стационарной точке функции f, и, кроме того, оценить радиус окрестности, из которой приближения Ньютона сходятся.

3.4 Теорема о квадратичной сходимости метода Ньютона Пусть f C2 и, более того, f удовлетворяет условию Липшица с константой L. Пусть f сильно выпукла с константой. Пусть Vx* — окрестность решения задачи (1), состоящая из точек x Rm таких, что

||f (x)|| <2 2 L

Тогда для x0 Vx* метод Ньютона квадратично сходится:

||xn? x*|| 2

L q2n,

где q = L||f (x0)||/2 2 < 1.

Доказательство.

По теореме 2.9 и 2.10 в условиях нашей теоремы решение x* задачи (1) существует и единственно. Воспользуемся аналогом формулыНьютона — Лейбница для функции f:

f (xn + h)? f ?(xn) = 1 0f (xn + sh) h ds

Вычитая из обеих частей этого равенства f (xn)h = 01f (xn)h dsи учитывая, что f удовлетворяет условию Липшица, получаем (ср.).

||f (xn + h) ?f (xn)? f (xn)h|| 1 0 [f (xn + sh) ?f (xn)]h ds

1 0 ||f (xn + sh)? f (xn)|| · || h|| ds 1 0

Ls||h||2ds =L

||h||2.

Положим в полученной оценке h = ?[f (xn)]?1f (xn):

||f (xn + h) f (xn) + f (xn)[f (xn)]?1f (xn)|| = || f (xn+1)|| L

||[f (xn)]?1f (xn)||2 L

||[f (xn)]?1||2· ||f (xn)||2.

Поскольку f сильно выпукла, f (xn) и поэтому (см. пред. задачу) ||[f (xn)]?1|| 1. Продолжая неравенство (10), получаем

||f (xn+1)|| L

||f (xn)||2.

С помощью (11) индукцией по n легко доказывается неравенство

||f (xn)|| L

2 2 2n?1||f (x0)||2n =2

||f (x0)||

2n =2 2

L q2n.

Наконец, в силу сильной выпуклости f, так как x* — решение задачи (1) и, следовательно, f (x*) = Q,

0 f (x*)? f (xn) (f (xn), x*? xn) + ||xn? x*|| 2,

или

(f (xn), xn? x*) || xn? x*|| 2.

Но тогда

||xn x*|| 2 (f (x*), xn? x*) ||f (x*)|| · ||xn? x*||,

откуда ||f (x*)|| || xn? x*||

Тогда из (12) следует нужное неравенство.

3.5 Продолжение обсуждения метода Ньютона Из доказанной теоремы следует, что чем меньше константа Липшица отображения x f (x), т. е. чем ближе это отображение к константе, и, следовательно, чем ближе функция f к квадратичной, тем быстрее сходится метод Ньютона. В частности, если f квадратична: f (x) = (Ax, x)/2 + (b, x) + c, то метод Ньютона конечен, а именно, сходится за один шаг, причем из любой начальной точки.

Если снизить требования гладкости на функцию f, например, отказаться от условия Липшица для f, то скорость сходимости, вообще говоря, падает.

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

3.6 Методы Ньютона с регулировкой шага Эти методы еще называют методами Ньютона — Рафсона, или демпфированными методами Ньютона. Они строятся по аналогии с градиентными методами с переменным шагом. Общий вид их таков

xn+1 = xn? n[f (xn)]?1f (xn)

Длина шага может выбираться с помощью алгоритма дробления шага (см. п. 2.9), требуя, например, выполнения неравенства

f (xn+1) = f (xn n[f xn)]?1f (xn)) f (xn) ?n (f (xn), [f (xn)]?1f (xn))

или, как в методе наискорейшего спуска полагая

n = argmin0{f (xn ?[f (xn)]?1f (xn))}

Можно показать, что методы Ньютона — Рафсона для сильно выпуклых функций глобально квадратично сходятся (по крайней мере для описанных выше алгоритмов выбора шага), причем вдали от точки минимума они сходятся линейно.

3.7 Метод Левенберга — Маркардта Этот метод основан на следующей идее. Чтобы избежать расходимости приближений метода Ньютона, вызванных неудачным выбором начального приближения (см. рис. 11), можно попытаться запретить следующей итерации быть слишком далеко от предыдущей. Для этого следующую итерацию ищут из условия

xn+1 = argmin (x) argmin 2

где ln — некоторый параметр (вообще говоря, свой на каждом шаге). Первые три слагаемых в определении функции? представляют собой квадратичную аппроксимацию функции f, а последнее слагаемое — «штраф», не позволяющий точке xn+1 уходить далеко от точки xn (с идеями метода штрафов мы еще столкнемся ниже). Минимум (по крайней мере, стационарная точка) функции? вычисляется в явном виде из следующего уравнения (относительно x)

Q = (x) = f (xn) + f (xn)(x ?xn) + ln (x? xn).

Как легко видеть,

xn+1 = argmin (x) = xn? [f (xn) + lnI]?1f (xn)

Последняя формула и есть метод Левенберга — Маркардта.

Очевидно, что если ln = 0, то (13) представляет собой метод Ньютона, а если ln велико, то (поскольку [f (xn) + lnI]?1 (ln)?1I при больших ln) формула (13)близка к градиентному методу. Поэтому, подбирая значения параметра ln, можно добиться, чтобы метод (13), во-первых, сходился глобально, и во-вторых, квадратично. Можно, например, выбирать ln из следующих соображений: угол между направлениями шага и антиградиента должен быть острым, а значение функции на каждом шаге должно квалифицировано убывать. В этом случае ln должно удовлетворять следующим условиям (здесь мы обозначаем «антинаправление» шага [f (xn) + lnI]?1f (xn) через yn)

(yn, f (xn))

||yn|| · || f (xn)||1

f (xn+1) f (xn) ?2(yn, f (xn))

где 1 (0, 1) и 2 (0, ½) — параметры.

3.8 Еще один недостаток метода Ньютона. Модифицированный метод Ньютона В некоторых задачах более существенным недостатком метода Ньютона является его большая вычислительная трудность: на каждом шаге требуется вычисление оператора (матрицы) f (xn) и его (ее) обращение, что при больших размерностях стуит в вычислительном плане очень дорого. Один из способов обхода этих трудностей состоит в «замораживании» оператора f (xn) — использовании на каждом шаге [f (x0)]?1 взамен [f (xn)]?1:

xn+1 = xn? [f (x0)]?1f (xn)

Геометрическая интерпретация модифицированного метода Ньютона (14) изображена на рис.

Рис.

Можно показать, что при естественных ограничениях модифицированный метод Ньютона сходится лишь линейно (это плата за уменьшение объема вычислений). Можно также не замораживать оператор [f (xn)]?1 навсегда, а обновлять его через определенное число шагов, скажем k:

xn+1 = xn? [f (x[n/k]· k)]?1f (xn)

здесь [a] в верхнем индексе обозначает целую часть числа a. Можно доказать, что если функция f сильно выпукла и f удовлетворяет условию Липшица, то

||xn+k? x*|| C||xn? x*||k+1,

т. е. за k шагов порядок погрешности уменьшается в k + 1 раз, что соответствует следующей оценке погрешности на каждом шаге:

||xn+1? x*|| C||xn? x*||k k+1.

Другими словами, метод (15) является методом k? k+1-го порядка сходимости. Таким образом, метод (15) занимает промежуточное положение между методом Ньютона (k = 1) и модифицированным методом Ньютона (14) (k =) как по скорости сходимости, так и по объему вычислений.

Другой способ уменьшения объема работы, связанного с вычислением функции f (xn) описывается в следующем пункте.

3.9 Метод секущих Напомним, что метод секущих решения уравнения (2) заключается в приближенной замене функции F в этом уравнении не касательной y = F (xn) +F (xn)(x? xn), а секущей гиперплоскостью.

Например, в одномерном случае — прямой y = F (xn) + (F (xn)? F (xn?1))(x ?xn) /(xn ?xn?1). Эта замена приводит (в скалярном случае!) к следующему методу решения задачи (1):

xn+1 = xn? xn? xn?1

f (xn) f (xn?1)

f (xn)

который и называется методом секущих.

Известно, что для достаточно гладких выпуклых функций порядок сходимости этого метода равен, где = (5 + 1)/2 1.618 — известная константа (называемая золотым сечением).

Рис.

В многомерном случае поступают следующим образом. Пусть xn, xn?1, …, xn? m — уже вычисленные m + 1 итерации.

Для каждой компоненты fj функции f (j = 1, …, m) построим в Rm+1 гиперплоскость Sj, проходящую через m + 1 точку (xi, fj (xi)) (i = n? m, …, n) графика этой компоненты. Пусть P —" горизонтальная" проходящая через нуль гиперплоскость в Rm+1: P = {(x, y) RmЧR; y = 0}. В качестве xn+1 возьмем точку пересечения гиперплоскостей P иSj:

xn+1 P mj = 1 Sj

(в общем положении эта точка единственна).

Несложные рассуждения показывают, что xn+1 можно вычислять так. Пусть 0, …, n — решение системы

M i = 0 if (xn?i) = 0, m i = 0 i = 1.

Тогда

xn+1 = m i = 0 ixn? i

Затем описанные действия повторяются для точек xn+1, xn, …, xn? m+1.

Отметим, что поскольку на каждом шаге в системе (16) меняется лишь один столбец, то ее решение на каждом шаге можно обновлять с помощью специальной процедуры, не требующей большого объема вычислений.

Отметим, что метод секущих, в отличие от ранее рассматривавшихся методов, не является одношаговым в том смысле, что для вычисления следующей итерации ему не достаточно информации, полученной на предыдущем шаге — нужна информация, полученная на m + 1 предыдущих шагах. Такие методы называются многошаговыми. В следующем параграфе мы рассмотрим ряд таких методов. Методы же Ньютона и градиентный являются одношаговыми: для вычисления xn+1 требуется знать поведение функции и ее производных только в точке xn.

ЗАКЛЮЧЕНИЕ

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

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

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

1. Васильев Ф. П. Численные методы решения экстремальных задач. — М.: Наука, 1980.

2. Сухарев А. Г., Тимохов А. В., Федоров В. В. Курс методов оптимизации. — М.: Наука, 1986.

3. Поляк Б. Т.

Введение

в оптимизацию. — М.: Наука, 1983.

4. Сеа Ж. Оптимизация. Теория и алгоритмы. — М.: Мир, 1973.

5. Зангвилл У. Нелинейное программирование. Единый подход. — М.: Сов. радио, 1973.

6. Банди Б. Методы оптимизации (вводный курс). — М.: Радио и связь, 1988.

7. Компьютерное методическое пособие по методам параметрической оптимизации. МГТУ им. Баумана, 1997

.ur