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