ББК 22.18 С 91 УДК 519.6 Рекомендовано Министерством высшего и среднего специального образования СССР для использования в учебном процессе студентами вузов, обучающимися по специальностям «Прикладная математика» и «Экономическая кибернетика» СухаревА.Г.,ТимоховА.В.,ФедоровВ.В. Курс методов оптими- зации.—М.: Наука, Главная редакция физико-математической литературы, 1986.—328 с. Книга написана на основе курсов лекций по оптимизации, которые на про- тяжении ряда лет читались авторами на факультете вычислительной математики и кибернетики МГУ. Основное внимание уделено методам минимизации функ- ций конечного числа переменных. Книга может служить также введением в вы- пуклый анализ и теорию условий оптимальности в экстремальных задачах. Для усвоения материала достаточно владения стандартными курсами математическо- го анализа и линейной алгебры. Для студентов и аспирантов, изучающих методы оптимизации, и специали- стов в области прикладной математики. Рецензенты: кафедра теории управления и исследования операций МФТИ; доктор физико-математических наук Л. Л. Петров 1702070000—006 053(02)-86 78-83 Издательство «Наука». Главная редакция физнко-математической литературы, 1986 ОГЛАВЛЕНИЕ Предисловие .................................... 5 Глава 1. Введение в оптимизацию ...................... 7 § 1. Понятие о задачах оптимизации ...,.,,,,.,........ 7 § 2. Начальные сведения о численных методах оптимизации ...,,. 30 Глава 2. Методы одномерной минимизации ................. 41 § 1. Численные методы минимизации унимодальных функций , . , , . 42 § 2, Численные методы минимизации многоэкстремальных функций . . 48 § 3. Понятие об оптимальных методах поиска экстремума ..,,,.. 52 Глава 3, Основы выпуклого анализа ..................... 56 § 1. Выпуклые множества .......................... 56 § 2. Теоремы отделимости и их некоторые приложения ......... 69 § 3. Выпуклые функции ........................... 86 § 4. Субградиент и субдифференциал выпуклой функции ........ 101 § 5. Системы выпуклых и линейных неравенств ............. 113 Глава 4. Теория необходимых и достаточных условий оптимальности . 121 § 1. Условия оптимальности в общей задаче минимизации ....... 121 § 2. Дифференциальные условия оптимальности в задаче математиче- ского программирования ........................ 129 § 3. Теория двойственности и недифференциальные условия оптималь- ности в задаче выпуклого программирования ............ 151 § 4. Условия оптимальности и двойственность в задачах линейного и квадратичного программирования ................... 171 Глава 5, Численные методы безусловной оптимизации .......... 186 § 1. Градиентный метод ........................... 186 § 2. Метод Ньютона и его модификации ................. 191 § 3, Методы сопряженных направлений .................. 197 § 4. Эвристические методы нулевого порядка ............... 206 Глава 6. Численные методы условной оптимизации ............ 210 § 1. Симплекс-метод решения задач линейного программирования . . . 210 § 2. Метод проекции градиента ....................... 224 § 3. Метод условного градиента ...................... 228 § 4. Конечный метод решения задач квадратичного программирования 232 § 5. Метод штрафных функций ...,....,,...,....,.... 240 § 6. Метод параметризации целевой функции ............... 262 § 7. Метод линеаризации .......................... 266 I* 3 Глава 7. Методы дискретной оптимизации ................. § 1, Примеры дискретных оптимизационных задач и вопросы эффек- тивности алгоритмов .......................... § 2. Целочисленные и частично целочисленные задачи линейного про- граммирования ........................... § 3. Решение задачи о коммивояжере методом ветвей и' границ . . '. . § 4. Метод динамического программирования ............... § 5. Целочисленная задача распределения ресурсов при вогнутых целе- вых функциях .............................. § 6. Приближенные методы ......................... Глава 8. Элементы теории оптимального управления ........... § 1. Постановка задачи оптимального управления ............ § 2. Принцип максимума Понтрягина ... .\ .............. § 3, Примеры применения принципа максимума ............. Приложение .................................... Список литературы ................................ Предметный указатель ....,......,.,.,,,.,........., СПИСОК ЛИТЕРАТУРЫ Алексеев В. М., Тихомиров В. М., Фомин С. В. Оптимальное уп- равление.—М.: Наука, 1979. А о к и М. Введение а методы оптимизации.—М.: Наука, 1977. Ax о А., ХопкрофгДж., Ульман Дж. Построение и анализ вычисли- тельных алгоритмов.—М.: Мир, 1979. АшмановС. А. Введение в математическую экономику.—М.: Наука, 1984. АшмановС. А. Линейное программирование.—М.: Наука, 1981. Белоусов Е.Г. Введение в выпуклый анализ и целочисленное програм- мирование.—М.: Изд-во МГУ, 1977. Базара М., Шетти К. Нелинейное программирование.—М.: Мир, 1982- . БатищевД.И. Поисковые методы оптимального проектирования. —М.: Сов. радио, 1975. Беллман Р. Динамическое программирование.—М.: ИЛ, 1960. БеллманР., Дрейфус С. Прикладные задачи динамического програм- мирования.—М.: Наука, 1965. Болтянский В. Г. Оптимальное управление дискретными системами. —М.: Наука, 1973. Васильев Ф.П. Численные методы решения экстремальных задач.—М.: Наука, 1980. Васильев Ф. П. Методы решения экстремальных задач.—М.: Наука, 1981. Гольштейн Е. Г. Теория двойственности в математическом программиро- вании и ее приложения,—М.: Наука, 1971. Гроссман К., К а план А. А. Нелинейное программирование на основе безусловной минимизации.—Новосибирск: Наука, 1981. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые за дачи.—М.: Мир, 1982. Данциг Д. Линейное программирование, его обобщения и применение.— М.: Прогресс, 1966. Даффин Р., ПитерсонЭ., Зенер К. Геометрическое программирова- ние.—М.: Мир, 1972. Демьянов В. Ф., Васильев Л. В. Недифференцируемая оптимизация. — М.: Наука, 1981. Евтушенко Ю. Г. Методы решения экстремальных задач и их примене- ние в системах оптимизации.—М.: Наука, 1982. Еремин И. И., Лстафьев Н. Н. Введение в теорию линейного и выпук- лого программирования.—М.: Наука, 1976. За нгвилл У. И. Нелинейное программирование. Единый подход.—М.: Сов. радио, 1973. 23. 3 асл а вс к и и Ю. Л. Сборник задач по линейному программированию,— М.: Наука, 1969. 24. Зойтендейк Г. Методы возможных направлений.—М.: ИЛ, 1963. 25. Ильин В. А., Позняк Э. Г. Линейная алгебра.—М.: Наука, 1978. 26. Ильин В. А., Садовничий В. А., С ендов Бл. X. Математический анализ.—М.; Наука, 1979. 27. Канторович Л. В., ГорсткоА.Б. Оптимальные решения в эконо- мике,—М.: Наука, 1972. 28. Карманов В. Г. Матема гическое программирование.—М.: Наука, 1980. 29. Корбут А. А., Ф и н к ель ште и н Ю. Ю. Дискретное программирова- ние.—М.: Наука, 1969. 30. Лотов А. В. Введение в экономико-математическое моделирование.—М.: Наука, 1984. 31. Лэсдон Л. С. Оптимизация больших систем.—М.: Наука, 1975. 32. М арчу к Г. И. Методы вычислительной магематики.—М.: Наука, 1980. 33. Михалевич В. С., Куке а А. И. Методы последовательной оптимиза- ции,—М.: Наука, 1983. 34. Моисеев Н. Н. Численные методы в теории оптимальных систем.—М.: Наука, 1971. 35. Моисеев Н. Н., Иванилов Ю. П., Столярова Е. М. Методы опти- мизации.—М.: Наука, 1978. 36. Неми ровски и А. С., Юдин Д. Б. Сложность задач и эффективность методов оптимизации. —М.: Наука, 1979. 37. О ре О. Теория графов.—М.: Наука, 1968. 38. Подиновский В. В., Ногин В. Д. Парето-оптимальные решения много- критериальных задач.—М.: Наука, 1982. 39. Поляк В. Т. Введение в оптимизацию.—М.: Наука, 1983. 40.ПонтрягинЛ.С., Болтянский В. Г., Гамкрелидзе Р. В., Ми- щенко Е. Ф. Математическая теория оптимальных процессов.—М.: Наука, 1976. 41. Пропой А. И. Элементы теории оптимальных дискретных процессов.— М.: Наука, 1973. 42. Пшеничный Б. Н. Выпуклый анализ и экстремальные задачи,—М.: Наука, 1980. 43. Пшеничный Б. Н. Необходимые условия экстремума.—М.: Наука, 1982. 44. Пшеничный Б. Н. Метод линеаризации.—М.: Наука, 1983. 45. Пшени ч ный Б. Н., Д а н и л и н Ю. М. Численные методы в экстремаль- ных задачах.—М,: Наука, 1975. 46. Рокафеллар Р. Выпуклый анализ.—М.: Мир, 1973. 47. С а а т и Т. Целочисленные методы оптимизации и связанные с ними экстре- мальные проблемы.—М.: Мир, 1973. 48. Сергиенко И. В., Каспшицкая М. Ф. Модели и методы решения на ЭВМ комбинаторных задач оптимизации.—Киев: Наук. думка, 1981. 49. Сергиенко И. В., Лебедева Т. Т., Рощин В. А. Приближенные ме- тоды решения дискретных задач оптимизации.—Киев: Наук. думка, 1980. 50. Современное состояние теории исследования операций /Под ред. Н. Н. Моисе- ева,—М.: Наука, 1979. 51. Стронгин Р. Г. Численные методы в многоэкстремальных задачах.—М. Наука,.1978. 32» 52. Сухарев А. Г. Оптимальный поиск экстремума.—М.: Изд-во МГУ, 1975. 53. Тимохов А. В. Математические модели экономического воспроизводства.— М.: Изд-во МГУ, 1982. 54. Тихонов А. Н., Арсенин В. Я. Методы решения некорректных задач. — М.: Наука, 1979. 55. Федоров В. В. Численные методы максимина.—М.: Наука, 1979. 56. Фиакко А., Мак-Кормик Г. Нелинейное программирование. Методы по- следовательной безусловной минимизации.—М.: Мир, 1972. 57. Хедли Дж. Нелинейное и динамическое программирование.—М.: Мир, 1967. 58. Цурков В. И. Декомпозиция в задачах большой размерности.—М.: Наука, 1981. 59. Численные методы условной оптимизации /Под ред. Ф. Гилла, У. Мюррэя — М.: Мир, 1977. 60. Шор Н. 3. Методы минимизации недифференцируемых функций и их прило- жения.—Киев: Наук. думка, 1979. 61. Юд и н Д. Б., Гольштейн Е. Г. Линейное программирование. —М.: Наука, 1969. 62. Юдин Д. Б., Юдин А. Д. Экстремальные модели в экономике.—М.: Экономика, 1979. 63. Avriel М. Nonlinear Programming: Analysis and Methods.—Englewood Cliffs: Prentice-Hall, 1976. 64. G i 11 P. E., M u г г а у W., W r i g h t М. Н. Practical Optimization. —London, N. Y.: Academic Press, 1981. (Русский перевод: ГиллФ., МюррейУ. Рай т М. Практическая оптимизация.—М.: Мир, 1985.) 65. JacobyS. L. S., Kowalik J. S., Pizzo J. T. Iterative Methods for Nonlinear Optimization Problems. — Englewood Cliffs: Prentice-Hall, 1972. ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ Алгоритм второго порядка 31 — комбинированного метода штрафов 255 — Лэнд и Дойг 281 — метода штрафов 253, 255 — — — непрерывный 258 — нулевого порядка 31 — оптимальный 52 — пассивного поиска минимума 43 — пассивный 31 — первого порядка 31 — полиномиальный 278 — последовательно-оптимальный 54 — последовательный 32 — экспоненциальный 278 Базис опорной точки 214 Барьерная штрафная функция 241, 244 Вариация игольчатая 309 Вектор Куна — Таккера 152 Внешняя штрафная функция 241, 244 Внутренность множества 318 Внутренняя штрафная функция 241, 244 Временная сложность алгоритма 278 Входная длина задачи 278 Выпуклое множество 16 Выпуклый конус 62 — многогранник 62 Гессиан 319 Гиперплоскость 17 — касательная 90 — опорная 73 — разделяющая 71 — собственно опорная 73 Градиент 9, 318 Граница множества 69, 318 — — относительная 69 Дробление шага 39 Задача безусловной оптимизации 9 — вариационного исчисления 313 — выпуклая 17 — выпуклого программирования 20 — двойственная 155 — дискретного программирования 26, 274 — дискретной оптимизации 26 — квадратичного программирования 22, 180, 262 — классическая на условный экстре- мум 12 — краевая принципа максимума 302 — оптимизации конечномерная 7 — лексикографическая 262 — математического программирования 18 — минимаксная 150, 262, 266 — о коммивояжере 275, 282, 287, 294 — оптимального быстродействия 298 — — управления 27, 296 _ _ _ Больца 298 — — — Лагранжа 298 _ -- _ Майера 298 — — — простейшая 310 — — — с закрепленным временем 298 — о рюкзаке 274 — оптимизации конечномерная 7 — проектирования точки 185, 225 — прямая 155 — распределения ресурсов 275, 290, — регулярная 130 — синтеза 312 — условной оптимизации 11 — целочисленного программирования 26 — экстремальная 8 — NP-полная 278 Замыкание множества 318 Значение задачи 155 Итерация метода 32 323 52. Сухарев А. Г. Оптимальный поиск экстремума.—М.: Изд-во МГУ, 1975. 53. Тимохов А. В. Математические модели экономического воспроизводства.— М.: Изд-во МГУ, 1982. 54. Тихонов А. Н., Арсенин В. Я. Методы решения некорректных задач. — М.: Наука, 1979. 55. Федоров В. В. Численные методы максимина.—М.: Наука, 1979. 56. Фиакко А., Мак-Кормик Г. Нелинейное программирование. Методы по- следовательной безусловной минимизации.—М.: Мир, 1972. 57. Хедли Дж. Нелинейное и динамическое программирование.—М.: Мир, 1967. 58. Цурков В. И. Декомпозиция в задачах большой размерности.—М.: Наука, 1981. 59. Численные методы условной оптимизации /Под ред. Ф. Гилла, У. Мюррэя — М.: Мир, 1977. 60. Шор Н. 3. Методы минимизации недифференцируемых функций и их прило- жения.—Киев: Наук. думка, 1979. 61. Юд и н Д. Б., Гольштейн Е. Г. Линейное программирование. —М.: Наука, 1969. 62. Юдин Д. Б., Юдин А. Д. Экстремальные модели в экономике.—М.: Экономика, 1979. 63. Avriel М. Nonlinear Programming: Analysis and Methods.—Englewood Cliffs: Prentice-Hall, 1976. 64. G i 11 P. E., M u г г а у W., W r i g h t М. Н. Practical Optimization. —London, N. Y.: Academic Press, 1981. (Русский перевод: ГиллФ., МюррейУ. Рай т М. Практическая оптимизация.—М.: Мир, 1985.) 65. JacobyS. L. S., Kowalik J. S., Pizzo J. T. Iterative Methods for Nonlinear Optimization Problems. — Englewood Cliffs: Prentice-Hall, 1972. ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ Алгоритм второго порядка 31 — комбинированного метода штрафов 255 — Лэнд и Дойг 281 — метода штрафов 253, 255 — — — непрерывный 258 — нулевого порядка 31 — оптимальный 52 — пассивного поиска минимума 43 — пассивный 31 — первого порядка 31 — полиномиальный 278 — последовательно-оптимальный 54 — последовательный 32 — экспоненциальный 278 Базис опорной точки 214 Барьерная штрафная функция 241, 244 Вариация игольчатая 309 Вектор Куна — Таккера 152 Внешняя штрафная функция 241, 244 Внутренность множества 318 Внутренняя штрафная функция 241, 244 Временная сложность алгоритма 278 Входная длина задачи 278 Выпуклое множество 16 Выпуклый конус 62 — многогранник 62 Гессиан 319 Гиперплоскость 17 — касательная 90 — опорная 73 — разделяющая 71 — собственно опорная 73 Градиент 9, 318 Граница множества 69, 318 — — относительная 69 Дробление шага 39 Задача безусловной оптимизации 9 — вариационного исчисления 313 — выпуклая 17 — выпуклого программирования 20 — двойственная 155 — дискретного программирования 26, 274 — дискретной оптимизации 26 — квадратичного программирования 22, 180, 262 — классическая на условный экстре- мум 12 — краевая принципа максимума 302 — оптимизации конечномерная 7 — лексикографическая 262 — математического программирования 18 — минимаксная 150, 262, 266 — о коммивояжере 275, 282, 287, 294 — оптимального быстродействия 298 — — управления 27, 296 _ _ _ Больца 298 — — — Лагранжа 298 _ -- _ Майера 298 — — — простейшая 310 — — — с закрепленным временем 298 — о рюкзаке 274 — оптимизации конечномерная 7 — проектирования точки 185, 225 — прямая 155 — распределения ресурсов 275, 290, — регулярная 130 — синтеза 312 — условной оптимизации 11 — целочисленного программирования 26 — экстремальная 8 — NP-полная 278 Замыкание множества 318 Значение задачи 155 Итерация метода 32 323 Классическая задача на условный экс- тремум 12 Компакт 318 Конус 57 — выпуклый 57 — заостренный 84 — многогранный 62 — рецессивный 69 Критерий Сильвестра 317 Линейная комбинация 58 — — аффинная 58 — — выпуклая 58 — — неотрицательная 58 Линейного программирования задача 22, 171 — — — каноническая 23 — — — общая 23 — — — основная 23 — — стандартная 23 — — — целочисленная 26, 279 — — — частично булева 26, 274 — — — — целочисленная 26, 279 Линейное подпространство 60 — — ортогональное 80 Линия уровня 11 Луч 16 Матрица неотрицательно определенная 317 — положительно определенная 317 — симметрическая 317 Метод бесконечношаговый 33 — ветвей и границ 280 — возмущений 163 — вращения системы координат 207 — градиентный 186 — динамического программирования 286 — дихотомии 43 — золотого сечения 45 — искусственного базиса 222 — квазиньютоновский 194, 195 — конечный (конечношаговый) 33 — кубической интерполяции 48 — линеаризации 266 — ломаных 49 — наискорейшего спуска 187 — Ньютона 192 — — с регулировкой шага 194 — оптимальный 52 — отсечения 280 — парабол 47 — параметризации целевой функции 262 — перебора 49 — переменной метрики 196 324 Метод покрытий 50 — проекции градиенга 226 — симплексный 208 — с модифицированной функцией Ла- гранжа 266 — сопряженных градиентов 201 — — направлений 198 — — — нулевого порядка 199 — спуска 36 — субградиентный 190 — условного градиента 228 — Фибоначчи 44 — центров 266 — штрафных функций 240 М-метод 223 Методы приближенные 292 — эвристические 206 Минор матрицы главный 317 — — угловой 317 Множества отделимые 70 — сильно отделимые 71 — собственно отделимые 71 Множество аффинное 57 — возможных направлений 121 — выпуклое 16 — дискретное 26 — допустимое 7 — замкнутое 318 — Лебега 96 — многогранное 81 — направлений убывания 121 — ограниченное 318 — открытое 318 — относительно открытое 64 — полиэдральное 17 — сопряженное 78 — технологическое 21 Множители Лагранжа 13 Надграфик 102 Направление возможное 121 — возрастания 36 — убывания 35, 121 Направления сопряженные 197 Неравенство Йенсена 87 Оболочка аффинная 59 — выпуклая 59 — коническая 59 Ограничения активные 132 — неравенства 19 — пассивные 132 — прямые 19 — равенства 19 — функциональные 19 Окрестность 318 Операция приведения 283 Оптимальная траектория 298 Относительная внутренность 64 Отображение выпуклозначное 106 — замкнутое 106 — локально ограниченное 106 — многозначное 106 — монотонное 106 — субдифференциальное 106 Отрезок 16 Полиэдр 17, 80 Полупространство 17 Последовательности эквивалентные 317 Последовательность минимизирующая 33 Правильное отсечение 280 Предел последовательности 317 — функции 317 Предельная точка 318 — — траектории 258 Приведенная матрица 283 Принцип Лагранжа 130 — максимума Понтрягина 299 — оптимальности 287 — уравнивания 151 Проекция 69 Производная по направлению 95, 319 Прямая 16 Размерность выпуклого множества 65 Симплекс 69 Симплекс-мегод 210 Симплекс-таблица 219 Скорость сходимости 33 — — геометрической прогрессии 33 — — градиентного метода 188 — — квадратичная 33 — — линейная 33 — — сверхлинейная 33 Сложность задач дискретной оптимиза- ции 277 Соотношение двойственности 156 Сопряженная система 299 Субградиент 102 Субдифференциал 102 Субдифференциальное отображение 106 Теорема двойственности 156 — — выпуклых множеств 79 — Дубовицкого—Милютина 84 — Каратеодори 61 — Куна—Таккера 139, 160, 162, 163 Теорема Люстерника 135 — о неявной функции 135 — отделимости 72, 74 — регулярности 115, 116, 117 — Фана 114 — Фаркаша 75 — Хелли 68 Теория двойственности 155 Точка внутренняя 318 — глобального минимума 7 — граничная 318 — допустимая 7 — крайняя выпуклого множества 76 — локального минимума 7 — минимума 7 — опорная 211 — — невырожденная 214 — особая 234 — относительно внутренняя 64 — предельная 318 — стационарная 13 — строгого минимума 7 — экстремума 8 Управление 296 — допустимое 296 — оптимальное 298 — программное 312 — синтезирующее 312 Уравнение Беллмана 287 — Эйлера 314 Условие второго порядка 141 — дополняющей нежесткости 132 — достаточное 9 — квазиньютоновское 195 — линейности 139 — необходимое 9 — оптимальности 9 —регулярности 130 — р-регулярности 245 — Слейтера 139 — — модифицированное 139 — трансверсальности 300 Условный антиградиент 229 Фазовые координаты 296 Формула Лагранжа 319 — Ньютона—Лейбница 319 — Тейлора 319 Функционал интегральный 298 — терминальный 298 Функция вогнутая 17, 86 — выпуклая 17, 86 — Гамильтона 299 — дважды дифференцируемая 319 — дифференцируемая 318 — — по направлению 319 325 Функция квадратичная 319 — квазивыпуклая 48, 101 — квазидифференцируемая 150 — Кобба—Дугласа 21 — Лагранжа 12, 129 — — регулярная 14, 130 — линейная 17 — непрерывная 317 — овражная 190 — полунепрерывная 100 — производственная 21 — сильно выпуклая 86 — строго выпуклая 17, 86 Функция унимодальная 42 — целевая 7 — числовая 317 — числового аргумента 317 Шаг метода 32 Штрафная функция 241 — — внешняя 241, 244 — — внутренняя (барьерная) 241, 244 — — квадратичная 244 — — степенная 244 Алексей Григорьевич Сухарев Александр Васильевич Т и м о х о в Вячеслав Васильевич Федоров КУРС МЕТОДОВ ОПТИМИЗАЦИИ Редактор Н. И. Воронина Художественный редактор Т. Н. Кольченко Технический редактор С. Я. Шкляр Корректоры: Е. Ю. Рычагова, Н. Д. Дорохова ИБ №. 12571 Сдано в набор 22.02.85. Подписано к печати 12.12.85. Т-22374. Формат 60x90'/i6. Бумага тип. № 2. Гар- нитура литературная. Печать высокая. Усл. печ. л. 20,5. Усл. кр.-отт. 20,5. Уч.-изд. л. 24.32. Тираж 13 000 экз. Заказ 1215. Цена 1 р. 80 к. Ордена Трудового Красного Знамени издательство «Наука» Главная редакция физико-математической литературы. 117071 Москва В-71, Ленинский проспект, 15 Отпечатано с матриц ордена Октябрьской Рево- люции, ордена Трудового Красного Знамени Ле- нинградского производственно-технического объ- единения <:Печатный Двор» имени А. М. Горь- кого Союзполиграфпрома при Государственном комитете СССР по делам издательств, полигра- фии и книжной торговли. 197136, Ленинград, П-136, Чкаловский пр., 15, в Ленинградской ти- пографии № 4 ордена Трудового Красного Зна- мени Ленинградского объединения «Техническая книга» им. Евгении Соколовой Союзполиграф- прома при Государственном комитете СССР по делам издательств, полиграфии и книжной торговли. 191126, Ленинград, Социалистиче- ская ул., 14.