Учебная работа. Метод Ньютона

1 Звезда2 Звезды3 Звезды4 Звезды5 Звезд (Пока оценок нет)
Загрузка...

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

ВВЕДЕНИЕ

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

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

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

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

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

f(x)min,(1)

где f: RmR. Точка x* Rm называется решением задачи (1) <#"justify">. ГРАДИЕНТНЫЕ методы

2.1 Общие соображения и определения

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

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

f(x) min,(1)

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

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

при всех n N. Такие последовательности иногда называют релаксационными, а методы построения релаксационных последовательностей — итерационными методами или методами спуска. Последовательность, удовлетворяющую (<#"justify">б) сходится, если

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

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

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

г) сверхлинейно сходится, если для любого q (0, 1) и некоторого (зависящего от q) C выполнено неравенство (3) <#"justify">Если эти свойства выполняются только для x0 достаточно близких к x*, то как всегда добавляется эпитет «локально».

2.2 Эвристические соображения, приводящие к градиентным методам

Выше уже отмечалось <#"162" src="/wimg/14/doc_zip1.jpg" />

Рис.

Геометрическая интерпретация градиентного метода с постоянным шагом изображена на рис. <#"154" src="/wimg/14/doc_zip2.jpg" />

Рис.

2.4 один пример исследования сходимости

Изучим сходимость градиентного метода с постоянным шагом <#"justify">откуда x** = 0. очевидно также, что если x0 = 0, то и xn = 0 при всех n.

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

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

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

2.5 Теорема об условной сходимости градиентного метода с постоянным шагом

Пусть в задаче (1) <#"justify">и поэтому по формуле Ньютона — Лейбница для функции

(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 , эту цепочку можно продолжить:

(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)} не возрастает и, следовательно, релаксационность <#"justify">||f (xn)||2 1 1 — 2 -1 [f(xn)  f(xn+1)] 0 при n

2.6 Замечания о сходимости

Подчеркнем, что теорема 3.5 <#"justify">Доказательство.

Решение x* = argmin f(x) существует и единственно в силу теорем 2.9 <#"justify">F(y) = F(x) + 1 0F [x + s(y  x)](y x) ds,

или, для x = x* и y = xn, учитывая, что f (x*) = <#"justify">f (xn) = 1 0 f [x* + s(xn  x*)](xn  x*) ds

(здесь мы, как и выше, воспользовались задачей 2.3 <#"justify">выполнено неравенство

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

Интеграл, стоящий в этом неравенстве, определяет линейный (симметричный <#"justify">+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) <#"justify">2.8 об оптимальном выборе шага

Константа q, фигурирующая в теореме 2.7 <#"center">квадратичный градиентный линейный шаг

Рис.

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

Рис.

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

Условие (11) <#"justify">

Рис.

другими словами, n выбирается так, чтобы следующая итерация была точкой минимума функции f на луче L. такой вариант градиентного метода называется методом наискорейшего спуска. Заметим, кстати, что в этом методе направления соседних шагов ортогональны. В самом деле, поскольку функция: f(xn f (xn)) достигает минимума при = n, точка n является стационарной точкой <#"justify">3. метод НЬЮТОНА

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

Если исходить из того, что необходимым этапом нахождения решения задачи

(x) min

где f: Rm R, является этап нахождения стационарных точек <#"justify">и в качестве следующего приближения возьмем решение задачи

(x) min

Геометрическая интерпретация формул (3) <#"237" src="/wimg/14/doc_zip6.jpg" />

Рис.

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

3.2. теорема о локальной сверхлинейной сходимости метода Ньютона

Пусть f дважды непрерывно дифференцируема, а x* — невырожденная стационарная точка <#"justify">x x* ||F (x)  F (x*)|| = 0.

поскольку F (x*) невырожден, в силу (7) <#"justify">x x* ||[F (x)]1  [F (x*)]1|| = 0.

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

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

F(x) = F(x*) + F (x*)(x  x*) + o(x — x*) <#"justify">Но тогда в силу

x x* [F (x)]1F(x) = [F (x)]1F (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*, например, окрестность {x Rm: ||(x  x*)|| ||x  x*||/2}. В силу (9) <#"justify">||xn+1  x*|| 1

||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 Обсуждение метода Ньютона

Таким образом, метод Ньютона <#"201" src="/wimg/14/doc_zip7.jpg" />

Рис.

разумеется, как метод второго порядка <#"justify">||f (x)|| <2 2 L

Тогда для x0 Vx* метод Ньютона <#"justify">где q = L||f (x0)||/2 2 < 1.

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

По теореме 2.9 <#"justify">(xn + h)  f (xn) = 1 0f (xn + sh)h ds

Вычитая из обеих частей этого равенства f(xn)h = 01f (xn)h dsи учитывая, что f удовлетворяет условию Липшица <#"justify">||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||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) и поэтому (см. пред. задачу <#"justify">||f (xn+1)|| L

||f (xn)||2.

С помощью (11) <#"justify">||f (xn)|| L

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

||f (x0)||

n =2 2

L q2n.

наконец, в силу сильной выпуклости <#"justify">или

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

Но тогда

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

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

Тогда из (12) <#"justify">(xn+1) = f(xn n[f xn)]1f (xn)) f(xn) n(f (xn), [f (xn)]1f (xn))

или, как в методе наискорейшего спуска <#"justify">(f (xn)(x  xn), x  xn) +ln

||x  xn||2}

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

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

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

Очевидно, что если ln = 0, то (13) <#"justify">(yn, f (xn))

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

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

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

3.8 Еще один недостаток метода Ньютона. модифицированный метод Ньютона

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

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

Геометрическая интерпретация модифицированного метода Ньютона (14) <#"219" src="/wimg/14/doc_zip8.jpg" />

Рис.

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

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

здесь [a] в верхнем индексе обозначает целую часть числа a. Можно доказать, что если функция f сильно выпукла <#"justify">т. е. за k шагов порядок погрешности уменьшается в k + 1 раз, что соответствует следующей оценке погрешности на каждом шаге:

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

другими словами, метод (15) <#"justify">+1 = xn xn  xn1

f (xn) f (xn1)(xn)

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

Известно, что для достаточно гладких выпуклых функций <#"justify">

Рис.

В многомерном случае поступают следующим образом. Пусть 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:

+1 P mj = 1 Sj

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

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

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) <#"justify">ЗАКЛЮЧЕНИЕ

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

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

ЛИТЕРАТУРА

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

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

. Поляк Б.Т. Введение в оптимизацию. — М.: Наука, 1983.

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

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

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

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

Учебная работа. Метод Ньютона