ОТ АВТОРА Эта книга была написана в 1980 г. и опубликована в 1983г.; английский перевод появился в 1987 г. В то время казалось, что теория и методы решения задач оптимизации в основном сформированы и устоялись. Целью книги была систематизация этой области знаний, изложение разнообразных алгоритмов с единой точки зрения и сравнение их. Однако вскоре последовали революционные события, которые привели к существенному пересмотру как общей идеологии оптимизации, так и появлению принципиально новых методов. В 1984 г. была опубликована статья Кармаркара, в которой предлагался итеративный алгоритм линейного программирования, радикально отличающийся от симплекс-метода. Алгоритм сопровождался оценкой его трудоемкости (оценкой числа итераций, необходимых для достижения заданной точности); эта оценка оказывалась полиномиально зависящей от размерности задачи. Такие оценки существовали и раньше (например, для метода эллипсоидов), однако метод Кармаркара оказался удивительно эффективным и с вычислительной точки зрения. Вскоре методы с полиномиальной оценкой появились и для других задач выпуклой оптимизации. Фундаментальную роль сыграло понятие самосогласованных функций, введенное Ю. Е. Нестеровым и А. С. Немировским; эти методы получили название методов внутренней точки. Оказалось, что они могут быть обобщены на задачи с матричными переменными и матричными неравенствами. Это определило их огромную роль в задачах оптимизации, возникающих в теории управления. С другой стороны, еще более важные события происходили в самой идейной основе оптимизации. Если раньше для сравнения методов использовалась в основном асимптотическая скорость сходимости, то после выхода пионерской монографии А. С. Неми¬ровского и Д. Б. Юдина стало возможным говорить о трудоемкости методов, то есть оценивать объем вычислений необходимых для получения приближения с заданной точностью. Более того, было введено понятие сложности класса задач оптимизации — нижней оценки трудоемкости любого метода, использующего ту или иную информацию о задаче. На этой основе удалось выделить эффективные алгоритмы, для которых трудоемкость совпадает по порядку со сложностью. С тех пор в оптимизации произошло еще многое — была создана теория робастной оптимизации, предложены алгоритмы для решения сверхбольших задач и т. д. Были изданы прекрасные книги по выпуклой оптимизации. На этом фоне естественно возникает вопрос о целесообразности переиздания данной монографии. Мне кажется, что это имеет смысл. Во-первых, те успехи, которые были достигнуты за последние годы, относятся в основном к выпуклой оптимизации. Невыпуклым задачам уделялось гораздо меньше внимания, а их роль на практике не менее важна. Во-вторых, читателю будет интересен генезис основных идей и методов оптимизации, обсуждение не только формальных, но и содержательных постановок задач. Книга переиздается без каких-либо изменений, внесены лишь небольшие исправления. Б. Т. Поляк, август 2013 г. ![]() Главный научный сотрудник Института проблем управления РАН, доктор технических наук. Заместитель главного редактора журнала «Автоматика и телемеханика», член редколлегий 5 международных журналов. Лауреат премий имени А. А. Андронова и Б. Н. Петрова РАН, почетный член ИФАК (IFAC Fellow), награжден золотой медалью EURO-2012. Работал в университетах США, Франции, Италии, Израиля, Тайваня и других стран. Свыше 20 его учеников — кандидаты и доктора наук. Организатор ежегодных молодежных школ «Управление, информация и оптимизация». Автор 4 монографий, 220 статей в журналах и свыше 200 докладов на российских и международных конференциях. Основные работы — по теории управления и оптимизации.
|