Осипенко К.Ю. Выпуклый анализ

URSS. 2022. 144 с. ISBN 978-5-9519-3296-9.

Серия: Учебник Школы прикладной математики и информатики МФТИ

Серия: Классический учебник МГУ

Белая офсетная бумага

Твердый переплет

Аннотация

Книга посвящена основам выпуклого анализа и его применению к задачам линейного программирования. В основе ее лежат курсы лекций, прочитанные автором на механико-математическом факультете МГУ имени М. В. Ломоносова и на факультете прикладной математики и управления МФТИ. Изложение основ выпуклого анализа ведется на простом, доступном языке, не требует дополнительных знаний, кроме самых начальных понятий из теории линейных нормированных пространств.... (Подробнее)

Оглавление

Предисловие к серии «Учебник Школы прикладной математики и информатики МФТИ»				6
Предисловие				8
Глава 1. Общая теория				9
1.1. Введение				9
1.2. Выпуклые множества				10
1.3. Аффинные подпространства				14
1.4. Теорема Каратеодори				18
1.5. Теоремы Радона и Хелли				22
1.6. Теоремы отделимости				26
1.7. Вторая теорема отделимости в конечномерном случае				28
1.8. Аффинная независимость. Симплексы				29
1.9. Относительная внутренность. Первая теорема отделимости в конечномерном случае				33
1.10. Выпуклые функции				36
1.11. Теорема Каруша—Куна—Таккера				39
1.12. Субдифференциал				43
1.13. Теорема Ферма в субдифференциальной форме				46
1.14. Субдифференциальное исчисление. Теорема Моро—Рокафеллара				48
1.15. Теорема Дубовицкого—Милютина				52
1.16. Субдифференциальная форма теоремы Каруша—Куна—Таккера				55
1.17. Двойственность выпуклых множеств				57
1.18. Двойственность выпуклых функций				58
1.19. Сопряженные функции. Преобразование Лежандра—Фенхеля—Юнга				61
1.20. Двойственность экстремальных задач				65
Глава 2. Линейное программирование				67
2.1. Задача линейного программирования в нормальной форме и двойственная к ней				67
2.2. Конус. Замкнутость конечнопорожденного конуса				68
2.3. Существование решения задачи линейного программирования и двойственной к ней				71
2.4. Теорема о двойственности в задаче линейного программирования				73
2.5. Различные формы задач линейного программирования и соответствующие двойственные задачи				75
2.6. Задача линейного программирования со смешанными ограничениями				78
2.7. Выпуклый анализ и теория линейных неравенств				80
2.8. Крайние точки в задаче линейного программирования				83
2.9. Симплекс-метод решения задач линейного программирования				87
2.10. Пример применения симплекс-метода				95
2.11. Метод искусственного базиса [-0.2pt]для нахождения начальной крайней точки				96
2.12. Примеры задач линейного программирования				100
2.12.1. Задача оптимального планирования производства				100
2.12.2. Транспортная задача				101
2.12.3. Задача на минимакс				102
2.13. Транспортная задача				103
2.14. Свойства транспортной задачи				107
2.15. Методы нахождения начальной крайней точки в транспортной задаче				109
2.15.1. Метод «северо-западного угла»				110
2.15.2. Минимум по матрице				113
2.15.3. Минимум по строке				115
2.15.4. Минимум по столбцу				117
2.16. Задача, двойственная к транспортной задаче. Метод потенциалов				120
2.17. Алгоритм решения транспортной задачи с помощью метода потенциалов				126
Глава 3. Дополнения				133
3.1. Наилучшее приближение в линейном нормированном пространстве				133
3.2. Наилучшее равномерное приближение многочленами. Теорема Чебышева				134
3.3. Многочлены Чебышева				138
Литература				140
Предметный указатель				141

Предисловие

Курс выпуклого анализа читается студентам третьего курса факультета управления и прикладной математики МФТИ в осеннем семестре. Он является первой частью курса оптимизации, который продолжает читаться в последующих семестрах. Свойство выпуклости позволяет проще решать оптимизационные задачи. Этим объясняется появление этой темы в самом начале рассмотрения задач оптимизации. Более того, на примере выпуклых задач ярко демонстрируется принцип двойственности, при котором каждой оптимизационной задаче ставится в соответствие некоторая другая, называемая двойственной. Совместное рассмотрение этих двух задач позволяет глубже изучить их свойства и получить решения, как правило, и той, и другой. Оптимизационные выпуклые задачи находят много применений на практике, в частности, в экономике. Поэтому в читаемом курсе уделяется достаточно внимания задачам линейного программирования.

В основе предлагаемого пособия лежат лекции, которые автор читал на механико-математическом факультете

МГУ и на факультете управления и прикладной математики МФТИ. При написании пособия автор систематически обращался к работам своих коллег Г. Г. Магарил-Ильяева, В. М. Тихомирова [5] и Э. М. Галеева [2], которым глубоко благодарен за ценные обсуждения и советы.

Об авторе

Осипенко Константин Юрьевич

Доктор физико-математических наук, профессор кафедры общих проблем управления механико-математического факультета МГУ имени М. В. Ломоносова. Читает курсы лекций по выпуклому анализу, вариационному исчислению и оптимальному управлению на механико-математическом факультете МГУ и на кафедре математических основ управления МФТИ. Область научных интересов: теория приближений, теория оптимального восстановления. Автор более 160 научных работ.