В книге излагаются методы и алгоритмы численного решения задач, возникающих в математическом программировании, экономике, теории оптимального управления и других областях науки и практики, в которых возникают задачи численного нахождения экстремума функций и функционалов. Основное внимание уделено изложению алгоритмов с высокой скоростью сходимости и практически удобных для реализации на ЭВМ. Рассматриваются методы минимизации функций как без ограничений на независимые переменные, так и учитывающие такие ограничения.

Книга будет полезной как специалистам в области математического программирования, вычислительной математики и теории оптимального управления, так и широкому кругу студентов и инженеров, встречающихся в практике с решением задач минимизации функций.

Библ. 144 назв.

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

Сразу же следует подчеркнуть, что в последние годы произошло изменение тех требований, которые предъявляются к новым вычислительным алгоритмам. Если ещё лет десять — пятнадцать назад с интересом воспринимался любой новый алгоритм для той или иной задачи минимизации, то теперь просто построение нового алгоритма недостаточно. Необходимо показать, чем он лучше уже известных. Таким образом возникает проблема сравнения эффективности различных алгоритмов. К сожалению, эта проблема не допускает простого решения. Дело в том, что для сравнения эффективности необходимо задаться критерием эффективности, а эти критерии могут быть разные. Например, критерием эффективности может быть точность получаемого результата, время счёта, объём необходимой памяти вычислительной машины и т. п. Причём зачастую требуется оценивать алгоритм по довольно противоречивым критериям.

При отборе алгоритмов, включённых в данную книгу, авторы в основном исходили из критерия точности результата и быстроты сходимости итерационного процесса. Однако даже такое ограничение не позволяет однозначно упорядочить все алгоритмы и сказать, какой из них лучше, а какой хуже. Дело в том, что получаемые оценки скорости сходимости являются оценками не для конкретных задач, а для классов задач. Поэтому алгоритм плохой для широкого класса задач может оказаться эффективным на более узком классе. Это делает необходимым для вычислителя иметь в запасе большой набор алгоритмов и в зависимости от конкретной задачи применять тот или иной из них.

Совершенно не безразлично также, за счёт каких средств достигается высокая скорость сходимости алгоритма. В практических задачах часто вычисление даже первых производных от функции вызывает трудности, которые при попытке вычислять вторые производные становятся непреодолимыми. Поэтому основной упор в книге делается на описание таких алгоритмов, которые требуют лишь вычисления первых производных либо только вычисления значения функции.

При изложении вычислительных методов мы рассматриваем конечномерный случай. Это обусловлено двумя причинами. Во-первых, при расчётах на вычислительной машине задачу так или иначе надо аппроксимировать конечномерной. Во-вторых, большинство известных алгоритмов сравнительно просто обобщаются на случай минимизации функционалов без каких-либо существенных изменений. Поэтому нам казалось целесообразным вести всё изложение для конечномерного случая. Это также позволило сделать книгу доступной широкому кругу читателей, поскольку для понимания большинства излагаемых результатов требуется лишь знание основ математического анализа и линейной алгебры.

Чтобы не загромождать изложение, ссылки на литературу в основном тексте почти не приводятся, а вынесены в краткую библиографию, которой сопровождается каждая глава. Мы не пытались охватить всю литературу по рассматриваемым вопросам, так как это невозможно ввиду её обширности. Поэтому список литературы включает в основном лишь те статьи и монографии, которые непосредственно использовались при паписании этой книги.

Заметим, что в данной книге мы совершенно не рассматриваем методы решения обширного и важного класса некорректных экстремальных задач, которые разрабатываются в работах А. Н. Тихонова и его учеников и последователей. Мы также почти не касаемся вопроса о решении задач оптимального управления. Изучение таких задач с различных точек зрения и методов их решения проводится в монографии Н. Н. Моисеева «Численные методы в теории оптимальных систем»…

ПРЕДИСЛОВИЕ

Книги на ту же тему

1. Математические методы управления несколькими динамическими процессами, Григоренко Н. Л., 1990
2. Современное состояние теории исследования операций, Моисеев Н. Н., ред., 1979
3. Введение в минимакс, Демьянов В. Ф., Малозёмов В. Н., 1972
4. Методы оптимизации, Моисеев Н. Н., Иванилов Ю. П., Столярова Е. М., 1978
5. Теория игр, Оуэн Г., 1971
6. Прикладной функциональный анализ, Балакришнан А. В., 1980
7. Геометрическое программирование, Даффин Р., Питерсон Э., Зенер К., 1972
8. Теория максимина и её приложение к задачам распределения вооружения, Данскин Д. М., 1970
9. Введение в теорию линейного и выпуклого программирования, Еремин И. И., Астафьев Н. Н., 1976
10. Практические занятия по курсу математического программирования, Капустин В. Ф., 1976
11. Равновесная термодинамика и математическое программирование, Каганович Б. М., Филиппов С. П., 1995
12. Параллельные алгоритмы целочисленной оптимизации, Хохлюк В. И., 1987
13. Разрешимость и устойчивость задач полиномиального программирования, Белоусов Е. Г., Андронов В. Г., 1993
14. Итеративные методы в теории игр и программировании, Беленький В. З., Волконский В. А., Иванков С. А., Поманский А. Б., Шапиро А. Д., 1974
15. Прикладное оптимальное проектирование: Механические системы и конструкции, Хог Э. Д., Арора Я. С., 1983
16. Численные методы оптимизации: Единый подход, Полак Э., 1974
17. Оптимальное управление дифференциальными и функциональными уравнениями, Варга Д., 1977
18. Анализ сложных систем и элементы теории оптимального управления, Раскин Л. Г., 1976
19. Элементы динамического программирования, Вентцель Е. С., 1964
20. Динамические задачи дискретной оптимизации, Рихтер К., 1985