год издания — 1975, кол-во страниц — 320, тираж — 18000, язык — русский, тип обложки — твёрд. 7Б тканев. суперобл., масса книги — 370 гр., издательство — Физматлит

серия — Оптимизация и исследование операций

цена: 299.00 руб

Сохранность книги — хорошая

Формат 84x108 1/32. Бумага типографская №1

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

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

Библ. 144 назв.

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

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

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

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

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

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

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

ПРЕДИСЛОВИЕ

Предисловие	8

Г л а в а I. Введение в теорию математического программирования	13

§ 1. Выпуклые множества	13
1. Определение. Теорема отделимости (13). 2. Выпуклые конусы (15). 3. Строго и сильно выпуклые множества (19).
§ 2. Выпуклые функции	19
1. Определение. Основные свойства (20). 2. Дифференциальные свойства (21). 3. Строго и сильно выпуклые функции (24). 4. Вогнутые функции (27).
§ 3. Выпуклое программирование	27
1. Постановка задачи. Основные свойства (27). 2. Необходимые условия минимума (29). 3. Теорема Куна-Таккера (32). 4. Двойственная задача (32). 5. Задача линейного программирования (34). 6. Задача квадратичного программирования (36).
§ 4. Необходимые условия минимума	38
1. Основные определения (38). 2. Необходимые условия минимума (38). 3. Минимаксная задача (45). 4. Необходимые условия второго порядка (47).
§ 5. Некоторые дополнительные сведения	49
К р а т к а я б и б л и о г р а ф и я	50

Г л а в а II. Методы минимизации функций без ограничений	51

§ 1. Градиентные методы	52
1. Метод наискорейшего спуска (52 ). 2. Различные варианты метода ( 58 ). 3. Другие градиентные методы (61). 4. Качественный анализ методов (64).
§ 2. Метод Ньютона с регулировкой шага	67
1. Построение метода (67). 2. Теоремы о свойствах метода (69). 3. Модификации обобщённого метода Ньютона (73). 4. Обсуждение свойств метода Ньютона (76).
§ 3. Методы двойственных направлений	78
1. Соображения о выборе схемы методов (78). 2. Обоснование методов (80). 3. Построение различных алгоритмов (86). 4. Определение вектора p_k (89). 5. Организация начала процесса (92). 6. Минимизация квадратичной формы (93). 7. Обсуждение свойств методов (94).
§ 4. Методы сопряжённых направлений. Минимизация квадратичных функций	96
1. Сопряжённые направления и их свойства (96). 2. Построение методов (100). 3. Общие свойства методов (105). 4. Конкретные алгоритмы (110). 5. Минимизация выпуклой квадратичной функции (116). 6. Обсуждение результатов (120).
§ 5. Методы сопряжённых направлений. Минимизация произвольных функций	122
1. Соображения о применимости методов (122). 2. Теорема о сходимости методов (123). 3. Изучение свойств различных алгоритмов (131). 4. Сходимость процессов без восстановления (142). 5. Обсуждение результатов (147).
§ 6. Методы, не требующие вычисления производных	152
1. Вводные замечания (152). 2. Построение методов двойственных направлений (153). 3. Замечания по реализации методов двойственных направлений (161). 4. Методы сопряжённых направлений (163). 5. Обсуждение результатов (170).
К р а т к а я б и б л и о г р а ф и я	171

Г л а в а III. Методы решения задач с ограничениями	173

§ 1. Задача квадратичного программирования	173
1. Операторы проектирования (174). 2. Минимизация квадратичной функции на подпространстве (175). 3. Алгоритм для общей задачи квадратичного программирования (178). 4. Вычислительные аспекты (187). 5. Задача квадратичного программирования с простыми ограничениями (189).
§ 2. Метод возможных направлений	191
1. Метод выбора возможного направления (192). 2. Алгоритм метода возможных направлений (196). 3. Обоснование сходимости алгоритма (197). 4. Построение начального приближения (200).
§ 3. Метод условного градиента и метод Ньютона	201
1. Правило выбора длины шага (202). 2. Описание алгоритма (203). 3. Обоснование и оценка скорости сходимости алгоритма (203). 4. Оценка сходимости для сильно выпуклой области (207). 5. Метод Ньютона с регулировкой шага (209). 6. Свойства метода Ньютона (209).
§ 4. Метод отсекающей гиперплоскости	217
1. Алгоритм (218). 2. Вычислительные аспекты (220). 3. Заключительные замечания (221).
§ 5. Метод линеаризации	221
1. Основные предположения (222). 2. Формулировка алгоритма (223). 3. Сходимость алгоритма (223). 4. Вычислительные аспекты (229). 5. Некоторые обобщения (232). 6. Задача линейного программирования (236). 7. Локальная оценка скорости сходимости (241).
§ 6. Метод линеаризации: решение систем равенств и неравенств и нахождение минимакса	248
1. Системы равенств и неравенств (249). 2. Сходимость алгоритма (250). 3. Замечания (253). 4. Достаточные условия сходимости (254). 5. Решение задачи о нахождении минимакса (258).
§ 7. Локальное ускорение сходимости	264
1. Постановка задачи. Основные формулы (265). 2. Алгоритм (270). 3. Вычислительные аспекты. Применение к задаче математического программирования (273). 4. Задача минимизации с ограничениями типа равенства (274).
§ 8. Метод штрафных функций	276
1. Обоснование метода штрафных функций (278). 2. Выпуклое программирование (282). 3. Вычислительные аспекты (284). 4. Метод Фиакко и Мак-Кормика (285).
§ 9. Методы проектирования с восстановлением связей	287
1. Схема построения методов (287). 2. Методы первого порядка (292). 3. Метод второго порядка (297). 4. Методы минимизации с повышенной эффективностью (299). 5. О решении общей задачи математического программирования (301). 6. Заключительные замечания (302).
К р а т к а я б и б л и о г р а ф и я	302

П р и л о ж е н и е. Вычислительные схемы основных алгоритмов	305

Л и т е р а т у р а	311

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

Математические методы управления несколькими динамическими процессами, Григоренко Н. Л., 1990
Современное состояние теории исследования операций, Моисеев Н. Н., ред., 1979
Введение в минимакс, Демьянов В. Ф., Малозёмов В. Н., 1972
Методы оптимизации, Моисеев Н. Н., Иванилов Ю. П., Столярова Е. М., 1978
Теория игр, Оуэн Г., 1971
Прикладной функциональный анализ, Балакришнан А. В., 1980
Геометрическое программирование, Даффин Р., Питерсон Э., Зенер К., 1972
Теория максимина и её приложение к задачам распределения вооружения, Данскин Д. М., 1970
Введение в теорию линейного и выпуклого программирования, Еремин И. И., Астафьев Н. Н., 1976
Практические занятия по курсу математического программирования, Капустин В. Ф., 1976
Равновесная термодинамика и математическое программирование, Каганович Б. М., Филиппов С. П., 1995
Параллельные алгоритмы целочисленной оптимизации, Хохлюк В. И., 1987
Разрешимость и устойчивость задач полиномиального программирования, Белоусов Е. Г., Андронов В. Г., 1993
Итеративные методы в теории игр и программировании, Беленький В. З., Волконский В. А., Иванков С. А., Поманский А. Б., Шапиро А. Д., 1974
Прикладное оптимальное проектирование: Механические системы и конструкции, Хог Э. Д., Арора Я. С., 1983
Численные методы оптимизации: Единый подход, Полак Э., 1974
Оптимальное управление дифференциальными и функциональными уравнениями, Варга Д., 1977
Анализ сложных систем и элементы теории оптимального управления, Раскин Л. Г., 1976
Элементы динамического программирования, Вентцель Е. С., 1964
Динамические задачи дискретной оптимизации, Рихтер К., 1985

elapsed time 0.021 sec

/Наука и Техника/Математика

ОГЛАВЛЕНИЕ

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