Д. Химмельблау APPLIED NONLINEAR PROGRAMMING David M. Himmelblau ПРИКЛАДНОЕ НЕЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ The University of Texas, Austin, Texas Перевод с английского И. M. БЫХОВСКОЙ и Б. Т. ВАВИЛОВА Под редакцией M, Л. БЫХОВСКОГО McGraw-HilI Book Company 1972 ИЗДАТЕЛЬСТВО «МИР» МОСКВА 1975 УДК 51.380.115 Книга посвящена методам оптимального управления системами с нелинейными целевыми функциями. Описаны методы нелинейного программирования как при отсутствии ограничений на управляю- щие переменные, так и при наличии ограничений. Рассматриваются такие вопросы, как возможность получения решения, время оптими- зации, точность решения и т. д. Для наиболее важных методов при- водятся программы решения на языке ФОРТРАН. Каждая глава содержит много примеров, не 'юлько поясняющих теорию, но и иллю- стрирующих необходимые вычислительные процедуры и используе- мые программы. Книга представляет интерес для специалистов по автоматическо- му управлению; вычислительной технике и прикладной математике. Редакция литературы по новой технике (С) Перевод на русский язык, «Мир», 1974 _ 3314-429 U41 (01)-75 148-74 СОДЕРЖАНИЕ Предисловие ............................ 5 Часть I. Предварительные сведения Глава 1. Введение .......................... 8 Глава 2. Задача нелинейного программирования и ее оптимальное решение 14 2.1. Задача линейного программирования ............ 14 2.2. Общая задача нелинейного программирования ....... 18 2.3. Связь задачи нелинейного программирования с реальным процессом .......................... 22 2.4. Обозначения и терминология ................ 30 2.5. Необходимые и достаточные условия оптимальности решения 39 2.6. Эффективные методы одномерного поиска .......... 50 2.7. Классификация методов нелинейного программирования ... 58 Литература .......................... 69 Часть II. Методы нелинейного программирования без ограничений Глава 3. Методы минимизации без ограничений, использующие производные ................................ 72 3.1. Градиентные методы ................... 72 3.2. Метод вторых производных (метод Ньютона) и связанные с ним алгоритмы ........................ 83 3.3. Сопряженность и сопряженные направления ......... 98 3.4. Методы переменной метрики ................ 117 3.5. Краткий обзор алгоритмов программирования без ограничений 142 Литература .......................... 153 Глава 4. Методы минимизации без ограничений, не использующие производные (методы поиска) ......................... 156 4.1. Прямой поиск ...................... 157 4.2. Поиск по деформируемому многограннику ......... 163 4.3. Методы Розенброка и Дэвиса, Свенна, Кемпи ....-..._. 173 4.4. Метод Пауэлла ...................... 184 4.5. Методы случайного поиска ................. 193 Литература .......................... 207 Глава 5. Сравнение алгоритмов нелинейного, программирования при отсутствии ограничений .......................... 210 5.1. Критерии оценки ..................... 210 5.2. Тестовые задачи ...................... 214 5.3. Оценивание алгоритмов нелинейного программирования при отсутствии ограничений .................. 220 Литература .......................... 237 Часть III. Методы нелинейного программирования при наличии ограничений Глава 6. Процедуры минимизации при наличии ограничений; методы линейной аппроксимации ........................ 242 6.1. Аппроксимирующее линейное программирование ...... 246 6.2. Алгоритм нелинейного программирования .......... 266 6.3. Проективные методы ................... 269 6.4. Метод допустимых направлений (метод Заутендайка) ..... 300 6.5. Метод обобщенного приведенного градиента (МОПГ) ..... 303 Литература .......................... 329 Глава7. Процедуры минимизации при наличии ограничений: методы штрафных функций ............................ 333 7.1. Методы штрафных функций специальной структуры ..... 337 7.2. Метод последовательной безусловной минимизации (комбинированный метод штрафных функций) ............. 345 Литература .......................... 378 Глава 8. Процедуры минимизации при наличии ограничений: метод скользящего допуска ........................... 381 8.1. Определение Ф, Т (х) и почти допустимых точек ....... 382 8.2. Стратегия алгоритма скользящего допуска ......... 385 8.3. Процедура отыскания допустимых и почти допустимых точек 392 8.4. Начало и окончание поиска ................ 400 8.5. Методы решения задач нелинейного программирования с зо- нальной неопределенностью ................ 407 Литература ......................... 410 Глава 9. Оценка эффективности методов нелинейного программирования при наличии ограничений ...................... 411 9.1. Критерии, используемые при оценке эффективности алгоритмов нелинейного программирования .......... 411 9.2. Сравнение некоторых алгоритмов нелинейного программирования при наличии ограничений: двумерные задачи ...... 416 9.3. Сравнение некоторых алгоритмов оптимизации при наличии ограничений в случае более сложных задач ........ 424 Литература .......................... 443 Приложение А. Задачи нелинейного программирования и их решения . . . 444 Приложение Б. Программы на языке ФОРТРАН, непоставляемые коммерчески ................................ 480 Приложение В. Матрицы ....................... 516 Приложение Г. Стандартная таймер-программа ............. 523 Приложение Д. Обозначения ..................... 525 ПРЕДИСЛОВИЕ Цель этой книги состоит в том, чтобы в доступной форме изложить некото- рые из наиболее эффективных методов нелинейного программирования и дать сравнительную оценку этих методов Для решения общей задачи нелинейного про- граммирования было предложено довольно много алгоритмов, однако лишь не- многие из них оказались эффективными для задач большой размерности. Ни один из этих алгоритмов не имеет по отношению к другим таких преимуществ, чтобы его можно было считать универсальным средством решения любых задач не- линейного программирования, В данной книге описанию используемых методов уделяется больше внима- ния, чем математическим доказательствам сходимости алгоритмов нелинейного программирования для определенных типов задач. Такие доказательства, разу- меется, важны; однако они применимы только к весьма узким категориям задач и*могут служить лишь как дополнительная информация для исследователя, при- меняющего тот или иной алгоритм. В отличие от линейного программирования при решении задачи нелинейного программирования выбранный алгоритм может оказаться эффективным, даже если не удается доказать его сходимость. Справед- ливо и обратное утверждение, а именно: наличие доказательства сходимости алго- ритма в частных случаях может не означать, что он окажется удовлетвопитель- ным для более сложных задач. В книге подробно описаны те алгоритмы нелинейного программирования, которые оказались достаточно эффективными на практике. При сравнении алго- ритмов были использованы следующие критерии: 1) надежность; 2) скорость решения; 3) время подготовки задачи для решения; 4) точность решения; 5) степень выполнения ограничивающих условий. Рассматриваемые методы предназначены для оптимизации значения некоторой нелинейной функции при ограничениях в виде равенств и (или) неравенств, содержащих функции большого числа переменных. Все эти переменные являются детерминированными (в отличие от случайных, или стохастических, переменных). Описанные методы могут быть практически реализованы лишь при помощи совре- менных цифровых или гибридных ЭВМ. Использование аналоговых вычислитель- ных машин не рассматривается. Не рассматриваются также ни целочисленное (или дискретное) программирование, ни методы поиска оптимального решения динами- ческих задач, т. е. задач, в которых время является одним из параметров. В этой книге мы не стремимся раскрыть отдельные тонкости методов оптими- зации, однако здесь приведены все необходимые подробности, позволяющие чи- тателю проследить существенные этапы каждого из рассматриваемых методов. Нередко оказывается, что детали программирования некоторого алгоритма, особенно в часто повторяемых процедурах, заметно влияют на качество работы ал- горитма в целом.-Подробно рассмотренные примеры в конце каждого раздела пояс- няют вычислительные аспекты алгоритмов; для иллюстрации логической струк- туры алгоритмов приведено большое количество блок-схем. Приложение Б содер- жит нееколько машинных программ для наиболее удачных алгоритмов. Благодаря Предисловие тому что для всех алгоритмов используются одни и те же обозначения, можно глуб- же понять их структурные связи друг с другом и общие свойства. Книга состоит из трех частей. Первая часть содержит две главы. Глава 1 пред- ставляет собой краткое введение; в гл. 2 формулируется общая задача нелинейного программирования, рассматривается связь нелинейного программирования с дру- гими видами математического программирования и, наконец, устанавливаются необходимые и достаточные условия существования оптимального решения. Во второй части рассматриваются алгоритмы нелинейного программирования при отсутствии ограничений. В гл. 3 описывается градиентный метод, метод вто- рых производных и другие связанные с ними стратегии, в которых используются производные. Глава 4 посвящена рассмотрению стратегий поиска. В гл. 5 дается оценка различных алгоритмов оптимизации при отсутствии ограничений. В третьей части описываются алгоритмы оптимизации при наличии ограни- чений. Глава 6 посвящена рассмотрению методов линеаризации. В гл. 7 изло- жены методы штрафных функций, а в гл. 8 описан метод скользящего допуска. Оценки алгоритмов оптимизации при наличии ограничений приводятся в гл. 9. Приложение А содержит ряд упражнений с соответствующими решениями. Кроме того, в каждой главе (за исключением первой) приводятся дополнительные задачи, предлагаемые читателю для решения. Для понимания описанных в книге алгоритмов необходимо знание основ ма- тематического анализа, некоторое умение обращаться с матрицами и векторами, а также знакомство с методами решения задач линейного программирования. В приложении В приводятся основные сведения из матричной алгебры. Для чтения машинных программ необходимо знание основ программирования на ФОРТРАНе. Однако эти программы снабжены необходимыми инструкциями, так что их можно использовать, владея лишь методикой перфорирования Такого рода «механиче- ский» подход к использованию программ иногда оказывается вполне приемлемым. однако при отсутствии должной осторожности он может привести к ошибкам. Д. М. Химмельблау Часть I ПРЕДВАРИТЕЛЬНЫЕ СВЕДЕНИЯ В первой части книги сформулирована задача нелинейного программирования, показана ее связь с реальными физическими задачами, а также приведена терминология, связанная с нелиней- ным программированием. Кроме того, здесь описаны методы, с по- мощью которых можно определить, действительно ли предполага- емое оптимальное решение является оптимальным, Глава 1 ВВЕДЕНИЕ На протяжении всей своей истории люди при необходимости принимать решения прибегали к сложным ритуалам. Они устраивали торжественные церемонии, приносили в жертву животных, гадали по звездам и следили за полетом птиц. Они полагались на народные приметы и старались следовать примитивным правилам, облегчаю- щим им трудную задачу принятия решений. В настоящее время для принятия решения используют новый и, по-видимому, более научный «ритуал», основанный на применении электронно-вычисли- тельной машины. Без современных технических средств человече- ский ум, вероятно, не может учесть многочисленные и разно- образные факторы, с которыми сталкиваются при управлении пред- приятием, конструировании ракеты или регулировании движения транспорта. Существующие в настоящее время многочисленные мате- матические методы оптимизации уже достаточно развиты, что по- зволяет эффективно использовать возможности цифровых, и гиб- ридных вычислительных машин. Одним из этих методов является математическое программирование, включающее в себя как частный случай нелинейное программирование. Термин «математическое программирование» предложен Робер- том Дорфманом приблизительно в 1950 г.; теперь он объединяет линейное программирование, целочисленное программирование, вы- пуклое программирование, нелинейное программирование и програм- мирование при наличии неопределенности. Нелинейное програм- мирование имеет дело с оптимизацией нелинейных функций при линейных и (или) нелинейных ограничениях. Типичными областями его применения являются прогнозирование, планирование промыш- ленного производства, управление товарными ресурсами, контроль качества выпускаемой продукции, планирование обслуживания и ремонта, проектирование технологических линий (процессов), учет и планирование капиталовложений. Пока еще не существует общего метода решения нелинейных задач оптимизации, такого, как, например, симплексный алгоритм, разработанный для задач линей- ного программирования. Нелинейное программирование при реше- нии задач включает в себя элементы экспериментирования. Его развитие до сих пор сводилось к предложениям частных алгоритмов, Введение программированию их, проверке результатов применения этих алгорит- мов в конкретных задачах, представляющих практический интерес, и построению лучших алгоритмов на основе приобретенного опыта. Последние двадцать лет в области математического програм- мирования значительные усилия были сконцентрированы на линей- ном программировании. Полученные результаты столь значительны, что достигнутый здесь уровень позволяет решать большинство практических задач. Что же касается нелинейного программи- рования, то, хотя здесь и было предложено большое число различных стратегий поиска решений, успешное применение нашли лишь не- многие алгоритмы. Область применения разработанных алгоритмов нелинейного программирования весьма ограничена. В связи с даль- нейшим развитием ЭВМ и растущей необходимостью более точно решать задачи, представляющие практический интерес, возникает необходимость в методах решения задач нелинейного программи- рования с более широкой областью применимости. Большинство практических задач имеет несколько (а некоторые, возможно, даже бесконечное число) решений. Целью оптимизации является нахождение наилучшего решения среди многих потенци- ально возможных в соответствии с некоторым критерием эффектив- ности или качества. Задача, допускающая лишь одно решение, не требует оптимизации. Оптимизация может быть осуществлена при помощи многих стратегий, начиная с весьма сложных анали- тических и численных математических процедур и кончая разумным применением простой арифметики. Предполагая, что подлежащая оптимизации задача некоторым образом определена (не обязательно математически), можно классифицировать общие методы оптими- зации следующим сбразом: 1. Аналитические методы, использующие классические методы дифференциального и вариационного исчислений. Эти методы заклю- чаются в определении экстремума функции / (х) путем нахождения тех значений х, которые обращают в нуль производные / (х) по х. В случае поиска экстремума f (х) при наличии ограничений приме- няются такие методы, как метод множителей Лагранжа и метод ограниченных вариаций. При использовании аналитических методов задача оптимизации должна быть сформулирована математически с тем, чтобы можно было обращаться со всеми фигурирующими в ней функциями и переменными при помощи известных правил. Для решения больших существенно нелинейных задач аналитические методы оказываются непригодными, и поэтому в данной книге они не рассматриваются. 2. Численные методы, использующие предшествующую инфор- мацию для построения улучшенных решений задачи при помощи итерационных процедур. Численные методы применяются для решения задач, которые не могут быть решены аналитически, и, поскольку практические задачи поддаются решению численными 10 Глава 1 методами, именно эти методы нелинейного программирования явля- ются предметом обсуждения в данной книге. К другим общим методам, которые эффективно применяются при решении задач оптимизации, но которые здесь не рассматрива- ются, относятся следующие: 3. Графические методы, основанные на графическом изображе- нии функции, подлежащей максимизации или минимизации, в зависимости от одной или нескольких переменных. Экстремум функции в этом случае получают непосредственно путем анализа ее графика. Преимущество графических методов состоит в том, что они просты и сразу показывают, существует решение или нет. С другой стороны, они применимы в тех случаях, когда критерий качества является функцией одной или максимум двух независи- мых переменных. 4. Экспериментальные методы. Экстремум функции можно иногда найти, экспериментируя непосредственно с реальными переменными вместо того, чтобы исследовать соответствующую мате- матическую модель. Результаты одного эксперимента используют- ся для планирования следующего эксперимента, позволяющего получить улучшенные результаты. 5. Методы исследования различных вариантов. Эти методы осно- ваны на анализе нескольких возможных решений одной и той же задачи с целью выбора наилучшего. Таким образом, «наилучшее» решение, полученное методом исследования различных вариантов, будет скорее всего лишь субоптимальным. При выборе наиболее подходящего способа описания реальных процессов приходится сталкиваться с рядом трудностей, которые для удобства обсуждения можно подразделить на две группы. Одна группа связана с построением математической модели про- цесса, а другая — с численными методами решения. В этой книге мы можем только отметить эти трудности и, где возможно, указать пути их устранения при описании того или иного конкретного ал- горитма. Математическая модель содержит функции, участвующие в про- цедуре оптимизации. Очевидно, для того чтобы искомый экстремум имел физический смысл, выбранная модель должна адекватно отра- жать существенные черты реального процесса. Но даже если это требование выполнено, при построении модели встречаются следу- ющие типичные затруднения: 1. Оптимизируемый критерий может быть нечувствительным к изменениям независимых (оптимизируемых) переменных и по- этому не удается определить четко выраженный экстремум. 2. Оптимизируемый критерий или некоторые из ограничений могут принимать в области поиска решения неограниченные зна- чения; значения частных производных в математической модели также могут стать неограниченными. Особенно подвержены этой опасности Введение 11 модели с полиномами в знаменателе. Так, например, значения функции у= ьo+l:'lx:^ ЬгЧ + ЬцХг и ее первой частной производной по х^ ду _ — &о&2 + &1&з^ дх! ~ ФЛ + Ь^ХУ обращаются в бесконечность при Ь^ = —Ь^. Эту трудность можно преодолеть, ограничив области допустимых значений неза- висимых переменных путем введения дополнительных ограничений в задачу, или же изменив формулировку самой математической модели. 3. Переменные могут быть плохо масштабированы. Трудности масштабирования могут возникнуть, например, когда один из членов в выражении для критерия имеет существенно иной порядок величины, чем другой. При этом критерий становится нечувстви- тельным к изменениям значений переменных в меньшем члене. Например, значение целевой функции </== 100^-0,010л:| будет мало зависеть от изменения х^, если только значение ^ вслед- ствие используемых физических единиц измерения не окажется много больше значения х^. Если х^ представляет собой величину того же порядка, что и х^, то либо одну переменную, либо обе пере- менные можно умножить на масштабные множители, в результате чего оба члена в правой части приведенного выше соотношения ока- жутся величинами одного и того же порядка. Положим, например, Xi = lOxi, ^=10-2^, ^= 10-\, xi= W~xi Тогда члены в выражении для целевой функции становятся вели- чинами одного порядка. После того как найден экстремум для •"2 ~2 У == Х\ — Х2, можно определить значения х^ и ^ п0 значениям A'i и х^. Конечно, не всегда удается так легко изменить масштаб функций в матема- тической модели, как это сделано в рассмотренном примере. 4. В плохо построенной математической модели переменные мо- гут оказаться взаимосвязанными. Взаимное влияние переменных можно проиллюстрировать на примере очень простого критерия, в который входит произведение двух параметров: у = 2зд + 10. 12 Глава I Здесь каждая из переменных л-i и ^а может принимать различные значения при заданном значении произведения х^. В том случае, когда имеет место взаимное влияние переменных, осуществлять масштабирование гораздо сложнее. Для исключения членов, со- держащих произведение двух переменных, квадратичные формы можно привести к каноническому виду. При этом определяются новые координатные оси, называемые главными осями, относитель- но которых данная поверхность второго порядка симметрична. На- пример, поверхность у == 7х1 4- 6х1 + 5л:! — 4х^ — 4х^Хз — бд-i — 24х.г + \8ху + 18 путем смещения начала координат и поворота координатных осей может быть приведена к виду у— 18 =3^+6^+9^1. В новой системе координат масштабирование каждого члена зна- чительно проще, чем в исходной системе. Нелинейные функции можно сделать квадратичными при помощи подходящего преобра- зования модели или разложения соответствующих функций в ряд Тейлора с сохранением конечного числа членов. Более тонким примером, в котором взаимное влияние переменных оказывается также весьма ощутимым, является следующий: у = х^л. 5. В математической модели может оказаться, что некоторые из переменных исключаются путем их надлежащего преобразова- ния. Пусть, например, у = х] + 2ад + xl + 2 = (л:1 + х^ + 2. После преобразования х^ + х; == х-, получим г/=л'?+2. . Таким образом, вместо двух переменных в выражении для у оста- лась только одна переменная х^, которую и следует варьировать, чтобы найти экстремум у. Вторая группа трудностей связана с численными методами решения задачи оптимизации: ^ 1. Как выбрать подходящие начальные значения независимых переменных? Поскольку задача содержит нелинейные функции, то в отличие от анализа линейных систем при этом возможно суще- ствование нескольких экстремумов. Следовательно, если начальные значения переменных находятся слишком далеко от искомого экс- тремума, оптимизация может закончиться не в точке глобального экстремума, а в некоторой точке, соответствующей локальному экстремуму. Часто приблизительно оптимальные значения незави- Введение 13 симых переменных можно получить на основе ранее проведенных исследований или исходя из физичюких соображений. В крайнем случае можно выбрать несколько начальных векторов из допустимой области и проверить, дают ли они одно и то же значение критерия в точке экстремума. Но при таком подходе имеются свои трудности; о них уже упоминалось в связи с обсуждением проблемы построения адекватной модели. 2. Как учесть стохастическую (случайную) природу физических переменных? Реальная возможность того, что коэффициенты и пере- менные в математической модели могут быть случайными величи- нами, в этой книге не рассматривается. 3. Как уменьшить ошибки вычислительной процедуры? Пог- решности, возникающие при учете лишь конечного числа членов при разложении функций в ряды, снижают эффективность многих алгоритмов. Устойчивость решения зависит от того, сходится ли в пределе решение «аппроксимирующей» задачи нелинейного про- граммирования к решению исходной задачи. Могут возникнуть так- же неприятности из-за ошибок округления в процессе оптимиза- ции, особенно при аппроксимации производных разностными выра- жениями. Как и любой математический аппарат, методы нелинейного программирования нельзя слепо применять для решения той или иной задачи без тщательного предварительного анализа. Практи- ческое применение методов нелинейного программирования требует от исследователя определенного искусства. При этом совершенно необходимо корректное построение модели и применение подхо- дящих численных процедур. Книга состоит из трех частей. Первая часть посвящена пробле- ме нелинейного программирования. Во второй части дается описа- ние различных методов нелинейного программирования при от- сутствии ограничений и проводится их сравнение. Наконец, в тре- тьей части рассматриваются рабочие алгоритмы для нелинейно- го программирования при наличии ограничений и проводится их сравнительная оценка. В приложениях содержатся упражнения (вместе с решениями), а также неопубликованные до сих пор ма- шинные программы алгоритмов нелинейного программирования, УВАЖАЕМЫЙ ЧИТАТЕЛЬ! Ваши замечания о содержании книги, ее оформлении, качестве перевода и другие просим присылать по адресу: 129820, Москва, И-110, ГСП, 1-й Рижский пер., 2, издательство «Мир».- ЛИТЕРАТУРА 1. Dantzig G. В., Linear Programming and Extension, Princeton Univ. Press, Prin- ceton, N. J., 1963. 2. Wilde D. J., Beightler C. S., Foundations of Optimization, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1967. 3. Ponste\nJ.,J.S!AM Rev.,9, 115(1967). 4. Kuhn W. W., Tucker A. W., Nonlinear Programming, Proc. 2nd Berkeley Symp. on Mathematical Statistics and Programming, Univ. of California Press, Berkeley, 1951, pp. 481—493. 5. Fiacco A. V., McCormick G. P., Nonlinear Programming, Wiley, Inc., N. Y., 1968. 6. McCormick Q. P., SIAM J. Appl. Math., 15, 641 (1967). 7. Pennisi L., Trans. Am. Math. Soc., 74, 177 (1953). 8. Wilde D.J., Optimum Seeking Methods, Prentice-Hall, Inc., Englewood Cliffs, N. J., 1964. 9. Coggins G. P., Univariate Search Methods, Imperial Chemical Industries Ltd., Central Instr. Lab. Res. Note 64/11, 1964. 10. Box M. J., Davies D., Swann W. H., Nonlinear Optimization Techniques, Che- mical Industries Monograph 5, Oliver and Boyd, Edinburgh, 1970. 11. ICI Note 64/3, 1964. 12. Powell M. J. D., Computer J., 7, 155 (1964); см. также Walsh J., ed., Numerical Analysis, Academic Press Inc., London, 1966. 13. Gilbert E. G., Simulation, 10, 350 (1967). ДОПОЛНИТЕЛЬНАЯ ЛИТЕРАТУРА Fiacco A. V., Sequential Unconstrained Minimization Methods for Nonlinear Programming, Ph. D. Dissertation, Northwestern Univ., Evanston, 111., 1967. Fiacco A. V., McCormick G. P., Sequential Unconstrained Minimization Techniques for Nonlinear Programming, Wiley, N. Y., 1968. Kunzi H. P., Zum heutigen stand der nichtlinearen Optimierungs Theorie, Unterneh mersforsch, 12, 1 (1968). Kunzi H. P., Krelle W.,0ettli W., Nonlinear Programming, Blaisdell, Waltham, Mass., 1966. 70 Глава 2 _______ Kunzi H. P., Tzscharch H. Q., Zehnder С. A., Numerical Methods of Mathematical Optimization, Academic Press, N. Y., 1968. Mangasarian 0. L., Nonlinear Programming, McGraw-Hill, N. Y., 1969. Mangasarian 0. L., Fromovitz. The Fritz-John Necessary Optimality Conditions in the Presence of Equality and Inequality Constraints, J. Math. Anal. Appl., 17, 34 (1967) Schechter R. S., Beveridge G. S. G., Sufficiency Conditions in Constrained Varia- tions, Ind. Eng. Chem. Fundamentals, 5, 571 (1966). Schechter R. S., Beveridge G.S.G., Optimization: Theory and Practice, McGraw- Hill, N. Y., 1970. Wilde D. J., BeightlerC. S., Foundations of Optimization, Prentice-Hall, Englewood Cliffs, N. J., 1967. Zangwill W. I., Nonlinear Programm.ng: A Unified Approach, Prentice-Hall, Eng- lewood Cliffs, N.J„ 1969. Методы минимизации, использующие производные 153 ЛИТЕРАТУРА 1. Goldstein A. A., Numerical Math., 4, 146 (1962). 2. Akaike H., Ann. Inst. Statist. Math., Tokyo, 11, 1 (1959). 3. Elder H., Ph. D. Dissertation, Purdue Univ., Lafayette, Ind., 1966. 4. Box G. E. P., Wilson К. В., J. Roy. Statist. Soc., B13, 1 (1951). 5. Langley J. W., J. Am. Statist. Assoc., 62, 819 (1967). 6. Rosenbrock H. H., Computer J., 3, 174 (1960). 7. Greenstadt J., Math. Computation, 21, 360 (1967). 8. MarquardtD. W., J. SIAM, 11, 431 (1963). 9. Levenberg K., Quart. Appl. Math., 2, 164 (1944). 10. Goldfeld S. M., Quandt R. E., Trotter H.'F., Econometrica, 34, 541 (1966). 11. Zwart P. В., Nonlinear Programming: A Quadratic Analysis of Ridge Paraly- sis, Washington Univ., Rep. COO-1493-21, St. Louis, Mo., Jan. 1969. 12. Hestenes M. R., The Conjugate Gradient Method for Solving Linear Systems, in Proc. of the Symp. on Applied Mathematics, Vol. VI, McGraw-Hill, N. Y., 1956, pp. 83—102. 13. Fletcher R., Reeves C, M., Computer J.. 7, 149 (1964). 14. Hestenes M. R., Stiefel E. L.,J. Res. Natl. Bur. Std., B49, 409 (1952). 15. Beckmanf. S., The Solution of Linear Equations by the Conjugate Gradient Method, Ж Mathematical Methods for Digital Computers, Ralston A., Wilf H. S., eds., Vol. 1, Wiley, Inc., N. Y., 1960. 16. Shah В. V., Buehler R. J., Kempthorne 0., J. SIAM, 12, 74 (1964). 17. Forsythe G. E., Motzkin Т. S., Bull. Am. Math. Soc., 57, 183 (1951). 18. Zoutendijk G., Methods of Feasible Directions, American Elsevier Publ. Co., N. Y., 1960. ^.^McCormick G. P., Pearson J.D., Chap. 21 in: Optimization, Fletcher R, ed., Academic Press Inc., London,. 1969. 20. Miele A., Cantrell J. W., Rice Univ. Aero-Astronautics Rept. 56, Houston, Тех., 1969. 21. Cragg E. E., Levy A. V., Rice Univ. Aero-Astronautics Rept. 58, Houston, Тех., 1969. 22. BroydenC. G., Math. Computation, 21, 368 (1967). 23. Goldfarb D., Chap. 18 in: Optimization, Fletcher R., ed., Academic Press Inc., N. Y„ 1969. 24. Davidon W. C., Computer J., 10, 406 (1968); Chap. 2 in: Optimization, Flet- cher R., ed.. Academic Press Inc., N. Y., 1969. 25. Powell M.J.D., Rank One Methods for Unconstrained Optimization, AERE Rept. TP 372, 1969. 26. Murtagh В. A., Sargent R. W. H., in: Optimization, Fletcher R., ed. , Academic Press Inc., London, 1969. 27. Davidon W. C., USAEC Doc. ANL-5990 (rev.), Nov. 1959. 28. Fletcher R., Powell M. J. D., Computer J„ 6, 163 (1963). 29. Bard Y., On a Numerical Instability of Davidon-like Methods, IBM N. Y. Sci. Center Rept. 320-2913, Aug. 1967. 30. Stewart G. W., /. Assoc. Computer Machinery, 14, 72 (1967). 31. Pearson J. D., Computer J.. 13, 171 (1969). 32. Greenstadt J., Math. Computation, 24, 1(1970). 33. Goldfarb D., Math. Computation. 24, 23 (1970). 34. Fletcher R., Computer J., 13, 317 (1970). 35. Goldstein A. A., Price J. F., Numerical Math.. 10, 184 (1967). 36. Pack D. C., Swan G. W., J. Fluid Mech.. 25, 165 (1966). 37. Wheeling R. F., Сот/я. Assoc. Computer Mach., 3, 632 (I960). 38. Brooks S. H., Operations Res., 7, 430 (1959). 154 Глава 3 ДОПОЛНИТЕЛЬНАЯ ЛИТЕРАТУРА ОБЩИЕ ВОПРОСЫ Box M. J., A Comparison of Several Current Optimization Methods, and the Use of Transformations in Constrained Problems, Computer J., 9, 67 (1966). Dorn W. S., Nonlinear Programming: A. Survey, Management Sci., 9, 171 (1963). HestenesM. R., J. Opt. Tlieory and Appl., 4, 303 (1969). Hurt J. J., A Review of Algorithms for Optimization, Univ. of Iowa Rep. 22, June 1970. Kowalik J., Osborne M. R., Methods for Unconstrained Optimization Problems, American Elsevier, N. Y., 1968. Meyers G. E., Properties of the Conjugate Gradient and Davidon Methods, J. Opt. Theory Appl., 2 (1968). Powell M. J. D., A Survey of Numerical Methods for Unconstrained Optimization, SIAM Rev., 12, 79 (1970). Ribiere G., Sur la methode de Davidon-Fletcher-Powell pour la minimisation des fonctions, Management Sci., 16, 572 (1970). Schechter R. S., Beveridge G. S. C., Optimization: Theory and Practice, McGraw- Hill, N. Y., 1970. Spang H. A., Ill, A Review of Minimization Techniques for Nonlinear Functions, SIAM Rev., 5, 343 (1962). Topkis D. M., Veinott A. F., On the Convergence of Some Feasible Direction Algo- rithms for Nonlinear Programming, J. SIAM Control, 5, 268 (1967). Wilde D. J,, Optimum Seeking Methods, Prentice-Hall, Englewood Cliffs, N. J., 1964. Wilde D. J., Beightler C. S., Foundations of Optimization, Prentice-Hall, Engle- wood Cliffs, N. J., 1967. Wolfe P., Recent Developments in Nonlinear Programming, Advan. Computers, 3, 155—187 (1962). ДРУГИЕ МЕТОДЫ НЕЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ БЕЗ ОГРАНИЧЕНИЙ, ИСПОЛЬЗУЮЩИЕ ПРОИЗВОДНЫЕ Booth A. D., An Application of the Method of Steepest Descents to the Solution of Systems of Nonlinear Simultaneous Equations, Quart. J. Mech. Appl. Math., 11, 460, 191 (1949). Broyden C. G., The Convergence of a Class of Double-Rank Minimization Algorithms; 1. General Considerations, J. I.nst. Math. Appl., 6, 76 (1970). Broyden С. G., The Convergence of a Class of Double-Rank Minimization Algorithms; 2. The New Algorithms, J. Inst. Math. Appl., 6, 222 (1970). Crockett J. G., Chernoff H., Gradient Methods of Maximization, Pacific J. Math., 5, 33 (1955). Curry H. D., The Method of Steepest Descent for Nonlinear Minimization Problems, Quart, Appl. Math., 2, 258 (1944). Dixon L. C. W., Biggs M. C., Meander — A Newton Based Procedure for ./V-Dimen- sional Function Minimization, Technical Rept. № 9, The Hatfield Polytechnic, Hatfield, England, April 1970. Goldfield S. M., Quandt R. E., Trotter H. F., Maximization by Quadratic Hill Clim- bing, Econometrica. 34, 541 (1966). HuangH. Y., Levy А. В., J. Opt. Theory and Appl.. 6, 269 (1970). Jacobson D. H., Oksman W., An Algorithm That Minimizes Homogeneous Functi- ons of N Variables in N 4- 2 Iterations and Rapidly Minimizes General Fun- ctions, Technical Rept. № 618, Division of Engineering and Applied Physics, Harvard Univ., Cambridge, Mass., Oct. 1970. Методы минимизации, использующие производные 155 Marquardt D. W., An Algorithm for Least Squares Estimation of Nonlinear Para- meters, SIAM J., 11, 431 (1963). Murtagh В. A., Sargent R. W. H., A Constrained Minimization Method with Qua- dratic Convergence, Chap. 14 in: Optimization, Fletcher R., ed.. Academic Press Inc., London, 1969. Murtagh B. A., Sargent R. W. H., Computer J., 13, 185 (1970). Papaioannou Т., Kempthorne 0., Parallel Tangents and Steepest Descent Opti- mization Algorithm, Wright-Patterson Air Force Base Rept. ARL 70-0117, July 1970. Powell M. J. D., An Iterative Method for Finding Stationary Values of a Function of Several Variables, Computer J., Vol. 5, 1962. Shah В. V., Buehler R. J., Kempthorne 0., Iowa State Univ. Statist. Lab. Tech. Rept. 3, 1961; 2 (rev.), 1962; J. Soc. Ind. Appl. Math.,Vo\. 12, 1964. Shanno D. F., SIAM J. Numer. Anal., 7, 366 (1970). Shanno D. F., Math. Computation, 24, 647 (1970). Shanno D. F., Kettler P. C., Math. Computation, 24, 657 (1970). Siddall J. N.. Optisep Designers Optimization Subroutines, McMaster Univ. Rept. ME/70/DSN/REP/1, Faculty of Engineering, Hamilton, Ontario, Canada, 1970. ЛИТЕРАТУРА 1. Hooke R., Jeeves T. A., J. Assoc. Computer Mach., 8, 212 (1962). 2. Wood С. Р., Application of «Direct Search» to the Solution of Engineering Pro- blems, Westinghouse Res. Lab. Sci. Paper 6-41210-1-P1, 1960. 3. Nelder J. A., Mead R., Computer J., 7, 308 (1964). 4. Spendley W., Hext G. R., Himsworth F. R., Technometrics, 4, 441 (1962). 5. Box M. J., Computer J., 8, 42 (1965); Campey I. G., Nickols D. G., Simplex Minimization, Imperial Chem. Industries, Ltd., 1961. 6. Paviani D., Ph. D. Dissertation, The Univ. of Texas, Austin, Тех., 1969. 7. RosenbrockH. H., Computer J., 3, 175(1960). 8. Swann W. H., Report on the Development of a New Direct Search Method of Optimization, Imperial Chem. Industries, Ltd. Central Instr. Lab. Res. Note 6413, 1964. 9. Palmer J. R., Computer J.. 12, 69 (1969). 10. Powell M. J. D., Computer J„ 7, 155 (1964); 7, 303 (1965). 11. Smith C. S., The Automatic Computation of Maximum Likelihood Estimates, NCB Sci. Dept. Rept. SC846/MR/40, 1962, 12. Zangwill W. I., Computer J., 10, 293 (1967). 13. J. Operations Res., 6, 244 (1958). 14. Favreau R. R., Franks R. G. E., Statistical Optimization, Proc. 2nd Intern. Conf. for Analog Computation, Strasbourg, 1958, Presses Academiques Euro- peenes, Brussels, 1959, p. 437. 15. Mitchell В. A,, Simulation. 4, 399 (1965). 16. Box M. J., Computer J., 8, 42 (1965). 17. Hilleary R. R., U. S. Naval Postgraduate School Techn. Rept./Res. Paper 59, March 1966. 18. Kelly R. J., Wheeling R. F., A Digital Computer Program for Optimizing Non- linear Functions, Mobil Oil Corp., Research Dept., Central Research Div., Princeton, N. J., July 1962. 19. Uchiyama Т., Hydrocarbon Process, 47 (12), 85 (1968). 20. Kushner H., Efficient Iterative Methods for Optimizing the Performance of Multi-parameter Noisy Systems, MIT Lincoln Lab. Rept. 22G-0043 (AD 245802), Oct. 1960. ДОПОЛНИТЕЛЬНАЯ ЛИТЕРАТУРА ОБЩИЕ ВОПРОСЫ Box M. J., A Comparison of Several Current Optimization Methods, and the Us? of Transformations in Constrained Problems, Computer J., 9, 67 (1966). Dorn W. S., Nonlinear Programming: A Survey, Management Sci., 9, 171 (1963). Kowalik J., Osborne M. R., Methods for Unconstrained Optimization Problems, American Elsevier, 1968. 208 Глава 4 Powell M. J. D., A Survey of Numerical Methods for Unconstrained Optimization, SIAM Rev., 12, 79 (1970). Schechter R. S., Beveridge G. S. G., Optimization: Theory and Practice, McGraw- Hill, N. Y., 1970. Spang H. A., Ill, A Review of Minimization Techniques for Nonlinear Functions, SIAM Rev., 4, 343 (1962). Wilde D. J., Optimum Seeking Methods, Prentice-Hall, Englewood Cliffs, N. J., 1964. Wilde D. J., Beightler C. S., Foundations of Optimization, Prentice-Hall Engle- wood Cliffs, N. J., 1967. Wolfe P., Recent Developments in Nonlinear Programming, Advan. Computers. 3, 155-187 (1962). ДРУГИЕ МЕТОДЫ НЕЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ БЕЗ ОГРАНИЧЕНИЙ, НЕ ИСПОЛЬЗУЮЩИЕ ПРОИЗВОДНЫЕ НЕСЛУЧАЙНЫЙ ПОИСК Berman G., Minimization by Successive Approximations, SIAM Numerical Ana- lysis, 3, 123 (1966). Berman G., Lattice Approximations to the Minima of Functions of Several Variab- les, J. Assoc. Computer Mach., 16, 286 (1969). Campey I. G., Nickols D. G., Simplex Minimization, Imperial Chemical Industries, Ltd., Aug. 1961. Fletcher R., Functional Minimization without Evaluating Derivatives, Computer J., 8, 33 (April 1965). Kiefer J., Sequential Minimax Search for a Minimum, Proc. Am. Mach. Soc., 4, 502 (1953). Kiefer J., Optimum Sequential Search and Approximation Methods under Minimum Regularity Assumptions, SIAM J.. 5, 105 (1957). Mitchell R. A., Kaplan J. L., Nonlinear Constraint Optimization by a Nonrandom Complex Method, /. Res. Natl. Bur. Std., 72C, 249 (1968). Spendley W., Hext G. R., Himsworth F. R., The Sequential Application of Simplex Designs in Optimization and Evolutionary Operation, Technometrics, 4, 441 (1962). Swann W. H., Report on the Development of a New Direct Search Method of Opti- mization, Imperial Chemical Industries, Ltd., Central Instr. Lab. Res. Note 64/3, 1964. Vignes J., Algorithme pour la determination d'un extremum local d'une fonction de plusiers variables, Rev. Inst. Franc. Petroie, 23, 537 (1968). Whitte В. F. W., Two New Direct Minimum Search Procedures for Functions of Several Variables, Spring Joint Computer Conf., Washington, D. C., April 1964. Wood C. F., Application of «Direct Search» to the Solution of Engineering Problems, Westinghouse Res. Lab. Sci. Paper 6-41210-1-P1, 1960. СЛУЧАЙНЫЙ поиск Bekey G. A., Gran M. H., Sabroff A. E., Wong A., Parameter Optimization by Random Search Using Hybrid Computer Techniques, Proc. Fall Joint Compu- ter Conf., 1966, p. 191. Brooks S. H., A Discussion of Random Methods for Seeking Maxims, J. Operations Res., 6, 244 (1958). Методы минимизации, не использующие производные 209 Brooks S. H., A Comparison of Maximum Seeking Methods, J. Operations Res. Soc. Am., 7 (1959). Favreau R. R., Franks R. G. E., Random Optimization by Analog Techniques, Proc. 2nd Intl. Conf. for Analog Computation, Strasbourg, France, Sept. 1958, Pres- ses Academiques Europeenes, Brussels, 1959, pp. 437, 443. Gallagher P. J., MOP-1, An Optimizing Routine for the IBM 650, Can. Q. E. Civi- lian Atomic Power Dept. Rept. R60cAP35, 1960. McArthur D. S., Strategy in Research, Alternative Methods for the Design of Expe- riments, IRE Trans., EM-8, 34 (1961). Matyas J., Random Optimization, Automatic and Remote Control, 26, 244 (1965). Mitchell В. А., А.'Hybrid Analog-Digital Parameter Optimizer for ASTRAC II, Simulation, 4, 398 (1965). Munson J. К., Rubin A. I., Optimization by Random Search on the Analog Compu- ter, IRE Trans., EC-8, 200 (1959). Schumer M. A., Steiglitz K., IEEE Trans. Autom. Control, AC-13, 270 (1968). Shimuzu Т., A Stochastic Approximation Method for Optimization Problems, J. Assoc. Computer Mach., 16, 511 (1969). Zeilnik H. E., Sondak N. E., Davis R. S., Gradient Search Optimization, Chem. Eng. Progr., 58 (8), 35 (1962). ЛИТЕРАТУРА 1. Rosenbrock H. H., Computer J., 3, 175 (1960). 2. Whitte В. F., Hoist W. R., Spring Joint Computer Conf., Washington, D. C., 1964. 3. Beale E. M. L., On an Iterative Method of Finding a Local Minimum of a More Than One Variable, Princeton Univ. Stat. Techn. Res. Group Techn, Rept. 25, Nov. 1958. 4. Wood С. F., Westinghouse Res. Labs. 5. Powell M. J. D., Computer J., 7, 155 (1964). 6. Cragg E. E., Levy A. V., Rice Univ. Aero-Astronautics Rept. 58, Houston, Тех., 1969. 7. Leon A., A Comparison Among Eight Known Optimizing Procedures, in: Recent Advances in Optimization Techniques, Lavi A., Vogi T. P., eds., Wiley, Inc. N. Y., 1966. 8. Stevens D. F., Instructions for the Use of VARMINT, Univ. of California, Law- rence Radiation Lab., Berkeley, June 1961. 9. Baer R. M., Computer J., 5, 193 (1962). 10. Doerfler T. E., Partan Minimization by Method of Parallel Tangents, Iowa State Univ., Ames, Iowa, April 1964. 11. Wortman J. D., NLPROG, Ballistic Res. Lab. Mem. Rept. 1958, Aberdeen Proving Grounds, Md., Jan. 1969. 12. Pletcher R., Powell M. J. D., Computer J., 6, 163 (1963). 13. Fletcher R., Computer J., 8, 33 (1965). 14. McCormick G. P., Pearson J. D., Chap. 21 in: Optimization, Fletcher R., ed., Academic Press, Inc., London, 1969. 238 Глава 5 15. Pearson J. D., Computer J., 13, 171 (1969). 16. Box M. J., Computer .]., 9, 67 (1966). 17. Powell M. J. D., Computer J., 7, 303 (1965). 18. Box M. J., Computer J , 9, 67 (1966). 19. BarnesJ. G P., Computer J., 8, 66(1965). 20. Powell M. J. D., Computer J , 7, 303 (1965). 21. Spendley W., Chap. 16 in: Optimization, Fletcher R,, ed., Academic Press, Inc., London, 1969. 22. Bard Y., Comparison of Gradient Methods for the Solution of Nonlinear Para- meter Estimation Problems, IBM N. Y. Sci. Center Kept. 320-2955, 1968; SIAM J. Numerical Anal., 7, 157 (1970). ЛИТЕРАТУРА 1. Griffith R. E., Stewart R. A., Management Sci., 7, 379 (1961). 2. Glass H., Cooper L., J. Assoc. Computer Mach., 12, 71 (1965). 3. Olson F. A., ACM SIGMAP Workshop, IBM Data Processing Div., June 14— 15, 1966. 4. Smith H. V., A Process Optimization Program for Nonlinear Systems: POP II, IBM Gen. Program Library 7090 H9 IBM 0021, 1965. 5. Zwart P. В., SIGMAP Workshop on Nonlinear Programming, Yorktown Heights, N. Y., 1967. 6. Wilson R. В., Ph. D. Dissertation, Harvard Univ. Graduate School of Busi- ness Administration, Boston, 1963. 7. Beale E. M. L., Numerical Methods, in: Nonlinear Programming, Abadie J., ed., Interscience Publ., N. Y., 1967. 8. Graves G. W., Whinston А. В., Univ. Calif. Western Management Sci. Inst. Paper 108, Los Angeles, Sept. 1966. 9. Frank M., Wolfe P., Naval Res. Logistics Quart., 3, 95 (1956). 10. Barnes G. К., M. S. Thesis, Univ. of Texas, Austin, Тех., 1967. 11. DiBella С. W., Stevens W. F., Ind. Eng. Chem. Process Design Develop., 4, 16 (1965). 12. Frisch R., The Multiple Method for Linear Programming, Mem. Univ. Socia- •- lokon Inst., Oslo, Oct. 1955. » 330 Глава 6 13. Zoutendijk G., Methods of Feasible Directions, Elsevier Publ. Co., Amsterdam, 1960. 14. Rosen J. В., J. Soc. !nd. Appl. Math.. 8, 181 (1960); 9, 514 (1961). 15. Rosen J. В., Men-ill R. P., Gradient Projection— GP90, Share Program 7090-H2-3430GP90. 16. Murtagh B. A., Sargent R. W. H., Chap. 14 in: Optimization, Fletcher R., ed., Academic Press, London, 1969. 17. Householder A. S., The Theory of Matrices in Numerical Analysis, Blaisdell Publ. Co., Waltham, Mass., 1964, p. 8. 18. Kflnzi H. P., Krelle W., Nonlinear Programming, Blaisdell Publ. Co., Waltham, Mass., 1966. 19. Fletcher R., J. Inst. Math. Appl., 5, 2 (1969). 20. Cross К. Е., АЕС Doc. K-1746, May 30, 1968. 21. Davidon W. С., АЕС Doc. ANL-5990 (rev.), 1959. 22. Goldfarb D., Ph. D. Dissertation, Princeton Univ., Princeton, N. J., 1966. 23. Goldfarb D., Lapidus L., Ind. Eng. Chem. Fundamentals, 7, 142 (1968). 24. Davies D., The Use of Davidon's Method in Nonlinear Programming, ICI Ltd. Rept. MSDH/68/110, Aug. 1968; Doc. N69-33235 from CFSTI, Springfield, Va. 25. Murtagh B. A., Sargent R. W. H., Chap. 14 in: Optimization, Fletcher R., ed., Academic Press, London, 1969. 26. Householder A. S., The Theory of Matrices in Numerical Analysis, Blaisdell Publ. Co., Waltham, Mass., 1964, p. 10. 27. Zoutendijk G., Methods of Feasible Directions, Elsevier Publ. Co., Amsterdam, 1960. 28. Zoutendijk G., SIAM J. Control, 4, 194 (1966). 29. Wolfe P., Recent Developments in Nonlinear Programming, Rand Corp. Rept. R-401-PR, 1962. 30. Abadie J., Carpentier J., Generalization de la methode du gradient reduit de Wolfe au cas de contraintes nonlineaires, Proc. IFORS Conf.; Chap. 4 in: Opti- mization, Fletcher R., ed., Academic Press, London, 1969. ' 31. Faure P., Huard P., Rev. Franc Recherche Operationelle, 9, 167 (1965). 32. Abadie J., Guigou J., Gradient reduit generalise, Electricite de France Note HI 069/02, April 15, 1969. 33. Wolfe P., Notices Am. Math. Soc., 9 (4), 308 (1962); Methods of Nonlinear Programming, in: Recent Advances in Mathematical Programming, Gra- ves R. L., Wolfe P., eds., McGraw-Hill, N. Y., 1963, pp. 76—77. 34. Kunzi H. P., Unternehmensforschung, 12, 1 (1968). 35. Mylander W. С., Computer J., 8, 391 (1965). 36. Box M. J., Computer J., 8, 42 (1965). ДОПОЛНИТЕЛЬНАЯ ЛИТЕРАТУРА ОБЩИЕ ВОПРОСЫ Abadie J., Numerical Experiments with the GRG Method, in: Integer and Nonli- near Programming, Abadie J., ed., North Holland Publ. Co., Amsterdam, 1970. Bellmore M., Greenberg H. J., Jarvis J. J., Generalized Penalty-function Concepts in Mathematical Optimization, Operations Res., 18, 193 (1970). Carpentier J., Abadie J., Generalisation de la methode du gradient reduit de Wolfe au cas de contraintes nonlineaires, Proc. IFORS Congr., Cambridge, Mass Aug. 29 — Sept. 2, 1966. Charnes A., Cooper W. W., Nonlinear Power of Adjacent Extreme Point Methods in Linear Programming, Econometrica, 25, 132 (1957). Davies D., Some Practical Methods of Optimization: Notes for the NATO Summer Методы линейной аппроксимации 331 School, on Integer and Nonlinear Programming, Academic Press, N. Y., June 18—20, 1969. Davies D., Review of Constrained Optimization, Clearinghouse for Federal Scienti- fic and Technical Information, Document N 69-36898, Sept. 30, 1968. Dennis J. В., Mathematical Programming and Electrical Networks, MIT, Cam- bridge, Mass., 1959. Faure P., Huard P., Resolution de programmes mathematiques a fonction nonli- neaire par la methode du gradient reduit, Rev. Franc. Recherche Operationelle, № 36, 167 (1965). Fletcher R., Clearinghouse for Federal Scientific and Technical Information, Docu- ment N 69-37016, Sept. 30, 1968. Griffith R. E., Stewart R. A., A Nonlinear Programming Technique for Optimiza- tion of Continuous Processing Systems, Management Sci., 7, 379 (1961). Kleinbohm К., Ein Verfahren zur approximativen Losung von konvexen Program- men, Ph. D. dissertation, Univ. of Zurich, 1966. Leviton E. S., Polyak В. Т., Constrained Minimization Methods, USSR Compu- tational Math. and Math. Phys.. 6, 1 (1966). Rosen J. В., The Gradient Projection Method for Nonlinear Programming, Part I J. Soc. Ind. Appl. Math., 8, 181 (1960); Part II, 9, 514 (1961); IBM Share Program 1399. Wolfe P., Methods of Nonlinear Programming, in: Nonlinear Programming, Aba- die J., ed., North Holland Publ. Co., Amsterdam, 1967. Zoutendijk G., Methods of Feasible Directions, American Elsevier, N. Y., 1960. СХОДИМОСТЬ АЛГОРИТМОВ Topkis D. M., Veinott A. E., On the Convergence of Some Feasible Direction Algo- rithms for Nonlinear Programming, J. SI AM Control., 5, 268 (1967). Zangwill W. I., Convergence Conditions for Nonlinear Programming Algorithms, Management Sci., 16, 1 (1969). ДРУГИЕ МЕТОДЫ НЕЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ ПРИ НАЛИЧИИ ОГРАНИЧЕНИЙ, ИСПОЛЬЗУЮЩИЕ ЛИНЕАРИЗАЦИЮ Chency E. W., Goldstein A. A., Newton's Method for Convex Programming and Tchebycheff Approximation, Numerical Math., 4, 253 (1959). De Remus L. V., Nonlinear Partition Programming, SIGMAP Workshop on Non- linear Programming, IBM Corporation, Yorktown Heights, N. Y., 1968. DiBella C. W., Stevens W. F., Process Optimization by Nonlinear Programming, Ind. Eng. Chem. Process Design Develop., 4, 16 (1965). Glass H., Cooper L., Sequential Search: A Method for Solving Constrained Optimi- zation Problems, J. ACM, 12, 71 (1965). Graves G. W., Whinston А. В., The Application of a Nonlinear Programming Al- gorithm to a Second Order Representation of the Problem, Univ. of California at Los Angeles, Western Management Sci. Inst. Paper 108, Sept. 1966 (AD641196). Hartley H. 0., Hocking R. R., Convex Programming by Tangential Approximation, Management Sci., 9, 600 (1963). Hartley H. 0., et al., Convex; A Computer Program for Solving Convex Prog- rams, Techn. Rep. № 23, Texas A and M Univ., College Station, Texas, July 1970. Hilleary R. R., The Tangent Search Method of Constrained Minimization, U. S. Naval Postgraduate School Techn. Rept. Res. Paper 59, March 1966 (AD 632121). » 332 Глава 6 Kelley J. E., The Cutting-plane Method for Solving Convex Programs, J. Soc. Ind. Appl. Math., 8, 703 (1960); Method of Gradients, Chap. 6 in: Optimization Techniques with Applications, Leitmann G., ed., Academic Press, N. Y., 1962. Kiinzi H. P., The Duoplex Method in Nonlinear Programming, J. S1AM Control, 4, 130 (1966). McGuire S. W., Hocking R. R., Hartley H. 0., Spherical Programming: A Convex Programming Algorithm, Techn. Rep. № 5, Inst. of Statistics , Texas A and M Univ., College Station, Texas, Oct. 1968. Miele A., Huang H. Y., Heideman J. C., Sequential Gradient-restoration Algorithm for Minimization of Constrained Functions — Ordinary and Conjugate Gra- dient Methods, J. Optimization Theory Appl., 4, 213 (1969). Mills D. H., Extending Newton's Method to Systems of Inequalities, Proc. 6th In- tern. Symp. on Math. Programming, Princeton, N. J., Aug. 1967. Mugele R. A., A Program for Optimal Control of Nonlinear Processes, IBM. Sy- stems J., 1, 2 (1962). Pinsker I. S., The Alternance Method (for Solution of Problems in Nonlinear Pro- gramming), Automatic Remote Control, 25, 280 (1964). Shanno D. F., An Accelerated Gradient Projection Method for Linearly Constrained Nonlinear Estimation, SIAM J. Appl. Math.. 18, 322 (1970). ЛИТЕРАТУРА 1. Fiacco A. V., McCormick Q. P., Nonlinear Programming, Wiley, N. Y., 1968. 2. Zangwill W. I., Management Sci., 13, 344 (1967). 3. Huard P., Resolution de programmes mathematiques a contraintes nonlineaires par la methode des centres, Note Electricite de France, HR 5690/3/3.17, 1964; см. также The Method of Centers in: Course A., Nonlinear Programming, North „ Holland Publ. Co., Amsterdam, 1965. 4. Fiacco A. V., McCormick G. P., Operations Res., 16, 820 (1968). 5. Pietrzykowski Т., Application of the Steepest Descent Method to Concave Pro- gramming, Proc. IFIPS Congr., Munich, North Holland Publ. Co., Amsterdam, 1962. 6. Fiacco A. V., McCormick G. P., J. Soc. Ind. Appl.Math., 15, 505 (1967). 7. Fiacco A. V., Ph. D. Dissertation, Northwestern Univ., Evanston, 111., 1967. 8. Dennis J. В., Mathematical Programs and Electrical Networks, Wiley, N. Y., 1959. 9. Box M. J., Davies D., Swann W. H., Nonlinear Optimization Techniques, 1CI Monograph of Mathematics and Statistics, № 5, Oliver and Boyd Ltd., London, 1969. 10. Carrol С. W., Operations Res., 9, 169 (1961). 11. Davies D., Some Practical Methods for Optimization, Notes for the NATO Sum- mer School on Integer and Nonlinear Programming, June 8—20, 1969. 12. Weisman J., Ph. D. Dissertation, Univ. of Pittsburgh, Pa., 1968. 13. Fiacco A. V., McCormick G. P., SIAM J. Appl. Malli., 15, 505 (1967). 14. Huard P., p. 209 in: Nonlinear Programming, Abadie J., ed., North Holland Publ., Amsterdam, 1967. Методы штрафных функций 379 15. Carroll С. W., Operations Res., 9, 169 (1961); Ph. D. Dissertation, Inst. of Paper Chemistry, Appleton, Wis., 1959. 16. Fiacco A. V., McCormick G. P., Management Set.. 10, 360, 601 (1964); 12, 816 (1966). 17. Wortman J. D., BRL 1958 (NLPROG), Jan. 1969. 18. Murray W., Proc. 6th Intern. Symp. on Mathematical Programming, Princeton, N. J., 1967. 19. Fletcher R., McCann A. P., Chap. 13 in: Optimization, Fletcher R., ed., Acade- mic Press, London, 1969. 20. Tabak D., IEEE Trans. Automatic Control, AC14, 572 (1969). 21. Galler W. S., Gotas H. В., J. Sanit. Eng, Div.. Am. Soc. Civil Engr., SA!, 163 (1966). 22. KleinM., Klimpel R. R., /. Indus. Eng., 18, 90 (1967). ДОПОЛНИТЕЛЬНАЯ ЛИТЕРАТУРА МЕТОДЫ МНОЖИТЕЛЕЙ ЛАГРАНЖА Arrow К. J., Hurwicz L., Gradient Methods for Constrained Optimization, J. Ope- rations Res. Soc., 5, 258 (1957). Bard Y., Greenstadt J. L., A. Modified Newton Method for Optimization with Equality Constraints, in: Optimization, Fletcher R., ed., Academic Press, London, 1969. Dorn W. S., On Lagrange Multipliers and Inequalities, J. Operations Res. Soc., 9, 95 (1961). Everett H., Generalized Lagrange Multiplier Methods for Solving Problems of Opti- mal Allocation of Resources, Operations Res., 11, 399 (1969). Falk J. E., Lagrange Multipliers and Nonconvex Programs, Res. Analysis Corp. Techn. Paper RAC-TP-335, Nov. 1968; Lagrange Multipliers and Nonlinear Programming, J. Math. Analysis Appl., 19, 141 (1967). Klein В., Direct Use of Extremal Principles in Solving Certain Optimizing Problems Involving Inequalities, J. Operations Res. Soc., 3, 169 (1955). Kuhn H. W., Tucker A. W., Nonlinear Programming, Proc. 2nd Berkeley Symp. on Math. Statist. Prob., Univ. California Press, Berkeley, Calif., 1951, p. 481. Takahashi I., Variable Separation Principle in Mathematical Programming, J. Operations Res. Japan, Vol. 6 (1964). Zwart, /. Opt. Theory and Appl., 6, 150 (1970). • МПБМ Bracken J., McCormick G. P., Selected Applications of Nonlinear Programming, Wiley, N. Y., 1968. Fiacco A. V., McCormick G. P., Nonlinear Programming: Sequential Unconstrai- ned Minimization Techniques, Wiley, N. Y., 1968. Lootsma F. A., Logarithmic Programming: A Method of Solving Nonlinear Program- ming Problems, Phillips Res. Rept., 22, 329 (1967); Constrained Optimization via Penalty Functions, Phillips Res. Rept., 23, 408 (1968). Pomentale Т., A New Method for Solving Conditioned Maxima Problems, /. Math. Analysis Appl., 10, 216 (1965). Schmit L. A., An Integrated Approach to Structural Analysis and Synthesis, Ц AlAA J., 3, 1104 (1964). ДРУГИЕ МЕТОДЫ Allran R. R., Johnsen S. E. J., Computer J., 13, 171 (1970). Bellmore M,, Greenberg H. J., Jarvis J. J., Oper. Res., 17, 229 (1969). 381 Глава 7 Fletcher R., McCann A. P., Acceleration Techniques for Nonlinear Programming, in: Optimization, Fletcher R., ed., Academic Press, London, 1969. Haarhoff P. C., Buys J. D., Computer J.. 13, 78 (1970). Huard P., Resolution of Mathematical Programming with Nonlinear Constraints by the Method of Centers, in: Nonlinear Programming, Abadie J., ed.. North Holland Publ. Co., Amsterdam, 1967. Kelley H. J., Denham W. G., Johnson I. L., Wheatley P. 0., An Accelerated Gra- dient Method for Parameter Optimization with Nonlinear Constraints, J. Astro- nautical Scl., 13, 166 (1966). Kowalik J., Osborne M. R., Ryan D. M., A New Method for Constrained Optimiza- tion Problems, Operations Res., 17, 973 (1969). Lasdon L. S., An Efficient Algorithm for Minimizing Barrier and Penalty Functi- ons, Techn. Memorandum № 210, Operations Res. Depart., Case Western Re- serve Univ., Dec. 1970. Lootsma F. A., Boundary Properties of Penalty Functions for Constrained Minimi- zation, Nat. Techn. Inform. Service, Document N70-33412, 1970. Morrison D. D., Optimization by Least Squares, SI AM J., Numerical Analysis, 5, 83 (1968). Murray W., Constrained Optimization, Nat. Phys. Lab. Rept. № NA79, Aug. 1969. Murray W., Behavior of Hessian Matrices of Barrier and Penalty Functions Arising in Optimization, Nat. Phys. Lab. Rept. № NA 77, April 1969. Powell M. J. D., A Method for Nonlinear Constraints in Minimization Problems, in: Optimization, Fletcher R., ed., Academic Press, London, 1969. Schwartz L. E., Large Step Gradient Methods, Chap. 8 in: Optimization, Fletcher R., ed., Academic Press, London, 1969. |§ Siddall J. N., McDonald J. F., OPTIPAC: The Designers Optimization Problem Solver, 2 vols., McMaster Univ., Mech. Engineering Depart., Hamilton, Ont., Canada, Oct. 1969. ЛИТЕРАТУРА 1. Paviani D., Himmelblau D. M., Operations Res.. 17 (1969). 2. Wilde D. J., Optimum Seeking Method», Prentice-Hall, Inc., Englewood Cliffs N. J., 1962, p. 32. ЛИТЕРАТУРА 1. Stocker D. С., A Comparative Study of Nonlinear Programming Codes M S Thesis, The Univ. of Texas, Austin, Тех., 1969. 2. Hoizman A. G., Comparative Analysis of Nonlinear. Programming Codes with the Weisman Algorithm, SRCC Rept. 113, Univ. of Pittsburgh, Pittsburgh Pa Nov.1969. 3. ColvilleA. R., IBM N. Y. Sci. Center Rept. 320-2949, June 1968. 4. Sauer R. N., Colville A. R., Burwick C. W., Hydrocarbon Process. Petrol Refiner 43, 85 (1964). ' ' 5. Bracken J., McCormick G. P., Selected Applications of Nonlinear Programming Wiley, Inc., N. Y., 1968. ДОПОЛНИТЕЛЬНАЯ ЛИТЕРАТУРА Rastrigin L. A., Criteria for Comparing Methods of Seeking an Extremum (English Trans.), Zavod Lab., 32, 1248, 1529 (1966). Rosen J. В., Su^uki S., Construction of Nonlinear Programming Test Problems Commuii. ACM. 8, 113 (1965).