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

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

ВВЕДЕНИЕ

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

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

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

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

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

f(x)min,                                                                                             (1)

где f: RmR. Точка x* Rm называется решением задачи (1) <#"721779.files/image001.gif">

Рис.

Геометрическая интерпретация градиентного метода с постоянным шагом изображена на рис. <#"721779.files/image002.gif">

Рис.

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

Изучим сходимость градиентного метода с постоянным шагом <#"721779.files/image003.gif">

Рис.

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

Рис.

Поведение итераций градиентного метода для этой функции изображено на рис. 8 <#"721779.files/image005.gif">

Рис.

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

Рис.

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

Пусть f дважды непрерывно дифференцируема, а x* - невырожденная стационарная точка <#"721779.files/image007.gif">

Рис.

Разумеется, как метод второго порядка <#"721779.files/image008.gif">

Рис.

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

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

здесь [a] в верхнем индексе обозначает целую часть числа a. Можно доказать, что если функция f сильно выпукла <#"721779.files/image009.gif">

Рис.

В многомерном случае поступают следующим образом. Пусть 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) <http://www.ict.nsc.ru/ru/textbooks/akhmerov/mo/4.html> меняется лишь один столбец, то ее решение на каждом шаге можно обновлять с помощью специальной процедуры, не требующей большого объема вычислений.

Отметим, что метод секущих <http://www.ict.nsc.ru/ru/textbooks/akhmerov/mo/4.html>, в отличие от ранее рассматривавшихся методов, не является одношаговым в том смысле, что для вычисления следующей итерации ему не достаточно информации, полученной на предыдущем шаге - нужна информация, полученная на m + 1 предыдущих шагах. Такие методы называются многошаговыми. В следующем параграфе мы рассмотрим ряд таких методов. Методы же Ньютона <http://www.ict.nsc.ru/ru/textbooks/akhmerov/mo/4.html> и градиентный <http://www.ict.nsc.ru/ru/textbooks/akhmerov/mo/3.html> являются одношаговыми: для вычисления xn+1 требуется знать поведение функции и ее производных только в точке xn.

ЗАКЛЮЧЕНИЕ

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

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

ЛИТЕРАТУРА

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

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

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

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

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

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

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