Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

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

Читайте также:
  1. I. Определение и проблемы метода
  2. I. ОПРЕДЕЛЕНИЕ И ПРОБЛЕМЫ МЕТОДА
  3. I. ОРГАНИЗАЦИОННО-МЕТОДИЧЕСКИЙ РАЗДЕЛ
  4. I. Экспертные оценочные методы
  5. II МЕТОДИЧЕСКИЕ РЕКОМЕНДАЦИИ ПО ПОДГОТОВКЕ К ПРАКТИЧЕСКОМУ ЗАНЯТИЮ
  6. II. Категории и методы политологии.
  7. II. МЕТОДИЧЕСКИЕ УКАЗАНИЯ ДЛЯ ВЫПОЛНЕНИЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ
Помощь в написании учебных работ
1500+ квалифицированных специалистов готовы вам помочь

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

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

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


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

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

 

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

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

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

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

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

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

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

 

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

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

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

|| || ≤ С2 || ||P , C1|| ||P ≤ - , (1.3)

где числа C1>0, C2>0, P1≥0, P2≥ 0.

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

= - Dk , (1.4)

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

C1|| ||P ||Z|| 2≤ С2 || ||P ||Z||2 , Z Rn (1.5)

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

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

, = - , (1.6)

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

Dk = 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( ) c1(R).

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

3) 0< < <1,

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

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

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

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

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

Обозначим A={ ≥0: r∙g′(0)≤g′( )≤0} . Это множество непустое, так как g′( )<0 и g( ) c1(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{ } и c1 = - , c2 = + , получим требуемое утверждение.

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

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

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

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

Теорема 1.

1) f: Rn " R, f(x) c1(Rn)

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

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

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

 

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

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

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

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

,

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

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

|| || ≤ (1.10)

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

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

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

.

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

, Rn,

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

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

, .

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

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

=-D , (2.1)

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

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

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. Пусть - число обусловленности Gk′QGk ( , где и - соответственно максимальное и минимальное значения матрицы),

где Gk′Gk = Dk.

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

. (2.7)

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

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

(2.8)

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

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

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

, x Rn. (2.9)

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

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

.

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

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

, (2.10)

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

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

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

= (Dk-1Dk , ) = (Dk , )k

Следовательно, вектор Dk можно рассматривать как градиент функции в точке в пространстве со скалярным произведением (∙ , ∙)k, а метод (1.1), (2.1) – как градиентный метод в пространстве с переменной метрикой, определяемой матрицей Dk-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 ) будет определяться числами обусловленности матриц Gk 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) можно трактовать как градиентный метод в пространстве с переменной метрикой, определяемой матрицей Dk-1 = .

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

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

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

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

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

(3.2)

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

.

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

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

φ(x) = 0. (3.3)

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

φ φ . (3.4)

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

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

.

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

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

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

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

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

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

3) O ( *)

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

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

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

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

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

 

(3.6)

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

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

*Упражнение 20. Доказать, что для функции из класса C2 в достаточно малой окрестности невыражденого локального минимума метод (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; просмотров: 264 | Нарушение авторских прав


 

 

<== предыдущая страница | следующая страница ==>
Метод Ньютона| Ручной счет

mybiblioteka.su - 2015-2022 год. (0.193 сек.)