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

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

Вычислительная схема метода

На отдельных этапах алгоритма метода Ньютона строятся квадратичные аппроксимации

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

Рис. 2.5

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

Из последнего равенства направление рк определяется равенством р* = х- хк=-^'к~кр'к, что позволяет получить общую схему метода Ньютона в виде

Напомним, что используемая квадратичная аппроксимация функционала строится как вторая производная функционала по векторному аргументу, определяемая равенством

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

Теорема о сходимости метода Ньютона

Для определения условий, которым должен удовлетворять шаг а^,, рассмотрим вспомогательные сведения. Пусть /7(х) — произвольная симметричная матрица, удовлетворяющая условиям

при любых х, уе9". Тогда если выбрать вектор р= -Р(л)Р(х) то (ф'(х)- р) = Ч Ф-. Р Ф") - -р)| Ф*|2 ПРИ условии, что ||ф'(х)|| * О- Таким образом, вектор р= -Р(.г)Г(х) определяет направление спуска функции ф(х). Исходя из этого, для минимизации ф(х) можно сформировать итерационный процесс:

где — последовательность произвольных матриц, удовлетворяющая условию (2.5.6). Нетрудно видеть, что процедуры (2.5.5) и (2.5.7) обладают общими свойствами, причем схема (2.5.7) является более общей.

Для связи процессов (2.5.5) и (2.5.7) рассмотрим схему

где используется матрица, обратная к Г^,. Это не отражается на существе дела, поскольку если матрица ¥к удовлетворяет условию (2.5.3), то для матрицы будут выполнены условия

В дальнейшем нам понадобится Вперед теорема.

Теорема. Результаты теоремы из полпараграфа 2.5.1 сохраняют силу и для метода (2.5.8).

Доказательство. Еслих = дгА + арк, где р^-= то

Отсюда вытекает, что неравенство (2.5.6) будет обязательно выполняться, если 1 - аМ / (2р) > е, т.е. а>а = = 2 р! -/ М. Тем самым обоснован выбор ак.

Поскольку (ф£, р*)<0 при условии ||ф*||*0,из условия

следует, что имеет место условие: ф/(+) < фА. Используя (2.5.10) и учитывая ограниченность ф(х) снизу аналогично тому, как в теореме 1 подпараграфа 2.5.1 доказывалось, что ||ф^|| —"0, устанавливаем, что при к-> °° (<р'к, р*)-"0. В соответствии с оценкой (2.5.9) это означает, что ||ф*||—"0. Отсюда в силу сильной выпуклости ф(х) следует сходимость последовательности (2.5.7) к решению х,.

Метод (2.5.5) можно рассматривать как процесс градиентного типа (2.5.7), считая, что Як[=[ Поскольку матрица <р'к' обладает требуемыми свойствами, сходимость метода обеспечивается. Поэтому процедура метода Ньютона (2.5.5) сходится к стационарной точке функционала ф(х) при выборе шага ак из условия (2.5.6).

Теорема о сходимости доказана, и далее можно формулировать алгоритм метода Ньютона.

Алгоритм метода Ньютона

Совокупность шагов алгоритма имеет следующий вид.

Шаг 1. Выбирается точка х0. Полагается хк = х0.

Шаг 2. Выбирается произвольное число а.

Шаг 3. Вычисляется вектор хА+1 = хк + арк.

Шаг 4. Вычисляется функционал ф(х^+,) = (р(хк + ар,,).

Шаг 5. Если ф(хЛ,+1)-ф(хЛ,)<еа(ф^, рк), то значение а принимается в качестве исходного а,; = а и далее — переход к шагу 6, иначе производится уменьшение ак (путем умножения на множитель <7,:0<г7<1)и затем — переход к шагу 4.

Шаг 6. Вычисляется очередное приближение:

Шаг 7. Проверяется условие стационарности ||ф,,+|| =

=( ч!+1> чм) <5 где 8 > 0 — малое число. Если |ф*+|| ^8, то далее — переход к шагу 8, иначе — к шагу 2, положив х^ = хА+1. Шаг 8. Останов.

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

Перейдем к иллюстрации вычислительной схемы метода.

Пример

Вычислить минимум квадратичной функции

Решение. Для минимизации можно воспользоваться алгоритмом метола Ньютона.

Шаг 1. Выбирается вектор х0 = (2,0,5,0)г, х(. = хп. Шаг 2. Полагаем а = 1,0.

Шаг 3. Вычисляется х^, = х^ + сср^., где направление

В результате хК = (2,0,5,0)т+ (5,0, -4,0)г= (7,0,1,0)гесть решение задачи, доставляющее минимум заданному функционалу.

Метод сопряженных градиентов

В методе сопряженных градиентов устранено обращение матриц вторых производных, необходимое в методе Ньютона.

Вычислительная схема метода

Введем понятие сопряженных векторов.

Определение 1. Два вектора рирв ЧЯ" называются сопряженными (А — ортогональными), если (рк, Ар.) = 0 при к Ф), А = АГ.

Метод эффективен для квадратичных выпуклых функций

где Л — симметричная положительно определенная матрица, т.е. (Ах, х) > 0, х * 0.

Для минимизации квадратичных функций строится последовательность {х^,}, где векторы р/, — сопряженные:

Обычно векторы рк строятся следующим образом:

причем параметр рА,, выбирается из условий сопряженности рк и рк+1- Алгоритм метода сопряженных градиентов имеет вид

где параметр ак выбирается из условия

Рассмотренные соотношения позволяют сформулировать алгоритм метода сопряженных градиентов.

Алгоритм метода сопряженных градиентов

Основные шаги алгоритма представляются следующей последовательностью.

Шаг 1. Выбирается произвольная точка х0 е 54", полагается к = 0.

Шаг 2. Вычисляется вектор р0= -<&(хо) = -<6. используя соотношения (2.5.4).

Шаг 3. Если 0 < к < п - 1, то переходим к шагу 4, иначе — если ф(х) квадратичный функционал, то далее — переход к шагу 8, а если ф(х) — произвольный выпуклый функционал, то — к шагу 7.

Шаг 4. Вычисляется х^+1 = х^ + а^р/(, где множитель

если ф(х) — квадратичная; а = а, если ф(х) произвольная, причем ак такое, что аА = а^тт{ (х^ р$)| а>

Шаг 5. Вычисляется направление рм = -фЧхА+1) +&+1Р,(.,

где

Шаг 6. Полагается к = к + 1 и далее — переход к шаг}' 3. Шаг 7. Так как ф(х) произвольный выпуклый функционал, то если Цфи'чЦ й§>0, положим х„_| = х0, р0 = -ф(х„_|), к =0 и переходим к шагу 3, иначе — к шагу 8. Шаг 8. Останов.

Метод вычисляет минимум квадратичной положительно определенной функции за число итераций меньшее, чем п. Для произвольной выпуклой функции — асимптотическая сходимость.

Пример

Вычислить точку минимума квадратичной функции

Решение. Минимум можно вычислить с помощью алгоритма. Шаг 1. Выбирается Хц = (4,0, 8,0)г, полагаем к = 0.

Шаг 2. Вычисляется направление р0 =41 д=-( 4д 10.0)7. Шаг 3. Так как к = 0 < п = 2, то — переход к шагу 4.

Шаг 4. Вычисляется вектор первого приближения решения

х, = х0 + о0р0, где а0 = -|(Ь, р„) + (х0, Ар„)| / (р0, Ар0) = 0,5, так как

(Ь, р0) = -116, (х0, АРо) = -192, (р„, Ар„) = 232.

Тогда вектор х, = (4,0,8,0)г + 0,5(-4,0, -10,0)г= (2,0,3,0)т-Шаг 5. Вычисляется вектор р, = -(^(х,) + Др0, где параметр р, =

= —С *Р > *Р! -<Ро)/(Ч>(|'<Ро)=0. так как ф{=(0,0)г, а остальные векторы

ненулевые.

Таким образом, вектор x] является решением задачи.

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