Файл: Сахарова Людмила Викторовна, Лукьянова Галина Викторовна Методы оптиизации для машинного обучения учебное пособие.doc

f (х) в произвольных точках. Такие ситуации часто встречаются в практически важных задачах оптимизации.Остановимся сначала на вычислительных процедурах вида (3.25), в которых выбор нового приближения к точке минимума определяется сравнением значений функции в нескольких точках пространства E_n.3.4.1. МИНИМИЗАЦИЯ ПО ПРАВИЛЬНОМУ СИМПЛЕКСУОпределение 3.7.Правильным симплексом в пространстве E_n на­зывается множество из п + 1 равноудаленных друг от друга точек (вер­шин симплекса). Отрезок, соединяющий две вершины, называется ребром симплекса.В пространстве E₂ правильным симплексом является совокупность вершин равностороннего треугольника, в E₃ – правильного тетраэдра.Если х⁰ – одна из вершин правильного симплекса в E_n то координаты остальных п вершин х¹ ,..,хⁿ можно найти, например, по формулам: (3.37)где d₁ , d₂ , a– длина ребра. Вершину х⁰ симплекса, построенного по формулам (3.37), бу­дем называть бaзовой.В алгоритме симплексного метода используется следующее важное свойство правильного симплекса. По известному симплексу можно построить новый симплекс отрaжением какой–либо вершины, например, х^k симметрично относительно центра тяжести х^c остальных вершин симплекса. Новая и старая вершины и х^k связаны соотношением: , где x^c . В результате получается новый правильный симплекс с тем же ребром и верши­нами =2x^c – х^k , хⁱ, i= 0,.. , n, ik. Таким образом, происходит перемещение симплекса в пространстве Е_n. На рис. 3.3 представле­на иллюстрация этого свойства симплекса в пространстве

---

Е₂.
Рис. 3.3. Построение нового симплексa в E₂ отрaжением точки х:

a — нaчaльный симплекс х⁰, х¹ , ; 

б — новый симплекс х⁰, х¹ , ; 

центр отрa­жения — точкax^c = (х⁰+ х¹)/2


Поиск точки минимума функции f (x) с помощью правильных сим­плексов производят следующим образом. На каждой итерации срав­ниваются значения f (х) в вершинах симплекса. Затем проводят опи­санную выше процедуру отражения для той вершины, в которой f (х) принимает наибольшее значение. Если в отраженной вершине получа­ется меньшее значение функции, то переходят к новому симплексу. В противном случае выполняют еще одну попытку отражения для вер­шины со следующим по величине значением f (х). Если и она не при­водит к уменьшению функции, то сокращают длину ребра симплекса, например, вдвое и строят новый симплекс с этим ребром. В качестве базовой выбирают ту вершину х⁰ старого симплекса, в которой функция принимает минимальное значение. Поиск точки минимума f (x) заканчивают, когда либо ребро симплекса, либо разность между значе­нии функции в вершинах симплекса становятся достаточно малыми. Опишем один из вариантов алгоритма этого метода.Шаг 0. Выбрать параметр точности , базовую точку х⁰ , ребро a и построить начальный симплекс по формулам (3.37). Вычислить f (х⁰).Шаг 1. Вычислить значения f (х) в вершинах симплекса х¹ , .., xⁿ .Шаг 2. Упорядочить вершины симплекса х⁰ , .., хⁿ так, что бы f (х⁰)  … f (х¹)  f (х^n–1)  f (хⁿ).Шаг 3. Проверить условие (3.38)Если оно выполнено, то вычисления прекратить, полагая х^*  х⁰ , f ^*  f (x⁰). В противном случае перейти к шагу 4.Шаг 4. Найти и выполнить отражение вершины хⁿ:

---

=2x^c – хⁿ .Если f () xⁿ), то положить хⁿ= и перейти к шагу 2. Иначе – перейти к шагу 5.

Шаг 5. Найти и выполнить отражение вершины х^n–1: = 2x ^c – х^n–1. Если f ( ) < f (х^n–1), то положить х^n–1 = и перейти к шагу 2. Иначе – перейти к шагу 6.

Шаг 6. Перейти к новому правильному симплексу с вдвое меньшим ребром, считая базовой вершиной х⁰ . Остальные п вершин симплекса найти по формуле хⁱ = (хⁱ + х⁰)/2, i=1, .., п. Перейти к шагу 1.

Геометрическая иллюстрация работы алгоритма в пространстве показана на рис. 3.4, где точки х⁰ , х¹ , х² – вершины начального симплекса, а пунктиром указаны процедуры отражения.




Рис. 3.4. Поиск точки минимума функции с помощью правильных симплексов в пространстве


Замечания:

1. Следует иметь в виду, что если функция f (х) многомо­дальна, то описанным методом может быть найдена точка ло­кального, а не глобального минимума f (х).

2. Если ограниченность снизу целевой функции не оче­видна, то в алгоритм метода следует включить дополни­тельную процедуру останова.
3.4.2. ПОИСК ТОЧКИ МИНИМУМА ПО ДЕФОРМИРУЕМОМУ СИМПЛЕКСУ

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

(3.39)

Геометрическая иллюстрация этих процедур для пространства E₂ приведена на рис. 3.5 и 3.6. Так как величина   (0; 1), то выбор точек z¹ и z² соответствует сжатию симплекса;   1, поэтому выбор точки z³ соответствует отражению, а  > 1 и выбор точки z⁴ приводит к рас­тяжению симплекса. Численные эксперименты показывают, что этот алгоритм хорошо работает в пространстве E_n для п  6. Отметим, что при деформациях утрачивается свойство правильности исходного симплекса. Поэтому, не стремясь к правильности начального симплекса, его строят из произвольной базовой точки х⁰  E_n , по формулам
, (3.40)

где e ⁱ – i–й базисный вектор; – параметр симплекса. На практике хорошо зарекомендовал себя следующий набор параметров ,  и  для выбора пробных точек zⁱ в формулах (3.39):

 = 1/2,  = 1 и  =2.


Рис. 3.5. Пробные точки z¹,z²,z³,z⁴ для перехода к новому симплексу


Рис. 3.6. Новые симлексы полученные в результате процедур сжатия (а,б); отражения (в); растяжения(г).

Опишем алгоритм метода поиска точки минимума функции по деформируемому симплексу.

Шаг 0. Выбрать параметр точности , параметры ,  и , базовую точку х⁰ , параметр  и построить начальный симплекс по формулам (3.37) или (3.40). Вычислить f (х⁰).

Шаг 1. Вычислить значения функции в вершинах симплекса х¹, . . . , xⁿ .

Шаг 2. Упорядочить вершины х⁰, . . . , xⁿ так, чтобы f (х⁰)  …  f (хⁿ).
Шаг 3. Проверить достижение заданной точности (условие (3.38)). Если оно выполняется, то вычисления завершить, полагая х *  х⁰, f  *  f (х⁰). Иначе – перейти к шагу 4.

Шаг 4. Найти и пробные точки z^k , k=1, …, 4 пo формулам (3.39). Найти f (z^*)= min f (z^k). Если f (z*) < f (zⁿ). то положить xⁿ=z^* и перейти к шагу 2. Иначе – перейти к шагу 5.

Шаг 5. Уменьшить симплекс, полагая хⁱ = (хⁱ + х⁰)/2, i = 1,.., nи перейти к шагу 1.

Замечание. Для того чтобы избежать сильной деформации симплекса, алгоритм иногда дополняют процедурой обновления. На­пример, после N шагов алгоритма из точки х⁰ снова строят симплекс по формулам (3.37) или (3.40), полагая а = ||x⁰–xⁿ||.

С теоретической точки зрения описанные методы минимизации слабо исследованы, однако практика показывает их работоспособ­ность.

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

(3.31): x^k+\ = x^k+_kp^k . В зависимости от способа выбора направления p^k и шага _k получаются различные алгоритмы минимизации.

3.4.3. МЕТОД ЦИКЛИЧЕСКОГО ПОКООРДИНАТНОГО СПУСКА

Этот метод заключается в последовательной минимизации целе­вой функции f (x) сначала по направлению первого базисного вектора е¹, затем второго – е² и т.д. После окончания минимизации по направ­лению последнего базисного вектора еⁿ цикл повторяется.

Опишем этот алгоритм.

Шаг 0. Выбрать х E_n ,критерий достижения точности (напри­мер, (3.28) или (3.29)), величину . Найти f (x), положить j= 1.

Шаг 1. Решить задачу одномерной минимизации Ф() = f (х + е^j) min,   R, т.е. найти *. Положить = х +^*е^j, вычис­лить f (х).

Шаг 2. Если j < п, то положить х = , j=j+1 и перейти к шагу 1, иначе – перейти к шагу 3.

Шаг 3. Проверить условие достижения точности ||х– || < 

или | f (x) – f ( )| <. Если оно выполняется, то положить х^* = , f  ^*=f ( ) и закончить поиск. Иначе – положить х = , f (х) = f ( ), j = 1 и перейти к шагу 1.

Замечание. Для приближенного решения вспомогательной задачи одномерной минимизации на шаге 1 алгоритма на практике, как правило, используют метод поразрядного поиска (см. разд. 2.2.2).

Эффективность метода циклического покоординатного спуска существенно зависит от свойств целевой функции.

Пример 3.5. Решить задачу f (x)=x²₁+х²₂  min, х Е₂ методом циклического покоординатного спуска.

Линии уровня этой целевой функции – окружности с центром в начале координат (рис. 3.7). Выберем произвольную начальную точку х, например х=(3,3). Очевидно, два шага исчерпывающего спуска сначала по направлению е¹ , затем – е² приведут в точку минимума х^* = (0,0).

В примере 3.5 точку минимума функции удалось найти точно за конечное число шагов. Это скорее исключение, чем правило.

Пример 3.6. Решить задачу f (x)=5x²₁+5х²₂ +8x₁х₂ min, х Е₂ методом циклического покоординатного спуска.

Сначала заметим, что поворот системы координат на угол – 45° (замена переменных x₁ =(y₁+y₂) / и x₁ =(–y₁+y₂) / приводит функцию к виду f ₁(y) =y²₁+9y²₂ . Очевидно, линии уровня целевой функции – эллипсы y²₁/9+y²₂=c² (рис. 3.8). Результаты расчетов по приведенному выше алгоритму представлены в табл. 3.2.



Рис. 3.7. К примеру 3.5.Рис. 3.8. К примеру 3.6.

Тaблицa 3.2

Номер итерации	x1	x2	f (x)
0	5	5	450
1	–4	5	45
2	–4	3,2	28,8
3	–2,56	3,2	18,43
4	–2,56	2,05	11,8
5'	–1,64	2,05	7,55
6	–1,64	1,31	4,83
7	–1,05	1,31	3,09
8	–1,05	0,84	1,98
9	–0,67	0,84	1,27
10	–0,67	0,54	0,81

Из табл. 3.2 и рис. 3.8 видно, что минимизирующая последовательность {х^k} сходится к точке минимума х^* = (0,0). Однако в отличие от решения за­дачи из примера 3.5 достижение точки минимума за конечное число шагов не гарантируется. Траектория поиска точки минимума в данной задаче имеет ярко выраженный зигзагообразный характер.Из примера 3.6 видно, что эффективность решения задачи методом циклического покоординатного спуска можно повысить, если дополнить его алгоритм периодически повторяющимся поиском точки минимума в направлениях pⁱ = xⁱ–x^i–1 из точек xⁱ. Так, например, если из точки х⁴ провести исчерпывающий спуск в направлении p⁴ = х⁴ – х² (координаты точек см. в табл. 3.2), то получим точку (–2,2 10^–5 ; 5,6  10^–3 ), распо­ложенную значительно ближе к точке минимума х^*=(0,0), чем точки х⁵, х⁶, х⁷.

Такой подход, состоящий в последовательном нахождении на­правлений убывания функции и минимизации ее по этим направлени­ям, лежит в основе ряда алгоритмов. Рассмотрим один из них.

3.4.4. АЛГОРИТМ ХУКА – ДЖИВСА

Этот алгоритм содержит две основные процедуры:

а) исследующий покоординатный поиск в окрестности данной точки, предназначенный для определения направления убывания f (х);

б) перемещение в направлении убывания.

Опишем алгоритм исследующего покоординатного поиска из заданной точки х с приращениями по каждой координате _j , j= 1, …, n

Шаг 1. Положить = x , i= 1.

Шаг 2. Сделать пробный шаг y= – _je ^j, где e ^j –j–й базисный вектор. Если f ( ) f (y), то перейти к шагу 3, иначе – к шагу 4.

Шаг 3. Сделать пробный шаг y= +_je ^j . Если f ( ) f (y), то перейти к шагу 5, иначе – к шагу 4.

Шаг 4. Положить = у.

Шаг 5. Положить j= j+ 1. Если j n, то перейти к шагу 2. В противном случае исследующий поиск окончен – получена точка для которой f ( ) <f (y), если  х.

Замечание. В результате исследующего поиска может оказаться, что =х. Тогда исследующий поиск считается неудачным. Если при этом норма приращения  =(₁,.., _n ) мала, т.е. |||| , где  – заданная точность, то полагают х^* = х. Если заданная точность не достигнута, то полагают =/ (постоянная  >1 – коэффициент уменьшения шага) и повторяют исследующий поиск.

Приведем теперь полный алгоритм Хука – Дживса.

Шаг 0. Выбрать начальную точку х⁰ , вектор приращений  =(₁,.., _n ), коэффициент уменьшения шага  >1, параметр окончания поиска  > 0.

Шаг 1. Провести исследующий покоординатный поиск из точки х⁰, т.е. найти точку . Если  х , то перейти к шагу 3, иначе – к шагу 2.

Шаг 2. Проверка на окончание поиска. Если ||||<, то прекратить поиск и положить х^*=х⁰. Иначе – положить =/ и перейти к шагу 1.

Шаг 3. Перемещение из точки х в направлении убывания – х⁰ : положить х¹ = + ( – х⁰) = 2 – х⁰ .

Шаг 4. Провести исследующий поиск в точке х¹ , т.е. найти точку . Если f ( ) < f ( ), то положить х⁰ = , = и перейти к шагу 3. Иначе – положить х⁰ = и перейти к шагу 1.

Пример 3.7. Рассмотрим графическую иллюстрацию решения задачи f (х)=(x₁+ 1)²+х²₂ min методом Хука – Дживса из начальной точки х⁰ =(2,3), вектор перемещений =(1/2,1).

Целевая функция f (х) представляет собой квадрат расстояния между точками х и х^* =(–1,0). Линии уровня f (х) – это окружности с центром в точ­ке х^*. Поэтому значения f (х) в промежуточных точках алгоритма легко сравни­вать, оценивая их расстояния от точки х^* на рис. 3.9. На рисунке пунктиром выделены траектории исследующего поиска, сплошными линиями – перемещения в направлении убывания. Убеди­тесь в соответствии графической иллю­страции описанному алгоритму.

Рис. 3.9. К примеру 3.7

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

Однако разработано довольно много методов минимизации, где в процедуру поиска точек минимума намеренно вводят эле­менты случайности.

3.4.5. МЕТОДЫ СЛУЧАЙНОГО ПОИСКА

Основой для этих методов служит итерационный процесс

, k = 0, 1, …, (3.41)

где _k > 0 – величина шага;  =(₁ , …, _n ) – некоторая реализация n – мерного случайного вектора .тБудем считать, что координаты вектора , – это независимые слу­чайные величины, равномерно распределенные на отрезке [–1; 1]. При­ведем несколько алгоритмов метода случайного поиска. Они могут ис­пользоваться как самостоятельные минимизирующие процедуры, или входить в состав других алгоритмов, например, использоваться для исследующего поиска в алгоритме Хука – Дживса.

Алгоритм 1 (с возврaтом при неудaчном шaге).

Шаг 0. Выбрать параметр точности  > 0, начальный шаг  >0, коэффициент уменьшения шага  >1, предельное число неудачных попыток N, начальную точку х. Вычислить f (х).

Шаг 1. Положить счетчик числа неудачных попыток j= 1.

Шаг 2. Получить реализацию случайного вектора .

Шаг 3. Найти пробную точку y=x+/||||, вычислить f (у).

Шаг 4. Если f (у)< f (х), то положить х = у, f (х) = f (у) и перейти к шагу 3. Иначе – перейти к шагу 5.

Шаг 5. Положить j =j + 1. Еслиj < N, то перейти к шагу 2, иначе к шагу .

Шаг 6. Проверка условия достижения точности. Если  < , то поиск завершить, полагая х^*=х, f  ^*= f (х). Иначе – положить  = /у и перейти к шагу 1.

Иллюстрация построения последовательности (3.41) с помощью описанного алгоритма для функции двух переменных приведена на рис. 3.10, где пунктиром показаны неудачные попытки определения х^k+1 из (3.41), не приводящие к уменьшению f (х).



Рис. 3.10. Иллюстрация работы алгоритма 1 в пространстве Е₂.

Замечание. На практике предельное число неудачных попыток N обычно полагают равным 3п, где п – число переменных целевой функции.

Алгоритм 2 (наилучшей пробы).

Этот алгоритм отличается от предыдущего только шагами 2 и 3:

Шаг 2. Получить т реализации случайного вектора :

¹ , …, ^m

Шаг 3. Найти пробные точки yⁱ = , i = 1,.., т, вы­делить f (уⁱ). Найти у^k из условия f (у^k)= и положить у= у^k .

3.4.6. МЕТОД СОПРЯЖЕННЫХ НАПРАВЛЕНИЙ

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

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

Рассмотрим сначала проблему поиска точки минимума сильно выпуклой квадратичной функции двух переменных. Ее линиями уровня являются эллипсы (рис. 3.11). Пусть р¹ и р² – направления главных осей этих эллипсов (они могут быть найдены как ортонормированный базис из собственных векторов матрицы A квадратичной функции). Ес­ли из произвольной точки х⁰E₂ выполнить итерационную процедуру х^k = х + _kр^k , k= l, 2, где величина шага _k находится из условия исчерпывающего спуска, то, очевидно, потребуется не более двух ша­гов для отыскания точки х^*.




Рис. 3.11. Минимазация строго выпуклой квадратичной функции двух переменных по направлениям главных осей методом наискорейшего спуска.

Такого же результата можно достичь и другим способом. Выберем некоторое направление р¹ и две точки х⁰ и у⁰ такие, чтобы векторы х⁰ – у⁰ и р¹ были неколлинеарны (рис. 3.12). Выполнив исчерпывающий спуск из точек х⁰ и у⁰ в направлении р¹ , получим точки х¹ и у¹ . По свойству исчерпывающего спуска в точках х¹ и у¹ имеет место касание соответствующих прямых (направлений убывания) и эллипсов (линий уровня целевой функции). Так как эллипсы различаются гомотетией с центром в точке х^* , то точки х^* , х¹ и у¹ расположены на одной пря­мой. Поэтому, полагая р² = х¹–у¹ и решая задачу f (х¹ + р²)  min , мы находим точку х^*. Таким образом, и в этом случае решение задачи ми­нимизации квадратичной сильно выпуклой функции будет получено за конечное число шагов.



Рис 3.12. Определение направления p² в процессе минимзации сильно выпуклой квадратичной функции двух переменных



Рис. 3.13. Минимизация квадратичной функции

Рассмотренному способу минимизации квадратичных функций двух переменных соответствует, например, такой алгоритм.

Шаг 0. Выбрать начальную точку х⁰  Е₂.

Шаг 1. Положить р¹ =е¹ . Найти точку х¹ с помощью исчерпывающего спуска из точки х⁰ по направлению р¹: f (х¹) = .

Шаг 2. а) положить у=х +с;

б) найти точку у из условия исчерпывающего спуска из точки у⁰ по направлению р¹: f (y¹) = ;

в) положить р² = х¹–у¹, найти точку x² из условия f (х²)= , вычисления закончить, положив х^*= x² .

Графическая иллюстрация работы алгоритма представлена на рис. 3.13. Поиск точки минимума доводится по так называемым сопряженным направлениям.

Определение 3.8. Ненулевые векторы р¹,..,р^k называются сопряженными относительно матрицы A размера (п п) (А–ортогональными), если

i, p^j> = 0, i  j , i,j = 1, …, k. (3.42)

Пример 3.8. Направления р¹ и р² , использованные в описанном выше алгоритме минимизации квадратичной функции двух переменных, являются A–ортогонaльными.

Рассмотрим скалярное произведение

2,p¹>=1–y¹), p¹>=1) – f  (y¹), p¹> = < f  (x¹), p¹> – 1), p¹>.

Так как точки х¹ и у¹ получены в результате исчерпывающего спуска по направлению р¹, то оба скалярных произведения < f  (x¹), p¹> и 1), p¹> равны нулю (см. (3.34)), поэтому 2, p¹> = 0.

Лемма 3.1. Система из п векторов р¹ , .., рⁿ, сопряженных относительно положительно определенной матрицы A, линейно незaвисимa.

Предположим противное, т.е. что существует линейная комби­нация, равная нулю:

, (3.43)

где не все _i = 0, например _k  0. Умножим обе части равенства (3.43) скалярно на вектор Aр^k . Тогда, с учетом свойства (3.42), полу­чим _k<Aр^k, р^k>=0. В силу положительной определенности матрицы A для ненулевого вектора р^k квадратичная форма <Aр^k, р^k> прини­мает положительное значение и, следовательно, _k = 0. Полученное противоречие доказывает лемму.

Таким образом, п ненулевых A–ортогональных векторов образуют базис в E_n .

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

f (х) = 1/2< Aх, х >+< b, х >+с

с положительно определенной матрицей A с помощью итерационного процесса

x^k = x^k–1 + _k p^k , k=1, 2, …, (3.44)

где векторы р^k A–ортогональны.

Лемма 3.2. Если в итерационном процессе (3.44) нa кaждом шaге используется исчерпывaющий спуск, то величинa шaгa _k будет

, k=1, 2, …, (3.45)

Раскрывая рекуррентную формулу (3.44), получаем

. (3.46)

Из формулы (3.46), учитывая выражение для градиента квадратичной функции f  '(x) = Aх + b, находим

.

(Умножая обе части этого равенства скалярно на вектор р^k и учитывая условие исчерпывающего спуска по направлению р^k ( < f  (x^k), р^k > = 0) и A–ортогональность векторов (3.42), получаем

< f  (x⁰), р^k > + _k <Aр^k,р^k> = 0.

Так как матрица A положительно определена, квадратичная форма <Aр^k,р^k>>0 и для величины шага _k получаем выражение (3.45).

Теорема 3.9. Последовaтельный исчерпывающий спуск по A–ортогонaльным нaпрaвлениям (3.44) приводит к точке минимумa квaдрaтичной функции не более чем зa п шaгов.

Согласно лемме 3.1 векторы р¹ ,.. ,рⁿ образуют базис в E_n , поэтому будем искать точку минимума х^* в виде

, (3.47)

где х⁰ – произвольная точка E_n. Подставим выражение (3.47) в необходимое и достаточное условие минимума сильно выпуклой квадратной функции f  '(х^*) = Aх^* + b = 0:

Ax⁰ + b + .

Умножая это равенство скалярно на вектор р^k , находим

< f  (x⁰), р^k > + u_k <Aр^k,р^k> = 0.

или

.

Коэффициенты разложения u_k точки х ^*– х по базису р¹ , совпадают с длинами шагов _k исчерпывающего спуска (3,45) в итерационном процессе (3.44). Поэтому определение точки х^* из (3.47) можно рассматривать как результат п шагов итерационного процесса (3.44), где _k = u_k.

Таким образом, точка минимума квадратичной функции будет найдена не более чем за п шагов.

Вопрос о нахождении базиса из A–ортогональных векторов в пространстве Е_n решается неоднозначно. В качестве такого базиса можно, например, взять ортогональный базис из собственных векторов матрицы A. Однако их поиск особенно при п > 2 представляет собой само­стоятельную довольно сложную задачу.

Итерационный процесс (3.44) последовательной одномерной ми­нимизации по сопряженным направлениям р^k можно организовать и без предварительного построения векторов р¹ , .., рⁿ, последователь­но находя их в процессе минимизации, как это было сделано выше для функции двух переменных.

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

Шаг 0. Выбрать начальную точку х⁰ Е_n .

Шаг 1. Положить р¹=е¹ . Найти точку х¹ из условия f (х¹)= .

Шаг 2. а) положить у⁰ =х¹+е² ;

б) найти точку у¹ из условия f (у¹)= ;

в) положить р¹ = х¹– у¹, найти точку х² из условия f (х²)= .

Шаг 3. а) положить у¹ = х² + е³;

б) найти у² , минимизируя f (x) последовательно по направлениям р¹ и р² , начиная из точки у¹;

в) положить р³ = х² – у² найти точку х³ из условия f (х³)= .

Шаг n. а) положить у^n–1 = х^n–1 + е ⁿ;

б) найти точку у ⁿ, минимизируя f (х) последовательно по направ­лениям

р¹,. ., р^n–1, начиная из точки у^n–1.

в) положить р ⁿ= х ^n–1 – у ^n–1, найти точку хⁿиз условия f ( х ⁿ)= .

Замечание. Как и в двумерном случае, можно показать, что направления р¹,.., рⁿ , построенные при выполнении этого алгоритма, являются A–ортогональными. Поэтому, если f (х) является квадратичной функцией с положительно определенной матрицей A и все задачи одномерной минимизации решаются точно, то х^* = хⁿ и вычисления на этом завершаются. Если же f (х) не является квадратичной фунцией или вспомогательные задачи одномерной минимизации решаются приближенно, то необходимо перейти к следующему шагу.

Шаг n + 1. (проверка условия останова). Если ||x⁰–xⁿ||  , где  – параметр точности, то поиск завершить, полагая х^* = хⁿ, иначе – положить х⁰ = хⁿ и перейти к шагу 1.

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

1   2   3   4   5   6   7   8   9   10

---

УПРАЖНЕНИЯ

1. Проверить, что точки хⁱ , i=0, .., n, удовлетворяющие формулам (3.37), являются вершинами некоторого правильного симплекса.2. Выполнить несколько итераций решения задачи f (x)=(x₁ + 1)² + x²₂min с помощью правильного симплекса, положить х⁰ = (5,3) и а = 1. Привести графическую иллюстрацию.Указание: линии уровня целевой функции – окружности с центром в точке (–1, 0).3. Как изменится процедура поиска точки минимума в упражнении 2 при использовании деформируемого симплекса? Дать графическую иллюстрацию (положить  = 0,5, = 1 и  = 2).4. Нарисовать линии уровня целевой функции из примера 3.6 и пояснить медленную сходимость метода циклического покоординатного спуска.5. Можно ли в исследующем поиске алгоритма Хука – Дживса использовать направления р¹ , .., рⁿ , отличные от базисных векторов е¹ , .., еⁿ ? Должны ли они быть линейно независимыми?6. Выполнить четыре итерации решения задачи f (x)=(x₁ + 1)² + x²₂  min методом Хука – Дживса. Положить  = 1/2,  = (2,1), х⁰ = (3,4). Привести графическую иллюстрацию.7. Из начальной точки х =(4,3) решить зaдaчу f (x)= 5x²₁ + 5x²₂ + 8x₁x₂  min методом сопряженных направлений.Указание: для величины шага _k использовать формулу (3.35).8. Показать, что взаимно ортогональные собственные векторы симметрической положительно определенной матрицы A являются A–ортогональными. 9. Проверить, что векторы р¹ = (1, 2) и р² = (5, –1) А–ортогональны относительно матрицы А = . Найти минимум функции f (x)= 3x²₁ – 2x₁x₂ + 3x²₂ + x₁ + 2x₂, выполняя наискорейший спуск последовательно по направлениям р¹ и р² .

3.5. МЕТОДЫ БЕЗУСЛОВНОЙ МИНИМИЗАЦИИ, ИСПОЛЬЗУЮЩИЕ ПРОИЗВОДНЫЕ ФУНКЦИИ

Пусть функция f (x) дифференцируема в E_n . В этом разделе рас­сматриваются итерационные процедуры минимизации видаX ^k = x ^k–1 + _k p ^k, k =1, .., x⁰  E_n, (3.48)где направление убывания р^k определяется тем или иным способом с учетом информации о частных производных функции f (x

---

), а величина шага а^>0 такова, чтоf (x ^k) < f (x ^k–1), k =1,2,.. (3.49)Так как функция предполагается дифференцируемой, то в ка­честве критерия останова в случае бесконечной итерационной по­следовательности {х^k}, как правило, выбирается условие (3.30): ||f '(x^k )|| <, хотя, разумеется, могут быть использованы и другие критерии.

3.5.1. МЕТОД ГРАДИЕНТНОГО СПУСКА

Положим в (3.48) на каждом шаге р^k = –f  (x ^k). Если f  (x ^k)  0, то условие (3.36) очевидно выполнено, т.е. направление вектора р^k явля­ется направлением убывания функции f (х), причем в малой окрестно­сти точки x^k направление р^k обеспечивает наискорейшее убывание этой функции. Поэтому можно найти такое _k > 0, что будет обеспе­чено выполнение условия (3.49).Приведем алгоритм одного из вариантов метода градиентного спуска.Шаг 0. Задать параметр точности  > 0, начальный шаг > 0, подобрать х  E_n. Вычислить f (х). Шаг 1. Найти f '(x) и проверить условие достижения точности:||f '(x)|| < . Если оно выполнено, вычисления завершить, полагая х^* = х, f ^*=f (х). Иначе – перейти к шагу 2.Шаг 2. Найти y=x–f '(x) и f (у). Если f (у) < f (х), то положить x =у, f (х) = f (у) и перейти к шагу 1, иначе – перейти к шагу 3.Шаг 3. Положить =/2 и перейти к шагу 2. Замечание. Вблизи стационарной точки функции f (x) величина ||f '(x)|| становится малой. Это может приводить к замедлению сходимости последовательности {х^k}. Поэтому иногда в (3.48) полагают p^k = – f '(x^k)/ ||f ' (x^k)|| , т.е. вместо –f '(x^k) используют вектор единичной длины того же направления.Приведем теоретическое обоснование сходимости градиентного метода с постоянным шагом _k  ;x^k+1= x^k–f '(x^k) (3.50)и получим оценку скорости сходимости при минимизации выпуклой вадратичной функции f (х)= <Ах, х>+>+ с.

Теорема 3.10. Пусть симметрическaя мaтрицa A квaдрaтичной функции f (х) положительно определенa, l и L – ее нaимень­шее и нaибольшее собственные знaчения (0 < lL). Тогдa при любых  (0; 2/L) и х⁰E_n итерaционнaя последовaтельность (3.50) сходится к единственной точке глобaльного минимумa функции f (х) линейно (со скоростью геометрической прогресcии (см. рaзд. 3.4)):

||(x^k – x^*)|| q^k ||(x⁰ – x^*)|| , (3.51)

где q = max {|1 – l|, |1 – L|}.

Так как матрица A положительно определена, функция f (х) cильно выпукла и, следовательно, точка х^* существует и единственна. Градиент f '(x) в этой точке обращается в нуль, т.е. f '(x^*)=Аx^*+b=0. Для точки х^k имеем: f '(x^k)=Аx^k+b= Аx^k+b – Аx^*– b = А(x^k–x^*). Оценим норму разности

||(x^k – x^*)|| = ||x^k – f '(x^k–1) – x^*|| = ||x^k–1 – x^* – A(x^k–1 – x^* )|| = || (E– A)(x^k–1 – x^* )||.
По свойству норм (3,6) имеем:

||x^k – x^*||  ||E– A||||x^k–1 – x^*||. (3.52)

Оценка сверху для нормы матрицы (3,7) дает:

||E– A||  q = max { |1– l|, |1– L| }. (3.53)

Зависимость q() представлена на рис. 3.14, из которого видно, что при  (0; 2/L) величина q < 1. Кроме того, из неравенств (3.51) и (3.53) получаем: ||x^k – x^*||  q ||x^k–1 – x^*|| , т.е. ||x^k – x^*||  q^k ||x⁰ – x^*||.



Рис 3.14. Зависимость оценки знаменателя геометрической прогрессии

Из рис. 3.14 видно, что вели­чина q принимает минимальное значение q^*=(L – l)/(L + l) при  =^* =2/(L + l). Поэтому от соотношения между L и l суще­ственно зависит число итераций градиентного метода при мини­мизации выпуклой квадратичной функции. Проиллюстрируем это на примере квадратичной функ­ции двух переменных.

При L = l> 0 точка минимума f (х) находится за один шаг.

Пример 3.9. Решить задачу f (x) =x²₁ +х²₂  min градиентным методом из начальной точки х⁰ = (1,1), положив  =^*.

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

.

Очевидно, l= L= 2. Поэтому

^* = 2/(L + l) = 1/2 и х¹ = х⁰ – f  '(х⁰) = (0,0).

Легко проверить, что х⁰ = х¹ .

При l= L линии уровня целевой функции f (x) – это концентриче­ские окружности, поэтому направление антиградиента указывает на центр этих окружностей, т.е. на точку глобального минимума f (х).

Если L>> l > 0, то линиями уровня являются эллипсы, полуоси ко­торых сильно различаются. Поэтому направление антиградиента в не­которой точке может сильно отличаться от направления к точке гло­бального минимума.

Пример 3.10. Из начальной точки х⁰=(1, 1) выполнить несколько итераций поиска точки минимума функции f (х) = x²₁ + 100х²₂ градиентным методом, полагая  =^*.

Собственные значения матрицы A этой квадратичной функции равны: l = 2, L = 200. Линиями уровня f (x) являются эллипсы, сильно вытянутые вдоль oси Ox₁. Поэтому в точке х⁰ направление вектора антиградиента –f ' (х⁰) = (– 2, – 200) сильно отличается от направления к точке глобального минимума х^*–х⁰ = (–1,–1). Положив в формуле (3.50)  =^*2/(l+L)=1/101, получим с учетом выражения для градиента f  '(x)=(2x₁, 200x₂) следующий закон изменения координат точек минимизирующей последовательности: x₁^k+1= x^k₁99/101; x₂^k+1= –x₂^k99/101. Отсюда видно, что последовательность {х^k} сходится к точке глобального минимума медленно и траектория сходимости имеет ярко выраженный зигзагообразный характер.

В курсе линейной алгебры для симметрической положительно оп­ределенной матрицы вводится число обусловленности матрицы =L/l – отношение наибольшего к наименьшему собственному значению. В задаче минимизации произвольной (не обязательно квадра­тичной) сильно выпуклой функции f (х) эта величина для матрицы ее вторых производных (гессиана) характеризует степень вытянутости линий (поверхностей) уровня f (х)=с. Очевидно, что всегда   . Если  велико, то линии (поверхности) уровня сильно вытянуты и говорят, то функция имеет овражный характер, т.е. резко меняется по одним управлениям и слабо – по другим, В подобных случаях задачу минимизации называют плохо обусловленной (см. пример 3.10). Если же  близко к единице, то линии (поверхности) уровня близки к окружностям (сферам) и задача минимизации является хорошо обусловлен­ной (см. пример 3.9).

3.5.2. МЕТОД НАИСКОРЕЙШЕГО СПУСКА

В этом варианте градиентного метода также полагают p^k =–f '(x^k) и величина шага ^k из (3.37) находится в результате ре­шения задачи одномерной минимизации

Ф_k()  min, где Ф_k() =f (x^k – f  '(х^k)),  > 0, (3.54)

т.е. на каждой итерации в направлении антиградиента –f '(x^k) совер­шается исчерпывающий спуск. Опишем алгоритм метода.

Шаг 0. Задать параметр точности  > 0, выбрать х E_n .

Шаг 1.Вычислить f '(x) и проверить условие достижения точно­сти: ||f '(x) ||<. Если оно выполнено, то положить х^*= х, f *=f (х) и по­иск завершить, иначе – перейти к шагу 2.

Шаг 2. Решить задачу одномерной минимизации (3.54) для х^k = х, т.е. найти ^*. Положить x = x–^*f '(x) и перейти к шагу 1.

Замечание. Решение задачи (3.54) можно получить одним из способов, описанных в гл. 2. Если функция f (х) квадратична, то для величины шага исчерпывающего спуска можно воспользоваться фор­мулой (3.35) при р^k=–f  (х^k).

Пример 3.11. Рассмотрим функцию f (х) = x²₁ + 100х²₂ и используем метод наискорейшего спуска для решения задачи ее минимизации из начальной точ­ки х⁰=(1,1).

Найдем компоненты градиента , и и гессиан . Величину шага исчерпывающего спуска найдем по формуле (3.35). Результаты вычислений приведены в табл. 3.3.
Тaблицa 3.3

Номер итерации	xk1	xk2	f (xk)	||f  (xk)||
0	1	1	101	200
1	9,910–1	–9,910–5	9,810–1	1,98
2	9,710–3	9,710–3	9,510–3	1,94
3	9.610–3	–9,610–7	9,210–5	1,9210–2

Сравните с решением примера 3.10.

3.5.3. МЕТОД СОПРЯЖЕННЫХ ГРАДИЕНТОВ

До сих пор в итерационной процедуре (3.48) в качестве направле­ния убывания функции f (х) мы использовали направление антиградиента: (х^k) . Однако такой выбор направления убывания не всег­да бывает удачным. В частности, для плохо обусловленных задач ми­нимизации направление антиградиента в точке х^k может значительно отличаться от направления к точке минимума х^*. В результате траек­тория приближения к точке минимума имеет зигзагообразный харак­тер (см. пример 3.10).

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

х^k+1= х^k + _kр^k , k = 0, 1, …; x⁰ E_n , p⁰ = –f  (х⁰), (3.55)

в котором величина шага находится из условия исчерпывающего спуска по направлению р^k. После вычисления очередной точки х^k+1, k = 0, 1,… новое направление поиска р^k+1 находится по формуле

р^k+1=–f  ( х^k+1) + _kp^k , k = 0, 1, …, (3.56)

где коэффициенты _k выбираются так, чтобы при минимизации квад­ратичной функции f (х) с положительно определенной матрицей A получалась последовательность А–ортогональных векторов р⁰, р¹,… Из условия <Aр^k+1,р^k+1>=0 имеем:

. (3.57)

Напомним, что для квадратичной функции шаг исчерпывающего спуска по направлению р^k равен

. (3.58)

Можно показать, что процесс (3.55)–(3.58) минимизации квадра­тичной функции с положительно определенной симметрической мат­рицей A дает точки х⁰, .., х^k и векторы р⁰, …, р^k такие, что если f  (xⁱ) при 0  i< k n–1, то векторы р⁰, …, р^k A–ортогональны, а градиенты f '(x⁰), .., f '(xⁱ) взаимно ортогональны.

Обращение градиента в нуль в очередной точке х^k итерационного процесса свидетельствует о достижении точки глобального минимума. Так как направления р^k в (3.55) являются A–ортогональными, рассмат­риваемый метод гарантирует нахождение точки минимума сильно выпуклой квадратичной функции не более чем за п шагов (см. теорему 3.9).

С учетом взаимной ортогональности градиентов f '(xⁱ) и условий исчерпывающего спуска по направлениям р^k можно упростить выра­жения (3.57) и (3.58). Выразим числитель дроби (3.58):
k),p^k>= k), –f  (x^k) + _k–1p^k–1> = –f  (x^k)² +_k–1k), p^k–1> =–f (x^k)².

(3.59)

Умножив обе части равенства (3.55) слева на матрицу Aи приба­вив к ним по вектору b, получим

f  (x^k+1)= f  (x^k)+ _k Aр^k . (3.60)

С учетом формулы (3.60) упростим числитель в выражении (3.57) для _k следующим образом:

<Af  (x^k+1), р^k > = k⁺¹),

Aр^k > = k⁺¹), > = . (3.61)

В результате выражения для _k и _k примут вид
; (3.62)

. (3.63)

Выражение (3.63) для коэффициента _k не содержит в явном виде матрицу A квадратичной функции. Поэтому метод сопряженных гра­диентов может применяться и для минимизации неквадратичных фун­кций. В этом случае итерационный процесс метода описывается соот­ношениями:

x^k+1 =x^k + _kp^k , x⁰  E_n , p⁰ = –f  (x⁰), k= 0, 1, …;  (3.64)

f (x^k + _kp^k) = , k= 0, 1, …; (3.65)

p^k+1= –f  (x^k+1) + _kp^k , k= 0, 1, …; (3.66)

, k= 0, 1, …; (3.67)
Разумеется, процесс (3.64)–(3.65) может не приводить к точке минимума функции f (х), отличной от квадратичной, за конечное число итераций. Далее, точное определение _k из условия (3.65) возможно лишь в редких случаях. Поэтому реализация каждой итерации метода будет сопровождаться неизбежными погрешностями. Эти погрешно­с­ти, накапливаясь, могут привести к тому, что векторы р^k перестанут указывать направление убывания функции и сходимость метода может нарушиться. Поэтому на практике в методе сопряженных градиентов через N шагов производят обновление метода, полагая _mN= 0, m = 1, 2, .. Номера mN называются моментами обновления метода (реcтарта). Часто полагают N=n – размерности пространства E_n . Если N=1, то получается частный случай метода сопряженных градиентов – метод наискорейшего спуска.

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

Шаг 0. Задать параметр точности  > 0, выбрать x⁰  E_n, найти f  (х⁰).

Шаг 1. Положить k= 0, р⁰ =–f  (х⁰).

Шаг 2. Решить задачу одномерной минимизации f (х^k + р^k)min,  > 0, т.е. найти  = _k .

Шаг 3. Положить х^k+1 = х^k + р^k и вычислить f '(х^k+1). Проверить условие достижения точности: ||f '(х^k+1)|| < . Если оно выполняется, то положить х⁰=х^k+1, f '(x⁰)=f '(х^k+1) и закончить поиск, иначе – перейти к шагу 4.

Шаг 4. Проверить условие k+ 1 = n. Если оно выполняется, то положить х⁰=х^k+1, f '(x⁰)=f '(х^k+1) и перейти к шагу 1 (рестарт), иначе – перейти к шагу 5.

Шаг 5. Вычислить коэффициент _k = ||f '(х^k+1)||2/ ||f '(х^k)||2 и найти новое направление поиска р ^k+1 =–f '(х^k+1)+ _kр ^k . Положить k=k+1 и перейти к шагу 2.

Замечание. Вблизи точки минимума дважды дифференцируемая функция с положительно определенной матрицей Гессе f ''(х^*), как правило, достаточно хорошо аппроксимируется квадратичной функцией. Поэтому можно надеяться на хороший результат применения этого метода для таких функций.

Пример 3.12. Методом сопряженных градиентов найти точку минимума функции f (x)=4x²₁ + 3x²₂ – 4 x₁x₂ + x₁ из начальной точки x⁰ = (0, 0).

Итерация 1.

Шаг 0. Положим  = 0,01, x⁰ = (0, 0), найдем f '(х⁰) = (1, 0)

Шаг 1. Положим k= 0, p⁰ = –f '(х⁰) = (–1, 0)

Шаг 2. Решим задачу одномерной минимизации f (х⁰ + р⁰)min. Получим ₀ = 1/8 (для нахождения ₀ можно было воспользоваться формулой (3.35).

Шаг 3. Найдем x¹ = х⁰ + ₀р⁰ = (–1/8, 0) и f '(х⁰) = (0, 1/2). Точность не достигнута, перейдем к шагу 4.

Шаг 4. Условие k +1=n не выполняется, перейдем к шагу 5.

Шаг 5. Найдем коэффициент ₀ и новое направление спуска p¹ = –f '(х¹) + ₀р⁰ = (–1/4, –1/2).

Итерация 2.

Шаг 2. Решим задачу одномерной минимизации f (х¹ + р¹)min. Получим ₁ = 1/4.

Шаг 3. Найдем x² = х¹ + ₁р¹ = (–3/16, –1/8) и f '(х²) = (0, 0). задача решена точно.

Таким образом, x^* = x² . Решение получено в результате двух итераций метода сопряженных градиентов, поскольку целевая функция квадратична в E_n и одномерные задачи минимизации на шаге 2 алгоритма решены точно.

3.5.4. МЕТОД НЬЮТОНА

Пусть функция f (x) дважды дифференцируема в E_n . Тогда для нее можно записать разложение по формуле Тейлора в окрестности точки x^k :

f (x) = f (х^k) + <f '(х^k), x–x^k > + <f (х^k)(x–x^k), x–x^k > +( || x–x^k ||2 )

Отсюда видно, что поведение функции f (x) с точностью до величины порядка ( || x–x^k ||2 ) может быть описано квадратичной функцией

Ф_k(x) = <f (х^k)(x–x^k), x–x^k > + <f '(х^k), x–x^k > + f (х^k). (3.68)

Минимизируем функцию Ф_k(x) вместо f (x). Найдем ее точку минимума x^k+1 из условия Ф_k(x) = 0:

Ф_k(x) = f (х^k)(x–x^k) + f (х^k) = 0. (3.69)

Пусть матрица Гессе f (х^k) положительно определена при всех xE_n и, следовательно, невырождена (det f (х^k) > 0). Тогда существует обратная матрица [f (х^k)]^–1. Отметим, что квадратичная функция (3.68) с положительно определенной матрицей f (х^k) сильно выпукла и уравнение (3.69) определяет единственную точку глобального минимума функции Ф_k(x). Умножим слева обе части равенства (3.69) на матрицу [f (х^k)]^–1 и найдем точку минимума x^k+1 квадратичной функции (3.68), аппроксимирующей f (x) в окрестности точки

x=x^k :

x^k+1 = x^k – [f (х^k)]^–1f (х^k) , k = 0, 1, … (3.70)

Итерационный процесс ––, начатый из произвольной точки x⁰E_n, называется методом Ньютона минимизации функции многих переменных и является обобщением метода Ньютона в одномерном случае (см. разд. 2.3.3).

Очевидно, для квадратичной функции с положительно определенной матрицей A применение метода Ньютона обеспечивает получение точки глобального минимума ровно за один шаг из любой точки x⁰E_n.

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

При выборе достаточно хорошего начального приближения x⁰E_n минимизирующая последовательность {x^k} для сильно выпуклой дважды дифференцируемой функции f (x) сходится к точке минимума с квадратичной скоростью (x^k, x^*) , q(0, 1). Если же точка x⁰ выбрана недостаточно близкой к точке х^*, то последовательность (3.70) может расходиться (см. разд. 2.3.3).

Отметим, что даже сходящаяся последовательность {x^k} метода Ньютона не всегда обеспечивает монотонное убывание f (x), т.е. нера­венство f (x^k+1) < f (x^k) для некоторых k=0,1,.. может нарушаться Этот недостаток устранен в обобщенном методе Ньютонa:

x^k+1 = x^k – _k[f  (x^k)]^–1f (x^k),

где величина _k > 0 находится на каждом шаге из условия исчерпыва­ющего спуска по направлению р^k = –[f  (x^k)]^–1f  (x^k).

Недостатком метода Ньютона является необходимость вычисле­ния и обращения матрицы Гессе на каждой итерации.

Пример 3.13. Найти точку минимума функции f (x)=4x²₁ + 3x²₂ – 4 x₁x₂ + x₁,методом Ньютона из начальной точки х⁰ = (0,0).

Градиент f (x⁰)=(–1,0), матрица Гессе

f  "(х⁰)=А= .

Найдем обратную матрицу [f (х⁰)]^–1 = . С помощью формулы (3.70) получаем x¹=x⁰–_k[f (х⁰)]^–1f (x⁰)=(–3/16, –1/8). Так как f '(x¹)=(0,0), то задача решена: х^* = х¹. Целевая функция квадратична, поэтому решение задачи по­лучено за одну итерацию.

3.5.5. КВАЗИНЬЮТОНОВСКИЕ МЕТОДЫ

Стремление уменьшить объем вычислений привело к созданию класса методов, близких по скорости сходимости к обобщенному ме­тоду Ньютона, но не использующих вторых производных целевой фун­кции f (х) и процедуры обращения матрицы f "(х). В методах этого типа используется итерационный процесс

X ^k+1 = x ^k –  _kH^(k) f (х^k), (3.71)

где H^(k) – некоторая квадратичная матрица размера п п, а величина шага _k> 0 выбирается из условия исчерпывающего спуска вдоль на­правления

р^k = –H^(k) f (х^k). В частности, если H^(k) = –[f (х^k)]^–1 , то процесс (3.71) представля­ет собой обобщенный метод Ньютона.

В квазиньютоновских методах матрица H^(k) строится с помощью рекуррентных формул на каждом шаге процесса (3.71). Вид этих формул определяет метод. Рассмотрим в качестве примера метод Давидона – Флетчера – Пауэла (ДФП – метод). Рекуррентная формула для H^(k) имеет вид

H^(k+1) =H^(k) + А^(k) + В^(k) , H⁽⁰⁾ = Е, А⁽⁰⁾ = В⁽⁰⁾ = 0 . (3.72)

| Матрицы А^(k) и В^(k) выражаются на каждом шаге через матрицу H^(k) и векторы–столбцы v^k = x^k+1 – x^k , u^k = f  (x^k+1) – f  (x^k) следую­щим образом (см. (3.4)):

, (3.73)

.

Пусть в итерационном процессе (3.71)–(3.73) при минимизации выпуклой дифференцируемой функции f (х) в очередной точке хⁱ градиент f '(хⁱ)  0, т.е. точка минимума f (х) еще не достигнута. Тогда все направления р^k = –H^(k)f '(х^k), iявляются направлениями убывания функции f (х).

Для доказательства этого утверждения запишем условие убывания (3.36) для направления р^k :

<р ^k , f  ' (х ^k)> = –< H^(k) f  ' (х ^k), f  ' (х ^k)> < 0.

Докажем по индукции, что для всех k i,H^(k)– симметрическая положительно определенная матрица– Очевидно, H⁽⁰⁾=Е обладает этими свойствами. Отметим, что из соотношений (3.72) и (3.73) следует, что матрица H^(k) является симметрической как линейная комбинация симметрических матриц. Предположим, что H^(k) положительно определена и докажем, что это справедливо и для матрицы H^(k+1) . Рассмотрим квадратичную форму <H^(k+1)х,х> при х  0:

<H^(k+1)х,х> = <H^(k) х,х> + – . (3.74)

Представим симметрическую матрицу H^(k) в виде H^(k) = С С^Т = С^ТС , где С – некоторая квадратная матрица размера nn Обозначим векторы Cx = q, а Cu^k = r, тогда равенство (3.74) можно записать в виде

<H^(k+1)х,х> = 2 – + .

(3.75)

Из неравенства Коши – Буняковского (3.2) следует, что q²r²  ² поэтому из (3.75) получим неравенство:

<H^(k+1)х, х>  .

Оценим скалярное произведение в знаменателе правой части неравенства (3.76) с учетом свойства исчерпывающего спуска:

k, u^k> = < x^k+1 – x, f  (x^k+1) – f  (x^k)> = _k< p^k, f  (x^k+1) – f  (x^k) > = _k< p^k, f  (x^k) > = _k< H^(k)f  (x^k), f  (x^k) > > 0

Из неравенства (3.76) видно, что <H^(k+1)х, х > > 0, т.е. матрица H^(k+1)так­же положительно определена.

Можно показать, что для квадратичной функции с положительно определенной матрицей A направления р^k в методе ДФП оказываются A–ортогональными. Отсюда следует, что точка минимума такой квад­ратичной функции этим методом будет найдена не более чем за п ите­раций.

Приведем описание алгоритма метода ДФП.

Шаг 0. Задать параметр точности  > 0, выбрать х  Е_n, вычис­лить f (x), положить Н=Е.

Шаг 1. Найти направление р = – Н f  '(х).

Шаг 2. Решить задачу одномерной минимизации f (х + р)  min,  >0,

т.е. найти ^*.

Шаг 3. Положить =х+^*р и найти f '(x). Проверить условие достижения точности: ||f '( )|[< . Если оно выполнено, то положить x^* = f ^* = f ( ) и прекратить поиск, иначе – перейти к шагу 4.

Шаг 4. Найти векторы v = –x, u = f  '( ) – f  '(х), матрицы . Положить H =H + A + B, х = , f  (х)= f  ( ) и перейти к шагу 1.

Пример 3.14. Методом ДФП решить задачу f (x)=4x²₁+ 3x²₂– 4x₁x₂+ x₁min.

Итерация 1.

Шаг 0. Положим  = 10^–4, х =(0,0), найдем f '(x)=(l,0), положим

Н = Е = = .

Шаг 1. Найдем направление р =– Н f  (х)=(– 1,0).

Шаг 2. Решим задачу f (х + р)  min, получим ^* = 1/8.

Шаг 3. Находим = х+^*р = (–1/8, 0), f '( ) = (0, 1/2). Так как ||f '( )||= 1/2>, переходим к шагу 4.

Шаг 4. Находим векторы

v = – x=(–1/8, 0), u = f  '( ) – f  '(x) = (–1, 1/2) и матрицы

,

,

.

Полагаем х= , f '(x)=f '( ) и переходим к следующей итерации, начиная с шага 1.

Итерация 2.

Шаг 1. Находим направление р=–Hf '(x)=( –1/5, –2/5).

Шаг 2. Решим задачу f (х + р)  min, получим ^* = 5/16.

Шаг 3. Находим = (– 3/16, –1/8), f (x) = (0,0). TAx как ||f  '( ) ||= 0 < , точность достигнута, поэтому полагаем х^* = =(–3/16, –1/8), f ^*=f ( )=3/16.

Есть и другие варианты квазиньютоновских методов. Они различаются способами построения матриц H ^(k)Например, в методе Мaк–Кормикa

.

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

Недостатком этих методов является необходимость хранения в памяти ЭВМ матриц H^(k), что при решении задач высокой размерности может создать определенные трудности.

УПРАЖНЕНИЯ

1. Функция f (x)= x²₁ + x²₂ – x₁x₂ + 2x₁ – 4x₂ минимизируется градиентным методом с постоянным шагом (_k). При каких значениях сходимость гарантирована? Найти ^* , выполнить три итерации метода при х⁰ = (1, 1).

2. Для функции из упражнения 1 выполнить три итерации поиска мини­мума по методу наискорейшего спуска при х⁰ = (1,1).

3. Вычислить антиградиент функции f (х) = 100(x₂ – x₁)² + (1– x₁)² в точках (–1,2; 1), (0, 0), (2, 1) и сравнить полученные направления с направлением в точку минимума х^*= (1,1), изобразив соответствующие векторы па плоскости.

4. Показать, что в методе наискорейшего спуска направления х^k+1 – х^k и x^k – x^k–1 ортогональны.

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

6. Выполнить три итерации в соответствии с методом наискорейшего спуска методом сопряженных градиентов, методом Ньютона и ДФП–методом для минимизации функции f (х) =(x₁+ 10x₂)² +5(x₃ – x₄)² + (x₂ – 2x₃)⁴ +10(x₁– x₄)⁴ при х⁰=(3, –1, 0,1).

7. Показать, что если матрица f  (х^k) положительно определена и f  (х^k )  0, то направление р^k = – [f  (x^k)]^–1f  (x^k) является направлением убывания функции f (х) в точке х^k .

8. Минимизировать методом сопряженных градиентов следующие функ­ции:

а) f (х) = 10x²₁+ 2x²₂ – 4x₁x₂ – 2x₁ – 2x₂ +1;

б) f (х) = x⁴₁+ x⁴₂ – 2x²₁x²₂ – 4x₁ + 3;

в) f (х) = (x²₁+ x₂ –11)² +( x₁ + x²₂ –7)².

Библиографический список

1. 
   Васильев Ф.П. Численные методы решения экстремальных задач. – М.: Наука. 1980.
   
2. 
   Будак Б.М., Васильев Ф.П. Приближенные методы решения задач оптимального управления (тексты лекций). – М.: МГУ, 1969. Вып. 2.
   
3. 
   Поляк Б. Т. Введение в оптимизацию. – М.: Наука, 1983.
   
4. 
   Кудрявцев Л. Д. Математический анализ. Т. 1,2. – М.: Высшая школа, 1970.
   
5. 
   Моисеев Н.Н., Иваншов Ю.П., Столярова Е.М. Методы оптимизации. – М.: Наука, 1978.
   
6. 
   Иоффе А.Д., Тихомиров В.М. Теория экстремальных задач. – М.: Наука, 1974.
   
7. 
   Гилл Ф., Миррей У., Райт М. Практическая оптимизация. – М.: Мир, 1–Л985.
   
8. 
   Сеа Ж. Оптимизация. Теория и алгоритмы. – М.: Мир, 1973.
   

* Если окажется, что =х₂ , то в качестве второй пробной точки (помимо х₂) можно взять любую другую точку интервала (x₁; x₃) например, или .

* В дальнейшем, там, где это не приводит к недоразумениям, символ «Т» будем опускать.

1   2   3   4   5   6   7   8   9   10

---