Алгоритм наилучшей пробы с направляющим гиперквадратом ....... 72 <...> Прямые методы поиска или методы нулевого порядка – это методы, в которых при поиске экстремума используется информация только о самой функции и не используется информация о ее производных. <...> МЕТОДЫ ОДНОМЕРНОГО ПОИСКА
Как правило, реально мы сталкиваемся с необходимостью решения
многомерных задач. <...> Но на этапах поиска в многомерных методах почти
обязательно сталкиваются с задачами одномерной минимизации в направлении некоторого вектора. <...> МЕТОД ДИХОТОМИИ
Предполагается, что минимизируемая функция f ( x ) унимодальна
на отрезке [a0 , b0 ] , и необходимо найти минимум этой функции на
7
заданном отрезке с некоторой точностью
гласно следующим соотношениям:
x1
a0
b0
2
и x2
a0
. Вычисляем две точки со-
b0
2
,
где
(рис. <...> Метод дихотомии
Затем сокращаем интервал неопределенности и получаем интервал
[a1 , b1 ] следующим образом. <...> С помощью найденных точек определяем новый интервал неопределенности. <...> Поиск заканчивается, если длина интервала неопределенности
[ak , bk ] на текущей итерации k становится меньше заданной точности:
bk
ak
8
.
В данном методе на каждой итерации минимизируемая функция
f ( x ) вычисляется дважды, а интервал неопределенности сокращается
практически в два раза (при малых
). <...> МЕТОД ЗОЛОТОГО СЕЧЕНИЯ
Этот метод позволяет найти минимум унимодальной функции на
заданной области [a0 , b0 ] , как правило, с меньшими вычислительными
затратами, чем метод дихотомии. <...> МЕТОД ФИБОНАЧЧИ
Последовательность чисел Фибоначчи подчиняется соотношению:
Fn
Fn
2
Fn ,
1
где n 1, 2, 3,... и F1 F2 . <...> Сам алгоритм метода Фибоначчи очень похож на алгоритм метода
золотого сечения. <...> Следует также отметить, что при практическом применении метод
золотого сечения по эффективности, скорости сходимости и точности
получаемого решения практически не уступает методу Фибоначчи. <...> Применяются различные эвристические
алгоритмы, используется интерполяция (аппроксимация) минимизируемой функции более простой <...>
Методы_оптимизации.pdf
Министерство образования и науки Российской Федерации
НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ
Б. Ю. ЛЕМЕШКО
МЕТОДЫ
ОПТИМИЗАЦИИ
Утверждено
Редакционно-издательским советом университета
в качестве конспекта лекций
НОВОСИБИРСК
2009
Стр.1
УДК 519.852(075.8)
Л 442
Рецензенты: д-р техн. наук, проф. А.А. Попов;
д-р физ.-мат. наук, проф. В.А. Селезнев
Работа подготовлена на кафедре прикладной математики
для студентов III курса ФПМИ (направление 010500 –
Прикладная математика и информатика, специальности 010503 –
Математическое обеспечение и администрирование
информационных систем)
Лемешко Б.Ю.
Л 442 Методы оптимизации : конспект лекций / Б.Ю. Лемешко. –
Новосибирск : Изд-во НГТУ, 2009. – 156 с.
ISBN 978-5-7782-1202-2
Курс лекций рассчитан на один семестр и предназначен для студентов
ФПМИ, но может быть полезен и студентам других специальностей. Настоящее
издание должно помочь студентам овладеть прикладными методами оптимизации.
УДК
519.852(075.8)
ISBN 978-5-7782-1202-2
© Лемешко Б.Ю., 2009
© Новосибирский государственный
технический университет, 2009
2
Стр.2
ОГЛАВЛЕНИЕ
Введение ................................................................................................................... 5
1. Методы одномерного поиска. .......................................................................... 7
1.1. Метод дихотомии .......................................................................................... 7
1.2. Метод золотого сечения ................................................................................ 9
1.3. Метод Фибоначчи ........................................................................................ 10
Контрольные вопросы ........................................................................................ 12
2. Прямые методы поиска .................................................................................. 12
2.1. Алгоритм Гаусса .......................................................................................... 13
2.2. Алгоритм Хука и Дживса ........................................................................... 14
2.3. Алгоритм Розенброка .................................................................................. 16
2.4. Симплексный метод Нелдера–Мида или поиск по деформируемому
многограннику ............................................................................................. 20
2.5. Метод Пауэлла и сопряженные направления ........................................... 24
2.5.1. Обоснование применения сопряженных направлений
в алгоритмах оптимизации ................................................................... 24
2.5.2. Алгоритм метода Пауэлла ..................................................................... 30
Контрольные вопросы ........................................................................................ 35
3. Методы первого порядка ................................................................................ 36
3.1. Алгоритм наискорейшего спуска ............................................................... 36
3.2. Метод сопряженных градиентов ................................................................ 38
3.3. Многопараметрический поиск ................................................................... 42
Контрольные вопросы ........................................................................................ 43
4. Методы второго порядка (метод Ньютона) ................................................ 44
Контрольные вопросы ........................................................................................ 47
5. Методы переменной метрики ........................................................................ 47
5.1. Введение ....................................................................................................... 47
5.2. Метод Бройдена ........................................................................................... 50
5.3. Метод Дэвидона–Флетчера–Пауэлла ........................................................ 52
5.4. Алгоритмы Пирсона .................................................................................... 54
5.5. Проективный алгоритм Ньютона–Рафсона ............................................... 55
5.6. Методы Гринштадта и Гольдфарба ........................................................... 55
5.7. Алгоритм Флетчера ..................................................................................... 56
5.8. Алгоритмы с аппроксимацией матрицы Гессе ......................................... 58
Контрольные вопросы ........................................................................................ 60
6. Методы штрафных функций ......................................................................... 60
Контрольные вопросы ........................................................................................ 64
7. Статистические методы поиска .................................................................... 64
7.1. Введение ....................................................................................................... 64
7.2. Простой случайный поиск .......................................................................... 66
3
Стр.3
7.3. Простейшие алгоритмы направленного случайного поиска ................... 68
7.3.1. Алгоритм парной пробы ........................................................................ 68
7.3.2. Алгоритм наилучшей пробы ................................................................. 69
7.3.3. Метод статистического градиента ........................................................ 70
7.3.4. Алгоритм наилучшей пробы с направляющим гиперквадратом ....... 72
7.4. Алгоритмы глобального поиска ................................................................. 73
Контрольные вопросы ........................................................................................ 76
8. Линейное программирование ........................................................................ 77
8.1. Основные определения и теоремы ............................................................. 77
8.2. Основная теорема линейного программирования .................................... 81
8.3. Симплекс-метод ........................................................................................... 83
8.3.1. Введение в симплекс-метод .................................................................. 83
8.3.2. Алгоритм симплекс-метода .................................................................. 87
8.3.3. Вырожденность в задачах линейного программирования ................. 92
8.4. Двойственность задач линейного программирования ............................. 94
8.4.1. Понятие двойственной задачи .............................................................. 94
8.4.2. Преобразования при решении прямой и двойственной задач ........... 95
8.4.3. Теоремы двойственности линейного программирования .................. 98
8.4.4. Метод последовательного уточнения оценок ................................... 102
Контрольные вопросы ...................................................................................... 105
9. Методы решения транспортной задачи ..................................................... 106
9.1. Формулировка классической транспортной задачи ............................... 106
9.2. Метод северо-западного угла ................................................................... 107
9.3. Метод минимального элемента ................................................................ 108
9.4. Теорема, лежащая в основе метода потенциалов ................................... 109
9.5. Алгоритм метода потенциалов ................................................................. 112
9.6. О вырожденности транспортной задачи ................................................. 117
Контрольные вопросы ...................................................................................... 118
10. Транспортная задача с ограничениями ................................................... 119
10.1. Постановка задачи ................................................................................... 119
10.2. Метод потенциалов для определения оптимального плана................. 120
10.3. Построение опорного плана ................................................................... 122
Контрольные вопросы ...................................................................................... 127
11. Транспортная задача по критерию времени .......................................... 127
Контрольные вопросы ...................................................................................... 131
12. Задача о максимальном потоке в транспортной сети ........................... 131
12.1. Постановка задачи ................................................................................... 131
12.2. Алгоритм построения максимального потока в транспортной сети ... 134
Контрольные вопросы ...................................................................................... 143
13. Параметрическое линейное программирование .................................... 143
13.1. Постановка задачи ................................................................................... 143
13.2. Алгоритм .................................................................................................. 145
Контрольные вопросы ...................................................................................... 152
Библиографический список ............................................................................. 153
4
Стр.4