К.2. ч.3. Киев: Освіта України, 2011. - 456 с.
Настоящая работа является систематическим изложением базовой теории оптимизации для конечномерных задач. Основное внимание уделяется идейным основам методов, их сравнительному анализу и примерам использования. Охвачен широкий круг задач — от безусловной минимизации до условной минимизации. Обсуждается методика постановки и решения прикладных проблем оптимизации. Приводятся условия экстремума, теоремы существования, единственности и устойчивости решения для основных классов задач. Исследуется влияние помех, негладкости функций, вырожденности минимума.
Работа предназначена для магистров, аспирантов, докторантов, инженеров, экономистов, статистиков, вычислителей и всех тех, кто сталкивается с задачами оптимизации.
Оглавление
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.2. Квазидифференцируемые функции
1.2.1. Определение и примеры квазидифференцируемых Функций
1.2.2. Свойства квазидифференцируемых функций
1.2.3. Примеры вычисления квазидифференциалов
1.2.4. Квазидифференцируемость выпукло-вогнутой функции
1.2.5. Необходимые условия оптимальности квазидифференцируемой функции на E(n)
1.2.6. Квазидифференцируемые множества
1.2.7. Необходимые условия оптимальности квазидифференцируемой функции на квазидифференцируемом множестве
1.3. Минимизация на всем пространстве
1.3.1. Необходимые и достаточные условия минимума выпуклой функции на E(n)
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.4.Обобщенный градиентный спуск
1.4.1. Проблема регулировки шага в методе обобщенного градиентного спуска
1.4.2. Основные теоремы о сходимости обобщенного градиентного спуска
1.4.3. Случай сходимости ОГС со скоростью геометрической прогрессии
1.4.4. Обобщенный градиентный спуск и фейеровские приближения
1.4.5. е-субградиентные методы
1.4.6. Обобщение метода ОГС на класс невыпуклых функций
1.5. Методы градиентного типа с растяжением пространства
1.5.1. Эвристика, лежащая в основе методов с растяжением пространства
1.5.2. Операторы растяжения пространства
1.5.3. Обобщенный градиентный спуск с растяжением пространства в направлении градиента
1.5.4. Вопросы сходимости алгоритмов ОГСРП
1.5.5. Применение метода ОГСРП к решению системы нелинейных уравнений
1.5.6. Метод минимизации, использующий операцию растяжения пространства в направлении разности двух последовательных почти-градиентов
1.5.7. Обоснование сходимости одного из вариантов r-алгоритма
1.5.8. Связь между алгоритмами ОГСРП и алгоритмами последовательных отсечений
1.5.9. Модифицированные вычислительные схемы обобщенных градиентных методов с растяжением пространства
1.6. Использование методов негладкой оптимизации к решению задач птимизации
1.6.1 Использование обобщенных градиентных методов в схемах декомпозиции
1.6.2. Использование r-алгоритмов для решения нелинейных минимаксных задач
1.6.3. Субградиентные методы переменной метрики
1.6.4. Одноранговое семейство релаксационных субградиентных методов с растяжением пространства
1.6.5. Метод сопряженных субградиентов с растяжением пространства
1.6.6. Реализация алгоритмов однорангового семейства субградиентных методов
1.6.7. Недифференцируемые овражные двумерные тест-функции Рыкова
1.6.8. Недифференцируемые овражные трехмерные, четырехмерные и многомерные тест-функции Рыкова
1.6.9. Исследование сходимости мультистартового субградиентного метода оптимизации в пространстве вейвлет преобразования
1.6.10. Многошаговые и другие методы минимизации недифференцируемых функций
1.6.11. Методы минимизации выпуклых функций при наличии помех
1.6.12. Поисковые методы
Литература
Настоящая работа является систематическим изложением базовой теории оптимизации для конечномерных задач. Основное внимание уделяется идейным основам методов, их сравнительному анализу и примерам использования. Охвачен широкий круг задач — от безусловной минимизации до условной минимизации. Обсуждается методика постановки и решения прикладных проблем оптимизации. Приводятся условия экстремума, теоремы существования, единственности и устойчивости решения для основных классов задач. Исследуется влияние помех, негладкости функций, вырожденности минимума.
Работа предназначена для магистров, аспирантов, докторантов, инженеров, экономистов, статистиков, вычислителей и всех тех, кто сталкивается с задачами оптимизации.
Оглавление
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.2. Квазидифференцируемые функции
1.2.1. Определение и примеры квазидифференцируемых Функций
1.2.2. Свойства квазидифференцируемых функций
1.2.3. Примеры вычисления квазидифференциалов
1.2.4. Квазидифференцируемость выпукло-вогнутой функции
1.2.5. Необходимые условия оптимальности квазидифференцируемой функции на E(n)
1.2.6. Квазидифференцируемые множества
1.2.7. Необходимые условия оптимальности квазидифференцируемой функции на квазидифференцируемом множестве
1.3. Минимизация на всем пространстве
1.3.1. Необходимые и достаточные условия минимума выпуклой функции на E(n)
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.4.Обобщенный градиентный спуск
1.4.1. Проблема регулировки шага в методе обобщенного градиентного спуска
1.4.2. Основные теоремы о сходимости обобщенного градиентного спуска
1.4.3. Случай сходимости ОГС со скоростью геометрической прогрессии
1.4.4. Обобщенный градиентный спуск и фейеровские приближения
1.4.5. е-субградиентные методы
1.4.6. Обобщение метода ОГС на класс невыпуклых функций
1.5. Методы градиентного типа с растяжением пространства
1.5.1. Эвристика, лежащая в основе методов с растяжением пространства
1.5.2. Операторы растяжения пространства
1.5.3. Обобщенный градиентный спуск с растяжением пространства в направлении градиента
1.5.4. Вопросы сходимости алгоритмов ОГСРП
1.5.5. Применение метода ОГСРП к решению системы нелинейных уравнений
1.5.6. Метод минимизации, использующий операцию растяжения пространства в направлении разности двух последовательных почти-градиентов
1.5.7. Обоснование сходимости одного из вариантов r-алгоритма
1.5.8. Связь между алгоритмами ОГСРП и алгоритмами последовательных отсечений
1.5.9. Модифицированные вычислительные схемы обобщенных градиентных методов с растяжением пространства
1.6. Использование методов негладкой оптимизации к решению задач птимизации
1.6.1 Использование обобщенных градиентных методов в схемах декомпозиции
1.6.2. Использование r-алгоритмов для решения нелинейных минимаксных задач
1.6.3. Субградиентные методы переменной метрики
1.6.4. Одноранговое семейство релаксационных субградиентных методов с растяжением пространства
1.6.5. Метод сопряженных субградиентов с растяжением пространства
1.6.6. Реализация алгоритмов однорангового семейства субградиентных методов
1.6.7. Недифференцируемые овражные двумерные тест-функции Рыкова
1.6.8. Недифференцируемые овражные трехмерные, четырехмерные и многомерные тест-функции Рыкова
1.6.9. Исследование сходимости мультистартового субградиентного метода оптимизации в пространстве вейвлет преобразования
1.6.10. Многошаговые и другие методы минимизации недифференцируемых функций
1.6.11. Методы минимизации выпуклых функций при наличии помех
1.6.12. Поисковые методы
Литература