Бейко І. В. Задачі, методи та алгоритми оптимізації

518(075.8)
Б41
Бейко І. В.
     Задачі, методи та алгоритми оптимізації : навч. посібник / І. В. Бейко, П. М. Зінько, О. Г. Наконечний. – 2-ге вид., переробл. – Київ : ВПЦ “Київський університет”, 2012. – 800 с.

Викладено сучасні методи й наведено алгоритми для розв’язання задач оптимізації. Розглянуто задачі оптимізації в багатокритеріальних та ієрархічних системах, одновимірної, безумовної оптимізації (диференційованої та недиференційованої), лінійного, нелінійного та стохастичного програмування, оптимізації в нескінченновимірних просторах. Сформульовано задачі, припущення, описано ідеї методів, покрокові алгоритми, теореми збіжності, наведено практичні поради щодо використання алгоритмів. Типові алгоритми апробовано на тестових прикладах.
     Для студентів, аспірантів. науковців, що спеціалізуються в гапузі теорії та практики прийняття оптимальних рішень, планування, прогнозування, проектування, виробництва та експлуатації систем різної природи.

ЗМІСТ

Передмова
Позначення й символи
Вступ.
Типові задачі оптимізації
Умови оптимальності та алторитми оптимізації
0.1. Приклади типових задач оптимізації
0.2. Методи наближено повного та цілеспрямованого перебору. Алторитми відтинань і мінорант
0.2.1. Методи повного перебору
0.2.2. Методи відтинань. Алгоритми медіан і половинного поділу
0.2.3. Метод мінорант
0.3. Необхідна умова мінімуму диференційовної функціїта градієнтні алгоритми оптимізації
0.3.1. Необхідна умова мінімуму
0.3.2. Екстремальні розв’язки задачі оптимізацн. Алторитм обчислення екстремального розв’язку
0.3.3. Метод Ньютона та метод вічнихдля уточнення екстремального розв’язку
0.4. Умови оптимальності й методи мінімізаціїдиференційовних функцій багатьох змінних
0.4.1. Методи Монте–Карло
0.4.2. Необхідна умова мінімуму диференційовної функціїбагатьох змінних і алгоритм найшвидшого спуску
0.4.3. Методи послідовних наближень
0.4.4. Г радієнтні методи, алгоритми допустимих напрямківі теореми збіжності
0.4.5. Необхідні й достатні умови оптимальностідля задачі мінімізації опуклої функції. Алгоритм узагальнених градієнтів
0.4.6. Методи відтинань для мінімізації опуклих функцій.Метод еліпсоїдів
0.4.7. Умови оптимальності для задачі мінімізаціїнеперервної функції з кусково-неперервними градієнтами
0.4.8. Методи стохастичних градієнтів
0.5. Прискорені методи оптимізації
0.5.1. Алгоритм спряжених градієнтівдля мінімізації квадратичних функцій
0.5.2. Методи другого порядку. Метод Ньютона
0.5.3. Квазіньютоновські методи
0.5.4. Прискорені методи оптимізаціїз розтягуванням простору
0.5.5. r -алгоритми мінімізації з розтягуванням просторув напрямку різниці субградієнтів
0.6. Умови оптимальності для задач оптимізаціїз обмеженнями
0.6.1. Теорема Каруша – Куна – Таккера для задачі опуклої оптимізації
0.6.2. Метод внутрішньої точкив лінійному програмуванні.
0.6.3. Необхідні умови оптимальності ,:шя задач оптнмшшїз диференційовними функціями обмежень
0.7. Методи оптимізації в задачахз обмеженнями
0.7.1. Методи штрафів для задач оптимізаціїз обмеженнями
0.7.2. Алгоритми двоетапної оптимізації
0.8.Методи оптимізації в задачах варіаційного численнята оптимального керування
0.8.1. Задачі варіаційного числення
0.8.2. Задачі оптимального керування
0.8.3. Методи розв’язання типових задачоптимального керування
0. 8.3.1 . Лінійна задача Майєра
0. 8.3.2. Побудова керування, оптимального за швидкодією
0.8.3.3. Двоїста задача Майєра.Мінімізація амплітуди керування
0.8.3.4. Мінімізація квадратичного функціонала
0.8.3.5. Узагальнена задача мінімізаціїквадратичного функціонала
0.8.3.6. Градієнтні методи побудовиоптимального керування
0.8.3.7. Числові методи побудови оптимального керуванняза наявності обмежень на керування
0.8.3.8. Числовий метод побудови оптимального керуванняза принципом максимуму)
0.8.3.9. Розв ‘язуючі оператори для оптимального керуванняскладними граф-операторами системами
0.8.3.10. Використання методів оптимізаціїдля побудови математичних моделей
Розділ 1. Методи прийняття рішень і оптимізаціїв багатокритеріальних та ієрархічних системах
1.1. Прийняття рішень (вибір) і оптимізація
1.1.1. Критеріальний підхід до вибору альтернатив
1.1.2. Нормалізований мультикритерій
1 .1.3. Суперкритерій
1.1.4. Метод головного частинного критерію
1.1.5. Метод послідовних поступок
1.1.6. Пошук альтернативи із заданими властивостями
1.1.7. Метод бажаної точки
1.1.8. Прийняття рішень в умовах невизначеності
1.1.9. Приклади постановок задачбататокритеріальиої оптимізації
1.1.9.1. Задача проектування оптимального програмного комплексу
1.1.9.2. Трирівнева задача керування гнучким автоматизованим виробництвом
1.2. Оптимізація в системах з ієрархічною структурою
1.2.1. Тривіальний випадок
1.2.2. Загальний випадок
1.2.2.1. Принцип гарантованого результату
1.2.2.2. Прийняття рішень в умовах доброзичливості
1.2.3. Приклади ієрархічних систем керування
1.2.3.1. Задача розподілу ресурсів
1.2.3.2. Задача нормування шкідливих викидів
1.2.3.3. Задача управління економічною системоюза допомогою штрафів і доплат (заохочень)
Розділ 2. Методи одновиміриої оптимізації
2.1. Методи Фібоначчі
2.1.1. Основний метод
2.1.2. Модифікація методу Фібоначчі
2.2. Метод золотого перерізу
2.3. Методи типу Ньютона
2.3.1. Метод Ньютона
2.3.2. Метод січних
2.4. Методи дотичних
2.4.1. Випадок диференційовної функції
2.4.2. Випадок недиференційовної функції
25. Методи глобального пошуку
2.5.1. Метод глобального пошуку
2.5.2. Рандомізований метод глобального пошуку
2.6. Методи пошуку інтервалу найбільших значеньбагатоекстремальних функцій
2.7. Методи пошуку глобального мінімуму,що використовують стохастичні автомати
2.7.1. Метод, що використовує модельБуша – Мостеллера
2.7.2. Метод, що використовуєусереднені значення функції
2.8. Адаптивні методи
2.8.1. Метод Кіфера – Вольфовиця
2.8.2. Простий перебір
Розділ 3. Методи оптимізації диференційовних функцій у задачах без обмежень
3.1. Аналітичні методи
3.1.1. Необхідна умова локальної оптимальності
3.1.2. Достатня умова локальної оптимальності
3.2. Градієнтні методи
3.2.1. Метод найшвидшого спуску
3.2.2. Модифікований метод найшвидшого спуску
3.2.3. Основний варіант градієнтного методу
3.2.4. Модифікація основного варіанта градієнтного метод (з подрібненням кроку)
3.2.5. Градієнтний метод зі сталим кроковим множником
3.2.6. Варіант градієнтного методуз матрицею прискорення збіжності
3.2.7. Модифікований градієнтний метод, що не потребує обчислення похідних
3.3. Методи типу Ньютона
3.3.1. Метод Ньютона – Канторовнча
3.3.2. Узагальнений метод Ньютона-Канторовича
3.3.3. Модифікація узагальненою методу Ньютона – Канторовича
3.3.4. Модифікований узагальнений метод Ньютона – Канторовича, що не вимагає обчислення матриці других похідних
3.4. Методи спряжених градієнтів
3.4.1. Загальна схема методу спряжених градієнтів
3.4.2. Метод спряжених градієнтів із відношенням
3.4.3. Модифікації методів спряжених градієнтів
3.4.4. Метод спряжених градієнтів для мінімізації квадратичних функцій
3.4.5. Реалізована модіфікація методу зі змінною метрикою
3.5. Методи спряжених напрямків
3.5.1. Метод спряжених напрямків із відновленням матриці
3.5.2. Метод спряжених напрямків без відновлення матриці
3.5.3. Мінімізація квадратичних функційза допомогою методу спряжених напрямків
3.5.4. Модифікований метод спряжених напрямків,шо не потребує обчислення похідних
3.6. Методи псевдообернених операторів
3.6.1. Основний метод
3.6.2. Стійке псевдообернення погано обумовлених матриць
3.7. Стохастичні квазіградієнтні методи
3.7.1 . Загальний стохастичний квазіградієнтний метод для детермінованих задач
3.7.2. Загальний стохастичний квазіградієнтний метод для стохастичних задач
3.7.3. Стохастичний квазіградієнтний методіз процедурою переривання
3.7.4. Стохастичний квазіградієнтний метод зі сталим кроковим множником
3.8. Метод локальних варіацій
3.9. Методи випадкового пошуку
3.9.1. Метод випадковою пошукув опуклих задачах мінімізації
3.9.2. Адаптивний метод випадкового пошуку
Розділ 4. Методи оптимізації недиференційовних функційі відшукання сідлових точок у задачах без обмежень
4.1. Означення узагальненого градієнта (субградієнта). Приклади обчислення субґрадієнтів
4.2. Опуклі функції та їх властивості
4.3. Методи узагальненого градієнтного спуску
4.3.1. Метод зі сталим кроковим множником
4.3.2. Основний метод
4.3.3. Модифікація основного методу
4.3.4. Перший метод зі спеціальним вибором крокового множника
4.3.5. Другий метод зі спеціальним вибором крокового множника
4.3.6. Метод, що використовує апріорне значення мінімуму функції
4.3.7. Метод, стійкий до похибок обчислень
4.3.8. Багатокроковий метод узагальненого градієнтного спуску
     ε-субградієнтний метод
4.4. Методи градієнтного типу з ростягненням простору
4.4.1. Метод градієнтного типу з розтягненням просторув напрямку майже градієнта
4.4.2. Методи градієнтного типу з розтягненням просторув напрямку різниці двох послідовних майже градієнтів (r(ά) – алгоритм)
4.5. Методи локального випадкового пошуку
4.5.1. Метод локальгою випадковою пошукуз парною пробою
4.5.2. Метод локального випадкового пошукуз поверненням при невдалому кроці
4.5.3. Метод локального випадкового пошукуз лінійною екстраполяцією
4.5.4. Меюд випадковою пошуку за найкращою пробоюз накопиченням
4.5.5. Метод статистичного традлєнта
4.6. Квазіградієнтні методи
4.6.1. Квазіградієнтний метод мінімізації слабоопуклої донизу функції
4.6.2. Стохастичний квазіградієнтний метод мінімізації слабоопуклої функції
4.7. ε – квазіградієнтні методи
4.7.1. ε – квазітрадієнтний метод мінімізації опуклих функцій
4.7.2.ε – квазіградієнтний метод мінімізації слабоопуклих функцій
4.8. Методи узагальнених майже градієнтівдля мінімізації функцій,що задовольняють локальну умову Ліпшнця
4.8.1. Детермінований випадок
4.8.2. Стохастинчний випадок
4.9. Метод усереднення напрямків спускудля мінімізації функцій, що задовольняють умову Ліпшиця
4.10. Методи послідовних наближеньдля розв’язання дискретних мінімаксних задач
4.10.1. Перший метод послідовних наближень
4.10.2. Модифікація першого методу послідовних наближень
4.10.3. Другий метод послідовних наближень
4.10.4. Модифікація другою методу послідовних наближень
4.11. Методи Ерроу – Гурвиця розв’язання неперервнихмінімакснихзадач
4.11.1. Детермінований метод Ерроу – Гурвиця
4.11.2. Стохастичний метод Ерроу – Гурвиця
4.12. Квазіградієнтні методи розв’язання дискретнихмінімакснихзадач стохастичного програмування
4.12.1. Мінімізація функції Eωmaxφi (x,ω)
4.12.2. Мінімізація функції maxEωφi (x,ω)
Розділ 5. Методи розв’язання задач лінійного програмування
5.1. Приклади задач лінійного програмування
5.2. Графічний спосіб розв’язання задач лінійного програмування
5.2.1. Задача лінійного програмуванняз максимізацією цільової функції
5.2.2. Задача лінійного програмуванняз мінімізацією цільової функції
5.2.3. Додаткові змінні в задачах лінійною програмування
5.2.4. Особливі випадки розв’язання задач лінійного програмування
5.3. Графічний аналіз чутливості
5.3.1. Аналіз чутливості коефіцієнтів цільової функції
5.3.2. Аналіз чутливості коефіцієнтів функцій обмежень. Вартість ресурсів
5.4. Загальна задача лінійного програмування
5.5. Стандартна задача лінійного програмування.Базис, базисний розв’язок
5.6. Канонічна задача лінійною програмування.Метод Жордана – Гаусса перебору вершин допустимої області
5.6.1. Канонічна задача лінійного програмування
5.6.2. Метод Жордана – Гаусса перебору вершиндопустимої області
5.6.3. Табличний симплекс-метод
5.7. Симплекс-метод і його варіанти
5.7.1. Розв’язання стандартної задачі лінійного програмуванняз n змінними графічним способом у просторі R²
5.7.2. Симплекс-мегод розв’язання невиродженої стандартної задачі лінійного програмування
5.7.3. Методи пошуку початкового базису
5.7.4. Симплекс-метод розв’язання виродженоїстандартної задачі лінійного програмування
5.7.5. Модифікований симплекс-мстод
5.8. Двоїстий симплекс-метод
5.8.1. Основний метод
5.8.2. Методи пошуку початкового опорногорозв’язку спряженої задачі
5. 8.2.1. Метод пошуку опорного розв’язкуспряженої задачі за відомим допустимим розв’язком
5.8.2.2. Метод пошуку оптимального розв’язкуспряженої задачі без попереднього обчисленнядопустимого розв’язку
5.8.3. Правило вибору вектора αs , який вводиться в базис,що гарантує від зациклювання у виродженому випадку
5.9. Методи послідовного скорочення нев’язок
5.9.1. Метод послідовною скорочення нев’язок
5.9.2. Метод двосторонніх оцінок
5.10. Методи блочного програмування
5.10.1. Метод розкладання Данцига – Вульфа
5.10.1.1. Випадок обмеженості множини Х¹
5. 10.1.2. Випадок необмежності множини Х¹
5.10.2. Метод розкладання для розв’язання задач лінійноюпрограмування з блочно-діагональною матрицею
5.10.3. Метод, що використовує узагальненийградієнтний спуск
5.11. Модифікований симплекс-методдля розв’язання задачі лінійного програмуванняз двосторонніми обмеженнями
5.11.1. Основний метод
5.11.2. Правило вибору індексу r (який визначає вектор α що виводиться з базису) для запобігання зациклювання
5.12. Модифікований симплекс-метод для розв’язання загальної задачі лінійного програмування
5.13. Ітераційні методи
5.13.1. Ітераційний метод Петшиковського
5.13.2. Ітераційний метод,що використовує модифіковану функцію Лагранжа
5.13.3. Ітераційний метод Федоренка
5.13.4. Алгоритм “Заєць” розв’язання прямої та двоїстої задачлінійного програмування
5.135. Ітераційний метод, що використовуємодифіковану функцію Лагранжа для розв’язаннядвоїстої пари задач лінійного програмування
5.14. Методи параметричного програмування
5.14.1. Випадок наявності параметра в цільовій функції
5.14.2. Випадок наявності параметрав правих частинах обмежень
Розділ 6. Методи розв’язання задач нелінійного та стохастичного програмування
6.1. Методи проекції градієнта
6.1.1. Загальний метод
6.1.2. Метод проекції градієнта для мінімізації функціїза лінійних обмежень
6.1.3. Гібридний метод проекції градієнта для мінімізаціїфункції за нелінійних обмежень
6.1.4. Метод проекції градієнта за наявності збурень
6.2. Загальний метод штрафних функцій
6.3. Методи зовнішніх штрафних функцій
6.3.1. Задачі з обмеженнями у вигляді нерівностей
6.3.2. Задачі з обмеженнями у вигляді рівностей
6.3.3. Модифікований метод із процедурою переривання
6.3.4. Метод зовнішніх штрафних функційдля мінімізації недиференційовних функцій
6.4. Методи внутрішніх штрафних функцій
6.4.1. Загальна схема
6.4.2. Реалізовна схема з процедурою переривання
6.4.3. Методи внутрішньої точкиіз застосуванням О-функцій
6.5. Комбіновані методи штрафних функцій
6.6. Методи можливих напрямків
6.6.1. Методи можливих напрямків розв’язання задачмінімізації з обмеженнями типу нерівностей
6.6.2. Методи можливих напрямків для розв’язання задачмінімізації з обмеженнями змішаного типу
6.6.3. Метод можливих напрямків із квадратичним пошуком
6.6.4. Модифікований метод можливих напрямків Зойтендейка
6.6.5. Аналог методу можливих напрямківу задачах мінімізації майже диференційовних функцій
6.6.6. Стохастичний аналог методу можливих напрямків
6.6.7. Методи можливих напрямків для відшукання точоклокальних мінімумів неопуклої функціїна неопуклій множині
6.7. Методи центрів
6.7.1. Основний варіант
6.7.2. Модифікований метод центрів
6.7.3. Реалізація модифікованого методу центрівіз використанням методу золотого перерізу
6.7.4. Реалізація модифікованого методу центрівіз використанням функцій переривання
6.8. Методи типу Ньютона
6.8.1. Методи типу Ньютона : регулюванням кроку
6.8.2. Метод типу Ньютона за наявності збурень
6.8.3.1. Квазіньютонівські методи
6.9. Методи лінеаризації
6.9.1. Обмеження типу нерівностей
6.9.2. Обмеження типу рівностей
6.9.3. Обмеження змішаного типу
6.9.4. Конструктивний метод лінеаризації
6.9.5. Аналог методу лінеаризації в детермінованих задачах мінімізації майже диференційовних функцій
6.9.6. Аналог методу лінеаризації в стохастичних задачах мінімізації майже диференційовних функщй
6.9.7. Стохастичний метод лінеаризації
6.10. Методи відсікання
6.10.1. Лінійний випадок
6.10.2. Загальний випадок
6.10.3. Метод відсікання з розтягненням просторудля розв’язання задач опуклого програмування
6.11. Методи, що використовують функцію Лагранжа
6.11.1. Аналітичний метод
6.11.2. Градієнтний метод для задач з обмеженнямитипу нерівностей
6.11.3. Градієнтний метод для задач з обмеженнямитипу рівностей
6.11.4. Метод квадратичної апроксимаціїдля задач з обмеженнями типу рівностей
6.11.5. Двоїстий метод для задачз обмеженнями типу рівностей
6.11.6. Метод Ньютона для задачз обмеженнями типу рівностей
6.12. Методи, що використовуютьмодифіковані функції Лагранжа
6.12.1. Градієнтний метод
6.12.2. Метод, що використовує штрафні функціекспоненціального типу
6.13. Методи навантаженого функціонала
6.13.1. Загальний випадок
6.13.2. Випадок опуклих функцій
6.13.3. Наближена схема
6.14. Методи штрафних оцінок
6.14. 1. Детермінований випадок
6.14.2. Стохастичний випадок
6.14.3. Метод штрафних оцінокдля задач опуклого програмування
6.15. Методи проекції узагальнених градієнтів
6.15.1. Основний метод
6.15.2. Багатокроковий метод узагальненоюградієнтного спуску
6.15.3. Методи проекції узагальненого градієнта для розв’язання граничних екстремальних задач
6.16. Методи умовною градієнта
6.16.1. Реалізовний метод умовного градієнта
6.16.2. Алгоритм Франка – Вульфа
6.16.3. Прискорений алгоритм Франка – Вульфа
6.17. Методи спряжених градієнтів
6.17.1. Метод спряжених градієнтіву детермінованому випадку
6.17.2. Стохастичний аналог методу спряжених градієнтів
6.18. Методи покоординатного спуску
6.18.1. Детермінований покоординатний спуск
6.18.2. Випадковий покоординатний спуск
6.19. Стохастичні квазіградієнтні методи
6.19.1. Методи проектування стохастичних квазіградієнтні
6.19.2. Стохастичний метод зменшення нев’язоку детермінованих задачах
6.19.3. Метод зменшення нев’язоку задачах стохастичного програмування
6.19.4. Гібридний стохастичний метод
6.20. Комбінований метод стохастичних градієнтіві штрафних функцій
6.21. Методи усереднення напрямків спуску
6.21.1. Детермінована задача
6.21.2. Стохастична задача
6.22. Прямий метод розв’язання задачстохастичного програмування
6.23. Метод випадкового пошукув опуклих задачах мінімізації
6.24. Методи розв’язання задач оптимізаціїз нескінченною кількістю обмежень
6.24.1. Загальний метод
6.24.2. Послаблений метод
6.25. Методи розв’язання задачквадратичною програмування
6.25.1. Метод спряжених градієнтів для мінімізації квадратичної функції на підпросторі
6.25.2. Метод спряжених градієнтів для розв’язання загальної задачі квадратичного програмування
6.25.3. Метод спряжених градієнтів для розв’язання задачіквадратичного програмування з просшми обмеженнями
6.25.4. Модифікація методу спряжених напрямківдля розв’язання задач квадратичною програмування великої розмірності
6.25.5. Стійкий метод для розв’язання задач квадратичного програмування
Розділ 7. Спеціальні методи розв’язання мінімаксних задач і відшукання сідлових точок
7.1. Методи послідовних наближень розв’язаннядискретних мінімаксних задач
7.1.1. Мінімаксна задача з обмеженнями простоі структури
7.1.2. Перший метод послідовних наближень розв’язаннямінімаксної задачі з обмеженнями типу нерівностей
7.1.3. Другий метод послідовних наближень розв’язаннямінімаксної задачі з обмеженнями типу нерівностей
7.1.4. Модифікація другого методу послідовних наближень
7.2. Узагальнений безпараметричний метод зовнішньої точкирозв’язання дискретних мінімаксних задач
7.2.1. Основний метод
7.2.2. Модифікація основного методу
7.3. Сітковий метод послідовних наближень розв’язаннянеперервних мінімаксних задач
7.4. Методи стохастичного квазіградієнтав задачі пошуку максиміну
7.4.1. Основний метод
7.4.2. Модифікація основного методу
7.4.3. Опуклий випадок
7.5. Квазіградієнтні методи розв’язаннянеперервних мінімаксних задачстохастичного програмування
7.5.1. Стохастичний квазіградієнтний метод
7.5.2. Модифікований стохастиний квазіґрадієнтний метод
7.6. Градієнтні методи знаходження сідлових точок
7.6.1. Основний метод
7.6.2. Градієнтний метод знаходження сідлових точок зі сталим кроковим множником
7.6.3. Узагальнений градієнтний метод
Розділ 8. Методи оптимізаціїв нескінченновимірних просторах
8.1. Диференціали, субдиференціали та їх властивості
8.2. Теореми про існування екстремумів.Необхідні умови екстремумів
8.3. Застосування методів оптимізаціїв нескінченно вимірних просторах
8.3.1. Проблема мінімізації квадритичних функціоналіві варіаційні рівняння
8.3.2. Багатокритеріальні задачі для варіаційних рівнянь
8.4. Рівновага за Штакельбергом
8.5. Набліжені методи розв’язання екстремальних задач
Література

Напишіть відгук

Ваша пошт@ не публікуватиметься. Обов’язкові поля позначені *

Можна використовувати XHTML теґи та атрибути: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>