К.2. ч.4. Киев: Освіта України, 2012. - 512 с.
Настоящая работа является систематическим изложением базовой теории оптимизации для конечномерных задач. Основное внимание уделяется идейным основам методов, их сравнительному анализу и примерам использования. Охвачен широкий круг задач — от безусловной минимизации до условной минимизации. Обсуждается методика постановки и решения прикладных проблем оптимизации. Приводятся условия экстремума, теоремы существования, единственности и устойчивости решения для основных классов задач.
Исследуется влияние помех, негладкости функций, вырожденности минимума. Работа предназначена для магистров, аспирантов, докторантов, инженеров, экономистов, статистиков, вычислителей и всех тех, кто сталкивается с задачами оптимизации.
Оглавление
1.Релаксационные методы безусловной оптимизации, основанные на принципах обучения
1.1. Релаксационные методы безусловной оптимизации гладких функций
1.1.1. Релаксационные методы безусловной оптимизации гладких функций
1.1.2. Выпуклые функции и их свойства
1.1.3. Условия экстремума задачи безусловной минимизации
1.1.4. Скорости сходимости последовательностей
1.1.5. Методы спуска
1.1.6. Оценка скорости сходимости методов спуска
1.1.7. Принципы организации методов одномерной минимизации22
1.1.8. Одномерный спуск с кубической интерполяцией
1.1.9. Градиентный метод
1.1.10. Метод Ньютона
1.1.11. Метод сопряженных градиентов
1.2. Квазиньютоновские методы минимизации, основанные на принципах обучения
1.2.1. Квазиньютоновские методы
1.2.2. Основные понятия теории обучения
1.2. 3. Вывод симметричных формул пересчета на основе одношагового алгоритма обучения
1.2.4. Вывод формулы пересчета BFGS основе одношагового алгоритма обучения, ее свойства, инвариантность
1.2.5. Глобальные скорость сходимости и ускоряющие свойства квазиньютоновских методов
1.2.6. Квазиньютоновский метод минимизации на основе двухшагового алгоритма обучения
1.2.7. Способы наращивания размерности подпространства квазиньютоновского соотношения
1.2.8. Обоснование сходимости квазиньютоновского метода минимизации на основе двухшагового алгоритма бучения
1.2.9. Результаты вычислительного эксперимента
1.3.Релаксационные субградиентные методы, основанные на принципах обучения
1.3.1.Основы негладкой оптимизации
1.3.2. Подход создания субградиентных методов типа «сопряженных субградиентов», основанных на принципах адаптации и обучения
1.3.3. Алгоритм с растяжением пространства для решения множества равенств
1.3.4. Алгоритм с растяжением пространства для решения множества неравенств
1.3.5. Релаксационный субградиентный метод с растяжением пространства в направлении субградиента
1.3.6. Связь релаксационного субградиентного метода с растяжением пространства с методом сопряженных градиентов
1.3.7. Реализация релаксационного субградиентного метода с растяжением пространства в направлении субградиента
1.3.8. Итерационный метод решения множества неравенств на основе алгоритма Качмажа
1.3.9. Алгоритм минимизации на основе алгоритма Качмажа
для решения множества неравенств
1.3.10. Релаксационный субградиентный метод с растяжением пространства в направлении субградиента
1.3.11.Связь релаксационного субградиентного метода с растяжением пространства с методом сопряженных градиентов
1.3.12.Реализация релаксационного субградиентного метода с растяжением пространства в направлении субградиента
13.13.Итерационный метод решения множества неравенств на основе алгоритма Качмажа
1.3.14.Алгоритм минимизации на основе алгоритма Качмажа для решения множества неравенств
1.3.15. Связь с методом сопряженных градиентов
1.3.16.Реализация алгоритма минимизации на основе алгоритма Качмажа для решения множества неравенств
1.3.17. Результаты численного исследования реализаций релаксационных субградиентных методов
1.4.Одноранговое семейство субградиентных методов с растяжение пространства, основанных на принципах обучения
1.4.1. Метод сопряженных субградиентов с растяжением пространства
1.4.2. Одноранговое семейство релаксационных субградиентных методов с растяжением пространства
1.4.3. Реализация алгоритмов однорангового семейства субградиентных методов
1.4.4. Анализ глобальной скорости сходимости алгоритма с растяжением пространства в направлении разности последовательных субградиентов
2.Рандомизированные алгоритмы оценивания и оптимизации при наличии помех
2.1. Основные элементы теории оценивания и оптимизации
2.1.1. Некоторые задачи и методы теории оценивания
2.1.2. Задача об обнаружении сигнала
2.1.3. Рандомизированные алгоритмы
2.1.4. Функционал среднего риска
2.1.5. Предсказание значений случайного процесса
2.2. Элементы регрессионного анализа, МНК
2.2.1. Наилучшая аппроксимация одной случайной величины с помощью другой
2.2.2. Оценивание по конечному числу наблюдений
2.2.3. Рекуррентные модификации МНК
2.3Оптимальная фильтрация случайных процессов
2.3.1Фильтр Винера–Колмогорова
2.3.2 Фильтр Калмана–Бьюси
2.4.Метод стохастической аппроксимации
2.4.1.Поиск корня неизвестной функции. Алгоритм Роббинса–Монро
2.4.2 Процедура Кифера-Вольфовица
2.4.3 Рандомизированные алгоритмы стохастической аппроксимации
2.4.4 Пассивная стохастическая аппроксимация
2.4.5Модификации алгоритмов СА
2.5.Алгоритмы случайного поиска
2.6. Элементы теории оценивания
2.6.1. Метод эмпирического функционала
2.6.2.Байесовские оценки
2.6.3.Метод максимума правдоподобия
2.6.4.Достижимая точность оценивания
2.7.Задачи оценивании и оптимизации при ограниченных, а в остальном произвольных помехах
2.7.1.Случайный сигнал, наблюдаемый на фонеограниченных помех
2.7.2.Метод рекуррентных целевых неравенств. Конечно-сходящиеся алгоритмы
2.7.3.Алгоритм Полоска
2.7.4. Стабилизирующий алгоритм "модифицированная полоска" при управлении линейным объектом
2.7.5.Метод эллипсоидов
3. Линейные задачи оценивания и оптимизации при почти произвольных помехах
3.1. Оценка параметров линейной регрессии с произвольными помехами
3.1.1.Постановка задачи, основные предположения
3.1.2.Оценивание по методу стохастической аппроксимации
3.1.3.Оценки по методу наименьших квадратов
3.2. Оценка параметров авторегрессии и скользящего среднего
3.2.1.Применение к моделям авторегрессии
3.2.2.Оценивание параметров модели скользящего среднего
3.2.3.Идентификация динамического объекта
3.2.4.Пробный сигнал
3.2.5.Введение параметра оценивания
3.2.6.Рандомизированный алгоритм идентификации
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.5. Доказательства теорем 3.1-36
4. Рандомизированные алгоритмы стохастической аппроксимации
4.1Формулировки и обоснования рандомизированных алгоритмов СА
4.1.1.Постановка задачи и основные предположения
4.1.2.Пробное возмущение и рандомизированные алгоритмы.
4.1.3.Сходимость оценок с вероятностью единица и в среднеквадратичном смысле
4.1.4.Дифференцирующие ядра и выбор распределения пробного возмущения
4.1.5.Скорость сходимости оценок
4.2. Оптимальные порядки точности алгоритмов стохастической оптимизации
4.2.1.Минимаксный порядок скорости сходимости рандомизированных алгоритмов СА
4.2.2.Нижняя граница для асимптотической скорости сходимости
4.3. Экспериментальные результаты
4.3.1.Сравнительное моделирование оценок ККВ и SPSA алгоритмов
4.3.2.Пошаговое выполнение алгоритма
4.4Доказательства теорем 4.1 и 4.2
5.Применения рандомизированных алгоритмов
5.1.Способ обнаружения некоторых элементов химического состава мишени
5.2.Адаптивное управление при произвольных ограниченных помехах
5.2.1.Рандомизиованный алгоритм идентификации
5.2.2.Адаптивная оптимизация
5.2.3.Адаптивное оптимальное управление неминимально–фазовым объектом второго порядка
5.3.Обучающиеся системы
5.3.1. Аппроксимация функции с помощью линейной комбинации известных функций
5.3.2.Модель обучаемой системы. Нейронные сети
5.3.3.Задача самообучения
5.3.4.Синхронизация сигналов светофоров при управлении движением на сети дорог
5.3.5.Оптимальный выбор целей для систем оружия
5.3.6.Поиск скрытых объектов с помощью ЭЛО
5.3.7.Исследование ритмической структуры стихов
5.4.Оптимизация систем реального времени
5.4.1.Отслеживание дрейфа экстремума нестационарного функционала
5.4.2Оптимизация работы маршрутизатора
5.4.3.Оптимизация работы сервера
5.4.4.Расчет цен опционов
5.5.Квантовые компьютеры и рандомизированные алгоритмы
5.6.Доказательство лемм 5.1–5.3
Приложение
Литература
Настоящая работа является систематическим изложением базовой теории оптимизации для конечномерных задач. Основное внимание уделяется идейным основам методов, их сравнительному анализу и примерам использования. Охвачен широкий круг задач — от безусловной минимизации до условной минимизации. Обсуждается методика постановки и решения прикладных проблем оптимизации. Приводятся условия экстремума, теоремы существования, единственности и устойчивости решения для основных классов задач.
Исследуется влияние помех, негладкости функций, вырожденности минимума. Работа предназначена для магистров, аспирантов, докторантов, инженеров, экономистов, статистиков, вычислителей и всех тех, кто сталкивается с задачами оптимизации.
Оглавление
1.Релаксационные методы безусловной оптимизации, основанные на принципах обучения
1.1. Релаксационные методы безусловной оптимизации гладких функций
1.1.1. Релаксационные методы безусловной оптимизации гладких функций
1.1.2. Выпуклые функции и их свойства
1.1.3. Условия экстремума задачи безусловной минимизации
1.1.4. Скорости сходимости последовательностей
1.1.5. Методы спуска
1.1.6. Оценка скорости сходимости методов спуска
1.1.7. Принципы организации методов одномерной минимизации22
1.1.8. Одномерный спуск с кубической интерполяцией
1.1.9. Градиентный метод
1.1.10. Метод Ньютона
1.1.11. Метод сопряженных градиентов
1.2. Квазиньютоновские методы минимизации, основанные на принципах обучения
1.2.1. Квазиньютоновские методы
1.2.2. Основные понятия теории обучения
1.2. 3. Вывод симметричных формул пересчета на основе одношагового алгоритма обучения
1.2.4. Вывод формулы пересчета BFGS основе одношагового алгоритма обучения, ее свойства, инвариантность
1.2.5. Глобальные скорость сходимости и ускоряющие свойства квазиньютоновских методов
1.2.6. Квазиньютоновский метод минимизации на основе двухшагового алгоритма обучения
1.2.7. Способы наращивания размерности подпространства квазиньютоновского соотношения
1.2.8. Обоснование сходимости квазиньютоновского метода минимизации на основе двухшагового алгоритма бучения
1.2.9. Результаты вычислительного эксперимента
1.3.Релаксационные субградиентные методы, основанные на принципах обучения
1.3.1.Основы негладкой оптимизации
1.3.2. Подход создания субградиентных методов типа «сопряженных субградиентов», основанных на принципах адаптации и обучения
1.3.3. Алгоритм с растяжением пространства для решения множества равенств
1.3.4. Алгоритм с растяжением пространства для решения множества неравенств
1.3.5. Релаксационный субградиентный метод с растяжением пространства в направлении субградиента
1.3.6. Связь релаксационного субградиентного метода с растяжением пространства с методом сопряженных градиентов
1.3.7. Реализация релаксационного субградиентного метода с растяжением пространства в направлении субградиента
1.3.8. Итерационный метод решения множества неравенств на основе алгоритма Качмажа
1.3.9. Алгоритм минимизации на основе алгоритма Качмажа
для решения множества неравенств
1.3.10. Релаксационный субградиентный метод с растяжением пространства в направлении субградиента
1.3.11.Связь релаксационного субградиентного метода с растяжением пространства с методом сопряженных градиентов
1.3.12.Реализация релаксационного субградиентного метода с растяжением пространства в направлении субградиента
13.13.Итерационный метод решения множества неравенств на основе алгоритма Качмажа
1.3.14.Алгоритм минимизации на основе алгоритма Качмажа для решения множества неравенств
1.3.15. Связь с методом сопряженных градиентов
1.3.16.Реализация алгоритма минимизации на основе алгоритма Качмажа для решения множества неравенств
1.3.17. Результаты численного исследования реализаций релаксационных субградиентных методов
1.4.Одноранговое семейство субградиентных методов с растяжение пространства, основанных на принципах обучения
1.4.1. Метод сопряженных субградиентов с растяжением пространства
1.4.2. Одноранговое семейство релаксационных субградиентных методов с растяжением пространства
1.4.3. Реализация алгоритмов однорангового семейства субградиентных методов
1.4.4. Анализ глобальной скорости сходимости алгоритма с растяжением пространства в направлении разности последовательных субградиентов
2.Рандомизированные алгоритмы оценивания и оптимизации при наличии помех
2.1. Основные элементы теории оценивания и оптимизации
2.1.1. Некоторые задачи и методы теории оценивания
2.1.2. Задача об обнаружении сигнала
2.1.3. Рандомизированные алгоритмы
2.1.4. Функционал среднего риска
2.1.5. Предсказание значений случайного процесса
2.2. Элементы регрессионного анализа, МНК
2.2.1. Наилучшая аппроксимация одной случайной величины с помощью другой
2.2.2. Оценивание по конечному числу наблюдений
2.2.3. Рекуррентные модификации МНК
2.3Оптимальная фильтрация случайных процессов
2.3.1Фильтр Винера–Колмогорова
2.3.2 Фильтр Калмана–Бьюси
2.4.Метод стохастической аппроксимации
2.4.1.Поиск корня неизвестной функции. Алгоритм Роббинса–Монро
2.4.2 Процедура Кифера-Вольфовица
2.4.3 Рандомизированные алгоритмы стохастической аппроксимации
2.4.4 Пассивная стохастическая аппроксимация
2.4.5Модификации алгоритмов СА
2.5.Алгоритмы случайного поиска
2.6. Элементы теории оценивания
2.6.1. Метод эмпирического функционала
2.6.2.Байесовские оценки
2.6.3.Метод максимума правдоподобия
2.6.4.Достижимая точность оценивания
2.7.Задачи оценивании и оптимизации при ограниченных, а в остальном произвольных помехах
2.7.1.Случайный сигнал, наблюдаемый на фонеограниченных помех
2.7.2.Метод рекуррентных целевых неравенств. Конечно-сходящиеся алгоритмы
2.7.3.Алгоритм Полоска
2.7.4. Стабилизирующий алгоритм "модифицированная полоска" при управлении линейным объектом
2.7.5.Метод эллипсоидов
3. Линейные задачи оценивания и оптимизации при почти произвольных помехах
3.1. Оценка параметров линейной регрессии с произвольными помехами
3.1.1.Постановка задачи, основные предположения
3.1.2.Оценивание по методу стохастической аппроксимации
3.1.3.Оценки по методу наименьших квадратов
3.2. Оценка параметров авторегрессии и скользящего среднего
3.2.1.Применение к моделям авторегрессии
3.2.2.Оценивание параметров модели скользящего среднего
3.2.3.Идентификация динамического объекта
3.2.4.Пробный сигнал
3.2.5.Введение параметра оценивания
3.2.6.Рандомизированный алгоритм идентификации
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.5. Доказательства теорем 3.1-36
4. Рандомизированные алгоритмы стохастической аппроксимации
4.1Формулировки и обоснования рандомизированных алгоритмов СА
4.1.1.Постановка задачи и основные предположения
4.1.2.Пробное возмущение и рандомизированные алгоритмы.
4.1.3.Сходимость оценок с вероятностью единица и в среднеквадратичном смысле
4.1.4.Дифференцирующие ядра и выбор распределения пробного возмущения
4.1.5.Скорость сходимости оценок
4.2. Оптимальные порядки точности алгоритмов стохастической оптимизации
4.2.1.Минимаксный порядок скорости сходимости рандомизированных алгоритмов СА
4.2.2.Нижняя граница для асимптотической скорости сходимости
4.3. Экспериментальные результаты
4.3.1.Сравнительное моделирование оценок ККВ и SPSA алгоритмов
4.3.2.Пошаговое выполнение алгоритма
4.4Доказательства теорем 4.1 и 4.2
5.Применения рандомизированных алгоритмов
5.1.Способ обнаружения некоторых элементов химического состава мишени
5.2.Адаптивное управление при произвольных ограниченных помехах
5.2.1.Рандомизиованный алгоритм идентификации
5.2.2.Адаптивная оптимизация
5.2.3.Адаптивное оптимальное управление неминимально–фазовым объектом второго порядка
5.3.Обучающиеся системы
5.3.1. Аппроксимация функции с помощью линейной комбинации известных функций
5.3.2.Модель обучаемой системы. Нейронные сети
5.3.3.Задача самообучения
5.3.4.Синхронизация сигналов светофоров при управлении движением на сети дорог
5.3.5.Оптимальный выбор целей для систем оружия
5.3.6.Поиск скрытых объектов с помощью ЭЛО
5.3.7.Исследование ритмической структуры стихов
5.4.Оптимизация систем реального времени
5.4.1.Отслеживание дрейфа экстремума нестационарного функционала
5.4.2Оптимизация работы маршрутизатора
5.4.3.Оптимизация работы сервера
5.4.4.Расчет цен опционов
5.5.Квантовые компьютеры и рандомизированные алгоритмы
5.6.Доказательство лемм 5.1–5.3
Приложение
Литература