- •Аннотация
- •Оглавление
- •Предисловие
- •ГЛАВА 1. Задачи оптимизации. Основные определения
- •1.1. Задачи оптимизации
- •1.2. Минимум функции одной переменной
- •1.3. Унимодальные функции
- •1.4. Выпуклые функции
- •1.5. Условие Липшица
- •1.6. Классическая минимизация функции одной переменной
- •Вопросы и задания для самоконтроля
- •ГЛАВА 2. Одномерная минимизация функций. Прямые методы
- •2.1. О прямых методах
- •2.2. Метод перебора
- •2.3. Метод поразрядного поиска
- •2.4. Метод дихотомии
- •2.5. Метод золотого сечения
- •2.6. Сравнение методов перебора, дихотомии и золотого сечения
- •2.7. Метод парабол
- •Вопросы и задания для самоконтроля
- •Задание для численной реализации в среде программирования MATLAB
- •ГЛАВА 3. Одномерная минимизация. Методы, использующие информацию о производных целевой функции
- •3.1. Метод средней точки
- •3.2. Метод хорд
- •3.3. Метод Ньютона
- •3.4. Возможные модификации метода Ньютона
- •3.5. Методы минимизации многомодальных функций
- •Вопросы и задания для самоконтроля
- •Задание для численной реализации в среде программирования MATLAB
- •ГЛАВА 4. Задача минимизации функции многих переменных. Необходимые и достаточные условия безусловного экстремума
- •4.1. Постановка задачи и определения
- •4.2. Свойства выпуклых множеств и выпуклых функций
- •4.3. Необходимые и достаточные условия безусловного экстремума
- •Вопросы и задания для самоконтроля
- •5.1. Выпуклые квадратичные функции
- •5.2. Общие принципы многомерной минимизации
- •5.3. Метод градиентного спуска
- •5.4. Метод наискорейшего спуска
- •5.5. Метод сопряженных направлений
- •5.6. Метод сопряженных градиентов
- •5.7. Метод Ньютона
- •5.8. Квазиньютоновские методы
- •Вопросы и задания для самопроверки
- •Задание для численной реализации в среде программирования MATLAB
- •ГЛАВА 6. Прямые методы безусловной минимизации многомерных задач
- •6.1. Проблема минимизации многомерных задач
- •6.2. Минимизация функций по правильному (регулярному) симплексу
- •6.3. Минимизация функций при помощи нерегулярного симплекса
- •6.4. Метод циклического покоординатного спуска
- •6.5. Метод Хука–Дживса
- •6.6. Методы случайного поиска
- •Вопросы и задания для самопроверки
- •Задание для численной реализации в среде программирования MATLAB
- •7.1. Условный экстремум при ограничениях типа равенств
- •7.2. Условный экстремум при ограничениях типа неравенств
- •Вопросы и задания для самопроверки
- •ГЛАВА 8. Линейное программирование
- •8.1. Определения. Примеры задач линейного программирования
- •8.2. Общая и каноническая задачи линейного программирования
- •8.3. Геометрическое истолкование задач линейного программирования
- •8.4. Аналитическое решение задач линейного программирования
- •Вопросы и задания для самоконтроля
- •Литература
|
|
k |
|
|
|
|
|
f (xk ) = f (x0 ) + ∑αi Api . |
|
|
|
|
|
i=1 |
|
|
|
Умножая |
обе части |
этого равенства скалярно на pk |
и |
учитывая |
условие |
исчерпывающего спуска по направлению pk : ( f (xk ), p k ) = 0 |
и A −ортогональность |
||||
векторов, получаем |
|
|
|
|
|
|
|
( f (x0 ), p k ) +αk ( Ap k , p k ) = 0 . |
|
|
|
Так как |
матрица |
A положительно определена, |
квадратичная |
форма |
|
(Apk , pk ) > 0 и для величины шага αk получаем выражение (5.17). |
|
||||
Теорема. |
Последовательный исчерпывающий спуск |
по |
A –ортогональным |
направлениям (5.16) приводит к точке минимума квадратичной формы не более чем за n шагов.
□ Доказать самостоятельно. Предположить, что существуют uk ≠ αk , и
получить, что они совпадают. ■
Вопрос о нахождении базиса из A –ортогональных векторов в пространстве En
решается неоднозначно. В качестве такого базиса можно, например, взять ортогональный базис из собственных векторов матрицы A . Однако их поиск при n > 2 представляет собой самостоятельную и довольно сложную задачу.
Итерационный |
процесс |
xk = xk −1 +αk pk , k =1, 2, ... |
последовательной |
одномерной минимизации по сопряженным направлениям pk |
можно организовать |
и без предварительного построения векторов p1 , ..., pn , последовательно находя их в процессе минимизации, как это было сделано выше в примере с минимизацией функции двух переменных. И в этом случае для квадратичной функции с положительно определенной матрицей A для нахождения минимума достаточно конечное число шагов. Если не является квадратичной функцией или
вспомогательные задачи одномерной минимизации решаются приближенно, потребуются дополнительные вычисления.
Метод сопряженных направлений, рассмотренный выше, относится к числу наиболее эффективных методов минимизации выпуклых квадратичных функций. Его недостатком является необходимость решать довольно большое количество задач одномерной минимизации.
5.6. Метод сопряженных градиентов
88
При использовании методов градиентного и наискорейшего спуска в итерационной процедуре
xk +1 = xk |
+αk pk , |
k = 0,1,... |
в качестве направления убывания |
функции |
f (x) использовалось направление |
антиградиента: pk = − f (xk ). Однако такой выбор направления убывания не всегда бывает удачным. В частности, для плохо обусловленных задач минимизации направление антиградиента в точке xk может значительно отличаться от направления к точке минимума x . В результате траектория приближения к точке минимума имеет зигзагообразный характер. Воспользуемся другим подходом, идея которого была изложена при построении метода сопряженных направлений. Будем определять направления спуска pk не только через вектор антиградиента − f (xk ) ,
но и через направление спуска pk −1 |
на предыдущем шаге. |
Это позволит более |
полно учесть особенности функции f (x) при нахождении ее минимума. |
||
Используется итерационный процесс |
|
|
xk +1 = xk +αk pk , k = 0, 1, ...; |
x0 En , p0 = − f (x0 ) , |
(5.19) |
в котором величина шага αk находится из условия исчерпывающего спуска по
направлению pk . Далее, |
после вычисления очередной точки xk +1 , |
k = 0, 1, ..., новое |
|||||
направление поиска pk +1 |
находится по формуле, отличной от антиградиента: |
||||||
|
pk +1 = − f (xk +1 ) + βk p k , |
k = 0, 1, ... , |
|
(5.20) |
|||
где коэффициенты |
βk |
выбираются так, чтобы при минимизации квадратичной |
|||||
функции f (x) с |
положительно определенной |
матрицей |
A получалась |
||||
последовательность |
A −ортогональных |
векторов |
p0 , p1 , ... . |
Из условия |
|||
(Apk +1 , pk ) = 0 имеем: |
|
|
|
|
|
|
|
|
|
βk = |
(A f (xk +1 ), pk ) |
. |
|
(5.21) |
|
|
|
|
|
||||
|
|
|
(Apk , pk ) |
|
|
|
Ранее, при обсуждении метода сопряженных направлений было показано, что
для квадратичной функции шаг исчерпывающего спуска по направлению pk равен
αk = − |
( f (xk ), p k ) |
. |
(5.22) |
|
|||
|
(Apk , pk ) |
||
Утверждение. Итерационный процесс |
(5.19)−(5.22) минимизации |
квадратичной функции с положительно определенной симметрической матрицей
89
A дает точки |
x0 , ..., xk |
и векторы p0 , ..., pk такие, что если |
f (xi ) ≠ 0 при |
||||
0 ≤i < k ≤ n −1, |
то векторы |
p0 , ..., |
pk |
A −ортогональны, |
а |
градиенты |
|
f (x0 ), ..., f (xi ) |
взаимно ортогональны. |
|
|
|
|
||
Так как направления |
pk |
в (5.20) |
являются A −ортогональными, |
то метод |
гарантирует нахождение точки минимума сильно выпуклой квадратичной функции не более чем за n шагов.
С учетом взаимной ортогональности градиентов f (xi ) и условий
исчерпывающего спуска по направлениям pk можно упростить выражения (5.21) и
(5.22) для αk |
и βk . В результате получим, |
что итерационный процесс метода |
||||||||||||||
сопряженных градиентов описывается соотношениями |
|
|||||||||||||||
xk +1 |
= xk +αk |
pk , k = 0, 1, ...; |
|
x0 En , |
p0 = − f (x0 ) , |
(5.23) |
||||||||||
|
f (xk +αk pk ) = min f (xk |
+α pk ), |
k = 0, 1, ... , |
(5.24) |
||||||||||||
|
|
|
|
|
|
|
α>0 |
|
|
|
|
|
|
|
|
|
|
pk +1 |
= − f (xk +1 ) + βk |
p k , k = 0, 1, ... , |
(5.25) |
||||||||||||
|
|
βk = |
|
|
|
f (xk +1 ) |
|
|
|
2 |
, |
k =1, 2, ... |
(5.26) |
|||
|
|
|
|
|
|
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
f (xk ) |
|
2 |
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
Следует отметить, что выражение для коэффициента βk не содержит в явном виде матрицу A квадратичной формы. Поэтому метод сопряженных градиентов может применяться для минимизации неквадратичных функций.
Итерационный процесс (5.23)−(5.26) может не приводить к точке минимума неквадратичной функции за конечное число итераций. Более того, точное
определение αk из условия (5.22) возможно лишь в редких случаях, а вектора pk
на образуют, вообще говоря, A −ортогональную систему относительно какой-либо матрицы A . Поэтому реализация каждой итерации метода будет сопровождаться неизбежными погрешностями. Эти погрешности, накапливаясь, могут привести к
тому, что векторы pk перестанут указывать направление убывания функции и
сходимость метода может нарушаться. Поэтому в методе сопряженных градиентов применяется практический прием − через каждые N шагов производят обновление метода, полагая βm N = 0, m =1, 2, ... . Номера m N называют моментами
90
обновления метода, или рестарта. Часто полагают N = n − размерности пространства En . Если N =1, то получается частный случай метода сопряженных градиентов − метод наискорейшего спуска.
Вблизи точки минимума дважды дифференцируемая функция с положительно определенной матрицей Гессе H (x ) , как правило, достаточно хорошо
аппроксимируется квадратичной функцией. Поэтому можно надеяться на хороший результат применения метода сопряженных градиентов для функций такого вида.
Пример 5.7. Методом сопряженных градиентов найти точку минимума
функции f (x) = 4x2 +3x2 − 4x x |
2 |
+ x |
из начальной точки x0 = (0, 0)T . |
|||||||||
1 |
2 |
1 |
1 |
|
|
|
|
|
|
|
|
|
□ Итерация 1. |
|
|
|
|
|
|
|
|
|
|
|
|
Шаг 1. Положим ε = 0,01, |
x0 |
= (0, 0)T , |
и найдем f (x0 ) = (1, 0)T . Перейдем к |
|||||||||
шагу 2. |
|
|
|
|
|
|
|
|
|
|
|
|
Шаг 2. Положим k = 0, |
p0 |
= − f (x0 ) = (−1, 0)T . Перейдем к шагу 3. |
||||||||||
Шаг 3. Решим задачу одномерной минимизации |
f (x0 |
+α p0 ) → min. Получим |
||||||||||
α0 =1/ 8 . – Здесь применили формулу α0 = − |
( f (x0 ), p0 ) |
= − |
|
(Ax0 + b, p0 ) |
. Перейдем |
|||||||
|
|
|||||||||||
|
|
|
|
|
|
(Ap0 , p0 ) |
|
|
|
(Ap0 , p0 ) |
||
к шагу 4. |
|
|
|
|
|
|
|
|
|
|
|
|
Шаг 4. Найдем |
x1 = x0 |
+α0 p0 = (−1/ 8, |
0)T |
и f (x1 ) = (0, 1/ 2)T . Точность не |
||||||||
достигнута, прейдем к шагу 5. |
|
|
|
|
|
|
|
|
|
|
||
Шаг 5. Условие k +1 = n не выполняется (нет рестарта), перейдем к шагу 6. |
||||||||||||
Шаг 6. Найдем коэффициент β0 =1/ 4 и новое направление спуска |
||||||||||||
p1 = − f (x1 ) + β0 p0 = (−1/ 4, −1/ 2)T . Перейдем к следующей итерации. |
||||||||||||
Поскольку x1 , f (x1 ) и p1 |
= − f (x1 ) + β0 |
p0 |
уже вычислены на итерации 1, то |
|||||||||
итерацию 2 начинаем с шага 3. |
|
|
|
|
|
|
|
|
|
|||
Итерация 2. |
|
|
|
|
|
|
|
|
|
|
|
|
Шаг 3. Решим задачу одномерной минимизации |
f (x1 +α p1 ) → min . Получим |
|||||||||||
α =1/ 4 . Перейдем к шагу 4. |
|
|
|
|
|
|
|
|
|
|
|
|
Шаг 4. Найдем x2 |
= x1 +α1 |
p1 = (−3 /16, −1/ 8)T и f (x2 ) = (0, 0)T − задача решена |
||||||||||
точно. |
|
|
|
|
|
|
|
|
|
|
|
|
91