- Артикул:00-01117535
- Автор: А. С. Немировский, Д. Б. Юдин
- Тираж: 4600 экз.
- Обложка: Твердая обложка
- Издательство: Наука (все книги издательства)
- Город: Москва
- Страниц: 384
- Формат: 60х90 1/16
- Год: 1979
Развернуть ▼
Монография посвящена исследованию круга вопросов, относящихся к сложности задач и трудоемкости методов математического программирования. В книге рассматриваются теоретические потенциальные нижние границы трудоемкости численных методов решения экстремальных задач стандартных классов (гладких, негладких выпуклых, сильно выпуклых и гладких выпуклых, выпуклых стохастических) при различных предположениях о типе и качестве информации о задаче, доступной методу на каждом шаге. Предложены методы, в существенном реализующие эти потенциальные границы.
Монография рассчитана на специалистов, занимающихся теорией и приложениями численных методов оптимизации, в том числе на разработчиков алгоритмов для АСУ, и на студентов и аспирантов - математиков и вычислителей.
Содержание
Предисловие
Глава I. Введение
§ 1. Постановка проблемы оценки сложности задач оптимизации и основные результаты работы: неформальное описание
§ 2. Семейства задач математического программирования. Приближенные решения и их погрешность
§ 3. Численные методы решения задач математического программирования
§ 4. Характеристики методов па задаче и на классе. Сложность
§ 5. Некоторые утверждения о методах математического программирования
§ 6. О сложности классов многоэкстремальных задач
§ 7. Доказательство теоремы 3.4
Глава II. Выпуклое программирование. Методы с линейной сходимостью для классов общих выпуклых задач
§ 1. Выпуклые множества и выпуклые задачи
§ 2. Классы выпуклых экстремальных задач
§ 3. Метод центров тяжести для решения общих выпуклых задач
§ 4. Специальные версии МЦТ
§ 5. Реализуемый вариант МЦТ
Глава III. Методы зеркального спуска
§ 1. Идея методов
§ 2. Регулярные пространства
§ 3. ЗС-методы на классах липшицевых выпуклых задач
§ 4. Методы зеркального спуска для классов общих выпуклых задач
§ 5. Некоторые дополнительные доказательства
Глава IV. Сложность классов общих выпуклых задач (точный оракул первого порядка)
§ 1. Сложность классов общих выпуклых задач
§ 2. Сложность классов липшицевых выпуклых задач
§ 3. Рекомендации по применению методов решения общих (липшицевых) выпуклых задач
§ 4. Доказательство нижних оценок сложности. I
§ 5. Доказательство нижних оценок сложности. II
§ 6. Доказательство нижних оценок сложности. III
Глава V. Задачи выпуклого стохастического программирования
§ 1. Классы выпуклых задач стохастического программирования
§ 2. Оптимизация без ограничений
§ 3. Сложность задач стохастического программирования
Глава VI. Решение выпукло-вогнутых игр и задач стохастического программирования с ограничениями
§ 1. Классы выпукло-вогнутых игровых задач
§ 2. ЗС-методы решения игр: случай детерминированного оракула
§ 3. ЗС-методы решения игр: случай стохастического оракула
§ 4. Решение выпуклых операторных неравенств
§ 5. Решение экстремальных задач с операторными ограничениями
§ 6. Решение условных стохастических задач
§ 7. Задачи «сложного» стохастического программирования
Глава VII. Сильно выпуклые задачи
§ 1. Классы гладких и сильно выпуклых экстремальных задач
§ 2. Квадратичное программирование и оценка снизу сложности сильно выпуклых классов
§ 3. Сильно выпуклое программирование: безусловные задачи
§ 4. Задача на минимакс
§ 5. Решение условных сильно выпуклых и гладких задач
§ 6. Доказательство теоремы 4.3
Глава VIII. Эффективность стандартных методов сильно выпуклого программирования
§ 1. О стандартных методах сильно выпуклого программирования
§ 2. Метод Флетчера - Ривса
§ 3. Метод Полака - Рибьера
§ 4. Метод проекций Зойтендейка
§ 5. Замечания о методе Давидона - Флетчера - Пауэлла
Глава IX. Методы выпуклого программирования нулевого порядка
§ 1. Методы нулевого порядка: детерминированный оракул. I
§ 2. Методы нулевого порядка: детерминированный оракул. II
§ 3. Методы нулевого порядка: стохастический оракул. I
§ 4. Методы нулевого порядка: стохастический оракул. II
Приложение. Математические дополнения
§ 1. Польские пространства, борелевы функции, меры
§ 2. Банаховы пространства
Основные обозначения
Литература
Предметный указатель