Ф. ГИЛЛ, У. МЮРРЕЙ, М. РАЙТ
ПРАКТИЧЕСКАЯ ОПТИМИЗАЦИЯ
PRACTICAL OPTIMIZATION
Philip E. Gill
Walter Murray
Margaret H. Wright
Systems Optimization Laboratory
Department of Operations Research
Stanford University
California, USA
ПЕРЕВОД С АНГЛИЙСКОГО
В. Ю. Лебедева
ПОД РЕДАКЦИЕЙ
А. А. Петрова
Academic Press
A Subsidiary of Harcourt Brace Jovanovich, Publishers
London New York Toronto Sydney San Francisco
1981
МОСКВА «МИР» 1985
ББК 22.143
Г 47
УДК 681.3
Гилл Ф., Мюррей У., Райт М.
Г 47 Практическая оптимизация:
1985.—509 с., ил.
Пер. с англ.—М.: Мир,
Книга американских специалистов, знакомых советским читателям по переводу «Численных методов условной оптимизации» (М.! Мир, 1977), представляет собой пособие по математическому программированию. Авторы тщательно отобрали и из- ложили только те алгоритмы, которые эффективны при решении практических задач.
Для математиков-прикладникоп, научных работников, специалистов, студентов, изучающих или применяющих в своей работе оптимизационные методы.
2405000000-086
6-85, ч. 1
ББК 22.143
517.1
041 (01)-85
Редакция литературы по математическим наукам
1981 by Academic Press Inc. (London) Ltd.
Перевод на русский язык, «Мир», 1985
ОГЛАВЛЕНИЕ
Предисловие редактора перевода . . ................. Б
Предисловие .... .......................... 7
Глава 1. Введение . . ........................ 9
1.1. Постановка задачи оптимизации . .............. 9
1.2. Классификация оптимизационных задач . .......... 12
1.3. Краткий обзор содержания . .....'........... 14
Глава 2. Основы ........................... 16
2.1. Введение в теорию ошибок вычислений ............ 16
2.1.1. Измерение ошибки . . .................. 16
2.1.2. Представление числа в машине . ............. 17
2.1.3. Ошибки округления . . ................. 19
2.1.4. Ошибки при выполнении арифметических операций .... 21
2.1.5. Ошибки компенсации ................... 23
2.1.6. Точность при последовательных вычислениях ....... 24
2.1.7. Анализ ошибок для алгоритмов . ............ 25
2.2. Введение в вычислительную линейную алгебру ........ 26
2.2.1. Предварительные сведения ................ 26
2.2.2. Векторные пространства ... .............. 33
2.2.3. Линейные преобразования ... ............. 38
2.2.4. Линейные уравнения ... ................ 41
2.2.5. Разложения матриц ... ................ 50
2.2.6. Многомерная геометрия ... .............. 64
2.3. Элементы многомерного анализа . . ............. 66
2.3.1. Функции многих переменных; линии уровня ....... 66
2.3.2. Непрерывные функции и их производные ......... 66
2.3.3. Порядок функции ... ................. 72
2.3.4. Теорема Тейлора ... ................. 73
2.3.6. Конечно-разностная аппроксимация производных ..... 74
2.3.6. Скорости сходимости последовательностей . ....... 78
Глава 3. Условия оптимальности ................... 81
3.1. Определение минимума ...... ~7 ............. 81
3.2. Безусловная оптимизация . . ................ 84
3.2.1. Одномерный случай . . ................. 84
3.2.2. Многомерный случай . . ................. 86
3.2.3. Свойства квадратичных функций . . ........... 88
506______ ______ _____Оглавление_____________________
3.3. Оптимизация при линейных ограничениях . ......... 90
3.3.1. Задачи с ограничениями типа линейных равенств ..... 91
3.3.2. Задачи с ограничениями типа линейных неравенств .... 95
3.4. Оптимизация при нелинейных ограничениях . ........ 104
3.4.1. Задачи с ограничениями типа нелинейных ........ 104
3.4.2. Задачи с ограничениями типа нелинейных неравенств . . . 109
Глава 4. Методы безусловной минимизации .............. 111
4.1. Методы для функции одной переменной ............ 111
4.1.1. Поиск нуля функции одной переменной .......... 111
4.1.2. Методы одномерной минимизации . . ........... 118
4.2. Методы для негладких функций многих переменных ..... 124
4.2.1. Применение методов с сопоставлением значений функции . . 124
4.2.2. Метод многогранника .................. 125
4.2.3. Составные недифференцируемые функции . . ....... 128
4.3. Методы для гладких функций многих переменных ...... 132
4.3.1. Модельная схема минимизации гладких функций ..... 132
4.3.2. Сходимость модельной схемы ............... 133
4.4. Методы второго порядка . . ................. 141
4.4.1. Метод Ньютона . . ................... 141
4.4.2. Стратегии для знаконеопределенной матрицы Гессе .... 144
4.5. Методы первого порядка . . ................. 158
4.5.1. Ньютоновские методы с конечно-разностной аппроксимацией 158
4.5.2. Квазиньютоновские методы ... ............ 160
4.6. Методы минимизации гладких функций без вычислений производных . 174
4.6.1. Конечно-разностная аппроксимация первых производных . 175
4.6.2. Квазиньютоновские методы без вычисления производных . 180
4.7. Методы решения задач о наименьших квадратах ....... 183
4.7.1. Происхождение задач о наименьших квадратах; основания для использования специальных методов . ........... 183
4.7.2. Метод Гаусса - Ньютона ... ............. 184
4.7.3. Метод Левенберга-Маркардта ... .......... 188
4.7.4. Квазиньютоновские методы ... ............. 189
4.7.5. Скорректированный метод Гаусса - Ньютона . . ..... 190
4.7.6. Нелинейные уравнения ... ............... 193
4.8. Методы решения задач большой размерности ......... 195
4.8.1. Дискретные методы Ньютона для функций с разреженными матрицами Гессе . 196
4.8.2. Квазиньютоновские методы для функций с разреженными матрицами Гессе . 198
4.8.3. Методы сопряженных градиентов . ........... 200
4.8.4. Квазиньютоновские методы с ограниченной памятью .... 208
4.8.5. Методы сопряженных градиентов с улучшением обусловленности . 209
4.8.6. Решение ньютоновских уравнений линейным методом сопряженных градиентов . 212
Глава 5. Задачи с линейными ограничениями ............. 216
5.1. Методы поиска минимума при ограничениях-равенствах . . . 216
5.1.1. Принцип организации алгоритмов . . .......... 217
5.1.2. Расчет направления поиска . . ............. 220
5.1.3. Представление нуль-пространства ограничений . . .... 225
5.1.4. Специальные формы целевой функции . .......... 228
_______ ___ Оглавление__________ _______507
5.1.5. Оценки множителей Лагранжа . . ............ 229
5.2. Методы активного набора для задач с ограничениями типа линейных неравенств . 233
5.2.1. Модельная схема . . .................. 235
5.2.2. Расчет направления поиска и длины шага ........ 236
5.2.3. Интерпретация оценок множителей Лагранжа ....... 238
5.2.4. Вычисления при изменении рабочего списка ....... 240
5.3. Задачи специальных типов . . ............... 246
5.3.1. Линейное программирование ... ............ 246
5.3.2. Квадратичное программирование ... .......... 248
5.3.3. Линейная задача о наименьших квадратах с ограничениями 252
5.4. Задачи с малым числом ограничений общего вида ....... 256
5.4.1. Квадратичные задачи с положительно определенными матрицами Гессе . 256
5.4.2. Методы вторых производных для решения задач общего вида 258
5.5. Задачи с ограничениями специального вида ......... 261
5.5.1. Минимизация при простых ограничениях на переменные . 261
5.5.2. Задача со смесью простых ограничений и ограничений общего вида . 264
5.6. Большие задачи с линейными ограничениями ........ 266
5.6.1. Методы решения больших задач линейного программирования ... 266
5.6.2. Большие задачи с линейными ограничениями и нелинейными критериями .. 270
5.7. Поиск начальной допустимой точки . ............ 278
5.8. Реализация методов активного набора . ........... 280
5.8.1. Определение начального рабочего списка . ........ 280
5.8.2. Линейно зависимые ограничения . . ........... 282
5.8.3. Нулевые множители Лагранжа . . ........... 283
Глава 6. Задачи с нелинейными ограничениями ............ 286
6.1. Общие определения ... .................. 287
6.1.1. Функция выигрыша . . ................. 287
6.1.2. Классификация подзадач ... .............. 288
6.2. Методы штрафных и барьерных функций .......... 289
6.2.1. Методы гладких штрафных и барьерных функций ..... 289
6.2.2. Методы негладких штрафных функций . ......... 298
6.3. Методы приведенных градиентов и проекций градиентов . . . 304
6.3.1. Общие соображения ... ................ 304
6.3.2. Поиск при ограничениях-равенствах . . ......... 305
6.3.3. Определение рабочего списка ............... 309
6.4. Методы модифицированных функций Лагранжа . ....... 310
6.4.1. Определение модифицированной функции Лагранжа . ... 311
6.4.2. Схема алгоритмов с модифицированными функциями Лагранжа . 314
6.4.3. Вариации стратегии поиска . . ............. 317
6.5. Методы спроектированного лагранжиана . . ......... 320
6.5.1. Предварительные соображения ... ........... 320
6.5.2. Подзадача с целевой функцией общего вида ....... 322
6.5.3. Квадратичная подзадача ... .............. 325
6.5.4. Стратегии для дефектных подзадач ............ 332
6.5.5. Построение активного набора . . ............ 333
6.6. Оценки множителей Лагранжа . . ............. 338
6.6.1. Оценки первого порядка . . ............... 339
6.6.2. Оценки второго порядка . . .............. 340
508 Оглавление__
6.6.3. Оценки множителей для ограничений-неравенств . .... 342
6.6.4. Проверки состоятельности ... ............. 343
6.7. Задачи большой размерности . ............... 344
6.7.1. Использование подзадачи с линейными ограничениями . . 344
6.7.2. Использование квадратичной подзадачи . . ........ 346
6.8. Задачи специальных типов . . ................ 351
6.8.1. Специальные задачи минимизации негладких функций . . 351
6.8.2. Специальные задачи с ограничениями . .......... 352
Глава 7. Моделирование . . ..................... 356
7.1. Введение .... ...................... 356
7.2. Классификация оптимизационных задач . . ......... 357
7.3. Исключение необязательных разрывностей . . ........ 359
7.3.1. Роль точности вычисления функций модели ...... 359
7.3.2. Аппроксимация по рядам и таблицам .......... 361
7.3.3. Определение функций подзадачей . . .......... 362
7.4. Преобразования задач ... ................. 364
7.4.1. Упрощение или исключение ограничений . ........ 364
7.4.2. Задачи с функциональными переменными . ....... 370
7.5. Масштабирование .... .................. 371
7.5.1. Масштабирование заменой переменных . . ........ 371
7.5.2. Масштабирование в нелинейных задачах о наименьших квадратах . 373
7.6. Постановка ограничений .................. 375
7.6.1. Вырождение ...................... 375
7.6.2. Использование ограничений с допусками ........ 376
7.7. Задачи с дискретными и целочисленными переменными . . . 380
7.7.1. Псевдодискретные переменные ............. 380
7.7.2. Целочисленные переменные ............... 382
Глава 8. Практические вопросы .................... 385
8.1. Применение библиотечных программ . . ........... 385
8.1.1. Выбор метода ... ................... 385
8.1.2. Роль пользователя ... ................ 392
8.1.3. Выбор параметров пользователем . . .......... 394
8.1.4. Ошибки в программах пользователя ............ 400
8.1.5. Работа с ограниченным математическим обеспечением . . . 403
8.2. Свойства численного решения . . .............. 406
8.2.1. Что такое правильный ответ? . ............. 406
8.2.2. Предельная точность решения . . ............ 407
8.2.3. Критерии останова ... ................. 412
8.3. Анализ результатов счета . . ................ 421
8.3.1. Оценка пригодности численного решения . ........ 421
8.3.2. Другие способы подтверждения оптимальности . ..... 427
8.3.3. Анализ чувствительности ... ............. 429
8.4. Что может не получаться (и как тогда поступать) ....... 433
8.4.1. Переполнение при подсчете функций задачи ....... 433
8.4.2. Недостаточное уменьшение функции выигрыша ...... 434
8.4.3. Устойчиво медленный прогресс .............. 438
8.4.4. Выполнение максимального числа итераций или обращений к процедуре вычисления целевой функции ........... 440
8.4.5. Отсутствие ожидаемой скорости сходимости. . ...... 440
8.4.6. Неудачное направление поиска . . ........... 441
_______509
8.5. Оценка точности вычисления функций задачи ........ 442
8.5.1. Роль точности ...
8.5.2. Оценивание точности ... ...........
8.5.3. Переоценивание точности ... .............
8.6. Выбор конечных разностей . . ..........
8.6.1. Ошибки конечно-разностных приближений; хорошо отмасштабированные функции
8.6.2. Процедура автоматического оценивания конечно-разностных интервалов
8.7. Подробнее о масштабировании ...............
8.7.1. Масштабирование заменой переменных . . .......
8.7.2. Масштабирование значений целевой функции .......
8.7.3. Масштабирование ограничений ... .......
Вопросы и ответы
Библиография .
ПРЕДИСЛОВИЕ РЕДАКТОРА ПЕРЕВОДА
Читатель знаком с Ф. Гиллом и У. Мюрреем не только по их многочисленным статьям в научных журналах. Они редактировали сборник трудов конференции по методам условной оптимизации, проведенной Национальной физической лабораторией (Великобри- тания, Тэддингтон) в январе 1974 года. Сборник был переведен на русский язык ". Это был обзор тогдашнего состояния численных ме- тодов отыскания экстремума функции при ограничениях. Он имел четкую прикладную направленность: концентрировал внимание читателя на трудностях, возникающих при практическом решении задач, и способах преодоления этих трудностей.
Предлагаемая монография Ф. Гилла, У. Мюррея и М. Райт «Практическая оптимизация» имеет столь же острую практическую направленность. Как и упомянутый сборник статей, она отражает современное — теперь уже спустя десятилетие — состояние мето- дов и техники решения задач оптимизации. Общая картина пред- стает перед читателем преломленной через призму опыта и, если угодно, научных вкусов авторов — больших знатоков своего дела. Это придает изложению и ясность, и логическую стройность, и ори- гинальность. Правда, отдельные детали получились не совсем удач- ными и потребовали от переводчика дополнительных усилий, чтобы точно передать существо дела.
Авторы старались написать книгу так, чтобы даже не слишком подготовленный читатель мог понять ее, не обращаясь к учебникам. Для ее чтения достаточно знать только основы математического анализа и линейной алгебры. Изложение начинается со сведений о способах представления чисел в ЭВМ, о возникающих при этом погрешностях и о погрешностях, сопутствующих вычислениям. Показано, как ошибки могут влиять на результаты работы алго- ритмов. Так, с самого начала внимание читателя привлекается к практическим вычислениям. Затем сообщаются нужные сведения из линейной алгебры и выводятся необходимые и достаточные усло- вия минимума функции как для случая, когда на независимые пере- менные не наложено никаких условий, так и для случая, когда ус- ловия наложены.
1) См. «Численные методы условной оптимизации». Ред. Ф. Гилл и У, Мюррей. —М.: Мир, 1977.
Предисловие редактора перевода
Теперь читатель подготовлен к изучению алгоритмов отыскания минимумов. Сначала он знакомится с алгоритмами безусловной оп- тимизации и уясняет, как сильно свойства гладкости функции и ин- формация об этих свойствах влияют на структуру алгоритмов и их эффективность. Затем наступает очередь алгоритмов вычисления минимума функции при линейных ограничениях. Алгоритмы реше- ния задач с ограничениями-равенствами конструируются на базе алгоритмов безусловной оптимизации, задачи с ограничениями-не- равенствами сводятся к последовательностям задач с равенствами при помощи правил построения наборов активных ограничений, т. е. ограничений, которые на текущем этапе вычислений считают равен- ствами. Последними предстают алгоритмы вычисления минимума функции при нелинейных ограничениях: методы штрафов, методы проектирования и методы модифицированных функций Лагранжа. Они включают в себя предыдущие алгоритмы.
Последние главы книги вновь обращают читателя к сугубо практическим вопросам: как реализовать изложенные методы, где и как их лучше использовать? Авторы не убоялись обсуждать плохо формализуемые (и поэтому обычно не обсуждаемые) вопросы, от ре- шения которых во многом зависит успех применения того или дру- гого алгоритма, например масштабирование задачи или критерии остановки вычислений. Многочисленные примеры и иллюстрации, систематически сопровождающие изложение материала, помогают читателю понять суть дела.
Книга «Практическая оптимизация» может служить и учебным пособием по математическому программированию и численным ме- тодам, и руководством к применению наиболее надежных из имею- щихся сейчас универсальных алгоритмов оптимизации. Ясность из- ложения основных принципов и практические советы, основанные на богатом опыте авторов, привлекут к книге всех, кто начинает изучать численные методы оптимизации. Общий взгляд авторов на алгоритмы, высказываемые ими суждения не оставят равнодушными и специалистов в этой области.
А. А. Петров
ПРЕДИСЛОВИЕ
Будучи сотрудниками Национальной физической лаборатории и Стэнфордского университета и участвуя в создании фонда про- грамм Группы численных алгоритмов (NAG), мы уже многие годы занимаемся разработкой и программным воплощением методов оп- тимизации. За последние двадцать лет в этой области были достиг- нуты большие успехи. Значительно улучшены показатели эффектив- ности и надежности математического обеспечения почти всех кате- горий оптимизационных задач. Однако возросла и сложность алго- ритмов: качество повышалось за счет привлечения более тонких идей численной линейной алгебры и теории вычислений с ограни- ченной точностью. Лучшие из современных программ поиска экстре- мума весьма сложны и действуют далеко не очевидным образом.
В этой книге мы рассматриваем — по необходимости в общих чертах — предмет практической оптимизации. Эпитет «практиче- ская» здесь и в названии книги употреблен, чтобы подчеркнуть, что внимание будет уделено не только формальным схемам, но также содержанию и особенностям их машинных реализации. В частности, исследована чувствительность алгоритмов к ошибкам вычислений с ограниченной точностью и обсуждены их алгебраические блоки.
Ради замкнутости изложения мы включили в книгу две предва- рительные главы: в одной представлены используемые в дальнейшем результаты вычислительной линейной алгебры и элементарные све- дения относительно последствий ошибок округления при расчетах на ЭВМ, а другая посвящена условиям оптимальности.
Избранные алгоритмы безусловной оптимизации и оптимизации при линейных и нелинейных ограничениях описаны в трех главах. Приводятся соображения, лежащие в основах алгоритмов, рассмат- риваются их теоретические и численные свойства. Для пояснения везде, где это уместно, даются примеры и иллюстрации. В основном мы представили алгоритмы, которые не раз успешно применяли на практике; иные обсуждаются лишь постольку, поскольку это спо- собствует пониманию некоторых важных моментов или служит ос- новой для последующих построений. Более подробные сведения, а также не попавшие в наш обзор алгоритмы можно найти по ссылкам, вынесенным в замечания, завершающие каждый большой раздел. Материал книги излагается достаточно подробно, и это позволяет рекомендовать ее в качестве учебника по курсу математического программирования.
Предисловие
Две последние главы посвящены менее формализованной, но от- нюдь не второстепенной тематике; их можно расценивать как «нази- дания пользователям». Например, здесь даны некоторые рекоменда- ции в отношении оптимизационного моделирования: по нашим наблюдениям, учет алгоритмических возможностей при разработке моделей часто оказывается весьма полезным. Кроме того, мы подроб- но обсуждаем вопросы выбора программы для конкретной задачи, интерпретации численного решения, диагностики (а иногда и устра- нения) причин плохой работы или отказа алгоритма.
При написании этой книги мы получали советы и помощь от многих людей. Прежде всего, хотим поблагодарить нашего друга и коллегу Майкла Сондерса не только за множество ценных коммен- тариев, но и за его добрый юмор и терпение, которые так помогли нам в минуты, когда казалось, что работа над книгой продлится вечность. Он играл ведущую роль в разработке представленных в главах 5 и 6 алгоритмов решения задач большой размерности.
Мы очень признательны Дэвиду Мартину за его постоянную под- держку группы оптимизации в Национальной физической лабора- тории и Джорджу Данцигу за его усилия по созданию алгоритми- ческой группы в Лаборатории оптимизации систем Стэнфордского университета.
Мы благодарим Брайена Хинде, Сузан Ходсон, Инид Лонг и Дэ- вида Рида за их участие в создании и испытаниях многих представ- ленных в этой книге алгоритмов. Разнообразную помощь при подготовке книги оказывали Грег Добсон, Дэвид Фукс, Стефания Гэй, Ричард Стоун и Уэс Винклер. Отдельные места удалось изложить яснее благодаря замечаниям Па- уло Беневидес-Соареса, Энди Конна, Лауреано Эскудеро, Дона Игл- харта, Джеймса Лайнесса, Хорхе Море, Майкла Овертона и Дэнни Соренсена. Мы благодарим Клива Холла ^воспдоизведение.сгенерирован- ных машиной рисунков на лазерном графопостроителе в Нацио- Т[а^1ьной~фйзйческой лаборатории. Прочие рисунки были мастерски исполнены Ненси Симина. Эта книга была набрана с помощью программной системы ТЕХ, созданнси^Донбм^Кнутом"1^ Мы благодарим его за то, что он предо- ставил нам различные макросы этой системы, позволившие улуч- шить качество окончательного текста.- Крис Туччи очень помог в подготовке последнего варианта. Наконец, мы хотим принести глубочайшую благодарность нашим близким, ободрявшим и поддерживающим нас в течение долгой ра- боты над книгой.
Стэнфордскнй университет Май 1981 г.
Ф. Э. Г.
У. М.
М. Г. Р.
1> D. Е. Knuth, ТЕХ and METAFONT, New Directions in Typesetting, Ame- rican Mathematical Society and Digital Press, Bedford, Massachusetts (1979).
ГЛАВА 1
ВВЕДЕНИЕ
Человечество ставит перед собой только те вадаш, которые оно может разрешить.
К. Маркс. Из предисловия к «Критике политической экономии» (1859)
1.1. ПОСТАНОВКА ЗАДАЧИ ОПТИМИЗАЦИИ
Постановка любой задачи оптимизации начинается с определе- ния набора независимых переменных и обычно включает условия, которые характеризуют их приемлемые значения. Эти условия на- зывают ограничениями задачи. Еще одной обязательной компонен- той описания является скалярная мера «качества», именуемая целевой функцией и зависящая каким-то образом от переменных. Решение оптимизационной задачи — это приемлемый набор значе- ний переменных, которому отвечает оптимальное значение целевой функции. Под оптимальностью обычно понимают максимальность или минимальность; например, речь может идти о максимизации прибыли или минимизации массы.
К задачам на поиск оптимума сводятся многие из проблем мате- матики, системного"анализа,.техники, экономики, медицины и ста- тистики. В частности, они возникают при построении математиче- ских моделей. Когда для изучения какого-нибудь сложного явления конструируется математическая модель, к оптимизации прибегают для того, чтобы определить такую структуру и такие параметры последней, которые обеспечивали бы наилучшее согласование с ре- альностью. Другой традиционной обласхью применения оптимиза- ции являются процедуры принятия^ решении, так как большинство из них нацелено именно на то, чтобы сделать «оптимальный» выбор. Помимо оптимизационных задач, представляющих самостоятельный интерес, на практике часто возникают задачи, которые «встроены» в некоторые вычислительные процессы, где они играют хотя и су- щественную, но все же вспомогательную роль. Это настолько ти- пичная ситуация, что при описании процесса в целом далеко не всегда указывают на наличие подобных задач; к примеру, сказав, что процесс предполагает определение точки, в которой какая-то функция достигает своего критического значения, могут и не доба- вить, что эта точка будет найдена решением оптимизационной задачи.
Данная книга посвящена вопросам численного поиска оптимума и в том числе оптимизационным алгоритмам. При описании таких алгоритмов всегда используют стандартные формы представления задач. В частности, полезно ввести некую универсальную форму,
10 Гл. 1. Введение
подходящую для большинства задач, встречающихся на практике. В качестве такой, формы мы будем использовать следующую:
NCP найти min F (х)
при ограничениях с, (х) = 0, 1=1, 2, ..., т';
с/(л:)^0, i=m'-\-\, ..., т.
Здесь целевая функция F и функция ограничений {с,} суть вещест- веннозначные скалярные функции. Говоря в дальнейшем о функ- циях задачи, мы будем иметь в виду F и {с,} одновременно.
В подтверждение тезиса о многообразии прикладных оптимиза- ционных задач мы рассмотрим две из них. Решение первой опреде- лило расположение материала на страницах данной книги. Эту ра- боту выполнила программная система машинного набора.. ТЕХ. Она предназначена для того, чтобы, соблюдая заданные размеры полей страниц, размещать на них вводимый текст в форме, удобной для чтения. Достигается это с помощью двух средств: система под- бирает расстояние между буквами, словами, строками и параграфа- ми и может разбивать последние слова строк в соответствии с пра- вилами переноса. Каждое из упомянутых расстояний имеет «идеаль- ное значение» и определенные границы варьирования. При этом за уклонение от идеала начисляется «штраф». Различные штрафы вво- дятся также, чтобы избежать нежелательных ситуаций типа появ- ления смежных строк, заканчивающихся переносимыми словами, или размещения в начале страниц формулы, вынесенной в отдель- ную строку. Суммарный штраф минимизируется. Таким образом, в задаче поиска хорошего расположения текста, решаемой системой ТЕХ, есть все элементы общей оптимизационной поставки: скаляр- ная функция измерения качества; переменные, значения которых подбираются из соображений минимизации этой функции; ограниче- ния на характер и величину разрешенных вариаций.
Следующий пример представляет собой упрощенный вариант задачи выбора профиля носовой части летательного аппарата с ми- нимальным сопротивлением в потоке газа. Здесь критерием качества является лобовое сопротивление тела при заданной скорости, а переменные, значения которых надо подобрать,— это конструктив- ные параметры. Чтобы формализовать' задачу, надо прежде всего выделить эти параметры, определив структуру математической мо- дели носовой части. Мы будем считать, что последнюю можно опи- сать как набор нескольких конических секций и одной сфериче- ской, причем радиус основания R полагается заданным. Эта модель изображена на рис. 1а, где перечислены и параметры, значения ко- торых предстоит выбрать. Хотя реальный профиль должен иметь более сложную форму, огрубления, допущенные в модели, будут приемлемыми, если число секций взять достаточно большим.
После того как структура модели носовой части зафиксирована, надо найти зависимость лобового сопротивления от восьми перемен-
1.1. Постановка задачи оптимизации 11
ных: oci, ..., а,. ''!> • • •> Лг Для этого потребуется соответствующая математическая модель обтекания. Мы ее строить не собираемся и отметим только, что, какова бы она ни была, результатом ее применения будет функция D (KI, . . ., «2, /"i, ..., /4), оценивающая лобовое сопротивление по значениям переменных. Она и станет це- левой функцией нашей задачи.
Рис. 1а. Модель профиля носовой части.
Для завершения формализации задачи о наилучшем профиле ос- талось выставить ограничения на величины переменных, вытекаю- щие из физического смысла проблемы и гарантирующие, что полу- ченное решение будет иметь смысл. В частности, первую группу ограничений составят условия неотрицательности радиусов /"i, ... ..., г,:
r;>0, t=l, .... 4.
Происхождение задачи требует также, чтобы значения углов {«,} лежали в диапазоне [0, л/2] и чтобы каждый следующий угол не превосходил предыдущего. Значит, в задачу следует включить ог- раничения вида
В носовой части летательного аппарата обычно устанавливаются всевозможные приборы. Их список может быть определен заранее, и тогда носовая часть должна иметь объем, достаточный для их раз- мещения. Кроме того, разумная конструкция должна иметь длину не больше заданной. Таким образом, в задаче будут присутствовать следующие ограничения:
объем
длина
Наконец, какие-то ограничения могли бы возникнуть из соображе-
ний прочности и на основании иных стандартов.
12 Гл. 1. Введение
Итак, мы свели проблему оптимизации профиля к математиче- ской задаче вида
найти min D (oii, ..., /•„)
при ограничениях
Характер и последовательность использованных при этом рассуж- дении типичны. Выделение представительного набора переменных, определение функции цели, описание требуемых качеств решения в терминах соотношений между переменными — таковы этапы мате- матической формализации любой прикладной оптимизационной проблемы. Теперь остается только выбрать какой-нибудь из алго- ритмов поиска минимума в задачах типа NCP и с его помощью рассчитать наилучший профиль.
1.2. КЛАССИФИКАЦИЯ ОПТИМИЗАЦИОННЫХ ЗАДАЧ
Подавляющее большинство оптимизационных задач, возникаю- щих на практике, приводятся к виду NCP. Даже те задачи, которые сами по себе в эти рамки не укладываются, часто могут быть сведе- ны к последовательности стандартных. Однако существование столь универсальной формы представления вовсе не означает, что разли- чиями между отдельными задачами следует пренебрегать. Наобо- рот, имея дело с конкретной постановкой, всегда надо постараться использовать ее особенности для того, чтобы организовать поиск решения самым эффективным образом. К примеру, усилия можно сэкономить, отказавшись от каких-то проверок, необходимых в об- щем случае, но лишних в конкретном, или избежав повторных вы- числений величин, являющихся константами. Ниже рассматривает- ся классификация разнообразных задач типа NCP по тем их особен- ностям, которые наиболее существенны для выбора алгоритма ре- шения.
Определение признаков, по которым разумно классифицировать оптимизационные задачи,— проблема не простая. ^амымдодЕ-Обиым способом «кл.ассиф.цхадии» было бы считать каждую задачу уникаль- ^ой7 Если бы любое изменение в постановке задачи существенно влияло на форму рациональной организации ее решения, это было бы оправданно и означало бы, например, что введение в задачу одной дополнительной переменной требует пересмотра алгоритма поиска оптимума. Однако, к счастью, подобной чувствительности алгорит- мов к вариациям постановок не наблюдается, что и позволяет гово- рить'о классификации в подлинном смысле этого слова. Хотя набо-
1.2. Классификация оптимизационных задач 13
pa признаков, идеального для всех случаев жизни, не существует, достаточно разумный список составить можно. Поскольку имеется в виду, что разным классам задач будут отвечать разные алгоритмы решения, этот список должен быть_результатом соразмерения выгод_ от эксплуатации выделяемых свойств и затрат да разработку соот- ветствующего математичесКого обеспечения-.
Наиболее очевидные различия между задачами связаны с мате- матическими характеристиками их функций. Например, в одном случае целевая функция будет гладкой, а в другом — разрывной; иногда функции задачи просты и свойства их понятны, а иногда явные выражения для функций отсутствуют и расчет их значений требует решения каких-то достаточно сложных подзадач.
В приведенной ниже таблице дана стандартная схема классифи- кации оптимизационных задач по типам их функций. Каждый из перечисленных признаков существен для выбора алгоритма реше- ния:
Типы F (х) Типы {с, (х)}
Функция одной переменной Линейная функция Сумма квадратов линейных функций Квадратичная форма Сумма квадратов нелинейных функ-ци и Гладкая нелинейная функция Нелинейная функция с разреженнои матрицей Гессе . Негладкая нелинейная функция Ограничения отсутствуютПростые ограничения на переменныеЛинейные функции Линейные функции с разреженной, матрицей коэффициентов ""'"' Гладкие нелинейные функции Гладкие нелинейные функции с разреженной матрицей ЯкобиНегладкие нелинейные функции
В соответствии с данной таблицей выделяется, например, категория задач на поиск минимума гладкой нелинейной функции при простых ограничениях на переменные.
Помимо названных существуют и другие признаки классифика- ции оптимизационных задач. Среди них обязательно следует упо- мянуть размерность. От нее зависит, сколько памяти и вычислений потребуется для поиска решения тем или иным методом. Как пра- вило, методы, эффективные для задач с небольшим числом перемен- ных не пригодны в случаях когда переменные исчисляются сот- нями или тысячами. Классификация по размерности всегда относи- тельна: считать ли задачу большой или маленькой, определяется тем, какие вычислительные средства имеются в распоряжении. Одна
14 Гл. 1. Введение
и та же задача для мини-ЭВМ может оказаться большой, а для обыч- ной машины — маленькой,
Еще один показатель, который может существенно различаться для разных задач и всегда учитывается при выборе алгоритмов,— это доступность прооизводных. В одних задачах аналитические зна- чения первых и вторых производных целевой функции вычисляются легко, а в других вычислению поддаются точные значения лишь самой функции. Когда говорят о доступности производных, то имеют в виду не только возможность построения процедуры расчета их точных значении, но и приемлемую трудоемкость этой процедуры. Последнее означает, что затраты на расчет производных сопостав- ляются с прочими затратами на реализацию поиска решения за- дачи.
Наконец, выбор алгоритма может определяться природой задачи и нуждами исследования, в рамках которого она возникла. Эти «внешние» факторы часто диктуют условия, никоим образом не вы- текающие из математической постановки задачи. Например, по какой-то причине может оказаться необходимым, чтобы некоторые ограничения были соблюдены без невязок яа всех итерациях. Суть задачи помимо прочего~определяет и точность, с которой ее надо решить; если, к примеру, результаты решения используются как второстепенные данные для некой внешней итерации, то тратить усилия на достижение максимальной точности бессмысленно.
Разбор методов оптимизации в последующих главах включает сведения о том, как различные свойства задач влияют на эффектив- ность методов. Будут даны также рекомендации, как выбрать спо- собы решения и анализа результатов в зависимости от категории задачи.
1.3. КРАТКИЙ ОБЗОР СОДЕРЖАНИЯ
Когда-то арсенал методов оптимизации был небогат, эти методы были простыми и казалось естественным положение, когда каждый, кому нужно было решить оптимизационную задачу, шел в библио- теку, подыскивал описание подходящей схемы в каком-нибудь журнале (а то и сочинял свою схему) и самостоятельно программи- ровалал ее. Однако времена меняются, и сегодня подобное положение было бы неприемлемо.
Во-первых, стало намного сложнее разбираться в литературе, сильно разросшейсяза. последние годы. Эти годы были порой бур- ного развития аппарата оптимизации, и нет такой категории задач, для которой не появилось бы новых алгоритмов. Сейчас уже трудно надеяться, что рядовой пользователь, полистав журналы, сможет найти самый подходящий алгоритм.
Во-вторых, современные алгоритмы оптимизации в большинстве своем довольно сложны. Поэтому, даже отыскав тот из них, который следовало бы применить, пользователь скорее всего не станет его
1.3. Краткий обзор содержания 15
программировать. К тому же, как показывают последние резуль- таты численного анализа, кустарная реализация не только слож- ных, но и внешне простых вычислений может приводить к большим ошибкам и численнрй неустойчивости.
Короче говоря, сегодняшний пользователь не хочет (и, с нашей точки зрения, не должен) конструировать свои процедуры поиска экстремума и писать свои программы решения оптимизационных задач, начиная «с нуля». Ему нужны не ссылки на журнальные статьи, а хорошие библиотеки, стандартных программ. Это, однако, не означает, что он может пребывать в полном неведении относи- тельно устройства алгоритмов, с которыми ему предстоит работать, и основных особенностей реализующих их пакетов.
Данная книга предназначена в помощь тому, кто хочет в полной мере использовать возможности доступного программного обеспече- ния оптимизационных задач. Точнее, мы надеемся, что она поможет наиболее эффективно применять имеющиеся методы в случаях, ког- да они пригодны, а также успешно адаптировать и модифицировать их, когда это необходимо. Наряду с обсуждёнием всевозможных процедур оптимизации в книге затрагивается ряд смежных вопро- сов, возникающих при решении большинства прикладных задач. В частности, даются рекомендации по поводу того, как ставить за- дачи, чтобы шансы на успешное решение были максимальны, и как разбираться в причинах отказов алгоритмов.
В гл. 2 приведен обзор избранных результатов численного ана- лиза. Знакомый с этим предметом читатель может ее пропустить. Особое внимание в ней уделено ошибкам машинной арифметики и некоторым из разделов вычислительной линейной алгебры. Этот материал образует основу для понимания дальнейшего изложения.
В остальных главах рассматриваются различные методы оптими- зации, способы постановки задач, вопросы использования стандарт- ных программ и анализа результатов вычислений. Мы хотим под- черкнуть, что изложение весьма сжато и содержит только самые необходимы cвeдeния. Пoэтoмy читатель не должен рассчитывать на то, что одолев книгу, он станет экспертом по затронутым в ней проблемам. Однако для понимания сути дела материала достаточно.
БИБЛИОГРАФИЯ
Абади Abadie J. (1978). «The GRG method for nonlinear programming», in Design and Implementation of Optimization Software (H. J. Greenberg, ed.), pp. 335— 362, Sijthoff and Noordhoff, Netherlands.
Абади и Гигу Abadie J. and Guigou J. (1970). «Numerical experiments with the GRG methods», in Integer and Nonlinear Programming (J. Abadie, ed.), pp, 529—536, North-Holland, Amsterdam.
Абади и Карпентье Abadie J. and Carpentier J. (1965). Generalisation de la methode du gradient reduit -de Wolfe au cas de contraintes non-lineares. Note HR6678, Electricite de France,Paris. — (1969). «Generalization of the Wolfe reduced-gradient method to the case of nonlinear constraints», in Optimization (R. Fletcher, ed.), pp. 37—49, Acade- mic Press, London and New York.
Авила и Конкус Avila J. H. and Concus P. (1979). Update methods for highly structured systems of nonlinear equations, SIAM J. Numer. Anal. 16, pp. 260—269.
Авриель Avriel M. (1976). Nonlinear Programming: Analysis and Methods, Prient ice-Hall, Inc., Englewood Cliffs, New Jersey.
Авриель и Дембо Avriel M. and DemboR.S. (eds.) (1979). Engineering Optimization, Math. Prog. Study 11.
Авриель, Рейкарт и Уайлд Avriel M., Rijckaert M. J. and Wilde D. J. (eds.) (1973). Optimization and Design, Prentice-Hall, Inc., Englewood Cliffs, New Jersey.
Аксельсон Axelsson 0. (1974). On preconditioning and convergence acceleration in sparse mat- rix problems, Report 74-10, CERN European Organization for Nuclear Rese- arch, Geneva.
Андерсен и Блюмфилд Anderssen R. S. and Bloomfield P. (1974). Numerical differentiation procedures for non-exact data, Num. Math. 22, pp. 157—182.
Андерсон и Бьёрк Anderson N. and Bjorck A. (1973). A new high-order method of the regula faisi type for computing a root of an equation, Nordisk Tidskr. Informationsbehandling (BIT) 13, pp. 253—264,
Андерсон и Осборн Anderson D. H. and Osborne M. R. (1977). Discrete, nonlinear approximations in polyhedral norms: a Levenberg-like algorithm, Num. Math. 28, pp. 157—170.
Библиография 479
Апостол Apostol T. M. (1957). Mathematical Analysis, Addison-Wesley, Massachusetts and London.
Армстронг и Годфри Armstrong R. D. and Godfrey J. P. (1979). Two linear programming algorithms for the discrete /i norm problem. Mathematics of Computation 33, pp. 289—300.
Байс Buys J. D. (1972). Dual Algorithms for Constrained Optimization Problems, Ph. D. Thesis, University of Leiden, Netherlands.
Байс и Гонин Buys J. D. and Gonin R. (1977). The use of augmented Lagrangian functions for sensitivity analysis in nonlinear programming. Math. Prog. 12, pp. 281—284.
Бакли Buckley A. G. (1975). An alternative implementation of Goldfarb's minimization algorithm. Math. Prog. 8, pp. 207—231. — (1978). A combined conjugate-gradient quasi-Newton minimization algorithm, Math. Prog. 15, pp. 200—210.
Балинский и Лемарешаль Balinski M. L. and Lemarechal C. (eds.) (1978), Mathematical Programming in Use, Math. Prog. Study, 9.
Банч и Кауфман Bunch J. R. and Kaufman L. C. (1977). Some stable methods for calculating inertia and solving symmetric linear equations, Mathematics of Computation 31, pp. 163—179. — — (1980). A computational method for the indefinite quadratic programming problem. Linear Algebra and its Applies. 34, pp. 341—370.
Банч и Парлет Bunch J. R. and Parlett B. N. (1971). Direct methods for solving symmetric inde- finite systems of linear equations, SIAM, J. Numer. Anal. 8, pp. 639—655.
Бард Bard Y. (1976). Nonlinear Parameter Estimation, Academic Press, London and New York.
Бард и Гринштадт Bard Y. and Greenstadt J. L. (1969). «A modified Newton method for optimization with equality constraints», in Optimization (R. Fletcher, ed.), pp. 299—306, Academic Press, London and New York.
Бартелс Bartels R. H. (1971). A stabilization of the simplex method. Num. Math. 16, pp. 414—434. — (1980). A penalty linear programming method using reduced-gradient basis- exchange techniques, Linear Algebra and its Applies. 29, pp. 17—32.
Бартелс и Голуб Bartels R. H. and Golub G. H. (1969). The simplex method of linear programming using the LU decomposition, Comm. ACM 12, pp. 266—268.
Бартелс, Голуб и Сондерс Bartels R. H., Golub G. H. and Saunders M. A. (1970). «Numerical techniques in mathematical programming», in Nonlinear Programming (J. B. Rosen, 0. L. Mangasarian and K. Ritter, eds.), pp. 123—176, Academic Press, London and New York.
Бартелс и Конн Bartels R. H. and Conn A. R. (1980). Linearly constrained discrete problems, ACM Trans. Math. Software 6, pp. 594—608.
480 Библиография
Бас и Деккер Bus J. С. Р. and Dekker Т. J. (1975). Two efficient algorithms with guaranteed convergence for finding a zero of a function, ACM Trans. Math. Software 1 pp. 330—345.
Бейкер и Венткер Baker Т. Е. and Ventker R. (1980). «Successive linear programming in refinery lo- gistic models», presented at ORSA/TIMS Joint National Meeting, Colorado Springs, Colorado.
Бен-Израэль Ben-Israel A. (1967). On iterative methods for solving nonlinear least-squares problems over convex sets, Israel J. of Maths. 5, pp. 211—224.
Бенишу, Готье, Анже и Рибьер Benichou M., Gauthier J. M., Hentges О. and Ribiere G. (1977). The efficient so- lution of large-scale linear programming problems—some algorithmic techni- ques and computational results, Math. Prog. 13, pp. 280—322.
Берд Byrd R. H. (1976). Local convergence of the diagonalized method of multipliers, Ph. D. Thesis, Rice University, Texas. — (1978). Local convergence of the diagonalized method of multipliers, J. Opt. Th. Applies, 26, pp. 485—600.
Бертсекас Bertsekas D. P. (1975a). Necessary and sufficient conditions for a penalty function to be exact. Math. Prog. 9, pp. 87—99. — (1975b). Combined primal-dual and penalty methods for constrained minimiza- tion, SIAM J. Control and Optimization 13, pp. 521—544. — (1976a). Multiplier methods: a survey, Automatica 12, pp. 133—145. — (1976b). On penalty and multiplier methods for constrained minimization, SIAM J. Control and Optimization 14, pp. 216—235. — (1979). «Convergence analysis of augmented Lagrangian methods», presented at the IIASA Task Force Meeting on «Generalized Lagrangians in Systems and Eco- nomic Theory», IIASA, Laxenburg, Austria (proceedings to be published in 1981).
Бест, Браунингер, Риттер и Робинсон Best M. J., Brauninger J., Ritter К. and Robinson S. M. (L981). A globaly and quadratically convergent algorithm for general nonlinear programming pro- blems, Computing 26, pp. 141—153.
Бете Betts J. T. (1976). Solving the nonlinear least-square problem, J. Opt. Th. Applies 18, pp. 469—483.
Бигc Biggs M. С. (1972). «Constrained minimization using recursive equality quadratic programming», in Numerical Methods for Non-Linear Optimization (F. A. Loots- ma), pp. 411—428, Academic Press, London and New York. — (1974). The Development of a Class of Constrained Optimization Algorithms and Their Application to the Problem of Electric Power Scheduling, Ph. D. Thesis, University of London. — (1975). «Constrained minimization using recursive quadratic programming: some alternative subproblem formulations», in Towards Global Optimization (L. C. W. Dixon and G. P. Szego, eds.), pp. 341—349, North-Holland, Am- sterdam.
Бил Beale E. M. L. (1959). On quadratic programming, Naval Res. Logistics Quarter- ly 6, pp. 227—243. — (1967a), «An introduction to Beak's method of quadratic programming», in Non-
Библиография 481 linear Programming (J. Abadie, ed.), pp. 143—153, North-Holland, Amster- dam. — (1967b). «Numerical methods», in Nonlinear Programming (J. Abadie, ed.), pp. 132—205, North-Holland, Amsterdam. — (1972). «A derivation of conjugate gradients», in Numerical Methods for Nonli- near Optimization (F. A. Lootsma, ed.), pp. 39—43, Academic Press London and New York. — (1974). «A conjugate-gradient method of approximation programming», in Opti- mization Methods for Resource Allocation (R. W. Cottle and J. Krarup, eds.), pp. 261—277, English Universities Press. — (1975). The current algorithmic scope of mathematical programming systems, Math. Prog. Study 4, pp. 1—11. — (1977). «Integer Programming», in The State of the Art in Numerical Analysis (D. Jacobs, ed.), pp. 409—448, Academic Press, London and New York. — (1978). «Nonlinear programming using a general mathematical programming system», in Design and Implementation of Optimization Software (H. J. Green- berg, ed.), pp. 259—279, Sijthoff and Noordhoff, Netherlands.
Блэнд Bland R. G. (1977). New finite pivoting rules for the simplex method. Math. of Oper. Res. 2, pp. 103—107.
Богc Boggs P. T. (1975). The solution of nonlinear operator equations by A-stable inte- gration techniques, SIAM J. Numer. Anal. 8, pp. 767—785.
Богc и Толле Boggs Р. Т. and Tolle J. W. (1980). Augmented Lagrangians which are quadratic in the multiplier, J. Opt. Th. Applies. 31, pp. 17—26.
Брайтон и Каллам Brayton R. К. and Cullum J. (1977). «Optimization with the parameters constrained to a box», in Proceedings of the IMACS International Symposium on Simula- tion Software and Numerical Methods for Differential Equations, IMACS. — (1979). An algorithm for minimizing a differentiable function subject to box constraints and errors, J. Opt. Th. Applies 29, pp. 521—558.
Браккен и Мак-Кормик Bracken J. and McCormick G. P. (1968). Selected Applications of Nonlinear Program- ming, John Wiley and Sons, New York and Toronto.
Брент Brent R. P. (1973a). Algorithms for Minimization without Derivatives, Prentice- Hall, Inc., Englewood Cliffs, New Jersey. — (1973b). Some efficient algorithms for solving systems of nonlinear equations, SIAM J. Numer. Anal. 10, pp. 327—344.
Бродли Brodlie К. W. (1977a). «Unconstrained optimization», in The State of the Art in Numerical Analysis (D. Jacobs, ed.), pp. 229—268, Academic Press, London and New York. — (1977b). An assessment of two approaches to variable metric methods, Math. Prog. 12, pp. 344—355.
Бройден Broyden С. G. (1965). A class of methods for solving nonlinear simultaneous equat- ions, Mathematics of Computation 19, pp. 577—693. — (1967). Quasi-Newton methods and their application to function minimization, Mathematics of Computation 21, pp. 368—381. — (1970). The convergence of a class of double-rank minimization algorithms, J. Inst. Maths. Applies. 6, pp. 76—90. 16 № 2984
482 Библиография
Бройден, Деннис и Море Broyden С. G., Dennis J. E., Jr. and More J. J. (1973). On the local and superlineal convergence of quasi-Newton methods, J. Inst. Maths. Applies. 12, pp. 223— 245.
Бузингер и Голуб Businger P. and Golub G. H. (1965). Linear least-squares solutions by Householder transformations. Num. Math. 7, pp. 269—276.
Бэрроудейл и Роберте Barrodale I. and Roberts F. D. K. (1973). An improved algorithm for descrete i linear approximation, SIAM J. Numer. Anal. 10, pp. 839—848.
Бэтчелор и Бил Batchelor A. S. J. and Beale E. M. L. (1976). «A revised method of conjugate-gra- dient approximation programming», presented at the Ninth International Symposium on Mathematical Programming, Budapest.
Ван-дер-Хук Van der Hoek G. (1979). Asymptotic properties of reduction methods applying linearly equality constrained reduced problems, Report 7933, Econometric Institute, Erasmus University, Rotterdam.
Ведин Wedin P. A. (1974). On the Gauss—Newton method for the nonlinear least-squares problem, Report 23, Swedish Institute for Applied Mathematics (ITM), Stock- holm.
Вулф Wolfe P. (1959). The simplex method for quadratic programming, Econometrica 27, pp. 382—398. _ (1962). The reduced-gradient method, unpublished manuscript, the RAND Cor- poration. — (1963a). A technique for resolving degeneracy in linear programming, SIAM J.Appl. Math. 11, pp. 205—211. — (1963b). «Methods of nonlinear programming», in Recent Advances in Mathemati- cal Programming (J. Abadie, ed.), pp. 67—86, North-Holland, Amsterdam. — (1966). On the convergence of gradient methods under constraints, IBM Research report, Zurich Laboratory. — (1967). «Methods of nonlinear programming», in Nonlinear programming (J. Aba- die, ed.), pp. 97—131, North-Holland, Amsterdam. — (1969). Convergence conditions for ascent methods, SIAM Review 11, pp. 226— 235. — (1976). Checking the calculation of gradients, Report RC 6007, IBM Yorktown Heights Research Center (May 1976). — (1980a). A bibliography for the ellipsoid algorithm. Report RC 8237, IBM York- town Heights Research Center (April 1980). — (1980b). The ellipsoid algorithm, in Optima, 1 (Newsletter of the Mathematical Programming Society, June 1980).
Гарсиа Паломарес и Мангасарьян Garcia Palomares U. M. and Mangasarian 0. L. (1976). Superlinearly convergent quasi-Newton algorithms for nonlinearly constrained optimization problems, Math. Prog. 11, pp. 1—13.
Гач и Ловас Gacs P. and LovaszL. (1981). Khachiyan's algorithm for linear programming, Math. Prog. Study 14, pp. 61—68.
Ге и Томас Gue R. L. and Thomas M. E. (1968). Mathematical Methods in Operations Research, The Macmillan Company, New York.
Библиография 483
Гилл Gill P. E. (1975). Numerical Methods for Large-Scale Linearly Constrained Optimi- zation Problems, Ph. D. Thesis, University of London.
Гилл, Голуб, Мюррей и Сондерс Gill P. E., Golub G. H., Murray W. and Saunders M. A. (1974). Methods for modi- fying matrix factorizations, Mathematics of Computation 28, pp. 505—535.
Гилл и Мюррей
Gill Р. E. and Murray W. (1972). Quasi-Newton methods for unconstrained optimi-
zation, J. Inst. Maths. Applies. 9, pp. 91—108.
— — (1973a). The numerical solution of a problem in the calculus of variations, in
Recent Mathematical Developments in Control (D. J. Bell. ed.), pp. 97—122,
Academic Press, London and New York.
— — (1973b). Quasi-Newton methods for linearly constrained optimization. Report
NAC 32, National Physical Laboratory, England.
— — (1973с). A numerically stable form of the simplex method, Linear Algebra
and its Applies. 7, pp. 99—138.
— — (1974a). Newton-type methods for unconstrained and linearly constrained op,-
timization. Math. Prog. 28, pp. 311—350.
— — (1974b). Numerical Methods for Constrained Optimization, Academic Press,
London and New York. (Имеется перевод: Ф. Гилл и У. Мюррей. Численные
методы условной оптимизации.—M.: Мир, 1977.)
— — (1974с). «Newton-type methods for linearly constrained optimization», in
Numerical Methods for Constrained Optimization (P. E. Gill and W.Murray,
eds.), pp. 29—66, Academic Press, London and New York.
— — (1974d). «Quasi-Newton methods for linearly constrained optimization», in
Numerical Methods for Constrained Optimization (P. E. Gill and W. Murray,
eds.), pp. 67—92, Academic Press, London and New York.
— — (1974e). Safeguarded steplength algorithms for optimization using descent
methods. Report NAC 37. National Physical Laboratory, England.
— — (1976a). «Nonlinear least squares and nonlinearly constrained optimization»,
in Numerical Analysis, Dundee 1975 (G. A. Watson, ed.), pp. 135—147, Sprin-
ger-Verlag Lecture Notes in Mathematics 506, Berlin, Heidelberg and New
York.
— — (1976b). Minimization subject to bounds on the variables. Report NAC 71,
National Physical Laboratory, England.
— — (1977a). «Linearly constrained problems including linear and quadratic pro-
gramming», in The State of the Art in Numerical Analysis (D. Jacobs, ed.),
pp. 313—363, Academic Press, London and New York.
— — (1977b). The computation of Lagrange multiplier estimates for constrained
minimization. Report NAC 77, National Physical Laboratory, England.
— — (1978a). Algorithms for the solution of the nonlinear least-squares problem,
SIAM J. Numer. Anal. 15, pp. 977—992.
— — (1978b). Numerically stable .methods for quadratic programming, Math. Prog.
14, pp. 349—372.
— — (1978с). The design and implementation of software for unconstrained optimi-
zation, in Design and Implementation of Optimization Software (H. Greenberg,
ed.), pp. 221—234, Sijthoff and Noordhoff, Netherlands.
— — (1979a). Conjugate-gradient methods for large-scale nonlinear optimization,
Report SOL 79-15, Department of Operations Research, Stanford University,
California.
— — (1979b). The computation of Lagrange multiplier estimates for constrained
minimization. Math. Prog. 17, pp. 32—60.
— — (1979с). «Performance evaluation for optimization software», in Performance
Evaluation of Numerical Software (L. D. Fosdick, ed.), pp. 221—234, North-
Holland, Amsterdam.
Гилл, Мюррей и Нэш Gill P. E., Murray W, and Nash S. G, (1981), Newton-type minimization methods
484 Библиография
using the linear conjugate-gradient method, Report (to appear). Department of Operations Research, Stanford University, California.
Гилл, Мюррей, Пикен и Райт Gill Р. Е., Murray W., Picken S. M. and Wright M. Н. (1979). The design and struc- ture of a Fortran program library for optimization, ACM Trans. Math. Software 5, pp. 259—283.
Гилл, Мюррей и Сондерс Gill Р. Е., Murray W. and Saunders M. A. (1975). Methods for computing and modi- fying the LDV factors of a matrix. Mathematics of Computation 29, pp. 1051— 1077.
Гилл, Мюррей, Сондерс и Райт
Gill Р. Е., Murray W., Saunders M. A. and Wright M. H. (1979). Two step-length
algorithms for numerical optimization, Report SOL 79-25, Department of Ope-
rations Research, Stanford University, California.
———— (1980). «A projected Lagrangian method for problems with both linear
and nonlinear constraints», presented at the SIAM 1980 Fall Meeting, Houston,
Texas. .
———— (1981a). «A numerical investigation of ellipsoid algorithms for large-
scale linear programming», in Large-Scale Linear Programming (Volume 1)
(G. B. Dantzig, M. A. Dempster and M. J. Kallio, eds.), pp. 487—509, IIASA
Collaborative Proceedings Series, CP-81-51, IIASA, Laxenburg, Austria.
— — — — (1981b). QP-based methods for large-scale nonlinearly constrained opti-
mization, Report SOL 81-1, Department of Operations Research, Stanford
University, California. To appear in Nonlinear Programming 4, (0. L. Manga-
sarian, R. R. Meyer and S. M. Robinson, eds.). Academic Press, London and
New York.
Глэд Glad S. T. (1979). Properties of updating methods for the multipliers in augmented Lagrangians, J. Opt. Th. Applies 28, pp. 135—156.
Глэд и Полак Glad S. Т. and Polak E. (1979). A multiplier method with automatic limitation of penalty growth, Math. Prog. 17, pp. 140—155.
Голуб и Перейра Golub G. H. and Pereyra V. (1973). The differentiation of pseudo-inverses and non- linear least-squares problems whose variables separate, SIAM J. Numer. Anal. 10, pp. 413—432.
Голуб и Райнх Golub G. H. and Reinsch C. (1971). «Singular value decomposition and least-squares solutions», in Handbook for Automatic Computation, Vol. II (J. H. Wilkinson and C. Reinsch, eds.), pp. 134—151, Springer-Verlag, Berlin, Heidelberg and New York.
Гольдфарб Goldfarb D. (1969). Extension of Davidon's variable metric method to maximization under linear inequality and equality constraints, SIAM J. Appl. Math. 17, pp. 739—764. — (1970). A family of variable metric methods derived by variational means, Ma- thematics of Computation 24, pp. 23—26. — (1980). Curvilinear path step lenth algorithms for minimization which use direc- tions of negative curvature, Math. Prog. 18, pp. 31—40.
Гольдфарб и Райд Goldfarb D. and Reid J. К. (1977). A practicable steepest-edge simplex algorithm, Math. Prog. 12, pp. 361—371.
Библиография 485
Гольдфельд, Квандт и Троттер Goldfeld S. M., Quandt R. Е. and Trotter H. F. (1966). Maximization by quadratic hill-climbing, Econometrica 34, pp. 541—551.
Гольдштейн и Прайс Goldstein A. and Price J. (1967). An effective algorithm for minimization, Numer Math. 10, pp. 184—189.
Гоффен Goffin J. L. (1980). Convergence results in a class of variable metric subgradient methods, Working Paper 80-08, Faculty of Management, McGill University, Montreal, Canada. To appear in Nonlinear Programming 4 (0. L. Mangasarian, R. R. Meyer and S. M. Robinson, eds.). Academic Press, London and New York.
Гринберг Greenberg H. J. (1978a). «A tutorial on matricial packing», in Design and Implemen- tation of Optimization Software (H. J. Greenberg, ed.), pp. 109—142, Sijthoff and Noordhoff, Netherlands. — (1978b). «Pivot selection tactics», in Design and Implementation of Optimization Software (H. J. Greenberg, ed.), pp. 143—174, Sijthoff and Noordhoff, Nether- lands.
Гринберг и Кэлан Greenberg H. J. and Kalan J. E. (1975). An exact update for Harris' TREAD, Math. Prog. Study 4, pp. 26—29.
Гринштадт Greenstadt J. L. (1967). On the relative efficiencies of gradient methods, Mathema- tics of Computation 21, pp. 360—367. — (1970). Variations on variable-metric methods. Mathematics of Computation 24, pp. 1-22. — (1972). A quasi-Newton method with no derivatives, Mathematics of Computa- tion 26, pp. 145—166,
Гриффит и Стюарт Griffith R. E. and Stewart R. A. (1961). A nonlinear programming technique for the optimization of continuous processing systems, Management Science, 7, pp. 379—392.
Грэхем Graham S. R. (1976). A matrix factorization and its application to unconstrained minimization. Project thesis for BSc. (Hons) in Mathematics for Business, Middlesex Polytechnic, Enfield, England.
Гэй Gay D. M. (1979a). On robust and generalized linear regression problems, Report 200, Mathematics Research Center, University of Wisconsin, Madison, Wisconsin. — (1979b). Computing optimal locally constrained steps, Report 2013, Mathematics Research Center, University of Wisconsin, Madison, Wisconsin.
Гэй и Шнабель Gay D. M. and Schnabel R. B. (1978). «Solving systems of nonlinear equations by Broyden's method with projected updates», in Nonlinear Programming 3 (0. L. Managasarian, R. R. Meyer and S. M. Robinson, eds.), pp. 245—28). Academic Press, London and New York.
Дальквист и Бьёрк Dahlquist G. and Bjorck A. (1974). Numerical Methods, Prentice-Hall Inc., Engle- wood Cliffs, New Jersey.
Данциг Dantzig G. B. (1963). Linear Programming and Extensions, Princeton University Press, Princeton New Jersey. (Имеется перевод: Дж. Данциг. Линейное про- граммирование, его обобщения и применения.— M.: Прогресс, 1966.)
486 Библиография
Данциг, Орден и Вулф Dantzig G. В., Orden A. and Wolfe P. (1955). Generalized simplex method for mini- mizing a linear form under linear inequality restraints. Pacific J. Math. 5, pp. 183—195.
Данциг, Демпстер и Каллио Dantzig G. В., DempsterM. A. H. and KallioM. J. (eds.) (1981). Large-Scale Linear Programming (Volume 1), IIASA Collaborative Proceedings Series, CP-81-51, IIASA, Laxenburg, Austria.
Дафф и Райд Duff I. S. and Reid J. K. (1978). An implementation of Tarjan's algorithm for the block triangularization of a matrix, ACM Trans. Math. Software 4, pp. 137— 147.
Даффин, Петерсон и Зенер Duffin R. J., Peterson E. L. and Zener С. (1967). Geometric Programming—Theory and Applications, John Wiley and Sons, New York and Toronto.
Деккер Dekker T. J. (1969). «Finding a zero by means of successive linear interpolation», in Constructive Aspects of the Fundamental Theorem of Algebra (B. Dejon and P. Henrici, eds.), pp. 37—48, Wiley Interscience, London.
Дембо Dembo R. S. (1978). Current state of the art of algorithms and computer software for geometric programming, J. Opt. Th. Applies. 26, pp. 149—184.
Дембо, Айзенштат и Штайхауг Dembo R. S., Eisenstat S. С. and Steihaug T. (1980). Inexact Newton method», Working Paper -^. 47, School of Organization and Management, Yale Univer- sity.
Дембо и Штайхауг Dembo R. S. and Steihaug T. (1980). Truncated-Newton algorithms for large-scale unconstrained optimization, Working Paper 41: 48, School of Organization and Management, Yale University.
Деннис Dennis J. E., Jr. (1973). «Some computational techniques for the nonlinear least- squares problem», in Numerical Solution of Systems of Nonlinear Algebraic Equations (G. D. Byrne and C. A. Hall, eds.), pp. 157—183, Academic Press, London and New York. — (1977). «Nonlinear Least Squares», in The State of the Art in Numerical Analysis (D. Jacobs, ed.), pp. 269—312, Academic Press, London and New York.
Деннис и Море Dennis J. E., Jr. and More J. J. (1974). A characterization of superlinear conver- gence and its application to quasi-Newton methods. Mathematics of Computa- tion 28, pp. 549—560. —— (1977). Quasi-Newton methods, motivation and theory, SIAM Review 19, pp. 46—89.
Деннис, Гэй и Уелш Dennis J. E., Jr., Gay D. M. and Welsch R. E. (1977). An adaptive nonlinear least- squares algorithm, Report TR 77-321, Department of Computer Sciences, Cor- nell University.
Деннис и Шнабель Dennis J. E., Jr. and Schnabel R. E. (1979). Least change secant updates for quasi- Newton methods, SIAM Review 21, pp. 443—469. — — (1980). A new derivation of symmetric positive definite secant updates. Report CU-CS-185-80, Department of Mathematical Sciences, Rice University.
Библиография 487
Джанг Djang A. (1980). Algorithmic Equivalence in Quadratic Programming, Ph. D. The- sis, Stanford University, California.
Джейн, Лэсдон и Сондерс Jain A., Lasdon L. S. and Saunders M. A. (1976). «An in-core nonlinear mathemati- cal programming system for large nonlinear programs», presented at ORSA/TIMS Joint National Meeting, Miami, Florida.
Джонсон Johnson E. L. (1978). «Some considerations in using branch-and-bound codes», in Design and Implementation of Optimization Software (H. J. Greenberg, ed.), pp. 241—248, Sijthoff and Noordhoff, Netherlands.
Джонсон и Пауэлл Johnson E. L. and Powell S. (1978). «Integer programming codes», in Design and Implementation of Optimization Software (H. J. Greenberg, ed.), pp. 225— 240, Sijthoff and Noordhoff, Netherlands.
Диксон Dixon L. C. W. (1972a). Quasi-Newton algorithms generate identical points, Math. Prog. 2, pp. 383—387. — (1972b). Quasi-Newton algorithms generate identical points. II. The proof of four new theorems, Math. Prog. 3, pp. 345—358. — (1975). Conjugate-gradient algorithms: quadratic termination without linear searches, J. Inst. Maths. Applies. 15, pp. 9—18.
Донгарра, Банч, Молер, Стюарт Dongarra J. J., Bunch J. R., Moler С. В. and Stewart G. W. (1979). LINPACK Users Guide, SIAM Publications, Philadelphia.
Дэвидон Davidon W. C. (1959). Variable metric methods for minimization, A. E. C. Res. and Develop. Report ANL-5990, Argonne National Laboratory, Argonne, Illinois. — (1975). Optimally conditioned optimization algorithms without line searches, Math. Prog. 9, pp. 1—30. — (1979). Conic approximations and collinear scalings for optimizers, SIAM J. Nu- mer. Anal. 17, pp. 268—281.
Дэвис и Рабинович Davis P. J. and Rabinowitz P. (1967). Numerical Integration, Blaisdell, London.
Дэниел, Грэг, Кауфман и Стюарт Daniel J. W., Gragg W. В., Kaufman L. C. and Stewart G. W. (1976). Reorthogo- nalization and stable algorithms for updating the Gram—Schmidt QR factori- zation, Mathematics of Computation 30, pp. 772—795.
Дюмонте и Виньес Dumontet J. and Vignes J. (1977). Determination du pas optimal dans le calcul des derivees sur ordineur, Revue francaise d'automatique, d'information et de re- cherche operationelle, Analyse numerique (RAIRO) 11, pp. 13—25.
Зангвилл Zangwill W. I. (1965). Nonlinear programming by sequential unconstrained maximi- zation, Working Paper 131, Center for Research in Management Science, Uni- versity of California, Berkeley. — (1967a). Nonlinear programming via penalty functions. Management Science 13, pp. 344—358. — (1967b). Algorithm for the Chebyshev problem, Management Science 14, pp. 58— 78.
Зойтендейк Zountendjik G, (1970), «Nonlinear programming, computational methods», in Inte-
488 Библиография ger and Nonlinear Programming (J. Abadie, ed.), pp. 37—86, North-Holland, Amsterdam.
Зуховицкий С. И., Поляк Р. А. и Примак М. Е. (1963). Алгоритм для решения задач выпуклого чебышевского приближения.— Докл. АН СССР, 1963, т. 135, № 5, с. 991—994.
Канторович Л. В. и Акилов Г. П. (1959). Функциональный анализ в нормирован- ных пространствах.—М.: Физматгиз, 1959.
Караламбус Charalambous С. (1978). A lower bound for the controlling parameter of the exact penalty function, Math. Prog. 15, pp. 278—290.
Караламбус и Конн Charalambous С. and Conn A. R. (1978). An efficient method to solve the minimax problem directly, SIAM J. Numer. Anal. 15, pp. 162—187.
Кауфман и Перейра Kaufman L. С. and Pereyra V. (1978). A method for separable nonlinear least-square» problems with separable nonlinear equality constraints, SIAM J. Numer. Anal. 15, pp. 12—20.
Кахан Kahan W. (1973). The implementation of algorithms: Part 1, Technical Report 20, Department of Computer Science, University of California, Berkeley.
Келли Kelley J. E. (1960). The cutting plane method for solving convex programs, J. Soc. Indust. Appl. Math. 8, pp. 703—712.
Кертис, Пауэлл и Райд Curtis A. R., Powell М. J. D. and Reid J. К. (1974). On the estimation of sparse Jacobian matrices, J. Inst. Maths. Applies. 13, pp. 117—119.
Кертис и Райд Curtis A. R. and Reid J. К. (1972). On the automatic scaling of matrices for Gaussian elimination, J. Inst. Maths. Applies. 10, pp. 118—124. — _ (1974). The choice of step lengths when using differences to approximate Jaco- bian matrices, J. Inst. Maths. Applies. 13, pp. 121—126.
Кляйн, Молер, Стюарт и Уилкинсон Cline А. К., Moler С. В., Stewart G. W. and Wilkinson J. H. (1979). An estimate for the condition number of a matrix, SIAM J. Numer. Anal. 16, pp. 368—375.
Кнут Knuth D. E. (1979). ТЕХ and METAFONT, New Directions in Typesetting, Ameri- can Mathematical Society and Digital Press, Bedford, Massachusetts.
KOKC Cox M. G. (1977). «A survey of numerical methods for data and function approxima- tion», in The State of the Art in Numerical Analysis (D. Jacobs, ed.), pp. 627— 668, Academic Press, London and New York.
Колвилл Colville A. R. (1968). A comparative study on nonlinear programming codes, Report No. 320-2949, IBM New York Scientific Center.
Колеман Coleman T. F. (1979). A Superlinear Penalty Function Method to Solve the Nonli- near Programming Problem, Ph. D. Thesis, University of Waterloo, Ontario, Canada.
Колеман и Конн Coleman Т. F. and Conn A. R. (1980a). Second-order conditions for an exact penalty [unction. Math. Prog. 19, pp. 178—185.
Библиография 489
— — (1980b). Nonlinear programming via an exact penalty function method: asymp- totic analysis, Report CS-80-30, Department of Computer Science, University of Waterloo, Ontario, Canada. — — (1980с). Nonlinear programming via an exact penalty function method: global analysis, Report CS-80-31, Department of Computer Science, University of Waterloo, Ontario, Canada.
Колеман и Море Coleman T. F. and More J. J. (1980). «Coloring large sparse Jacobians and Hessians», presented at the SIAM 1980 Fall Meeting, Houston, November 1980.
Конкус, Голуб и 0'Лири Concus Р., Golub G. H. and O'Leary D. P. (1976). «A generalized conjugate-gradient method for the numerical solution of elliptic partial differential equations», in Sparse Matrix Computations (J. R. Bunch and D. J. Rose, eds.), pp. 309—332, Academic Press, London and New York.
Конн Conn A. R. (1973). Constrained optimization using a non-differentiable penalty function, SIAM J. Numer. Anal. 10, pp. 760—779. — (1976). Linear programming via a non-differentiable penalty function, SIAM J. Numer. Anal. 13, pp. 145—154. — (1979). An efficient second-order method to solve the (constrained) minimax problem, Report CORR-79-5, University of Waterloo, Canada.
Конн и Петшиковский Conn A. R. and Pietrzykowski T. (1977). A penalty function method converging directly to a constrained optimum, SIAM J. Numer. Anal. 14, pp. 348—375.
Конн и Синклер Conn A. R. and Sinclair J. W. (1975). Quadratic programming via a non-differen- tiable penalty function, Report 75/15, Department of Combinatorics and Opti- mization, University of Waterloo, Canada.
Корт Kort B. W. (1975). «Rate of convergence of the method of multipliers with inexact minimization», in Nonlinear Programming 2 (0. L. Mangasarian, R. R. Meyer and S. M. Robinson, eds.), pp. 193—214, Academic Press, London and New York.
Корт и Бертсекас Kort В. W. and Bertsekas D. P. (1976). Combined primal dual and penalty methods for convex programming, SIAM J. Control and Optimization 14, pp. 268—294.
Коттл Cottle R. W. (1974). Manifestations of the Schur complement, Linear Algebra and its Applies. 8, pp. 189—211.
Коши Cauchy A. (1847). Methode Generate pour la Resolution des Systems d'Equations Simultanees, Сотр. Rend. Acad. Sci. Paris, pp. 536—538.
Кун Kuhn H. W. (1976). «Nonlinear programming: a historical view», in SIAM—AMS Proceedings, Volume IX, Mathematical Programming (R. C. Cottle and C. E. Lemke, eds.), pp. 1—26, American Mathematical Society, Providence, Rhode Island.
Кун и Таккер Kuhn H. W. and Tucker A. W. (1951). «Nonlinear Programming», in Proceedings of the Second Berkeley Symposium on Mathematical Statistics and Probability (J, Neyman, ed.), pp. 481—492, Berkeley, University of California Press.
490 Библиография
Курант Courant R. (1936). Differential and Integral Calculus (two volumes), Blackie, Lon- don and Glasgow. — (1943). Variational methods for the solution of problems of equilibrium and vibra- tions, Bull. Amer. Math. Soc. 49, pp. 1—23.
Кэниел и Дэкс Kaniel S. and Dax A. (1979). A modified Newton's method for unconstrained mini- mization, SIAM J. Numer. Anal. 16, pp. 324—331.
Кэррол Carrol С. W. (1959). An Operations Research Approach to the Economic Optimiza- tion of a Kraft Pulping Process, Ph. D. Thesis, Institute of Paper Chemistry, Appleton, Wisconsin. — (1961). The created response surface technique for optimizing nonlinear restra- ined systems, Operations Research 9, pp. 169—184.
Ланнесс Lyness J. N. (1976). «An interface problem in numerical software», Proceedings of the 6th Manitoba Conference on Numerical Mathematics, pp. 251—263. — (1977a), «Has numerical differentiation a future?» Proceedings of the 7th Mani- toba Conference on Numerical Mathematics, pp. 107—129. — (1977b). «Quid, quo, quadrature?» in The State of the Art in Numerical Analysis (D. Jacobs, ed.), pp. 535—560, Academic Press, London and New York. Лайнесс и Молер Lyness J. N. and Moler С. В. (1967). Numerical differentiation of analytic functi- ons, SIAM J. Numer. Anal. 4, pp. 202—210. Лайнесс и Сэнд Lyness J. N. and Sande G. (1971). ENTCAF and ENTCRE: Evaluation of normali- zed Taylor coefficients of an analytic function, Comm. ACM 14, pp. 669—675. Левенберг Levenberg К. (1944). A method for the solution of certain problems in least squares, Quart. Appl. Math. 2, pp. 164—168. Лемарешаль Lemarechal С. (1975). An extension of Davidon methods to non-differentiable pro- blems, Math. Prog. Study 3, pp. 95—109. Лемке Lamke С. Е. (1965). Bimatrix equilibrium points and mathematical programming, Management Science 11, pp. 681—689. Ленард Lenard M. L. (1979). A computational study of active set strategies in nonlinear programming with linear constraints, Math. Prog. 16, pp. 81—97. Ленбергер Luenberger D. G. (1973). Introduction to Linear and Nonlinear Programming, Ad- dison-Wesley, Menio Park, California. — (1974). A combined penalty function and gradient projection method for nonli- near programming, J. Opt. Th. Applies. 14, pp. 477—495. Лилл Lill S. A. (1972). «Generalization of an exact method for solving equality constra- ined problems to deal with inequality constraints», in Numerical Methods for Non-Linear Optimization (F. A. Lootsma, ed.), pp. 383—384, Academic Press, London and New York. Лоулер Lawler E. L. (1980). The great mathematical sputnik of 1979, University of Cali- fornia, Berkeley, California (February 1980).
Библиография 491
Лоусон и Хансон Lawson С. L. and Hanson R. J. (1974). Solving Least-Squares Problems, Prentice- Hall, Inc., Englewood Cliffs, New Jersey. Л у тем а Lootsma F. A. (1969). Hessian matrices of penalty functions for solving constrained optimization problems, Philips Res. Repts 24, pp. 322—331. — (1970). Boundary properties of penalty functions for constrained optimization problems, Philips Res. Repts 3. — (1972). «A survey of methods for solving constrained optimization problems via unconstrained minimization», in Numerical Methods for Non-Linear Optimiza- tion (F. A. Lootsma, ed.), pp. 313—347, Academic Press, London and New York. Лэсдон и Уорен Lasdon L. S. and Waren A. D. (1978). «Generalized reduced gradient software for linearly and nonlinearly constrained problems», in Design and Implementation of Optimization Software (H. J. Greenberg, ed.), pp. 335—362, Sijthoff and Noordhoff, Netherlands. Лэсдон, Уорен, Джейн и Ратнер Lasdon L. S., Waren A. D., Jain A. and Ratner M. (1978). Design and testing of a GRG code for nonlinear optimization, ACM Trans. Math. Software, 4, pp. 34— 50. Лэсдон, Фоке и Ратнер Lasdon L. S., Fox R. L. and Ratner M. (1973). An efficient one-dimensional search procedure for barrier functions, Math. Prog. 4, pp. 279—296. Мадсен Madsen К. (1975). An algorithm for the minimax solution of overdetermined systems of linear equations, J. Inst. Maths. Applies. 16, pp. 321—328. Мак-Кормик McCormick G. P.' (1969). Anti-zygzagging by bending. Management Science 15, pp. 315—320. — (1970a). The variable reduction method for nonlinear programming, Management Science 17, pp. 146—160. — (1970b). «A second-order method for the linearly constrained nonlinear program- ming problem», in Nonlinear Programming (J. B. Rosen, 0. L. Mangasarian and K. Ritter, eds.), pp. 207—243, Academic Press, London and New York. — (1977). A modification of Armijo's step-size rule for negative curvature, Math. Prog. 13, pp. 11—115. Мак-Лин и Уотсон McLean R. A. and Watson G. A. (1979). Numerical methods for nonlinear discrete ^ approximation problems, proceedings of the Oberwolfach Conference on Ap- proximation Theory (to appear). Мангасарьян Mangasarian 0. L. (1969). Nonlinear Programming, McGraw-Hill Book Co., New York. — (1975). Unconstrained Lagrangians in nonlinear programming, SIAM J. Control and Optimization 13, pp. 772—791. Маратос Maratos N. (1978). Exact Penalty Function Algorithms for Finite-Dimensional and Control Optimization Problems, Ph. D. Thesis, University of London. Марвил Marwil E. (1978). Exploiting Sparsity in Newton-Type Methods, Ph. D. Thesis, Cornell University, Ithaca, New York.
492 Библиография
Маркардт Marquardt D. (1963). An algorithm for least-squares estimation of nonlinear parame- ters, SIAM J.Appl. Math. 11, pp. 431—441. Марковиц Markowitz H. M. (1957). The elimination form of the inverse and its applications to linear programming, Management Science 3, pp. 255—269. Марстен Marsten R. E. (1978). XMP: A structured library of subroutines for experimental mathematical programming, Report 351, Department of Management Informa- tion Systems, University of Arizona, Tucson, Arizona. Марстен и Шанно Marsten R. E. and Shanno D. F. (1979). Conjugate-gradient methods for linearly con- strained nonlinearly programming. Report 79-13, Department of Management Information Systems, University of Arizona, Tucson, Arizona. Миеле, Крэгг, Айер и Леви Miele A., Cragg E. E., lyer R. R. and Levy A. V. (1971). Use of the augmented pe- nalty function in mathematical programming, Part I, J. Opt. Th. Applies. 8, pp. 115—130. Миеле, Крэгг и Леви Miele A., Cragg E. E. and Levy A. V. (1971). Use of the augmented penalty function in mathematical programming, Part II, J. Opt. Th. Applies. 8, pp. 131—153. Миллер Miller С. Е. (1963). «The simplex method for local separable programming», in Re- cent Advances in Mathematical Programming (R. L. Graves and P. Wolfe, eds.), pp. 89—100, McGraw-Hill Book Co., New York. Миффлин Mifflin R. (1975). A superlinearly convergent algorithm for minimization without evaluating derivatives. Math. Prog. 9, pp. 100—117. — (1977). Semismooth and semiconvex functions in constrained optimization, SIAM J. Control and Optimization 15, pp. 959—972. Mope More J.J. (1977). «The Levenberg—Marquardt algorithm: implementation and theory», in Numerical Analysis (G.A.Watson, ed.), pp. 105—116, Lecture Notes in Mathematics 630, Springer-Verlag, Berlin, Heidelberg and New York. — (1979a). On the design of optimization software, Report DAMTP 79/NA 8, Uni- versity of Cambridge. — (1979b). «Implementation and testing of optimization software», in Performance Evaluation of Numerical Software (L. D. Fosdick, ed.), pp. 253—266, North- Holland, Amsterdam. Море и Соренсен More J. J. and Sorensen D. C. (1979). On the use of directions of negative curvature in a modified Newton method. Math. Prog. 15, pp. 1—20. Муртаф Murtagh В. А. (1981). Advanced Linear Programming, McGraw-Hill Book Co., New York. (Имеется перевод: Б. Муртаф. Современное линейное программи- рование.—M.: Мир, 1984.) Муртаф и Сарджент Murtagh В. A. and Sargent R. H. W. (1969). «A constrained minimization method with quadratic convergence», in Optimization (R. Fletcher, ed.), pp. 215—246, Academic Press, London and New York. Муртаф и Сондерс Murtagh В. A. and Saunders M. A. (1977). MINOS User's Guide, Report SOL 77-9, Department of Operations Research, Stanford University, California.
Библиография 493
— — (1978). Large-scale linearly constrained optimization. Math. Prog. 14, pp. 41— — — (1980). A projected Lagrangian algorithm and its implementation for sparse nonlinear constraints. Report SOL 80-1R, Department of Operations Research, Stanford University, California, to appear in Math, Prog. Study on Constrained Optimization. Мэйн. и Маратос Mayne D. Q. and Maratos N. (1979). A first-order exact penalty function algorithm for equality constrained optimization problems, Math. Prog. 16, pp. 303—324. Мэйн и Полак Mayne D. Q. and Polak E. (1976). Feasible direction algorithms for optimization problems with equality and inequality constraints. Math. Prog. 11, pp. 67—80. Мюррей Murray W. (1967). «Ill-conditioning in barrier and penalty functions arising in con- strained nonlinear programming», presented at the Princeton Mathematical Programming Symposium, August 14—18, 1967. — (1969a). Constrained Optimization, Ph. D. Thesis, University of London. — (1969b). «An algorithm for constrained minimization», in Optimization (R. Flet- cher, ed.), pp. 247—258, Academic Press, London and New York. — (1971a). An algorithm for finding a local minimum of an indefinite quadratic program. Report NAC 1, National Physical Laboratory, England. — (1971b). Analytical expressions for the eigenvalues and eigenvectors of the Hessian matrices of barrier and penalty functions, J. Opt. Th. Applies. 7, pp. 189—196. — (1972a). «Second derivative methods», in Numerical Methods for Unconstrained Optimization (W. Murray, ed.), pp. 57—71, Academic Press, London and New York. — (1972b). «Failure, the causes and cures», in Numerical Methods for Unconstrained Optimization (W. Murray, ed.), pp. 107—122, Academic Press, London and New York. — (1976). «Constrained Optimization», in Optimization In Action (L. C. W. Dixon, ed.), pp. 217—251, Academic Press, London and New York. Мюррей и Овертон Murray W. and Overton M. L. (1980a). A projected Lagrangian algorithm for non- linear minimax optimization, SIAM J. Sci. Stat. Comput. 1, pp. 345—370. — — (1980b). A projected Lagrangian algorithm for nonlinear ^ optimization, Re- port SOL 80-4, Department of Operations Research, Stanford University, Cali- fornia. Мюррей и Райт Murray W. and Wright M. H. (1976). Efficient linear search algorithms for the lo- garithmic berrier function, Report SOL 76-18, Department of Operations Re- search, Stanford University, California. — — (1978). Projected Lagrangian methods based on the trajectories of penalty and barrier functions, Report SOL 78-23, Department of Operations Research, Stan- ford University, California. — — (1980). Computation of the search direction in constrained optimization algorithms, Report SOL 80-2, Department of Operations Research, Stanford University, to appear in Math. Prog. Study on Constrained Optimization. Назарет Nazareth L. (1977). A conjugate-direction algorithm without line searches, J. Opt. Th. Applies. 23, pp. 373—388. — (1979). A relationship between the BFGS and. conjugate-gradient algorithms and its implications for new algorithms, SIAM J. Numer. Anal. 16, pp. 794—800. Назарет и Носедал Nazareth L. and Nocedal J. (1978). A study of conjugate-gradient methods, Report SOL 78-29, Department of Operations Research, Stanford University, Califor- nia.
494 Библиография
Нелдер и Мид Nelder J. A. and Mead R. (1965). A simplex method for function minimization, Com- puter Journal 7, pp. 308—313.
Немировский А. С. и Юдин Д. Б. (1979). Эффективные методы решения задач выпуклого программирования большой размерности.— Экономика и мате- матические методы, 1979, № 2, с. 135—152.
Носедал Nocedal J. (1980). Updating quasi-Newton matrices with limited storage, Mathe- matics of Computation 35, pp. 773—782. Оливер Oliver J. (1980). An algorithm for numerical differentiation of a function of one real variable, J. Сотр. Appl. Math. 6, pp. 145—160. Оливер и Раффхед Oliver J. and Ruffhead A. (1975). The selection of interpolation points in numerical differentiation, Nordisk Tidskr. Informationbehandling (BIT) 15, pp. 283— 295. 0'Лири O'Leary D. P. (1980a). A discrete Newton algorithm for minimizing a function of many variables, Report 910, Computer Science Center, University of Maryland, College Park, Maryland. — (1980b). Estimating matrix condition numbers, SIAM J. Sci. Stat. Comput. 1, pp. 205—209. Орен Oren S. S. (1974a). Self-scaling variable metric (SSVM) algorithms. Part II: imple- mentation and experiments. Management Science 20, pp. 863—874. — (1974b). On the selection of parameters in self-scaling variable metric algo- rithms, Math. Prog. 7, pp. 351—367. Орен и Ленбергер Oren S. S. and Luenberger D. G. (1974). Self-scaling variable metric (SSVM) algo- rithms, Part I: criteria and sufficient conditions for scaling a class of algorithms, Management Science 20, pp. 845—862. Орен и Спедикато Oren S. S. and Spedicato E. (1976). Optimal conditioning of self-scaling and variable metric algorithms. Math. Prog. 10, pp. 70—90. Ортега и Рейнболдт Ortega J. M. and Rheinboldt W. С. (1970). Iterative Solution of Nonlinear Equations in Several Variables, Academic Press, London and New York. (Имеется перевод:
Дж. Ортега, В. Рейнболдт. Итерационные методы решения нелинейных систем уравнений со многими неизвестными.—M.: Мир, 1975.) Орчард-Хейс Orchard-Hays W. (1968). Advanced Linear Programming Computing Techniques, McGraw-Hill, New York. — (1978a). «History of mathematical programming systems», in Design and Imple- mentation of Optimization Software (H. J. Greenberg, ed.), pp. 1—26, Sijthoff and Noordhoff, Netherlands. — (1978^. «Scope of mathematical programmind software», in Design and Imple- mentation of Optimization Software (H. J. Greenberg, ed.), pp. 27—40, Sij- thoff and Noordhoff, Netherlands. — (1978с). «Anatomy of a mathematical system», in Design and Implementation of Optimization Software (H. J. Greenberg, ed.), pp. 41—102, Sijthoff and Noordhoff, Netherlands. Осборн и Райан Osborne M. R. and Ryan D. M. (1972). «A hybrid algorithm for nonlinear programm- ing», in Numerical Methods for Non-Linear Optimization (F. A. Lootsma, ed.), PP. 395—410, Academic Press, London and New York.
Библиография 495
Осборн и Уотсон Osborne M. R. and Watson G. A. (1969). An algorithm for minimax approximation in the nonlinear case. Computer Journal 12, pp. 63—68. — — (1971). An algorithm for discrete nonlinear /i approximation. Computer Jour- nal 10, pp. 172—177. Осен Aasen J.O. (1971). On the reduction of a symmetric matrix to tridiagonal form, Nordisk Tidskr. Informationsbehandling (BIT) 11, pp. 233—242. Паркинсон и Хатчинсон Parkinson J. M. and Hutchinson D. (1972). «An investigation into the efficiency of variants of the simplex method», in Numerical Methods for Non-Linear Optimi- zation (F. A. Lootsma, ed.), pp. 115—135, Academic Press, London and New York. Пауэлл Powell M. J. D. (1964). An efficient method for finding the minimum of a function of several variables without calculating derivatives, Computer Journal 7, pp. 155—162. — (1969). «A method for nonlinear constraints in minimization problems», in Opti- mization (R. Fletcher, ed.), pp. 283—298, Academic Press, London and New York. — (1970a). «A new algorithm for unconstrained optimization», in Nonlinear Pro- gramming (J. B. Rosen, 0. L. Mangasarian and K. Ritter, eds.), pp. 31—65, Academic Press, London and New York. — (1970b). «A hybrid method for nonlinear equations», in Numerical Methods for Nonlinear Algebraic Equations (P. Rabinowitz, ed.), pp. 87—114, Gordon and Breach, London. — (1971). On the convergence of the variable metric algorithm, J. Inst. Maths. Applies 7, pp. 21—36. — (1972). «Problems relating to unconstrained optimization», in Numerical Methods for Unconstrained Optimization (W. Murray, ed.), pp. 29—55, Academic Press, London and New York. — (1974). «Introduction to constrained optimization», in Numerical Methods for Constrained Optimization (P. E. Gill and W. Murray, eds.), pp. 1—28, Acade- mic Press, London and New York. — (1975). «Convergence properties of a class of minimization algorithms», in Non- linear Programming 2 (0. L. Mangasarian, R. R. Meyer and S. M. Robinson, eds.), pp. 1—27, Academic Press, London and New York. — (1976a). «A view of unconstrained optimization», in Optimization In Action (L. C. W. Dixon, ed.), pp. 117—152, Academic Press, London and New York. — (1976b). Some convergence properties of the conjugate-gradient method. Math. Prog. 11, pp. 42—49. — (1976с). «Some global convergence properties of a variable metric algorithm with- out exact line searches», in SIAM—AMS Proceedings, Volume IX, Mathematical Programming(R. C. CottleandC. E. Lemke, eds.), pp. 53—72, American Mathe- matical Society, Providence, Rhode Island. — (1977a). Restart procedures for the conjugate-gradient method. Math. Prog. 12. pp. 241—254. — (1977b). A fast algorithm for nonlinearly constrained optimization calculations, Report DAMTP 77/NA 2, University of Cambridge, England. — (1977с). «Numerical methods for fitting functions of two variables», in The State of the Art in Numerical Analysis (D. Jacobs, ed.), pp. 563—604, Academic Press, London and New York. — (1978). «The convergence of variable metric methods for nonlinearly constrained optimization calculations», in Monlinear Programming 3 (0. L. Mangasarian, R. R. Meyer and S. M. Robinson, eds.), pp. 27—63, Academic Press, London and New York.
496 Библиография
— (1980). «An upper triangular matrix method for quadratic programming», pre- sented at the symposium: Nonlinear Programming 4, Madison, Wisconsin, July 1980. — (1981). A note on quasi-Newton formulae for sparse second derivative matrices, Math. Prog. 20, pp. 144—151. Пауэлл и Тойнт Powell M. J. D. and Toint P. L. (1979). On the estimation of sparse Hessian matrices, SIAM J. Numer. Anal. 16, pp. 1060—1074. Перолд Perold A. F. (1981a). «Exploiting degeneracy in the simplex method», in Large-Scale Linear Programming (Volume 1) (G. B. Dantzig, M. A. H. Dempster and M. J. Kallio, eds.), pp. 55—66, IIASA Collaborative Proceedings Series, CP-81- 51, IIASA, Laxenburg, Austria. — (1981b). «A degeneracy-exploiting LU factorization for the simplex method», in Large-Scale Linear Programming (Volume 1) (G. В. Dantzig, M. A. H. Demp- ster and M. J. Kallio, eds.), pp. 67—96, IIASA Collaborative Proceedings Series, CP-81-51, IIASA, Laxenburg, Austria. Перри Perry A. (1977). A class of conjugate-gradient algorithms with a two-step variable- metric memory, Discussion Paper 269, Center for Mathematical Studies in Eco- nomics and Management Science, Northwestern University. Петере и Уилкинсон Peters G. and Wilkinson J. H. (1970). The least-squares problem and pseudo-inverses, Computer Journal 13, pp. 309—316. Петерсон Peterson E. L. (1976). Geometric programming, SIAM Review 18, pp. 1—51. Петшиковский Pietrzykowski Т. (1962). «Application of the steepest-ascent method to concave programming», in Proceedings of the IFIPS Congress, Munich, 1962, pp. 185— 189, North-Holland, Amsterdam. — (1969). An exact potential method for constrained maxima, SIAM J. Numer. Anal. 6, pp. 299—304. Полиа Polya G. (1913). Sur un algorithme toujours convergent pour obtenir les polynomes de meilleure approximation de Tchebycheff pour une fonction continue quel- conque, Comptes Rendus Hebdomadaires, Sceances de 1'Academie des Sciences, Paris. Пэйг Paige C. C. (1980). Error analysis of some techniques for updating orthogonal decom- positions, Mathematics of Computation 34, pp. 465—471. Райан Ryan D. M. (1971). Transformation Methods in Nonlinear Programming, Ph. D. The- sis, Australian National University. • — (1974). «Penalty and barrier functions», in Numerical Methods for Constrained Op- timization (P. E. Gill and W. Murray, eds.), pp. 175—190, Academic Press, London and New York. Райд Reid J. K. (1975), A sparsity-exploiting variant of the Bartels—Golub decomposi- tion for linear programming bases. Report CSS 20, Atomic Energy Research Establishment, Harwell, England. — (1976). Fortran subroutines for handling sparse linear programming bases, Re- port R8269, Atomic Energy Research Establishment, Harwell, England.
Библиография 497
Райт Wright M. H. (1976). Numerical Methods for Nonlinearly Constrained Optimization, Ph. D. Thesis, Stanford University, California. Робинсон Robinson S. M. (1972). A quadratically convergent algorithm for general nonlinear programming problems, Math. Prog. 3, pp. 145—156. — (1974). Perturbed Kuhn—Tucker point and rates of convergence for a class of nonlinear programming algorithms. Math. Prog. 7, pp. 1—16. Розен Rosen J. В. (1960). The gradient projection method for nonlinear programming, Part I—linear constraints, SIAM J. Appl. Math. 8, pp. 181—217. — (1961). The gradient projection method for nonlinear programming, Part II— nonlinear constraints, SIAM J. Appl. Math. 9, pp. 514—532. — (1978). «Two-phase algorithm for nonlinear constraint problem», in Nonlinear Programming 3 (0. L. Mangasarian, R.R.Meyer and S.M.Robinson, eds.), pp. 97—124, Academic Press, London and New York. Розен и Кройзер Rosen J. В. and Kreuser J. (1972). «A gradient projection algorithm for nonlinear constraints», in Numerical Methods for Non-Linear Optimization (F, A. Loots- ma, ed.), pp. 297—300, Academic Press, London and New York. Розенброк Rosenbrock H. H. (1960). An automatic method for finding the greatest or leass va- lue of a function, Computer Journal 3, pp. 175—184. Рокафеллар Rockafellar R. Т. (1970). Convex Analysis, Princeton University Press, Princeton New Jersey. (Имеется перевод: Р. Рокафеллар. Выпуклый анализ,—M., Мир, 1973.) — (1973а). A dual approach to solving nonlinear programming problems by uncon- strained optimization. Math. Prog. 5, pp. 354—373. — (1973b). The multiplier method of Hestenes and Powell applied to convex pro- gramming, J. Opt. Th. Applies. 12, pp. 555—562. — (1974). Augmented Lagrange multiplier functions and duality in nonconvex pro- gramming, SIAM J. Control and Optimization 12, pp. 268—285,
Руководство-справочник по ФОРТРАН-библиотеке NAG Fortran Library Reference Manual (Mark 8) (1981). Numerical Algorithms Group Limited, Oxford, England. Руководство-справочник по оптимизационному математическому обеспечению Numerical Optimization Software Library Reference Manual (1978). Division of Numerical Analysis and Computing, National Physical Laboratory, England. Pyxe Ruhe A. (1979). Accelerated Gauss—Newton algorithms for nonlinear least-squares problems, Nordisk Tidskr. Informations behandling (BIT)- 19, pp. 356—367. Pyxe и Ведин Ruhe A. and Wedin P. A. (1980). Algorithms for separable nonlinear least-squares problems, SIAM Review 22, pp. 318—337. Рэмзин и Ведин Ramsin H. and Wedin P. A. (1977). A comparison of some algorithms for the nonli- near least-squares problem, Nordisk Tidskr. Informationsbehandling (BIT) 17, pp. 72—90. Sargent R. W. (1974). «Reduced-gradient and projection methods for nonlinear pro- gramming», in Numerical Methods for Constrained Optimization (P. E. Gill and W, Murray, eds.), pp. 149—174, Academic Press, London and New York.
498 Библиография
Сарджент и Гаминибандара Sargent R. W. and Garainibandara К. (1976). «Optimal design of plate distillation columns», in Optimization In Action (L. C. W. Dixon, ed.), pp. 267—314, Academic Press, London and New York. Сарджент и Муртаф Sargent R. W. and Murtagh B. A. (1973). Projection methods for nonlinear pro- gramming, Math. Prog. 4, pp. 245—268. Свэн Swann W. H. (1972). «Direct search methods», in Numerical Methods for Unconstra- ined Optimization (W. Murray, ed.), pp. 13—28, Academic Press, London and New York. — (1974). «Constrained optimization by direct search», in Numerical Methods for Constrained Optimization (P. E. Gill and W. Murray, eds.), pp. 191—217, Academic Press, London and New York. Сиссер Sisser F. S. (1981). Elimination of bounds in optimization problems by transforming variables, Math. Prog. 20, pp. 110—121. Смит, Бойл, Гарбоу, Икебе, Клема и Молер Smith В. Т., Boyle J. M., Garbow В. S., Ikebe Y., Klema V. С. and Moler С. В. (1974). Matrix Eigensystem Rountines—EISPACK Guide, Lecture Notes in Computer Science 6, Springer-Verlag, Berlin, Heidelberg and New York. Сондерс Saunders M. A. (1976). «A fast, stable implementation of the simplex method using Bartels—Golub updating», in Sparse Matrix Computations (J, R. Bunch and D. J. Rose, eds.), pp. 213—226, Academic Press, New York. — (1980). Private communication. Соренсен Sorensen D. (1980a). Newton's method with a model trust region modification, Re- port ANL-80-106, Argonne National Laboratory, Argonne, Illinois. — (1980b). The Q-superlinear convergence of a collinear scaling algorithm for un- constrained minimization, SIAM J. Numer. Anal.. 17, pp. 84—114. Спедикато Spedicato E. (1975). «On condition numbers of matrices in rank two minimization algorithms», in Towards Global Optimization (L. C. W. Dixon and G. P. Szego, eds.), pp. 196—210, North-Holland, Amsterdam. Спендли, Хекст и Химсворт Spendley W., Hext G. R. and Himsworth F. R. (1962). Sequential application of simplex designs in optimization and evolutionary design, Technomoetrics 4, pp. 441—461. Стиплмен и Винарски Stepleman R. S. and Winarsky N. D. (1979). Adaptive numerical differentiation, Mathematics of Computation 33, pp. 1257—1264. Стоер Stoer J. (1971). On the numerical solution of constrained least-squares problems SIAM J. Numer. Anal. 8, pp. 382—411. — (1975). On the convergence rate of imperfect minimization algorithms in Broy- den's p-class, Math. Prog. 9, pp. 313—385. — (1977). On the relation between quadratic termination and convergence properties of minimization algorithms, Part I, theory. Num. Math. 28, pp. 343—366.
Стренг Strang G. (1976). Linear Algebra and its Applications, Academic Press, London and New York. (Имеется перевод: Г. Стренг. Линейная алгебра и ее применения.— M.: Мир, 1980.)
Библиография 499
Стюарт Stewart G. W. (1967). A modification of Davidon's method to accept difference ap- proximations of derivatives, J. ACM 14, pp. 72—83. — (1973). Introduction to Matrix Computations, Academic Press, London and New York. Съярле, Шульц и Варга Ciarlet P. G., Schultz M. H. and Varga R. S. (1967). Nonlinear boundary value problems I, Num. Math. 9, pp. 394—430. Tana Thapa M. N. (1979). A note on sparse quasi-Newton methods, Report SOL 79-13, Department of Operations Research, Stanford University, California. — (1980). Optimization of Unconstrained Functions with Sparse Hessian Matrices, Ph. D. Thesis, Stanford University, California. Тапиа Tapia R. A. (1974a). Newton's method for problems with equality constraints, SIAM J. Numer. Anal. 11, pp. 174—196. — (1974b). Newton's method for optimization problems with equality constraints, SIAM J. Numer. Anal. 11, pp. 874—886. — (1977). Diagonalized multiplier methods and quasi-Newton methods for constra- ined optimization, J. Opt. Th. Applies. 22, pp. 135—194. — (1978). «Quasi-Newton methods for equality constrained optimization: equiva- lence of existing methods and a new implementation», in Nonlinear Programm- ing 3 (0. L. Mangasarian, R. R. Meyer and S. M. Robinson, eds.), pp. 125— 164, Academic Press, London and New York. Тарьян Tarjan R, (1972). Depth-first search and linear graph algorithms, SIAM J. Comput. 1, pp. 146—160. Тойнт Toint P. L. (1977). On sparse and symmetric matrix updating subject to a linear equation. Mathematics of Computation 31, pp. 954—961. — (1978). Some numerical results using a sparse matrix updating formula in uncon- strained optimization. Mathematics of Computation 32, pp. 839—851. — (1979). On the superlinear convergence of an algorithm for solving a sparse mini- mization problem, SIAM J. Numer. Anal. 16, pp. 1036—1045. Томлин Tomlin J. A. (1975a). An accuracy test for updating triangular factors, Math. Prog. Study 4, pp. 142—145. — (1975b). On scaling linear programming problems, Math. Prog. Study 4, pp. 146— 166. — (1976). Robust implementation of Lemke's method for the linear complementa- rity problem, Report SOL 76-24, Department of Operations Research, Stanford University. Топкие и Вайнот Topkis D. M. and Veinott A. F., Jr. (1967). On the convergence of some feasible di- rection algorithms for nonlinear programming, SIAM J. Control 5, pp. 268— 279. Уяйлл Wilde D. J. (1978). Globally Optimal Design, John Wiley and Sons, New York and Toronto. Уилкинсон Wilkinson J. H. (1963). Rounding Errors in Algebraic Processes, Notes on Applied Sciences 32, Her Majesty's Stationery Office, London; Prentice-Hall, Inc. [also publisned by Englewood Cliffs, New Jersey]. — (1955). The Algebraic Eigenvalue Problem. Oxford University Press.
500 Библиография
Уилкинсон и Райнх Wilkinson J. H. and Reinsch С. (1971). Handbook for Automatic Computation, Vol. II, Springer-Verlag, Berlin, Heidelberg and New York. Уилсон Wilson R. B. (1963). A Simplicial Algorithm for Concave Programming, Ph. D. The- sis, Harvard University. Уотсон Watson G. A. (1979). The minimax solution of an overdetermined system of nonli- near equations, J. Inst. Maths. Applies. 23, pp. 167—180. Фалкерсон и Вулф Fulkerson D. R. and Wolfe P, (1962). An algorithm for scaling matrices, SIAM Review 4, pp. 142—146. Фиакко Fiacco A. V. (1976). Sensitivity analysis for mathematical programming using pe- nalty functions, Math. Prog. 10, pp. 287—311. Фиакко и Мак-Кормик Fiacco A.V. and McCormick G. P. (1968). Nonlinear Programming: Sequential Unconstrained Minimization Techniques, John Wiley and Sons, New York and Toronto. (Имеется перевод: А. Фиакко, Г. П. Мак-Кормик. Нелинейное программирование. Методы последовательной безусловной минимизации.— М.: Мир, 1972.) Флетчер Fletcher R. (1968), Generalized inverse methods for the best least-squares solution of systems of nonlinear equations, Computer Journal 10, pp. 392—399. — (1970a). A new approach to variable metric algorithms, Computer Journal 13, pp. 317—322. — (1970b). «A class of methods for nonlinear programming with termination and convergence properties», in Integer and Nonlinear Programming (J. Abadie, ed.), pp. 157—175, North-Holland, Amsterdam. — (1971a). A modified Marquardt subroutine for nonlinear least squares, Report R6799, Atomic Energy Research Establishment, England. — (1971b). A general quadratic programming algorithm, J. Inst. Maths. Applies. 7, pp. 76—91. — (1972a). An algorithm for solving linearly constrained optimization problems, Math. Prog. 2, pp. 133—165. — (1972b). «Minimizing general functions subject to linear constraints», in Numeri- cal Methods for Non-Linear Optimization (F. A. Lootsma, ed.), pp. 279—296, Academic Press, London and New York. —(1972с). Methods for the solution of optimization problems, Comput. Phys. Comm. 3, pp. 159—172. — (1973). An exact penalty function for nonlinear programming with inequalities, Math. Prog. 5, pp. 129—150. — (1974). «Methods related to Lagrangian functions», in Numerical Methods for Constrained Optimization (P. E. Gill andW. Murray, eds.), pp. 219—240, Aca- demic Press, London and New York. — (1976). Factorizing symmetric indefinite matrices, Linear Algebra and its App- lies. 14, pp. 257—272. — (1977). «Methods for solving nonlinearly constrained optimization problems», in The State of the Art in Numerical Analysis (D. Jacobs, ed.), pp. 365—448, Academic Press, London and New York. — (1980). Practical Methods of Optimization, Volume 1, Unconstrained Optimiza- tion, John Wiley and Sons, New York and Toronto. Флетчер и Джексон Fletcher R. and Jackson M. P. (1974). Minimization of a quadratic function of many variables subject only to upper and lower bounds, J, Inst. Maths. Applies. 14, pp. 159—174.
Библиография 501
Флетчер и Лилл Fletcher R. and Lill S. A. (1970). «A class of methods for non-linear programming: II. computational experience», in Nonlinear Programming (J. B. Rosen, 0. L. Mangasarian and K. Ritter, eds.), pp. 67—92, Academic Press, London and New York. Флетчер и Мак-Канн Fletcher R. and McCann A. P. (1969). Acceleration techniques for nonlinear program- ming, in Optimization (R. Fletcher, ed.), pp. 37—49, Academic Press, London and New York. Флетчер и Ривс Fletcher R. and Reeves C. M. (1964). Function minimization by conjugate gradients, Computer Journal 7, pp. 149—154. Флетчер и Пауэлл Fletcher R. and Powell M. J. D. (1963). A rapidly convergent descent method for minimization, Computer Journal 6, pp. 163—168. — _ (1974). On the modification of LDL,' factorizations, Mathematics of Compu- tation 28, pp. 1067—1087. Флетчер и Фримен Fletcher R. and Freeman T. L. (1977). A modified Newton method for minimiza- tion, J. Opt. Th. Applies. 23, pp. 357—372. Форрест и Томлин Forrest J. J. H. and Tomlin J. A. (1972). Updating triangular factors of the basis to maintain sparsity in the product form simplex method, Math. Prog. 2, pp. 263-278. Форсайт и Молер Forsythe G. E. and Moler C. B. (1967). Computer Solution of Linear Algebraic Systems, Prentice-Hall, Inc., Englewood Cliffs, New Jersey. Фоурер Fourer R. (1979). Sparse Gaussian elimination of staircase linear systems, Report SOL 79-17, Department of Operations Research, Stanford University, Califor- nia. Фриш Frisch K. R. (1955). The logarithmic potential method of convex programming, Memorandum of May 13, 1955, University Institute of Economics, Oslo, Nor- way. Хаархофф и Байс Haarhoff P. С. and Buys J. D. (1970). A new method for the optimization of a non- linear function subject to nonlinear constraints. Computer Journal 13, pp. 178— 184. Хайес Hayes J. G. (1970). Numerical Approximation to Functions and Data, Academic Press, London and New York. Хан Han S.-P. (1976). Superlinearly convergent variable metric algorithms for general nonlinear programming problems, Math. Prog. 11, pp. 263—282. — (1977a). Dual variable metric algorithms for constrained optimization, SIAM J. Control and Optimization 15, pp. 546—565. — (1977b). A globally convergent method for nonlinear programming, J. Opt. Th. Applies. 22, pp. 297—310. — (1978a). Superlinear convergence of a minimax method, Computer Science De- partment, Cornell University, Ithaca, New York.
502 Библиография
— (1978b). On the validity of a nonlinear programming method for solving mini- max problems. Report 1891, Mathematics Research Center, University of Wis- consin, Madison, Wisconsin. Хан и Мангасарьян Han S.-P. and Mangasarian 0. L. (1979). Exact penalty function in nonlinear pro- gramming, Math. Prog. 17, pp. 251—269. Харрис Harris P. M. J. (1973). Pivot selection methods of the Devex LP code. Math. Prog. 5, pp. 1—28. [Reprinted in Math. Prog. Study 4 (1975), pp. 30—57.] Хартли Hartley Н. О. (1961). Nonlinear programming by the simplex method, Economet- rica 29, pp. 223—237. Хачиян Л. Г. (1979). Полиномиальный алгоритм в линейном программирова- нии.—Докл. АН СССР, 1979, т. 244, с. 1093—1096. Хебден ; Hebden M. D. (1973). An algorithm for minimization using exact second deriva- tives, Report TP515, Atomic Energy Research Establishment, Harwell, Eng- land. Хеллерман и Рарик Hellerman E. and Rarick D. (1971). Reinversion with the preassigned pivot pro- cedure, Math. Prog. 1, pp. 195—216. — — (1972). «The patitioned preassigned pivot procedure (P4)», in Sparse Matrices and their Applications (D. J. Rose and R. A. Willoughby, eds.), pp. 67—76, Plenum Press, New York. Хестенс Hestenes M. R. (1946). Sufficient conditions for the isoperimetric problem of Bolza in the calculus of variations, Trans. Amer. Math. Soc. 60, pp. 93—118. — (1947). An alternative sufficiency proof for the normal problem of Bolza, Trans. Amer. Math. Soc. 61, pp. 256—264. — (1969). Multiplier and gradient methods, J. Opt. Th. Applies. 4, pp. 303—320. — (1979). «Historical overview of generalized Lagrangians and augmentability», presented at the HASA Task Force Meeting on «Generalized Lagrangians in Systems and Economic Theory», IIASA, Laxenburg, Austria (proceedings to be published in 1981). — (1980a). Conjugate-Direction Methods in Optimization, Springer-Verlag, Berlin, Heidelberg and New York. — (1980b). Augmentability in optimization theory, J. Opt. Th. Applies. 32, pp. 427— 440. Хестенс и Штифель Hestenes M. R. and Stiefel E. (1952). Methods of conjugate gradients for solving linear systems, J. Res. Nat. Bur. Standards 49, pp. 409—436. Хит Heath M. Т. (1978). Numerical Algorithms for Nonlinearly Constrained Optimiza- tion, Ph. D. Thesis, Stanford University, California. Хоув Howe S. (1973). New conditions for exactness of asimple penalty function, SIAM J. Control 11, pp. 378—381. Хэмминг Hamming R. W. (1962). Numerical Methods for Scientists and Engineers, McGraw- Hill Book Co., New York. — (1971). Introduction to Applied Numerical Analysis, McGraw-Hill Book Co., New York.
Библиография 503
— (1973). Numerical Methods for Scientists and Engineers (2nd Edition), McGraw- Hill Book Co., New York. Чарнес Charnes A. (1952). Optimality and degeneracy in linear programming, Econometrica 20, pp. 160—170. Чернее, Купер н Фергюсон Charnes A., Cooper W. W. and Ferguson R. (1955). Optimal estimation of executive compensation by linear programming, Management Science 2, pp. 138—151. Чемберлен Chamberlain R. M. (1979). Some examples of cycling in variable metric methods for constrained minimization, Math. Prog. 16, pp. 378—383. Чемберлен, Лемарешаль, Педерсон и Пауэлл Chamberlain P.M., Lemarechal С., Pederson Н. С. and Powell M. J. D. (1980). The watchdog technique for forcing convergence in algorithms for constrained optimization, Report DAMTP 80/NA 1, University of Cambridge. Шанно Shanno D. F. (1970). Conditioning of quasi-Newton methods for function minimiza- tion, Mathematics of Computation 24, pp. 647—657. — (1978). Conjugate-gradient methods with inexact searches, Math. of Oper. Res. 3, pp. 244—256. — (1980). On variable metric methods for sparse Hessians, Mathematics of Compu- tation 34, pp. 499—514. Шанно и Фуа Shanno D. F. and Phua К. Н. (1976). Algorithm 500—Minimization of unconstra- ined multivariate functions, ACM Trans. Math. Software 2, pp. 87—94. Шиттковски Schittkowski К. (1980). Nonlinear Programming Codes, Springer-Verlag Lecture Notes in Economics and Mathematical Systems, Volume 183, Berlin, Heidel- berg and New York. Шиттковски и Стоер Schittkowski К. and Stoer J. (1979). A factorization method for the solution of con- strained linear least-squares problems allowing data changes, Num. Math. 31, pp. 431—463. Шор Н. 3. (1970). О скорости сходимости метода обобщенного градиентного спуска с растяжением пространства.—Кибернетика, 1970, № 2, с. 80—85. Шор Н. 3. (1977). Метод отсечения с растяжением пространства для решения задач выпуклого программирования.— Кибернетика, 1977, № 1, с. 94—95. Шор Н. 3., Гершович В. И. (1979). Об одном семействе алгоритмов для решения задач выпуклого программирования.— Кибернетика, 1979, № 4, с. 62—67. Штифель Stiefel E. (1960). Note on Jordan elimination, linear programming and Tscheby- scheff approximation. Num.—Math. 2, pp. 1—17. Шуберт Schubert L. К. (1970). Modification of a quasi-Newton method for nonlinear equa- tions with a sparse Jacobian, Mathematics of Computation 24, pp. 27—30. Эблоу и Брайхем Ablow С. M. and Brigham G. (1955). An analog solution of programming problems, Operations Research 3, pp. 388—394. Эванс, Гулд и Толле Evans J. P., Gould F. J. and Tolle J. W. (1973). Exact penalty functions in non- linear programming. Math. Prog. 4, pp. 72—97.
504 Библиография
Эккер Ecker J. G. (1980). Geometric programming: methods, computations and applica- tions, SIAM Review 22, pp. 338—362.
Эль-Аттар, Видьясагар и Дутта El-Attar R. A., Vidyasagar M. and Dutta S. R. K. (1979). An algorithm for /i-norm minimization with application to nonlinear /i approximation, SIAM J. Numer Anal. 16, pp. 70—86.
Эскудеро Escudero L. (1980). A projected Lagrangian method for nonlinear programming Report G320-3401, IBM Palo Alto Scientific Center.
Эспвол и Стоун Aspvall В. and Stone R. E. (1980). Khachiyan's linear programming algorithm, Journal of Algorithms 1, 1—13.
Яррат и Наде Jarratt P. and Nudds D. (1965). The use of rational functions in the iterative solu- tion of equations on a computer. Computer Journal 9, pp. 62—65,