- Артикул:00-01117751
- Автор: И. В. Бейко, Б. Н. Бублик, П. Н. Зенько
- Тираж: 5000 экз.
- Обложка: Твердая обложка
- Издательство: Вища школа (все книги издательства)
- Город: Киев
- Страниц: 512
- Формат: 60х90/16
- Год: 1983
- Вес: 772 г
Развернуть ▼
В справочном пособии изложены современные методы и алгоритмы для решения задач оптимизации, возникающих по многих областях науки и техники, в сфере управления экономическими, социальными, техническими и другими процессами. Рассмотрены линейные и нелинейные, детерминированные и стохастические, гладкие и негладкие, минимаксные и другие задачи оптимизации. Все методы оптимизации представлены в виде детально разработанных алгоритмов. Для облегчения поиска необходимого алгоритма и его практического использовании приводится независимое описание каждого метода включающее постановку задачи оптимизации, ограничительные предположения, описание конкретных алгоритмов и соответствующих теорем сходимости, а также необходимые библиографические указания.
Книга рассчитана на работников научно-исследовательских учреждений и вычислительных центров, занимающихся вопросами разработки и применения методов оптимизации, а также на студентов, специализирующихся по прикладной математике и другим специальностям, связанным с использованием ЭВМ.
Содержание
Обозначения и символы
Предисловие
Введение. Элементы теории оптимизации и управления
0.1. Математические методы управления и задачи оптимизации
1. О математических методах поиска оптимальных решений 2. Основные задачи оптимизации 3. О задачах многоцелевого управления
0.2. О некоторых методах решения задач оптимизации
1. Метод полного перебора 2. О приближенных методах и оптимальных алгоритмах
0.3. Методы отсечений
1. Минимизация квазивыпуклых функций 2. Метод минорант. Минимизация лнпшицевых функций 3. Минимизация выпуклых функций. Метод эллипсоидов
0.4. О локализации решении с помощью необходимых и достаточных условий оптимальности. Дополнительная терминология
1. Необходимые условия оптимальности для дифференцируемых функций 2. Необходимые и достаточные условия оптимальности для задач выпуклого программирования. Теорема Куна - Таккера
3. Необходимые условия первого и второго порядка для задач нелинейного программирования
4. Условия оптимальности для задач минимизации негладких функций
0.5. Методы последовательных приближений
1. О способах выбора шаговых множителей в задачах безусловной оптимизации 2. О методах второго порядка 3. Методы сопряженных градиентов 4. О методах штрафов в задачах с ограничениями 5. О методах последовательных приближений для задач условной оптимизации и минимизация негладких функций
Часть I. Методы одномерной и безусловной оптимизации
Глава 1. Методы одномерной оптимизации
1.1. Методы Фибоначчи
1. Основной алгоритм 2. Модификация метода Фибоначчи
1.2. Метод золотого сечения
1.3. Оптимальный метод поиска экстремума унимодальных функций, удовлетворяющих условию Липшица
1.4. Оптимальный метод поиска экстремума выпуклых функций
1.5. Методы типа Ньютона
1. Метод Ньютона 2. Метод секущей
1.6 Методы касательных
1. Случай дифференцируемой функции 2. Случай недифференцируемой функции
1.7. Метод квадратичной аппроксимации
1.8. Метод отыскания абсолютного минимума функций, удовлетворяющих условию Липшица
1.9. Метод кусочно-кубической аппроксимации
1.10. Методы глобального поиска
1. Алгоритм глобального поиска 2. Рандомизированный алгоритм глобального поиска
1.11. Методы поиска интервала наибольших значений многоэкстремальных функций
1.12. Методы поиска глобального минимума, использующие стохастические автоматы
1. Алгоритм, использующий модель Буша - Мостеллера 2. Алгоритм, использующий усредненные значения функции
1.13. Адаптивные методы
1. Алгоритмы Кифера - Вольфовнца 2. Простой перебор
Глава 2. Методы оптимизации дифференцируемых функций
2.1. Градиентные методы
1. Метод наискорейшего спуска 2. Модифицированный метод наискорейшего спуска 3. Основной вариант градиентного метода 4. Градиентный метод с постоянным шаговым множителем
5. Вариант градиентного метода с матрицей ускорения сходимости
6. Модифицированный градиентный метод, не требующий вычисления производных
2.2. Методы типа Ньютона
1. Метод Ньютона - Канторовича 2. Обобщенный метод Ньютона - Канторовича 3. Модификации обобщенного метода Ньютона - Канторовича 4. Модифицированный обобщенный метод
Ньютона - Канторовича, не требующий вычисления матрицы вторых производных
2.3. Методы двойственных направлений
1. Основной вариант 2. Модифицированный метод двойственных направлений, не требующий вычислении производных
2.4. Методы сопряженных градиентов
1. Общая схема алгоритмов сопряженных градиентов 2. Метод сопряженных градиентов с восстановлением 3. Реализуемые модификации алгоритмов сопряженных градиентов 4. Метод сопряженных градиентов для минимизации квадратичных функций 5. Реализуемая модификация алгоритма с переменной метрикой
2.5. Методы сопряженных направлений
1. Метод сопряженных направлений с восстановлением матрицы 2. Метод сопряженных направлений без восстановления матрицы 3. Минимизация квадратичных функций с помощью метода сопряженных направлений 4.Модифицированный метод сопряженных направлений, не требующий вычисления производных
2.6. Методы псевдообратных операторов
1. Основной алгоритм 2. Устойчивое псевдообращение плохо обусловленных матриц
2.7. Методы минимизации вдоль собственных векторов матрицы, близкой к матрице Гессе
1. Основной вариант 2. Ускоренный вариант
2.8. Итеративные стохастические методы, использующие аналог функции Ляпунова
1. Основной алгоритм 2. Сходимость алгоритма в среднем
3. Сходимость алгоритма почти наверное 4. Модификации алгоритма
2.9. Стохастические квазиградиентные методы
1. Общий стохастический квазиградиентный метод для детерминированных задач 2. Общий стохастический квазиградиентный метод для стохастических задач 3. Стохастический квазиградиентный метод с процедурой прерывания 4. Стохастический квазиградиентный метод о постоянным шаговым множителем 5. Стохастический градиентный метод минимизации сложных функций регрессии
2.10. Метод локальных вариации
2.11. Методы самонастраивающихся программ
2.12. Общий метод спуска
2.13 Методы случайного поиска
1. Алгоритм случайного поиска в выпуклых задачах минимизации 2. Адаптивный алгоритм случайного поиска
Глава 3. Методы оптимизации недифференцируемых функций и методы отыскания седловых точек
3.1. Методы обобщенного градиентного спуска
1. Алгоритм с постоянным шаговым множителем 2. Основной алгоритм 3. Модификация основного алгоритма 4. Первый алгоритм со специальным выбором шага 5. Второй алгоритм со специальным выбором шага 6. Алгоритм, использующий априорное знание минимума функции 7.Помехоустойчивый алгоритм
8. Многошаговый метод обобщенного градиентного спуска 9. е-субградиентный метод
3 2. Методы градиентного типа с растяжением пространства
3.3. Методы градиентного типа с растяжением пространства в направлении разности двух последовательных почти градиентов (r (?) алгоритм)
3.4. Методы локального случайного поиска
1. Алгоритм локального случайного поиска с парной пробой 2. Алгоритм локального случайного поиска с возвратом при неудачном шаге 3. Алгоритм локального случайного поиска с линейной экстраполяцией 4. Алгоритм случайного поиска по наилучшей пробе с накоплением 5. Алгоритм статистического градиента
3.5. Псевдоградиентные методы адаптации и обучения
3.6. Квазиградиентные методы
1. Квазиградиентный метод минимизации слабовыпуклой вниз функции 2. Стохастический квазиградиентный метод минимизации слабовыпуклой функции
3.7. е-квазиградиентные методы
1. е-квазиграднентный метод минимизации выпуклых функций 2.е-квазиградиентный метод минимизации слабовыпуклых функций
3.8. Методы обобщенных почти градиентов для минимизации функций, удовлетворяющих локальному условию Липшица
1. Детерминированный случай 2. Стохастический случай
3.9. Метод усреднения направлении спуска для минимизации функций, удовлетворяющих условию Липшица
3.10 Конечно-разностный метод минимизации разрывных функций
3.11. Метод линеаризации решения дискретных минимаксных задач
3.12. Методы последовательных приближений для решения дискретных минимаксных задач
1. Первый метод последовательных приближений 2. Модификация первого метода последовательных приближений 3. Второй метод последовательных приближений 4. Модификация второго метода последовательных приближений 5. Третий метод последовательных приближений, использующий D-функцию
3.13. Сеточный метод последовательных приближении решения непрерывных минимаксных задач
3.14. Методы Эрроу - Гурвица решения непрерывных минимаксных задач
1. Детерминированный метод Эрроу - Гурвица 2. Стохастический метол Эрроу - Гурвица
3.15. Методы экстремального базиса для решения непрерывных минимаксных задач
1. Принципиальный алгоритм 2. е-метод 3. р-метод
4. Комбинированный е, р-метод
3.16. Обобщенный градиентный метод отыскания седловых точек
3.17. Квазиградиентные методы решения дискретных минимаксных задач стохастического программирования
1. Минимизация функции Е? mах iej(?i) (x, ?) 2. Минимизация функции Е? mах iej (?i) (x, ?)
Часть II. Методы условной оптимизации
Глава 4. Методы решения задач линейного программирования
4.1. Симплекс-метод и его варианты
1. Симплекс-метод решения невырожденной канонической задачи линейного программирования
2. Методы отыскания исходного базиса 3. Симплекс-метод решения вырожденной канонической задачи линейного программирования 4. Модифицированный симплекс- метод
4.2. Двойственный симплекс-метод
1. Основной алгоритм 2. Методы отыскания исходного опорного
решения сопряженной задачи 3. Правило выбора вектора аs вводимого в базис, гарантирующее от зацикливания в вырожденном случае
4.3. Методы последовательного сокращения невязок
1. Метод последовательного сокращения Невязок; 2. Метод двусторонних оценок
4.4. Обобщенный симплекс-метод
4.5. Методы блочного программирования
1. Метод разложения Данцига - Вулфа 2. Метод разложения решения задач линейного программирования с блочно-диагональной матрицей 3. Метод, использующий обобщенный градиентный спуск
4.6. Модификация симплекс-метода для решения задачи линейного программирования с двусторонними ограничениями
1. Основной алгоритм 2. Правило выбора индекса r (определяющего вектор аir выводимый из базиса) для предотвращения зацикливания
4.7. Модификация симплекс-метода для решения общей задачи линейного программирования
4.8. Итеративные методы
1. Итеративный метод Петшиковского 2. Итеративный метод, использующий модифицированную функцию Лагранжа 3. Итеративный метод Федоренко 4. Алгоритм «Заяц» решения прямой и двойственной задач линейного программирования 5. Итерационный метод, использующий модифицированную функцию Лагранжа для решения двойственной пары задач линейного программирования
4.9. Методы параметрического программирования
1. Случай наличия параметра в целевой функции 2. Случай наличия параметра и правых частях ограничений
4.10. Опорные методы
1. Прямой опорный метод 2. Метод обратной матрицы
Глава 5. Методы решения задач нелинейного и стохастического программирования
5.1. Методы Проекции градиента
I. Общий алгоритм 2. Метод проекции градиента для минимизации функций при линейных ограничениях 3. Гибридный метод проекции градиента для минимизации функций при нелинейных ограничениях 4. Метод проекции градиента при наличии возмущений
5.2. Общий метод штрафных функций
5.3. Методы внешних штрафных функций
1. Задачи с ограничениями в виде неравенств 2. Задачи с ограничениями в виде равенств
3. Модифицированные методы с процедурой прерывания 4. Метод внешних штрафных функций для минимизации недифференцируемых функций
5.4. Методы внутренних штрафных функций
1. Общая схема 2. Реализуемая схема с процедурой прерывания 3. Алгоритмы внутренней точки с применением Q-функцнй
5.5. Комбинированные методы штрафных функций
5.6. Стохастический метод штрафов
5.7. Методы возможных направлений
1. Методы возможных направлений решения задач минимизации с ограничениями типа неравенств 2. Методы возможных направлений решения задач минимизации с ограничениями смешанного типа
3. Метод возможных направлений с квадратичным поиском 4. Модифицированный метод возможных направлений Зойтендейка 5. Аналог метода возможных направлений в задачах минимизации почти дифференцируемых функций 6. Стохастический аналог метода возможных направлений 7. Методы возможных направлений для отыскания точек локальных минимумов невыпуклой функции на невыпуклом множестве
5.8. Методы центров
1. Основной вариант 2. Модифицированный метод центров 3. Реализация модифицированного метода центров с использованием метода золотого сечения 4. Реализация модифицированного метода центров с использованием функций прерывания
5 9. Методы чебышевских центров
1. Метод чебышевских центров 2. Модифицированный метод чебышевскнх центров
5.10. Методы типа Ньютона
1. Метод типа Ньютона о регулировкой шага 2. Метод типа Ньютона при наличии возмущений
3. Квазиньютоновские методы
5.11. Методы линеаризации
1. Ограничения типа неравенств 2. Ограничения типа равенств
3. Ограничения смешанного типа 4. Метод линеаризации, практически реализуемый на ЭВМ
5. Аналог метода линеаризации в детерминированных задачах минимизации почти дифференцируемых функций 6. Аналог метода линеаризации в стохастических задачах минимизации почти дифференцируемых функций 7. Стохастический метод линеаризации
5.12. Методы линеаризации в предельных экстремальных задачах
1. Детерминированный случай 2. Стохастический случай
5.13. Методы отсечения
1. Линейный случай. Общий случай 3. Метод отсечения с растяжением пространства для решения задач выпуклого программирования
5.14. Методы, использующие функцию Лагранжа
1. Градиентный метод для задач с ограничениями типа неравенств 2. Градиентный метод для задач с ограничениями типа равенств 3. Метод квадратичной аппроксимации для задач с ограничениями типа равенств 4. Двойственный метод для задач с ограничениями типа равенств 5. Метод Ньютона для задач с ограничениями типа равенств
5.15. Методы, использующие модифицированные функции Лагранжа
1. Градиентный метод 2. Метод. использующий штрафные функции экспоненциального типа
5.16. Методы нагруженного функционала
1. Общий случай 2. Выпуклый случай 3. Приближенная схема
5.17. Методы штрафных оценок
1. Детерминированный случай 2. Стохастический случай
3. Метод штрафных оценок для задач выпуклого программирования
5.18. Методы проектирования обобщенного градиента
1. Основной алгоритм 2. Многошаговый метод обобщенного градиентного спуска 3. Методы проектирования обобщенного градиента для решения предельных экстремальных задач
5.19. Методы условного градиента
1. Реализуемый метод условного градиента 2. Алгоритм Франка - Вулфа 3. Ускоренный алгоритм Франка - Вулфа
5.20. Методы сопряженных градиентов
1. Метод сопряженных градиентов 2. Стохастический аналог метода сопряженных градиентов
5.21. Методы управляющих последовательностей
1. Общий метод минимизации при наличии ограничений 2. Метод управляющих последовательностей
5.22. Методы внутренней аппроксимации
5.23. Методы покоординатного спуска
1. Детерминированный покоординатный спуск 2. Случайный покоординатный спуск
5.24. Релаксационные методы для общих задач нелинейного программирования
1. Непрерывный вариант 2. Дискретный вариант
5.25. Методы фейеровских приближений решения задач выпуклого программирования с негладкими ограничениями
1. Общий случай 2. Случай кусочно-линейных ограничений
5.26. Двойственные методы
1. Приближенный двойственный метод решения задач выпуклого программирования
2. Двойственный алгоритм переменной метрики
5.27. Глобально сходящийся метод
5.28. Стохастические квазиградиентные методы
1. Метод проектирования стохастических квазиградиентов 2. Стохастический метод сокращения невязок в детерминированных задачах 3. Метод сокращения невязок в задачах стохастического программирования 4. Гибридный стохастический метод
5.29. Комбинированный метод стохастических градиентов и штрафных функций
5.30. Методы усреднения направлений спуска
1. Детерминированная задача 2. Стохастическая задача
5.31. Прямой метод решения задач стохастического программирования
5.32. Метод случайного поиска в выпуклых задачах минимизации
5.33. Методы решения задач оптимизации с бесконечным числом ограничений
1. Общий алгоритм 2. Ослабленный алгоритм
5.34. Методы решения задач квадратичного программирования
1. Метод сопряженных градиентов для минимизации квадратичной функции на подпространстве
2. Метод сопряженных градиентов для общей задачи квадратичного программирования 3. Метод сопряженных градиентов для задачи квадратичного программирования о простыми ограничениями 4. Модификация метода сопряженных направлений для задач квадратичного программирования большой размерности 5 Устойчивый алгоритм решения задач квадратичного программирования
Глава 6. Специальные методы решения минимаксных задач и методы отыскания седловых точек
6.1. Методы последовательных приближений решения дискретных минимаксных задач
1. Минимаксная задача с ограничениями простой структуры
2. Первый метод последовательных приближений решения минимаксной задачи с ограничениями типа неравенств 3. Второй метод последовательных приближений решения минимаксной задачи с ограничениями типа неравенств 4. Модификация второго метода последовательных приближений
6.2. Обобщенный беспараметрический метод внешней точки решения дискретных минимаксных задач
1. Основной алгоритм 2. Ускоренный вариант алгоритма
6.3. Метод второго порядка решения задач дискретного минимакса
6.4. Сеточный метод последовательных приближений решения непрерывных минимаксных задач
6.5. Метод штрафа в задаче поиска максимина
6 6. Методы стохастического квазиградиента в задаче поиска максимина
1. Основной алгоритм 2. Следящий алгоритм 3. Выпуклый случай
6.7. Метод невязок в задаче поиска максимина
6.8. Квазиградиентные методы решения непрерывных минимаксных задач стохастического программирования
1. Стохастический квазиградиентный метод 2. Модифицированный стохастический квазиградиентный метод
6.9. Градиентные методы отыскания седловых точек
1. Основной алгоритм 2. Градиентный метод отыскания седловых точек с постоянным шаговым множителем 3 Обобщенный градиентный метод
6.10 Метод экспоненциальных штрафов отыскания седловых точек
6.11. Задачи оптимального управления и оценивания. Методы развязывающих операторов
Список литературы
Предметный указатель