Как обобщенный градиентный метод

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

(Методические указания)

Челябинск, 1992 г.

Методические указания составлен в помощь студентам четвертого курса математического факультета, изучающим курс “Методы оптимизации”.

Длинная работа является руководством при проведении занятий по темам “Градиентные методы”, “Методы переменной метрики” и “Метод Ньютона” в курсе “Методы оптимизации”. Приведен ряд упражнений, разъясняющих связь, структуру и особенности методов с единой позиции.

§1 Обобщенный градиентный метод в задаче безусловной оптимизации

Пусть функция f(x) является гладкой функцией на всем пространстве Rⁿ. Численный поиск точки локального минимума этой функции сводится к следующей схеме:

где – два последующих приближения искомой точки, > 0 –длина шага в направлении

Если вектор ξ_k является направление спуска (см. рис 1), т.е.. < 0 для

≠ 0 и = 0 для = 0, то процесс (1.1) называется обобщенным градиентным методом [I]. (Здесь и далее через обозначается вектор градиента функции , вычисленный в точке штрихом вверху – транспонирование). При этом, если для любой сходящейся под последовательности { }< { } такой, что ≠ 0, выполняется соотношение:

0 < | |, || || < +∞, (1.2)

то последовательно { } называют равномерно градиентной относительно последовательности { }.

Рис.I. Градиент и вектор спуска направлены в различные полупространства, определяемые гиперплоскостью – касательной к линии уровня =c=const в точке _.

По существу, условия (1.2) обеспечивают ограниченность последовательности { } и исключают взаимную ортогональность векторов и в пределе.

Упражнение I. Доказать, что последовательность { } будет равномерно градиентной, если для всех выполняются условия:

|| || ≤ С₂ || ||^P , C₁|| ||^P ≤ - , (1.3)

где числа C₁>0, C₂>0, P₁≥0, P₂≥ 0.

Упражнение 2. Доказать, что для

= - D_k , (1.4)

где D_k – положительно определенная симметричная матрица такая, что

C₁|| ||^P ||Z|| ²≤ С₂ || ||^P ||Z||², Z Rⁿ (1.5)

Выполняется условия типа (1.3)

Пример 1. Последовательность { }, построенная градиентным методом:

, = - , (1.6)

является равномерно градиентной. В том легко убедиться, если положить в (1.5)

D_k = E (E – единичная матрица).

Конкретная реализация обобщенного градиентного метода (1.1) определяется способами выбора шагового множителя и направления спуска . Примерами таких широко применяемых на практике реализаций служит градиентный метод, метод Ньютона, квазиньютоновские методы, методы сопряженных градиентов и многие их модификации [1,2,3,4,5,6,7].

Выбор шагового множителя обычно осуществляют одним из следующих способов [1, 5 ].

1 Правило Армийс.

При фиксированных значениях числовых параметров и полагают = , где - наименьшее из неотрицательных целых чисел , для которых

≥- .

2 Правило Голдстейна

При фиксированном шаговый множитель выбирают из условия:

3 Одномерная минимизация.

Параметр выбирают из условия:

, (1.7)

Где – максимально допустимая длина шага.

Обычно для решения (1.7) используется численные алгоритмы одномерного поиска [3,5,6,7]. Тогда, например, одномерную минимизацию можно завершить при выполнении неравенств (объясните почему):

(1.8)

где и - заданные числа из неравенства (0;1)

(параметр чаще всего берут близким к 0, например, см.упр.4)

4. Постоянный шаговый множитель.

Полагают = при все k.

Упражнение 3. Указать промежутки значений шагового множителя , изображенные на рис.2 и удовлетворяющие а) правилу Армийо; б) правилу Голдстейна.

Утверждение 1. 1) g: R " R, g() c¹(R).

2) M R, |M|<+ : g()≥M R,

3) 0< < <1,

4) g′(0) = dg/d | <0,

1)-4) 0<c₁<c₂: [c₁;c₂] выполнены неравенства:

g(0)-g() ≥ - g′(0),

| g’()|≤ ∙|g′(0)|.

Доказательство: Зафиксируем любое число r: <r< .

Обозначим A={ ≥0: r∙g′(0)≤g′()≤0}. Это множество непустое, так как g′()<0 и g() c¹(R).

Пусть =inf{ : A}. >0 так как r∙g′(0)>g′(0).

Тогда в силу определения для [0; ] выполнено неравенство:

g′()≤ r∙g′(0). (1.9)

Следовательно, (0; ): | g′()| ≤ | g′()| для

[ - ; + ] (см. рис. 3)

Рис. 3

С учетом (1,9) получим:

g()=g(0) + g′()d ≤g(0) + r∙ g′(0)∙ <g(0) + ∙ g′(0)∙ .

Поэтому в силу непрерывности функции g() (0; );

g() – g(0)≤ ∙ g′(0)∙ при [ - ; + ] (см. рис. 4)

Полагая = min{ } и c₁ = - , c₂ = + , получим требуемое утверждение.

Упражнение 4. Используя утверждение 1 доказать, что если функция ограничена снизу на Rⁿ, < 0, * = + , а параметры и выбраны так, что 0< < <1, то найдутся числа 0<c₁< c₂ такие, что для любого [c₁,c₂] условия (1,8) будут выполнены.

Упражнение 5. Пусть { } - последовательность, построенная обобщенным градиентным методом (1.1), и { } является равномерно градиентной относительно { } последовательностью. Доказать, что если

{ } { }: x* и f(x*) ≠ 0, то 0

при выборе шагового множителя по правилу Армийо.

Теорема 1.

1) f: Rⁿ " R, f(x) c¹(Rⁿ)

2){ } - последовательность, построенная обобщенным градиентным методом (1.1)

3){ } - равномерно градиентная относительно последовательность

4){ } - построена по правилу Армийо.

1)-4) Любая предельная точка * последовательности { } является точкой стационарности функции f(x),т.е. =0.

*Упражнение 6. Используя упражнение 5 доказать теорему 1.

*Упражнение 7. Доказать теорему 1 при выборе шагового множителя и одномерной минимизации с *= , из правила Голдстейна и из соотношений (1.8)

Указание: При доказательстве использовать неравенство:

,

где = x_k + и определено в результате одномерной минимизации, а = x_k и - из правила Армийо.

Теорема 1 позволяет ввести следующее правило для окончания итерационного процесса (1.1). Вычисления прекращаются, если полученная на очередной итерации точка x_k удовлетворяет неравенству:

|| || ≤ (1.10)

где - достаточно малое положительное число.

На практике такая точка обычно отождествляется с точкой стационарности функции f(x).

Упражнении 8. Доказать, что если для некоторых чисел c₁ > 0, c₂ > 0, p₁ > 0, p₂ > 0 и любого выполнены условия (1.3), то при определенных соотношения между числами и критерий (1.10) окончания процесса (1.1) эквивалентен критерию:

≤ .

Упражнение 9. Пусть * - такая точка локального минимума функции , что при некоторых >0, >0 и для O ( - окрестность точки *) имеет место неравенство:

, Rⁿ,

где - () - матрица вторых производных (матрица Гессе) функции , вычисленная в точке .

Доказать, что для O такого, что верны оценки:

, .

§ 2. Методы переменной метрики.

Зададим направление спуска в (1.1) по формуле:

=-D , (2.1)

где D - симметричная положительно определенная матрица (следовательно, представимая в виде D=G_kG_k′, где G_k - невырожденная матрица).

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

Q > 0, при (2.2)

Оценить скорость сходимости метода (2.1) для таких функций позволяет неравенство Л.В. Канторовича [8]:

, (2.3)

где A – положительно определенная симметричная матрица nxn с собственными значениями .

Справедливость данного неравенства (2.3) следует из свойств матрицы A и понятия выпуклого множества. В силу положительной определенности и симметричности A всегда ортогональная матрица B (B′=B^-1) такая, что

B′AB^-1 = = C.

Обозначая =B , неравенство (2.3) при ¹0 можем представить в виде:

1≤ =()() ≤ ,

где - квадрат отношения соответствующей координаты на норму вектора y, то есть:

≥ 0, i= ; . (2.4)

На плоскости рассмотрим n точек .

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

Наибольшего r значения произведение будет достигаться в точке * касания гиперболы =r с многоугольником . Искомая точка . Причем, число является решением следующей задачи:

(2.5)

Упражнение 10. Решить задачу (2.5) и убедиться в справедливости неравенства (2.3)

Упражнение 11. Доказать, что если ≠0, то при выборе из одномерной минимизации (1.7) c для метода (1.1), (2.1) в случае квадратичной функции (2.2) будем иметь:

(2.6)

*Упражнение 12. Пусть - число обусловленности G_k′QG_k (, где и - соответственно максимальное и минимальное значения матрицы),

где G_k′G_k = D_k.

Если определяется по формуле (2.6), то для квадратичной функции (2.2) на каждой итерации выполняется неравенство:

. (2.7)

Указание: Воспользоваться неравенством Л.В. Канторовича.

Если ≠ * для всех , то неравенство (2.7) можно представить в виде:

(2.8)

Обозначим правую часть неравенства (2.8) через l. Для положительно определенной симметричной матрицы G_k′QG_k l≤1. И если l<1, то при достаточно больших последовательность { } можарируется геометрической прогрессией const∙q^k со знаменателем q (l,1). В этом случае последовательность { } будет сходиться не медленнее, чем геометрическая прогрессия со знаменателем l (т.е. медленнее, чем линейно со знаменателем l).

Упражнение 13. Доказать, что последовательность { }, построенная по методу (1.1). (2.1) для квадратичной функции (2.2), сходится сверхлинейно (т.е. быстрее, чем любая геометрическая прогрессия со знаменателем qÎ(0;1)) тогда и только тогда, когда сверхлинейно сходится последовательность { }.

Указание: Для выполнения упражнения 13 докажите, что если и - соответственно минимальное и максимальное собственные значения положительно определенной симметричной матрицы Q, то

, x Rⁿ. (2.9)

Из неравенства (2.7) (как и из (2.8)) следует, что для ускорения сходимости последовательности {f(x_k)} матрицы D_k = G_k′G_k не обходимо выбирать так, чтобы числа обусловленности матриц G_k′QG_k были близки к 1 (т.е. собственные значения каждой матрицы были близки между собой). И при D_k≈Q^-1 в силу (2.6) шаговый множитель, определяемый с помощью одномерной минимизации, будет близок к 1. В частности, выбирая D_k=Q^-1, получим G_k′QG_k = G_k′(G_k′G_k)^-1G_k = E и , , а l=0. Поэтому = – Q^-1 = *, и в данном случае для получения точки минимума * требуется всего одна итерация.

Для произвольной целевой функции из класса C² в окрестности точки локального минимума * будем иметь:

.

И так как =0, то

Поэтому, если для функции последовательность { } строится с помощью обобщенного градиентного метода (1.1), (1.7), (2.1) и сходится к точке невырожденного (матрица определена положительно) локального минимума *, то как и для квадратичной функции, выполняется неравенство:

, (2.10)

Где - число обусловленности матрицы G_k′ G_k, а G_k′G_k = D_k.

Соотношение (2.10), как и в случае квадратичной функции, свидетельствуют о том, что для быстро сходимости процесса (1.1), (2.1) матрицы D_k необходимо по возможности выбирать близкими к [ ]^-1 чтобы . Это относительно ко всем рассмотренным выше способам выбора шагового множителя .

Всякая симметричная положительно определенная матрица D_k^-1 задает скалярное произведение = D_k^-1 и связанную с ним метрику. Линейную часть разложения функции f(x) в окрестности точки x можно представить в виде:

= (D_k^-1D_k , ) = (D_k , )_k

Следовательно, вектор D_k можно рассматривать как градиент функции в точке в пространстве со скалярным произведением (∙, ∙)_k, а метод (1.1), (2.1) – как градиентный метод в пространстве с переменной метрикой, определяемой матрицей D_k^-1 = [D()]^-1. В частности, если в процессе перехода от одной точки к другой метрику не изменять, то во всем пространстве она будет определена постоянной положительно определенной симметричной матрицей D^-1, которую можно представить в виде:

D^-1 = (GG′)^-1

где G – невырожденная матрица размерности . В этом случае матрица G будет определять переход к новой системе координат, в которой алгоритм (1.1), (2.1) будет представлен как обычный градиентный метод (1.6) [9]. Действительно, имеем:

= D^-1 = (G^-1)′ G^-1 = (G^-1 , D^-1 ) = , где = D^-1 ,

то есть

= D , (2.11)

И осуществляя данное линейное преобразование, получим:

= G =g(), g() = G = G′G G = G′ = G′ ,

= G^-1 = G^-1 - G^-1D = - G^-1 = - g().

Скорость сходимости процесса = - g() (или, что то же самое, процесса = - D ) будет определяться числами обусловленности матриц G_k′ G = g(), где = G^-1 . Поэтому алгоритм будет эффективным, если D ≈ [ ]^-1, то есть g() ≈ G′(GG′)^-1G = E.

На рис.6 изображены линии уровня ( =const) в окрестности точки =0 локального невырожденного минимума “овражной” функции двух переменных.

Применение в этом случае обычного градиентного метода (1.6) будет неэффективно, так как векторы = всякий раз будут ортогональны линиям уровня (см.рис.1), что, вероятнее всего, приведет к колебаниям от одной стенки оврага к другой и медленному продвижению к точке минимума вдоль оси оврага l. В то же время удачное линейное преобразование координат =G (что равносильно выбору матриц D ≈ [ ]^-1) может существенно изменить характер линий уровня и тем самым ускорить сходимость процесса (рис.7).

Упражнение 14. Рассмотрим пример функции .

Сделайте несколько итераций из начальной точки = (2;2)′ по методу (1.6), (1.7) и с использованием (2.11). В соответствующих системах координат изобразите линии уровня и проделанные итерации.

В действительности, при поиске точки минимума функция , матрица неизвестна. Поэтому на практике обычно полагают D ≈ [ ]^-1, что приводит к методу Ньютона.

§ 3. Метод Ньютона и его модификации.

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

Метод Ньютона называется итерационный процесс.

. (3.1)

Предполагая, что матрица невырождена.

Как отмечалось в §2, итерационный процесс (3.1) можно трактовать как градиентный метод в пространстве с переменной метрикой, определяемой матрицей D_k^-1 = .

Упражнение 15. Доказать, что метод Ньютона инвариантен относительно

линейного преобразования координат (2.11).

Упражнение 16. Доказать, что ньютоновское направление

= -[ ]^-1 для функции из класса C² в достаточно малой окрестности невыражденого локального минимума является направлением спуска, для правило Армийо выполняется при .

Для метода Ньютона

(3.2)

на каждой итерации можно интегрировать как результат аппроксимации минимизируемой функции f(x) её тейлоровским разложением в окрестности точки с точностью до квадратичных членов, то есть квадратичной функции:

.

В качестве x_k+1 берут точку стационарности функции , которая в случае положительной определенности матрицы Гессе будет и точкой абсолютного минимума данной функции. Поэтому для квадратичных функций с положительно определенной матрицей Гессе метод Ньютона (3.2) сходится за одну итерацию.

Поскольку в точке стационарности * функции =0, то метод Ньютона может быть использован и для поиска решения системы и алгебраических уравнений. Так, если функция φ: Rⁿ " Rⁿ имеет непрерывную производную φ() в некоторой окрестности точки *, удовлетворяющей системы уравнений

φ(x) = 0. (3.3)

а матрица φ( *) имеет обратную, то точка * можно найти по методу Ньютона:

φ φ . (3.4)

При этом имеет место, следующее утверждение.

Утверждение 2. Найдется такое (0; ), что для O ( *) корректно определена, целиком содержится в O ( *) и сходится к *. Причем, если ≠ * для , то сходимость будет сверхлинейной, т.е.

.

*Упражнение 17. Доказать утверждение 2, используя представление:

φ_k = φ[ * + t( – *)]dt( – *). (3.5)

Теорема 2. 1) φ: Rⁿ " Rⁿ, φ( *) = 0.

2) O ( *) такая, что при некоторых числах и и всех

, O ( *) имеют место соотношения:

║ φ() - φ()║≤ ║ - ║, ║[ φ()]^-1║≤

3) O ( *)

1) 2) 3) последовательность { }, построенная по методу Ньютона (3.4), сходится к * с квадратичной скоростью, т.е.

║ – *║ ≤ ║ – *║² для = 0,1,2,...

Упражнение 18. Используя представление (3.5), доказать теорему 2.

Замечание 1: Пологая φ() = в утверждении 2 и теореме 2, получим соответствующие утверждения для метода Ньютона (3.2), предназначенного для минимизации функции .

Упражнение 19. Пусть =1 и

(3.6)

где – малое положительное число.

Насколько малой должна быть окрестность невыражденого минимума *=0, чтобы метод (3.2) сходился к этой точке? Может ли здесь быть применена теорема 2?

*Упражнение 20. Доказать, что для функции из класса C² в достаточно малой окрестности невыражденого локального минимума метод (3.2) является обобщенным методом с равномерно градиентной последовательностью { }, обладающий релаксационностью (значения минимизируемой функции не возрастают от итерации к итерации).

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

1) на каждой итерации должна существовать обратная матрица к матрице Гессе;

2) с увеличением размерности пространства резко возрастает трудоемкость метода из-за обращения матрицы Гессе;

3) сходимость только локальная, поэтому приближение должно быть достаточно хорошим (см. функцию (3.6));

4) любая точка стационарности является точкой притяжения для метода (см. утверждение 2 и теорему 2);

5) релаксационность гарантируется только в достаточно малой окрестности точки невыражденого локального минимума (см. упр. 19);

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

Одной из таких модификаций является итерационный процесс (1.1), в котором определяется по правилу Армийо с =1, а в качестве выбирается ньютоновское направление, если существует обратная матрице Гессе, для которой выполнены соотношения:

c (3.7)

c (3.8)

Дата добавления: 2015-07-07