By WillardI.ZANGWILL •Associate Professor, School of Business Administration, University of California, Berkley NONLINEAR PROGRAMMING A UNIFIED APPROACH Prentice — Hall, Inc., Englvwood Cliffs, W. }., 1969. Уаллард И. ЗАНГВИЛЛ НЕЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ Единый подход Перевод с английского Д. А. Бабаева Под редакцией Е. Г. Гольштейна МОСКВА — «СОВЕТСКОЕ РАДИО» - 1973 6Ф0.1 327 УДК 519.82 Зангвилл У. Нелинейное программирование. Единый подход. 1969 г. Пер. с англ., под ред. Е. Г. Гольштейна, М., «Сов. радио», 1973, 312 с. Систематически излагаются вопросы нелинейного программиро- вания. Даются многочисленные постановки практических задач из обласги внешней торговли, решения уравнений регрессионного ана- лиза, планирования производства, конкуренции и другие, уклады- вающиеся в схему нелинейного программирования. Рассматривается геометрическое и квадратичное программирование, оптимальное управление, вогнутость и выпуклость, теория Куна—Таккера, двой- ственность, необходимые и достаточные условия оптимальности, мно- гочисленные алгоритмы. Имеется обширная библиография и боль- шое количество упражнений. Книга может быть использована математиками, разрабатываю- щими теоретические вопросы и вычислительные алгоритмы нелиней- ного программирования, а также инженерами и экономистами, зани- мающимися применением нелинейного программирования для реше- ния практических задач. 30 рис., 236 библ. назв. Редакция кибернетической литературы 3 3314-063 66-73 046 (01)-73 "" © Перевод на русский язык, «Советское радио», 1973. ПРЕДИСЛОВИЕ РЕДАКТОРА ПЕРЕВОДА Проникновение количественных методов в экономику, технику и другие области человеческой деятельности,ко- торое в последнее десятилетие неуклонно возрастает, усиливает внимание специалистов в области приклад- ных наук к математическому аппарату, используемому в интересующих их областях, и привлекает все большее число математиков к разработке математической пробле- матики прикладного характера. Математическое программирование, как известно, принадлежит к числу наиболее интенсивно используемых дисциплин прикладной математики, причем в последнее время все чаще возникают задачи, сводящиеся к схеме нелинейного программирования. Вместе с тем имеющая- ся на русском языке монографическая литература по не- линейному программированию (в отличие от линейного программирования) совершенно недостаточна. По суще- ству советский читатель располагает на сегодня лишь тремя книгами, которые содержат материал по методам нелинейного программирования: это монографии С. И. Зу- ховицкого и Л. И. Авдеевой, Дж. Хедли, Г. П. Кюнци и В. Крелле *1. В первых двух методам нелинейного про- граммирования уделено сравнительно мало места, при- чем описанные в этих книгах методы отражают уровень, достигнутый к 1963 г. Последняя книга посвящена исключительно методам квадратичного программирова- ния, важного, но весьма частного раздела нелинейного программирования, и содержит методы, разработанные к 1961 г. И хотя исследования по нелинейному программиро- ванию в последние годы ведутся интенсивно, однако по- знакомиться с ними можно либо по журнальной литера- *' С. И. Зухов и ц к и и, Л. И. Авдеева. Линейное и вы- пуклое программирование. «Наука», 1967; Дж. Хедл.и. Нелиней- ное и динамическое программирование.'«Мир», 1967; Г. П. К ю н- Ц и, В. Коелле. Нелинейное программирование. «Сов. радио», 1965. туре, либо по совсем недавно вышедшим иностранным книгам, среди которых настоящая монография является, пожалуй, наиболее интересной и полезной. Прежде всего, эта книга достаточно полно отражает зарубежный уровень по методам нелинейного програм- мирования, достигнутый к 1969 г. В ней подробно описаны методы оптимизации для задач без ограничений, включая методы сопряженных направлений и сопряженных градиентов, а также спосо- бы ускорения сходимости. Специальные главы посвяще- ны методам оптимизации для задач с линейными ограни- чениями и квадратичного программирования, методам штрафных функций и барьеров, возможных направлений, отсечений и ряду других принципов оптимизации. Вместе с тем следует подчеркнуть, что автор, видимо, недоста- точно знаком с исследованиями по нелинейному про- граммированию, проводимыми в Советском Союзе. По- этому в книге не затронуты, например, методы оптими- зации негладких выпуклых функций, методы типа алго- ритма фиктивной игры и ряд других. Безусловным достоинством книги является то, что доказательства сходимости почти всех методов проводят- ся в ней на основе единого подхода, разработанного автором. Дело в том, что для многих методов оптимиза- ции сходимость является следствием монотонности алго- ритма, компактности последовательности, им вырабаты- ваемой, и непрерывности отображения, используемого в алгоритме для вычисления последующего приближе- ния по предыдущему. Эти три момента в доказательстве сходимости, как правило, используются стандартным пу- тем. Автор сформулировал несколько общих теорем схо- димости, благодаря которым для доказательства сходи- мости конкретного алгоритма достаточно проверить, что он удовлетворяет определенным (типа упомянутых вы- ше) свойствам. Единый подход к анализу методов оптимизации, без- условно, облегчает изучение довольно разнообразного материала книги. Хотелось бы также упомянуть об элементарном и до- ходчивом стиле изложения, благодаря которому книгу с большой пользой смогут прочесть не только математи- ки, но и специалисты различных областей, где исполь- зуется нелинейное программирование. Активному усвоению материала в значительной сте- пени будут способствовать многочисленные упражнения, помещенные автором в конце каждой главы. При редактировании книги устранен ряд опечаток и неточностей, причем специальных оговорок в тексте по этому поводу не делается. Книга У. Зангвилла, предлагаемая вниманию совет- ского читателя, отличается оригинальным, доходчивым и в то же время достаточно строгим изложением и, как мне кажется, будет полезна широкому кругу математи- ков, инженеров и экономистов. Е. Г. Голыитейн ВВЕДЕНИЕ Нелинейное программирование, охватывая весьма широкий круг задач, является одним из основных раз- делов в теории оптимальных решений. Эта книга пред- ставляет собой новый и единый подход к нелинейному программированию, который не только облегчает изуче- ние предмета, но и помог получить много новых резуль- татов. Материал большей части книги основан на иссле- дованиях, проведенных автором и другими специалиста- ми, и раньше нигде не был опубликован. Нелинейное программирование в определенном смыс- ле подобно линейному программированию, в нем отсут- ствует лишь требование линейности функций, хотя, ко- нечно, теория нелинейного программирования охватывает и линейный случай. Большая общность нелинейных функ- ций позволяет осуществить исключительно точное моде- лирование реальных задач. В книге рассматриваются как постановки, так и методы решения подобных задач. Ключевой вопрос состоит в том, обеспечивает ли заданный алгоритм получение численного решения дан- ной задачи или, более точно, сходится ли вырабатывае^- мая им последовательность приближенных решений к точному решению задачи. Значительная часть книги посвящена анализу этого вопроса с помощью подхода, основанного на исследованиях автора по теории алго- ритмической сходимости. Изложенная здесь теория упро- щает многие известные ранее доказательства, дает дока- зательство сходи-мости новых алгоритмов и обеспечивает изучающих единым методом для освоения нелинейного программирования. Книгу можно разделить на три основные части. В первой части (гл. 1) приводятся формулировки раз- личных задач в терминах нелинейного программирова- ния. В ней рассматриваются задачи планирования про- изводства и управления запасами, регрессионного ана- лиза, поведения потребителя, проектирования теплооб- менников, управления движением ракеты, решения урав- нений, метода «затраты — эффективность» и финансового 8 анализа как задачи нелинейного программирования. Включены также экономические, математические, техни- ческие и научные приложения, приложения к сфере де- ловых отношений и управления государством, вопросы геометрического программирования, оптимального управ- ления и квадратичного программирования. Сформулировав задачу, мы приступаем к ее числен- ному анализу, добиваясь выделения оптимальной точки среди других допустимых точек. Вторая часть книги (гл. 2 и 3) посвящена задаче распознавания решения и рассматривает такие вопросы, как вогнутые и выпуклые функции, условия Куна—Таккера, условия регулярно- сти и теория двойственности. Она содержит экономиче- скую интерпретацию, а также двойственную задачу гео- метрического программирования и принцип максимума оптимального управления. Зная, как распознать точку, являющуюся решением задачи нелинейного программирования, мы приступаем к значительно более трудной задаче, а именно к задаче движения из точки, которая не является решением, в точ- ку, представляющую собой решение. Изучение этой за- дачи составляет третью и последнюю часть книги. По су- ществу эта задача сводится к исследованию алгоритмов, хотя мы рассматриваем также экономическую интерпре- тацию и приводим важную зависимость между теорией сходимости и теорией устойчивости Ляпунова для раз- ностных уравнений. Основной упор в третьей части сде- лан на теорию сходимости. Здесь не только представлено несколько новых алгоритмов, сходимость которых дока- зана с помощью этой теории, но при анализе ранее из- вестных алгоритмов вместо старых доказательств при- ведены новые, основанные на приведенных общих поло- жениях. Таким образом, установлен единый подход к ана- лизу алгоритмов нелинейного программирования. Теория сходимости обычно приводит к упрощению соответст- вующих обоснований: Хотя при использовании теории сходимости возникают, естественно, свои трудности, мы, тем не менее, надеемся, что ее применение облегчит ос- воение предмета и поможет в доказательстве сходимости других алгоритмов. Содержание книги. Книга не претендует на краткое изложение всех результатов, известных в нелинейном про- граммировании. Однако автор пытался включить в рабо- ту широкий круг наиболее интересных проблем. Многие вопросы нелинейного программировании, не приведенные в тексте, рассмотрены в упражнениях. Таким образом, упражнения представляют собой неотъемлемую часть книги. Кроме того, примечания в конце каждой главы содержат ссылки на литературу по данным вопросам, использование которой позволит более глубоко изучить предмет. Предварительная подготовка, необходимая для чтения книги. Книга предполагает знакомство читателя с неко- торыми разделами линейного программирования, мате- матического анализа и линейной алгебры (с введением в задачу линейного программирования, симплексным ме- тодом и теоремами двойственности линейного програм- мирования); из математического анализа предполагает- ся знакомство с пределами и последовательностями, не- прерывностью, дифференцированием, разложением в ряд Тейлора и замкнутыми множествами. В книге имеется приложение, которое поможет освежить в памяти чита- телей некоторые из этих вопросов. Из линейной алгебры' предполагается знакомство с операциями над матрицами и векторами и с линейной независимостью. В работе ис- пользуются и некоторые другие математические поня- тия, но они предварительно объясняются. Порядок изложения. Книга содержит достаточно ма- териала и может служить основой годового курса по нелинейному программированию или же обзора, рассчи- танного на несколько недель. 10 Краткий курс может состоять из следующих глав и параграфов: 2; 4; 5 (за исключением 5.4.4); 7.1; 8.1; 8.2; 10.1; 11; 12J1; 12.2; 13.1 и 13,2. Такой выбор разделов обес- печивает логически последовательное изложение и охва- тывает многие важные вопросы нелинейного программи- рования. Гл. 6 и 9 более трудные, их можно опустить при первом чтении, не прервав связь изложения. Логическая взаимосвязь глав изображена на рисунке (обратите внимание на то, что чтение книги можно на- чать с гл. 2). Ot СПИСОК ЛИТЕРАТУРЫ A b a d i e J. ed. Nonlinear Programming. John Wiley and Sons, Inc., New York, 1967. Apo stol Т. М. Mathematical Analysis. Addison—Wesley Publishing Co., Inc., Reading, Mass, 1957. Arrow K. J. A Gradient Method for Approximating SaddJe Points and Constrained Maxima. Paper P-223, The RAND Corporation, Santa Monica, Calif, 1951. Arrow K. J. and Enthoven A.C. Quasi-Concave Programming, Econometrica, XXIX, № 4, p. 779—800, 1961. Arrow K. J. and H u r w i с z L. Reduction of Constrained Maxima to Saddle Point Problems. Proceedings of the Third Berkeley Sym- posium on Mathematical Statistics and Probability, ed. Neyman J., University of California Press, Berkeley, p. 1—20, 1956. Arrow K. J. and H u r w i с z L. Decentralization and Computation in Research Allocation, p. 34—104 in Essays in Economics and Econometrics. University of North Carolina Press, Chapel Hill, 1960. Arrow K. J., H u г w i с z L. and U z a w a H. Studies in Linear and Non-Linear Programming. Stanford University Press, Stanford, Ca- lif, 1958. Эрроу, Гурвиц, Удзава. Исследования по линейному и нели- нейному программированию. М., Изд-во иностранной литературы. 1962. Arrow К. J., H u r w i с z L. and U z a w a H. Constraint Qualifi- cation in Maximization Problems, Naval Research Logistics Quar- terly, VIII, p. 175—91, 1961. Arrow K. J. and U z a w a H. Constraint Qualification in Maximi- zation Problems, II, Technical Report № 84, Institute for Mathe- matical Studies in Social Sciences, Stanford University, Stanford, Calif, 1960. A v r i e 1 M. and Wilde D. J. Optimal Condenser Design by Geomet- ric Programming. Stanford Chemical Engineering Report, 1966. Rarankin E.W. and D о r {in a n R. On Quadratic Programming. University of California Publication in Statistics, II, p. 285—318. University of California, Berkeley, 1955. В я u m о 1 W. J. Economic Theory and Onerations Analysis. Prentice- Hall, Inc., Englewood Cliffs, N. J, 1961. В e a 1 e E. M. L. On Minimizing a Convex Function Subject to Linear Inequalities. Journal of the Royal Statistical Society (B), XVII, p. 173—84, 1955. Be ale E. M. L. An Algorithm for Solving the Transportation Prob- lems when the Shipping Cost over each Route is Convex. Naval Research Logistics Quarterly, VI, p. 43—56, 1959. В e а 1 e E. M. L. On Quadratic Programming. Naval Research Logis- tics Quarterly, VI, p. 227—43, 1959. Beckman F.S. The Solution of Linear Eauations by the Conjugate Gradient Method. P. 62—72 in Mathematical Methods for Digital 303 Computers, eds. Raiston A. and Wilt II. S., John Wiley and Sons, Inc., New York, 1960. Bellman R. Dynamic Programming. Princeton University Press, Princeton, N. J„ 1957. Беллман. Динамическое программирование. М. Изд-во иностран- ной литературы, 1960. Bellman R. Adaptive Control Process: A Guided Tour. Princeton University Press, Princeton, N. J., 1961. Беллман. Процедси регулирования с адаптаХией. М., «Наука», 1964. Bellman R. and Dreyfus S. Applied Dynamic Programming. Princeton University Press, Princeton, N. J., 1962. Беллман, Дрейфус. Прикладные задачи динамического про- граммирования. М., «Наука», 1965. В е 11 r a m i E. J. and М с G i 11 R. A Class of Variational Problems in Search Theory and the Maximum Principle. Operations Research, XIV, № 2, p. 267—78, 1966. В erge С. Topological Spaces. Trans. by Patterson E. M., Oliver and Boyd, LTD., Edinburgh and London, 1963. В e r g e C. and Ghouila-Houri A. Programming, Games and Transportation Networks. Trans. Merrington M. and Ramanujacha- ryulu C., John Wiley and Sons, Inc., New York, 1966. В i r k h о f f G. and MacLane S.A Survey of Modern Algebra. The Macmillan Company, Publishers, New York, 194il. Blackwell D. Discrete Dynamic Programming. Annuals of Mathe- matical Statistics, XXXIII, p. 719—26, 1962. Boot J. C. G. On Sensitivity Analysis in Convex Quadratic Program- ming Problems. Operations Research, XI, № 5, p. 771—86, 1963. Boot J. C. G, Quadratic Programming. Rand McNally and Company, Chicago, 1964. Bregman L. M. The Method of Successive Projection for Finding a Common Point of Convex Sets. Soviet Mathematics, VI, p. 688— 92, 1963. Б р э г м а н Л. М. Нахождение общей точки выпуклых множеств методом последовательного проектирования. ДАН, 1965, 162: 3, с. 487—490. В г inkle у S. R. Calculation of the Equilibrium Compositions of Sys- tems of Many Constituents. Journal of Chemical Physics, XV, p. 107—10, 1947. Brooks S.H.A Comparison of Maximum-Seeking Methods. Opera- tions Research, VII, № 4, p. 430—57, 1959. Bui-Trong-Lieu and H u a r d P. La Methode des Centres dans un Espace Topologique. Numerische Mathematik, III, № 1,p.57—67. Burger E. On Extrema with Side Conditions. Econometrica, XXIII, № 4, p. 451—52, 1955. Butler Т. and Martin A. V. On a Method of Courant for Mini- mizing Functionals. Jou»ial of Mathematics and Physics, XLI, p. 291—99, 1962. Camp G. D. Inequality-Constrained Stationary Value Problems. Jour- nal of the Operations Research Society of America, III, p. 548—50, 1955. Canon M. D. and C u 11 u m C. D. A Tight Upper Bound on the Rate of Convergence of the Frank-WoIfe Algorithm, IBM Watson Research Center, Yorktown Heights, N, Y. (Mimeo), 1967. Canon M. D„ Cullum C. D. and Polak E. (in press). Optimi- 294 zation, Control, and Algorithms. McGraw-Hill Book Company, Bat>- lishers, New York. C a r r о 11 С. W. The Created Response Surface Technique for Optimi- zing Non — Linear Restrained Systems. Operations Research, IX, No 2, p. 169—84. С а г г о 11 С. W. An Operations Research Approach to the Economic Optimization of a Kraft Pulping Process. The Institute of Paper Chemistry, Appleton, Wis, 1959. C a u с h у A. L. Methode Generate pour la Resolution des Systemes d'Equations Simuitanees. Comptes Rendus. Academie Science, Pa- ris, XXV, p. 536—38, 1847. C e s а г i L. Problem! di Lagrange con Vincoli Unilaterali. Academia delle Science di Torino Atti 98, Supplement, p. 88—119, 1964. Charnes A. and Cooper W. W. Chance-Constrained Program- ming. Management Science, VI, p. 73—9, 1959. Charnes A. and Cooper W. W. Management Models and Indu- strial Applications of Linear Programming. 2 vols. John Wiley and Sons, inc., New York, 1961. Charnes А., С о о p e r W. W. and К о r t a n e k K. Duality, Haar Programms and Finite Sequence Spaces. Proceedings of the Na- tional Academy oi Science, XLVIII, p. 783, 1962. Charnes A. and L e m k e C. Minimization of Nonlinear Separable Convex Functionals. Naval Research Logistics Quarterly, I, p. 301—12, 1954. C h e n e у E. W. and G о 1 d s t e i n A. A. Newtons Method of Convex Programming and Tchebycheff Approximation. Numerische Mathematik, I, p. 253—68, 1959. Chevassus M. Condition Suffisante de Convergence pour des Me- thods Iteratives de Minimisation, No HR 7713, Electricite de Fran- ce, 1967. С о 11 a t z L. Functional Analysis and Numerical Mathematics, Chap. 27. Academic Press Inc., New York, 1966. Connors M.M. and Teichroew D. Optimal Control of Dynamic Operations Research Models. International Textbook Co., Scranton, Pa., 1967. Co'ttle R. W. A Theorem of Fritz John in Mathematical Program- ming. Research Memorandum RM-—3858—PR, The RAND Corpora- tion, Sante Monica, Calif, 1963a. С о 111 e R. W. Symmetric Dual Quadratic Programs. Quarterly of Applied Mathematics, XXI, p. 237—43, 1963b. С о 111 e R. W. and D a n t z i g G. B. Complementary Pivot Theories of Mathematical Programming, Technical Report No 16, Depart- ment of Operations Research, Stanford University, Stanford, Calif, 1967. Courant R. Variational Methods for the Solution of Problems of Equilibrim and Vibrations. Bulletin American Mathematics Society, XLIX, p. 1—23, 1943. С о x e t e r H. S. M. The Golden section, Phyllotaxis, and Wythoff's game, Scripta Mathematica, p. 135—43, 1954. Crockett J.B.andChernoff H. Gradient Methods of Maximi- zation. Pacific Journal of Mathematics, Y, p. 33—50, 1955. Curry H. The Method of Steepest Descent for Non-linear Minimiza- tion Problems. Quarterly of Applied Mathematics, II, p. 258—61, 1944. D a n t z i g G. B. Linear Programming Under Uncertainty. Manage- ment Science, I, p. 197—206, 1955. D a n t z i g G. B. Linear Programming and extensions, princeton uni- versity Press, Princeton, N. J., 1963. Данциг. Линейное программирование, его применения и обобще- ния. М., «Прогресс», 1966. D a n t z i n g G. В., ,Е i s e n b е г g Е. and С о 111 e R. W. Symmetric Dual Nonlinear Programs. Pacific Journal of Mathematics, XV, p. 809—12, 1965. D a n t z i g G. В., J о h n s о n S. and White W. A Linear Program- ming Approach to the Chemical Equilibrium Problem, Management Science, V, p. 38—43, 1958. D a v i d о n W. C. Variable Metric Method for Minimization, A. E. C. Research and Development Report, ANL—5990 (Rev.), 1959. Debreu G. Representation of a Preference Ordering by a Numerical Function, p. 159—65 in eds. Thrall R. M., Cooms C. H. and Da- vis R. L., Decision Processes. John Wiley and Sons, Inc., New York, 1954. Debreu G. Integration of Correspendences. Proceedings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability, II, Part I, eds. L. Le Corn and Neyman J. University of California Press, Berkeley, p. 351—72, 1967. Dennis J. В., Mathematical Programming and Electrical Networks, MIT Press, Cambridge, Mass, 1959. Денни с. Математическое программирование и электрические цепи. М., Изд-во иностранной литературы, 1961. D'Epenoux F. Sur un probleme de production et de stockage dans Caleatoire, Revue Francaise de Recherche Operationnelle, IV, No 1, p. 3—15./A Probabilistic Production and Inventory Problem, Ma- nagement Science, X (1963), p. 98—108. (A translation with some modifications of the French original.) D ' E s о р о D., A Convex Programming Procedure. Naval Research Logistics Quarterly, VI, No 1, p. 33—42, 1959. D о г n W. S. A Duality Theorem for Convex Programs, IBM Journal Research and Development, IV, p. 407—13, 1960a. D о r n W. S. A Symmetric Dual Theorem for Quadratic Programs. Journal of Operations Research Society of Japan, II, No 93, 1960b. D о r n W. S. Duality in Quadratic Programming. Quarterly of Applied Mathematics, XVIII, p. 155—62, 1960e. D о r n W. S. Self-Dual Quadratic Programs. Journal of the Society for Industrial and Applied Mathematics, IX, p. 51—4, 1961. D о г n W. S. Non-Linear Programming—A Survey. Management Science, IX, p. 171—208, 1963. Eggleston H.G. Convexity. Cambridge Tracts in Mathematics and Mathematical Physics, No 47, Cambridge University Press, Lon- don, 1963. E r e m i n I. I. The Relaxation Method of Solving Systems of Inequa- lities with Convex Functions on the Left Sides. Soviet Mathema- tics, VI, p. 219—22, 1965. Еремин И. И. Релаксационный метод решения систем неравенств с выпуклыми функциями в левых частях. ДАН, 1965, 160:5, с. 994—996. F a r k a s J. Uber die Tlieorie der einfachen Ungleichungen. Journal fur die reine und angewandle Mathematic, CXXIV, p. 1—27. 1901. 296 F e n с h е 1 W. Convex Cones, Sets, and Functions. Lecture Notes, De- partment of Mathematics, Princeton University, 1953. F i а с с u A. V. Sequential unconstrained Minimization Methods for Nonlinear Programming. Unpublished Ph. D. dissertation, North- western University, Evanston, III, 1967. Fiacco A. V. and McCormick G.P. Programming Under Non- linear Constraints by Unconstrained Minimization: A Primal — Dual Method, RAC—TP—96, Research Analysis Corp., McLean, Va, 1963. Fiacco A. V., М с С о г m i с k G. P. Computational Algorithm for the Sequential Unconstrained Minimization Technique for Nonli- near Programming. Management Science, X, No 2, 601—17, 1964а. Fiacco A. V., М с С о r m i с k G. P. The Sequential Unconstrained Minimization Technique lor Nonlinear Programming, A Primal — Dual Method, Management Science, X, No 2, p. 360—66, 1964b. Fiacco A. V., McCormick G. P. SUMT Without Parameters. System Research Memo. No 121, Tech. Inst., Northwestern Univer- sity, Evanston, 111, 1965a. Fiacco A. V., McCormick G. P. The Sequential Unconstramed Minimization Technique for Convex Programming with Equality Constraints, RAC-TP-155, Research Analysis Corp., McLean, Va, 1965b. Fiacco A.V.,M'cCormick G. P. Extensions of SUMT for Non- linear Programming Equality Constraints and Extrapolation. Ma- nagement Science, XII, No 11, p. 816—28, 1966. F i n k b e i n e r FI. D. T. Introduction to Matrices and Linear Trans- formations. Freeman W. H. and Co., Publishers, San Francisco, 1960. Fleming W. Functions of Several Variables. Addison-Wesley Publi- shing Co., Inc., Reading, Mass, 1965. Fletcher R. Function Minimization Witliout Evaluating Derivatives: A Review. The Computer Journal, VIII, No 1, p. 33—41, 1965. Fletcher R. and Р о w e 11 M. J. D. A Rapidly Convergent Descent Method for Minimization. The Computer Journal, VI, p. 163, 1963, Fletcher R. and Reeves C. M. Function Minimization by Conju- gate Gradients. The Computer Journal, VII, No 2, p. 149—54, 1964. Forsythe G. E. Computing Constrained Minima with Lagrange Multipliers. Journal of the Society for Industrial and Applied Ma- thematics, III, p. 173—78, 1955. Forsythe G. E. On the Asymptotic Directions of the s — Dimensio- nal Optimum Gradient Method, Technical Report No CS 61, Com- puter Science Department, Stanford University, Stanford, Calif, 1967. Frank M. and W о 1 f e P. An Algorithm for Quadratic Program- ming. Naval Research Logistics Quarterly, III, p. 95—110, 1956. F r i s h K. R. The Logarithmic Potential Method of Convex Program- ming, (Memo.) Univ. Inst. of Economics, Oslo, 1955. F u a r e P. and H u а г d P. Resolution de Programmes Mathemati- ques a Fonction Non Lineaire par la Methode du Gradient Reduit. Revue Francaise de Recherche Operationnelle, IX, No 36, p. 167— 206, 1965. Gale D. The Theory of Linear Economic Models. McGraw-Hill Book Company, New York, 1960. Г е и л. Теория линейных экономических моделей. М., Изд-во ино- странной литературы, 1963. 20—71 297 6 a s s §. t. Linear Programming, Methods . and Applications. McQraw-Hill Book Company, New York, 1958. Г а с с. Линейное программирование (методы и приложения). М., Физматгиз, 1961. G е о f f r i о п А. М. Strictly Concave Parametric Programming,' art I: Basic Theory. Management Science, XIII, No 3, p. 244—RJ, 1966. Geoffrion A.M. Strictly Concave Parametric Progr imrning, Part II: Additional Theory and Computational Consideratii ns. Ma- nagement Science, XIII, No 5, p. 359—70, 1967. G i Ь b s J. W. On the Equilibrium of Heterogeneous Substance--', The Scientific Papers of J. Willard Gibbs 1. Dover Publications, Inc., New York, 1961. Glover F., Truncated Enumeration Methods for Solving Pure and Mixed Integer Linear Programs, Working Paper No 27, Operations Research Center, University of California, Berkeley, 1966. Goldstein A. Cauchys Method of Minimization. Numerische Mathe- matic, IV, p. 146—50, 1962. Goldstein A. Convex Programming and Optimal Controls. SIAM Journal on Control, III, No 1, p. 142—46, 1965a. Goldstein A. On Steepest Descent. SIAM Journal of Control, III, No '1, p. 147—51, 1965b. Goldstein A. Minimizing Functionals on Normed Linear Spaces. SIAM Journal on Control, IY, No 1, p. 194—210, 1966. Goldstein A. and К r i p k e B. R. Mathematical Programming by Minimizinig Differentiable Functions. Numerische Mathematic, VI, p. 47—8, 1964. Graves R. L. and W о 1 f e P. Recent Advances in Mathematical Programming. McGraw-Hill Book Company, New York, '1963. H a d 1 e у G. F. How Practical is Nonlinear Programming? Product Engineering XXXI, p. 78—80, 1960, H a d 1 e у G. F. Linear Algebra. Addison-Wesley Publishing Co., Inc., Reading, Mass, 1961. H a d 1 e у G. F. Linear Programming. Addison-Wesley Publishing Co., Inc., Reading Mass, 1962. H a d 1 e у G. F. Nonlinear and Dynamic Programming. Addison-Wes- ley Publishing Co., Inc., Reading, Mass, 1964. Хэдли. Нелинейное и динамическое программирование. М., «Мир», 1967. H a I m a s P. R. Finite Dimensional Vector Spaces. (2nd ed.) D. Van Nostrand Company, Inc., Princeton, N. J., 1&58. Hancock H. Theory of Maxima and Minima, Dover Publications, Inc., New York, 1960. Hanson M.A.A Duality Theorem for Nonlinear Programming with Nonlinear Constraints, Australia Journal of Statistics, III, 1961. H e s t e n e s M. R., Calculus of Variations and Optimal Control Theo- ry. John Wiley and Sons, Inc., New York, 1966. Hestenes M.R. and S t i e f e 1 E. Methods of Conjugate Gradients for Solving Linear Systems. Journal of Research of the National Bureau of Standards, XLIX, p. 409, 1952. H i 1 d r e t h C. A Quadratic Programming Procedure, Naval Research Logistics Quarterly, XIV, p. 79—85, 1957. H i 11 i e r F. S. and Lieberman G.J. Introduction to Operations Research. Holden—Day, Inc., Publisher, San Francisko, 1967. 298 Himsworth F.R.,Spendley W. and H e x t G. R. The Sequen- tial Application of Simplex Design in Optimization and Evolutio- nary Operation. Technometrics, IV, p. 441, 1962. Hitch С. J. and M с К e a n R. N. The Economics of Defense in the Nuclear Age. Harvard University Press, Cambridge, Mass, 1960. Houthakker H. The Capacity Method of Quadratic Programming. Econometrica, XXVIII, No 1, p. 62—87, 1960. Howard R. Dynamic Programming and Markov Processes. MIT Press, Cambridge, Mass, 1960. H u T. Minimum Convex — Cost Flows in Network, RM—4263—PR. The RAND Corporation, Santa Monica, Calif, 1964. H u a r d P. Dual Programs. Journal Research and Development. VI, p. 137—39, 1962. H u a r d P. Method of Centers, Chap. 7 in Non-Linear Programming. ed. J. Abadie, John Wiley and Sons, Inc., New York, 1967. H u r w i с z L. Conditions for Economic Efficiency of Centralized and Decentralized Structure, p. 169 in Value and Plan. ed. Gregory Grossman. University of California Press. Berkeley and Los Ange- les, 1960. Ivanov V.-A General Approximation Method for Solving Linear Problems. Soviet Mathematics, III, No 2, p. 415—18, 1962a. Иванов В. Об одном общем приближенном методе решения ли- нейных задач. ДАН СССР, 1962, 143 : 3. Ivanov V. Algorithms of Rapid Rescent. Soviet Mathematics, III, No 2, p. 476—79, 1962b. Иванов В. iB. Об алгоритмах быстрого спуска. ДАН, '1968, 143:4, с. 775—778. John F. Extremum Problems with Inequalities as Side Condi- tions, pp. 187—204 in Studies and Essays Courant Anniversary Volume, ed. K. 0. Friedrichs, 0. E. Neugebauer, and J. J. Stoker, John Wiley and Sons, Inc. New York, 1948. K a 1 m a n R. E. and Bertram J.E. Control System Analysis and Design Via the Second Method-of Liapunov, I and II. Journal of Basic Engineering, LXXXII, p. 371—400, 1960. Kantorovich L. V. and Akilov G. P. Functional Analysis in Normed Spaces, Chap 15. The Macmillan Company, Publishers, New York, 1964. Канторович Л. В., Акилов Г. П. Функциональный анализ в нормированных пространствах. М., фиэматгиз, ;1959. Karamardian S. Duality in Mathematical Programming, ORC 66—2. Operations Research Center, University of California, Berke- ley, 1966. K a r 1 i n S. Mathematical Methods in Theory of Games, Programming, and Economics, vois. I and II, Addison — Wesley Publishing Co., Inc., Reading, Mass, 1959. К а р л и H. Математические методы в теории игр, программировании, экономике. М., «Мир», 1964. •Kelley J. L. General Topology. D. Van Nostrand Company, Inc., Princeton, N. J., 1963. К e 11 у J. E. The Cutting-Plane Method for Solving Convex Prog- rams. Journal of the Society for Industrial and Applied Mathema- tics, VIII, No 4, p. 703—12, 1960. K i e f e г J. Sequential Minimax Search for a Maximum, Proceedings of the American Mathematics Society, IV, p. 502—6, 1963. К о о p m a n s Т. ed. Activity Analysis of Production and Allocation, John Wiley and Sons, Ine., New York, 1981. 2o* т К ч h n H. W. and Tucker A. W. Nonlinear Programming, in Pro- ceedings of the Berkeley Symposium оч Mathematical Statistics and Probability, ed. J. Neyman. University of California Press, Berkeley and Los Angeles, California, n, 481—92, 1951. Kunzi H. P. and Krelle W. Nonlinear Programming. Blaisdell Publishing Co., Inc., Waltham, Mass, 1966. Кюнци, Крелле. Нелинейное программирование. М., «Советское радио», 1965. La Sail e J. and Lefschetz S. Stability by Liapunov's Direct Method. Academic Press Inc.. New York, 1961. Leitmann G. ed. Optimization Techniques: With Applications to Aerospace Systems, Academic Press Inc., New York. 1962. Методы оптимизации с приложениям;; к механике космического по- лета. Под ред. Ж. Лейтмаяа. М., «Наука», 1985. Lemke С. E. A Method for Solution of Quadratic Programs. Mana- gement Science, VIII, No. 4, p. 442—53, 1962. Lemke С. E. Bimatrix Equalibrium Po'nts and Mathematical Pro- gramming. Management Science, XI, No 11, p. 681—89, 1965. Lemke С. E. and Howson J. T. Equilibrium Points of Bimatrix Games. Journal of the Society for Industrial and Applied Mathe- matics, XII. No 2. p. 413—23, 1964. Lhermitte P. and Bessiere F. Sur les Possibilites de la Pro- grammation Non Lineaire Appliquee an Choix des Investissements. Actes de la 3 Conference Internationale de Recherche Operationel- le, Oslo, (Dunod). p. 597—609, 1963. L i a p u n о v A. M. Probleme General de la Stabilite du Movement, Ann. Fac. Sci. Toulouse. IX. p. 203—475, 1907. Malinvaud E. Statistical Methods of Econometrics, p. 310—14. Rand McNally and Company, Chicago, III, 1966. Mangasarian 0. L. Duality in Nonlinear Programming. Quar- terly of Applied Mathematics. XX, p. 300—302, 1962. Mangasarian O.L. Pseudo-Convex Functions. SIAM Journal on Control, III, No 2, p. 281—90, 1965. Mangasarian O.L. and F г о m о v i 1 z S. The Fritz John Neces- sary Optimality Conditions in the Presence of Equality and Ine- quality Constraints. Journal of Mathematical Analysis and Appli- cation, XVII, No 1, p. 37—47. Г967. Ma.ngasarian 0. L. and Ponstein J. Minimax and Duality in Nonlinear Propramming. Journal of Mathematical Analysis and Applications. XI, No 1—3. о. 504—18, 1965. M a n n e A. S. Scheduling of Petroleum Refinery Operations. Harvard University Press, Cambridge, Mass, 1956. Manne A. S. Linear programming and Seauential Decisions. Mana- gement Science. VI, No 3, p. 259—67, I960. Markowitz H. The Optimization of a Quadratic Function Subject to Linear Constraints. Naval Research Logistics Quarterly, III, p. 111—33, 1956. Markowitz H. Portfolio Selection (Cowles Foundation Monograph № 16). John Wiley and Sons, Inc.. New York, 1959. Martin D. W. and Tee G. J. Iterative Methods for Linear Equa- tions With Symmetric Positive Definite Matrix. The Computer Journal, IV, p. 242—54, 1961. McCormick G. P. and Z a n g w i 11 W. I. A Technique for Calcu- lating Second—Order Optima, Research Analysis Corp., McLean, Virginia (mimeo.), 1967, 800 Michael E. Topologies on Space of Sets, Transactions American Mathematics Society, LXXI, p. 151—82, 1951. Miller С. The Simplex Method for Local Separable Programming. Chap. 12 in Recent Advances in Mathematical Programming, Eds. R. Graves and P. Wolfe, McGraw-Hill Book Company, New York, 1963. N elder J. A. and Mead R. A Simplex Method for Function Mi- nimization. The Computer Journal, VIII, No. 3, p. 308—13, -'1965. Nemhauser G. L. Introduction to Dynamic Programming. John Wiley and Sons, Inc., New York, 1966. N i k a i d о H. On von Neumann's Minimax Theorem. Pacific Journal of Mathematics, IV, p. 65—72, 1964. Oliver T. and W i 1 d e D. J. Symmetric Sequential Minimax Search for a Maximum. Fibonacci Quarterly, II, No. 3, p. 169—75, 1964. Penrose R. A Generalized Inverse for Matrices. Proceedings of the Cambridge Philosophical Society, LI, p. 406—13, 1955. Pie'trzykowski T. Application of the Steepest Descent Method to Concave Programming. P. 185—89 in Proceedings of the IFIPS Congress, North Holland Coin., Amsterdam, Holland, 1962. Pisano Leonardo (Fibonacci) Scritti, No 1, p. 283—84, 1857. P о 1 a k E. and D e p а г i s M. An Algorithm for Minimum Energy Control, Memo ERL—M225, University of California, Berkeley, 1967. Pomentale T. A. New Method for Solving Conditioned Maxima Problems. Journal of Mathematical Analysis and Application, X, p. 216—20, 1965. Pontryagin L. S., Boltyanskii V. G., Gamkrelid- z e iR. V. and Mischenko E. F. The Mathematical Theory of Optimal Processes. Translated by K. K. Trinogoff, John Wiley and Sons, Inc., New York, 1962. Математическая теория апгимальных процессов. Авт.: Л. С. Понтря- гин, 'В. Г. Болтянский, Р. ;В. Гамкрелидзе, E. Ф. Мищенко. М., «Наука», 1969. Р о w e 11 M. J. D. An Iterative Method for Finding Stationary Values of a Function of Several Variables. The Computer Journal, V, No 2, p. 147, 1962. P о w e 11 M. J. D. An Efficient Method for Finding the Minimum of a Function of Several Variables without Calculating Derivatives, The Computer Journal, VII, No 2, p. 155—62, 1964. R e i t e г S. Efficiency and Prices in the Theory of an International Economy. Technical Report No '13, Stanford University, Stanford, Calif., Г954. R i 1 e у V. and G a s s S. J. Linear Programming and Associated Techniques. John Hopkins Press, Baltimore, Md., 1958. Rissanen J. On Dualil Without Convexity, RJ389, IBM San Jose Research Laboratory, San Jose, Calif., 1966. R i 11 e r K. Stationary Points of Quadratic Maximum Problems, Z. Wahrscheinlichkeitstheorie Verw, Geb 4, p. 149—58, 196'5. R i 11 e r K. A Method for Solving Maximum Problems with a Non- concave Quadratic Objective Function. Z.Wahrscheinlichkeitstheo- rie Verw, Qeb 4, p. 340—51, 1966. Roekafeller R.t. Duality Theorem» for Convex Functions. Bul- 301 letin of the American Mathematics Society, LXX, p. 189—92, 1960. Rockafeller R.T. Convex Analysis. Princeton University Press, Princeton, N. J., 1970, Рокфеллер Р. Т. Выпуклый анализ. М., «Мир», '1973. R о s e n J. В. The Gradient Projection Method for Nonlinear Pro- gramming, Part I, Linear Constraints. Journal of the Society for Industrial and Applied Mathematics, VIII, No 1, p. 181—217, I960. R о s e n J. B. The Gradient Projection Method for Nonlinear Program- ming, Part II, Nonlinear Constraints. Journal of the Society for Industrial and Applied Mathematics, IX, No 4, p. 514—32, 1961. R о s e n J. B. Convex Partition Programming, p. 159—76 in Recent Advances in Mathematical Programming, eds. Graves R. L. and Wolfe P., McGraw-Hill Book Company, New York, 1963. R о s e n J. B. Existence and Uniqueness of Equilibrium Solutions for Concave n-Person Games. Econometrica, XXXIII, No 3, p. 520—34, 1965. Rosen J. B. and Ornea J. C.'Solution of Nonlinear Programming Problems by Partitioning. Management Science, X, No 1, p. 160—73, 1963. Rosenbrock H.H.An Automatic Method for Finding the Grea- test or Least Value of a Function. The Computer Journal, III, No 2, p. 175, 1960. Royden H. L. Real Analysis, The MacMillian Company, Publishers, New York, 1963, Rutenberg D. Large Special Matrix Structures' and the Convex Simplex Method. Working Paper No 216, Center for Research in Management Science, University of California, Berkeley, 1967. Saaty T. L. and B ram J. Nonlinear Mathematics. P. 166—70, McGraw-Hill Company, New York, 1964. Samuelson P. A Note on the-Pure Theory of Consumers Beha- vior. Econometrica, XVII, p. 61—71 and 353—54, 1938. Samuelson P. Foundations of Economic Analysis. Harvard Uni- versity Press, Cambridge, Mass. 1947. Самуэльсон П. Экономика (тер. с англ.). М., «Прогресс», 1964. Sanders J. L. A Nonlinear Decomposition Principle. Operations Research, XIII, No 2, p. 266—71, 1965. Schecter S. Interation Methods for Nonlinear Programming. Transactions American Mathemat. Society, CIV, p. 179—89, 1962. Shah В. V,, B u e h 1 e r R. J. and К e rn p I h о r n e 0. The Method of Parallel Tangents (Partan) for Finding an Optimum. Office of Naval Research Report, NR-042-207, No 2, 1961. Shah B. V., B u e h 1 e r R. J. and i\ e m p t h о r n e 0. Some Algo- rithms for Minimizing a Function of Several Variables. Journal of the Society for Industrial and Applied Mathematics, XII, No 1, p. 74—92, SIAM Journal on Control (1966), See particularly IV, No 1, 1964. Simonnard M. Linear Programming. Translated by W. S. Jewell. Prentice-Hall, Inc., Englewood Cliffs, N. J., 1966. S i m m о n s G. F. Topology and Modern Analysis. McGraw-Hill Book Corn., New York, 1963. Slater M. Lagrange Multipliers Revisited; A Contribution to Non- linear Programming, Cowie» Cominigsion Discussion Paper Math. 403, 1950. 302 Spang H. A. A Review of Minimization Teehniques for Nonlinear Functions. Journal of the Society for Industrial and Applied Ma- thematics, IV, No 4, p. 343—65, 1962. Stiefel E. Relaxationsmethoden bester Strategic zur Losung li- nearer Gleichungssysteme. Commentarii Math., Helvetici 29, p. 157—79, 1955. Sloe г J. Duality in Nonlinear Programming and the Minimax Theo- rem. Numerische Mathematik, V, p. 371—79, 1963. Stone R. Linear Expenditure Systems and Demand Analysis: An Application to the Pattern of British Demand. The Economic Jour- nal, LXIV, p. 511—27, 1964. S t о n g R. E. A Note on the Sequential Unconstrained Minimization Technique for Non-Linear Programming. Management Science, 12, 1, No 12, p. 142-44, 1965. Theil H. and van de P a n n e C. Quadratic Programming as an Extension of Classical Quadratic Maximization. Management Sci- ence, VII, No 1, p. 1—20, 1960. T i n t e г G. Stochastic Linear Programming with Applications to Agricultural Economics. In Second S"mposium in Linear Pro- gramming, p. 197—228, 1955. Т о p k i s D. M. and V e i n о 11 A. F. On the Convergence of Some Feasible Direction Algorithms for Nonlinear Programming. SIAM Journal on Control, V, No 2, p. 268—79, 1967. Vajda S., Mathematical Programming. Addison-Wesley Publishing Co., Inc., Reading, Mass, 1961. Van de Panne C. and W h i n s t о n A. The Simplex and Dual Me- thod for Quadratic Programming. Operational Research Quarter- ly, XV, p. 355—88, 1964. Van Slyke R.M. and Wets R. J. B. L-Shaped Linear Programs with Applications to Optimal Control and Stochastic Program- ming. ORC-66-17, Operations .Research Center, University of Ca- lifornia, Berkeley, 1966. V e i n о 11 Jr., A. F. The Supporting Hyperplane Method for Uni- modal Program., Operations Research, XV, No 1, p. 147—52, 1967. Wagner H. Principles of Operations Research, Prentice-Hall. Inc., Engie-wood Cliffs, N. J., 1969. Вагнер Г. Основы исследования операций. М., «Мир», 1973. W a r g a J. A Convergent Procedure for Convex Programming. Jour- nal of the Society for Industrial and Applied Mathematics, XI, No 1, p. 579—87, 1963a. Warga J. Minimizing Certain Convex Functions. Journal of the Society for Industrial and Applied Mathematics, XI, No 1, p. 588—93, 1963b. Wegner P., A Nonlinear Extension of tho Simplex Method. Mana- gement Science, VII, No 1, p. 43—50, 1960. Wets R. Programming under Uncertainty: The Equivalent Convex Program. SIAM Journal on Applied Math., XIV, p. 89—'105, 1966. White W. В., John son S. M. and Dantzig G. B. Chemical Equilibrium in Complex Mixtures. Journal of Chemical Physics, XXVIII, p. 751-R5, 1968. Wilde D. J., Optimum Seeking Methods, Prentice-Hall, Inc., Engle- wood Cliffs, N. J., 1964. Уайлд Д. Дж. Методы поиска экстремума. М., «Наука», 1967. Wilde D. J. and B e i g h 11 e г С. S. Foundations of Optimization. Prentice-Hall, Inc., Englewood Cliffs, N. J., 1967. 303 W i 1 s о n R. В. A Simplician Algorithm for Concave Programming, Unpublished Ph. D. dissertation, Harvard University Graduate School of Business Administration Boston, 1963. W о 1 f e P. The Simplex Method for Quadratic Programming. Econo- metrica, XXVII, No 3, p. 382—98, 1959. Wolfe P. Accelerating the Cutting Plane Method for Non-linear Programming, Journal of the Society for Industrial and Applied Mathematics, IX, p. 481—88, 19Sla. Wolfe P. A Duality Theorem for Nonlinear Programming. Quartely of Applied Mathematics, XIX, p. 239—44, 1961b. Wolfe P. An Extended Simplex Method. Notices of the American Mathematics Society, IX, No 4, p. 308 (Abstract), 1962. Wolfe P. On the Convergence of Gradient Methods Under Con- straints. IBM Research Report RZ-204, IBM Zurich Research La- boratories, Ruschliken, Zurich, Switzerland, 1966. Z a n g w i 11 W. I. Minimum Concave Cost Flows, in Certain Net- works. Management Science-A, XIV, No 7, p. 429—50, 1966a. Z a n g w i 11 W. I. The Shortest Route Problem Under Either Con- cave or Convex Costs. Presented at 12tli Annual Operations Rese- arch Society of American Meeting, Santa Monica, Calif, 1966b. Zangwill W. I. A Deterministic Multi-Product, Multi-Facility Pro- duction and Inventory System. Operations Research, XIV, No 3, p. 486—508, 1966с. Zangwill W. I. A Backlogging Model and a Multi-Echelon Model of a Dynamic Economic Lot Size System—A Network Approach, Working Paper 177, Center for Research in Management Science, University of California, Berkeley, Calif, 1966d. Zangwill W. I. A deterministic Multi-Period Production Schedu- ling Model with Backlogging. Management Science—A, XIII, No 1, p. 105—19, 1966e. Zangwill W. I. Production Smoothing of Economic Lot Sizes with Non-Decreasing Requirements. Management Science—A, XIII, No3, p. 191—209, 1966f. Zangwill W. I. Convergence Condition for Nonlinear Program- ming Algorithms, Working Paper No 197, Center for Research in Management Science, University of California, Berkeley, Calif., 1966g. Zangwill W. I. Non-linear Programming via Penalty Functions. Management Science—A, XIII, No 5, p. 344—58, 1967a. Zangwill W. I. Extensions of Concavity, Minimax, Duality and Optimality, Working Paper No 219, Center for Research in Mana- gement Science, University of California, Berkeley, 1967b. Zangwill W. I. The Piecewise Concave Function. Management Science—A, XIII, No 11, p. 900—12, 1967e. Zangwill W. I. Application of the Convergence Conditions, 6th Symposium on Mathematical Programming, Aug. 14—18, 1967, Princeton University, Princeton, N. J., 1967d. Zangwill W. I. An Algorithm for the Chebyshev Problem—with an Equivalence to Non-linear Programming, Management Sci- ence—A, XIV, No 1, p. 58—78, 1967e. Zangwill W. I. Minimizing a Function Without Calculating De- rivatives. The Computer Journal, X, No 3, p. 293—96, 1967f. Zangwill W. I. The Convex Simplex Method. Management Sci- ence—A, XIV, No 3, p. 221—38, 1967g. 304 Zangwill W. I. A Decomposable Nonlinear Programming Appro- ach. Operations Research, XV, No 6, p. 1068—87, 1967h. Z о u t e n d i j k G. Methods of Feasible Directions, Amsterdam. Else- vier Publishing Co., Amsterdam, Holland, i960. Зойтендейк. Методы возможных направлений. М. Изд-во ино- странной литературы, 1963. Zontendijk G. Nonlinear Programming: A Numerical Survey. SIAM Journal on Control, IV, № 1, p. 194—210, 1966. 7uhovickii S. I., P о 1 i a k R. A. and P r i m a k M. E. An Al- gorithm for the Solution of a Problem of Convex Cebysev Appro- ximation. Soviet Mathematics, IV, No 4, p. 901—4, 1963. Зуховяцкяй С. И., Поляк Р. А., Примак М. E. Алгоритм для решения задачи выпуклого чебышевкжого приближения. ДАН СССР, 1963, 151 : 1. Z u h о v i с k i i S. I., P о 1 i a k R. Д., P r i m a k M. E. An Algorithm for the Solution of the Convex Programming Problem. Soviet Ma- thematics, IV, No 6, p. 1754—57, 1963. Зуховицкий С. И. Алгоритм для решения задачи выпуклого программирования. ДАН СССР, 1963, 153:5. Автономные отображения 81 Алгоритм ВСМ—СН («выпук- лый симплексный — метод— сопряженные направления») 175, 183 — Лагранжа 198, 205 — максимизация квадратичной функции 125 — опорной гиперплоскости 276 — отсечений 267 — — вогнутый 272 — симплексного метода 291 — скорейшего спуска Коши 102 — сопряженных направлений 128 — сходящийся 214 — е-возмущений 261 Алгоритмическая сходимость 211 Алгоритмическое отображение 148 Аппроксимации квадратичные 104 Вектор градиента 29 — направления 29 . Векторы-столбцы 287 Вогнутые функции 32 — —, интегрирование 59 — —, максимизация 165 Вогнутый алгоритм отсечений 272 Возможное направление 38 Выпуклость допустимой обла- сти с вогнутыми ограниче- ниями 34 Выпуклые множества 31 Выпуклый симплексный метод 149, 162 — — —, модификация 264 — — —, сходимость для за- дачи квадратичного про- граммирования .175 Вырождение 156 Гамильтониан 76 Геометрическое программиро- вание 18 306 ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ — —, двойственная задача 67 Гиперплоскость 290 Градиент 49 Двойственности теория 48, 235 — —, экономическая интерпре- тация 62 Двойственнность 235 Двойственный метод отсечений 279 Допустимая пара для двой- ственной задачи 51 Допустимое множество (мно- жество планов) 13 — — звездоподобное 59 Допустимый вектор (план) 13 Достаточность условий Куна — Таккера для звездообразных множеств 59 Задача геометрического про- граммирования 20 — квадратичного программи- рования 175 — — —, метод субоптимиза- ции на многообразиях 188 — — —, сходимость выпукло- го симплексного метода 175 — — —, сходимость за конеч- ное число шагов 181 — максимизации на многооб- разиях 167 — нелинейного программиро- вания (НЛП)12 — — — с линейными ограни- чениями 146 — — — без ограничений 30 97, 102, 246 — одномерного поиска 114 — оптимального управления 20 — регрессии при определении выбора потребителем 16 — управления запасами 25 — химического равновесия 27 Заклинивание 253 Замкнутые множества 289 — отображения 84 Замкнутость 141, 160 Золотое сечение 115 Идентификация оптимальной точки 28 Квадратичное программирова- ние 23, 79 Квазивогнутые функции 39 Компактность 86, 141 Композиции отображений 91, 96 Лемма Фаркаша 290 Линейное программирование 23, 55, 79, 290 Максимизация функции в ли- нейном многообразии 174 Математическое программиро- вание 5 Метод барьеров 229 — возможных направлений 246 — затраты—эффективность 15 — Лагранжа для задачи НЛП 196 — линейной аппроксимации 147 — отсечений 269 — сопряженных градиентов 132 — центров 196 — циклического координатного спуска 120 — штрафных функций Й28 — е-возмущений 257 Методы возможных направле- ний 98 — оптимизации для задач без ограничений 6 — — — с ограничениями 6 — — второго порядка 107 — построения сопряженных на- правлений 125 — решения задачи НЛП 196 — ускорения сходимости 174 — штрафных функций и барь- еров 225 Множество планов 15 Невогнутая задача с двой- ственным равенством 59 Незамкнутое отображение 85 Нелинейное программирование 5, 8, 12 — —, геометрическая интер- претация 26 — —, области применения 14 — —, применение в науке 16 Нелинейный регрессионный . анализ 25 Непрерывность 14.1, 288, 289 Ньютона модифицированный метод 103 Объективно обусловленные оценки (множители Лагран- жа, двойственные перемен- ные, теневые цены, припи- санные оценки) 65 Оптимальная пара 51 — точка 13 Оптимальное управление и принцип максимума 75 Ортогональные направления 134 Отображения точка — множе- ство 81 Переменные состояния 20 — управления 20 Планирование производства 24 Подпространства и многообра- зия 123 Подходящая точка 87, 104,201 Полупространство 290 Предел 287 Принцип максимума 76 Проектирование парового кон- денсатора 25 Производная по направлению 289 Псевдовогнутые функции 38 Псевдовыпуклые функции 38 Расстояние 287 Расширяющие шага 128 Ряд Тейлора 288 Свободная энергия Гиббса 26 Седловая точка 31, 48 — — и функция Лагранжа 49 Симплексный метод 291 Система разностных уравнений асимптотически устойчивая в целом 206 Смешанные алгоритмы 117, 120, 131, 139 Собственные векторы 108 — значения 108 Сопряженные направления 122 — —, построение из линейно- независимых направлений 133 Субоптимизация на многооб- разиях 177 307 Суперпозиция непрерывных функций 288 Теорема двойственности ли- нейного программирования 290 • — сходимости 87, 121, 211, 215 223 — — для методов возможных направлений 255 — — для методов отсечений 270 — — общая 219 — — первая 78 Теория Ляпунова 205 — сходимости 86 Точка дополняющая 189 — полудополняющая 189 Точная верхняя грань 142 — нижняя грань •144 Условие Куна — Таккера 40, 58, 64 — —, геометрическая интер- претация 45 — —, недостаточность 46 — — для ограничений — ра. венств 45 — —, применение к теории двойственности 62 — оптимальности 2-го порядка 107 — регулярности 43 Устойчивости основная теоре- ма 207 Фибоначчи параметры 115 Функции-ограничения 13 — свободной энергии Гиббса 26 Функция 288 — Лагранжа 48 — —, экономическая интерпре- тация 62 — позиномиальная 19 Химическое равновесие 26 Целевая функция 13 Цепное правило 289 Циклический координатный спуск 105 Частные производные 288 Эквивалентное определение за- мкнутых отображений 95 Явление заклинивания (заеда- ния) 245 — — в методе возможных на- правлений 248 Г л а в а 5. ЗАДАЧИ ББЗ ОГРАНИЧЕНИИ ...... \ ... 97 5.1. Зависимость подходящей точки от алгоритма . . 98 5.2. Методы возможных направлений и отображения М* и D .............. 98 5.3 Замкнутость отображения At' ....... 99 5.4. Алгоритмы для задач без ограничений . . . . 102 Приложение.'Процедуры одномерного поиска . . . . . 114 Глава 6. СМЕШАННЫЕ АЛГОРИТМЫ И КВАДРАТИЧНЫЕ МЕТОДЫ УСКО- РЕНИЯ СХОДИМОСТИ, ИСПОЛЬЗУЮЩИЕ СОПРЯЖЕННЫЕ НА- ПРАВЛЕНИЯ .............. 119 6.1. Смешанные алгоритмы и их использование для повы- шения скорости сходимости ........ 120 6.2. Сопряженные направления . ....... 122 6.3. Метод построения сопряженных направлений, исполь- .зующий только значения функции ...... 125 6.4. Метод сопряженных градиентов . . . . . . 132 Глава 7. НЕПРЕРЫВНОСТЬ, КОМПАКТНОСТЬ И ЗАМКНУТОСТЬ . . . 141 7.1. Максимум и верхняя грань ........ 141 7.2. Непрерывность, компактность и максимизация . . 143 Глава 8. НЕКОТОРЫЕ МЕТОДЫ ДЛЯ ЗАДАЧ С ЛИНЕЙНЫМИ ОГРАНИЧЕ- НИЯМИ ............... 146 8.1. Метод линейной аппроксимации ...... 147 8.2. Выпуклый симплексный метод ....... 149 8.3. Максимизация вогнутой функции субоптимизацией на многоабразиях ........... 165 Глава 9. МЕТОДЫ УСКОРЕНИЯ СХОДИМОСТИ И ЗАДАЧА КВАДРАТИЧ- НОГО ПРОГРАММИРОВАНИЯ .......... 174 9.1. Сходимость выпуклого симплексного метода для за- дачи квадратичного программирования . . . . 175 9.2. Метод субоптимизации на многообразиях для квадра- тичного программирования . ....... 188 Глава 10. НЕКОТОРЫЕ МЕТОДЫ РЕШЕНИЯ ЗАДАЧИ НЕЛИНЕЙНОГО ПРО- ГРАММИРОВАНИЯ С ПРИМЕНЕНИЕМ К ТЕОРИИ ЛЯПУНОВА ДЛЯ РАЗНОСТНЫХ УРАВНЕНИИ .......... 196 10.1. Метод центров ........... 197 10.2. Алгоритм Лагранжа .......... 198 10.3. Экономическая интерпретация ....... 205 10.4. Устойчивость систем конечно-разностных уравнений— теория Ляпунова .......... 205 310 Глава 11. НЕОБХОДИМЫЕ И ДОСТАТОЧНЫЕ УСЛОВИЯ СХОДИМОСТИ . . 211 И.!. Введение . ............ 211 11.2. Алгоритмы ......... ... z ' 11.3. Теоремы сходимости .......... z11 Глава 12. МЕТОДЫ ШТРАФНЫХ ФУНКЦИЙ И БАРЬЕРОВ ..... 225 12.1. Основы методов штрафных функций и барьеров . . 226 12.2. Метод штрафных функций ........ 231 12.3. Метод барьеров ........... z00 Глава 13. МЕТОД ВОЗМОЖНЫХ НАПРАВЛЕНИИ И ЯВЛЕНИЕ ЗАКЛИНИ- ВАНИЯ .......•..••••• 24Й 13.1. Отображение М3 ........... 245 13.2. Явление заклинивания в методе возможных направ- лений . ............. 248 13.3. Теорема сходимости для методов возможных направ- лений ...........••• 255 13.4. Метод е-возмущений ......... 257 Г л а в а 14. АЛГОРИТМЫ ОТСЕЧЕНИЙ ..."....... 267 14.1. Теория алгоритмов отсечений ....... 268 14.2. Вогнутый алгоритм отсечений . . . . . . . 272 14.3. Алгоритм опорной гиперплоскости ...... 276 14.4. Двойственный метод отсечений .... ... 279 Приложение. Необходимые сведения из общего курса мате- матики и линейного программирования ..... 287 Список литературы ............ 293 Предметный указатель ........... 306