ТЕОРИЯ И МЕТОДЫ СИСТЕМНОГО АНАЛИЗА М.ДЖ. ТОДД ВЫЧИСЛЕНИЕ НЕПОДВИЖНЫХ ТОЧЕК И ПРИЛОЖЕНИЯ К ЭКОНОМИКЕ ПЕРЕВОД С АНГЛИЙСКОГО Ю.Ф. КИЧАТОВА ПОД РЕДАКЦИЕЙ С.В. ЕМЕЛЬЯНОВА МОСКВА «НАУКА» ГЛАВНАЯ РЕДАКЦИЯ ФИЗИКО-МАТЕМАТИЧЕСКОЙ ЛИТЕРАТУРЫ 1983 32.81 Т 50 У ДК 62-5 О СЕРИЯ: "ТЕОРИЯ И МЕТОДЫ СИСТЕМНОГО АНАЛИЗА" Р е д а к ц и он на я коллегия серии академик ДМ. Гвишиачи (председатель) член-корреспондент АН СССР С.В. Емельянов (заместитель председателя) член-корреспондент АН СССР С.С. Шаталин доктор экономических наук ?.3. Мчльнер доктор технических наук Ю.С. Попков Michael J. Todd The Computation of Fixedd Points and Applications Springer-Veriag Berlin • Heidelberg • New York 1976 Вычисление неподвижных точек и приложения к экономике. Т о д д ММ. Дж./Пер. с англ. - М.: Наука. Главная редакция физико-математической литературы.!, 1983 г. - 112с. В монографии изложены методы вычисления неподвижных точек неппрерывных отображений, используемых для нахождения экономических равновесии. Подробно описаны алгоритмы, основанные на методе кусочно линейной гомотопии. I Проведено теоретическое сопоставление методйв и алгоритмов. Исследовано влияние эффектив- ных триангуляции на скорость сходимости. Книга предназначена для специалистов в области математической экономмики. Табл. 5, ил. 50, библ. 74. 1502000000-116 т 05 3(02)-83—— 197"83 ©by Springer-Veriag Berlin • HeidelUberg 1976. All Right*^ Reserved. Authorized translation from English language edition published by Sprir*iger-Verlag Berlin - Heidelberg -^ New York ©Перевод на русский язык. Издательств/0 "Наука", Главная редакция физико-математической литерат "УР1"1.1983. ОГЛАВЛЕНИЕ От редактора перевода ................................... 4 Предисловие .......................................... 5 Г л а в а I. Теорема Брауэра ................................ 7 Г л а в а II. Некоторые приложения теоремы Брау эра ................ 18 Глава III. Триангуляции ................................. 24 Глава IV. Алгоритмы поиска пестрых симплексов ................. 36 Г л а в а V. Обобщения теоремы Брауэра ........................ 47 Глава VI. Приложения теоремы Какутани и ее обобщений ............ 55 Глава VII. Первый алгоритм Ивза ........................... б2 Глава VIII: Алгоритм Меррилла ............................ 69 Глав а IX. Алгоритмы типа гомотопии ......................... 79 ГлаваХ. Триангуляции с непрерывным уменьшением резмера сетки ..... 84 Глава XI. Меры эффективности триангуляции ................... 95 Обозначения .......................................... 104 Литература ........................................... 105 Дополнение........................................... 109 ОТ РЕДАКТОРА ПЕРЕВОДА Формализация взаимодействия независимых участников сложных эко- номических процессов приводит к задачам, относительно которых до недавнего времени можно было делать только общие утверждения, ка- сающиеся существования решений. В конце 60-х годов наметились пути получения численных решений задач такого типа — стратегий в играх мно- гих лиц и равновесных цен в моделях общего экономического равновесия. Разработка принципиально новых вычислительных алгоритмов оказалась возможной благодаря эффективному использованию ряда глубоких ре- зультатов современной математики. Одна из идей — сведение решений к поиску неподвижных точек некоторых специально построенных функций или точечно-множественных отображений. Другая идея - превращение конструктивных доказательств существования неподвижных точек в вычислительные алгоритмы. Наконец, использование некоторого стандарт- ного рассуждения позволило унифицировать доказательство сходимости различных алгоритмов. Построенные на базе этих идей алгоритмы имеют одну интересную особенность: в отличие от методов математического программирования, где на каждом шаге уменьшается значение некоторого функционала, в алгоритмах вычисления неподвижных точек используют- ся другие критерии останова - комбинаторные. При реализации алгоритмов вычисления неподвижных точек возникли и были успешно решены различные технические проблемы, например, связанные с эффективным разбиением многомерных пространств на сим- плексы (триангуляция). В последнее время получены результаты, поз- волившие в целях ускорения сходимости учитывать ориентацию симплек- сов, линейность отдельных блоков моделей. При определенных условиях достигнута квадратичная скорость сходимости алгоритмов неподвижной точки. Круг задач, решаемых с помощью методов неподвижной точки, расширя- ется, не убывает поток публикаций по этой проблеме. Выход в свет пере- вода на русский язык книги Майкла Тодда, внесшего большой вклад в разработку методов- вычисления неподвижной точки, поможет читателю овладеть основными идеями и методами одного из плодотворных и быстро развивающихся направлений теоретических и прикладных исследований. Член-корреспондент АН СССР С.В. Емельянов ПРЕДИСЛОВИЕ Алгоритмы неподвижной точки находят различные приложения в мате- матической экономике, теории оптимизации, теории игр и при численном решении граничных задач. С момента выхода основополагающих работ Скарфа [56, 57]- о приближенном вычислении неподвижных точек непре- рывных отображений проделана большая работа по расширению области применимости и улучшению эффективности методов неподвижной точки. Большая часть полученных результатов так и осталась в исследователь- ских публикациях, хотя книга Скарфа [58] содержит исключительно четкое представление о силе методов неподвижной точки. Тем не менее, алгоритмы, описанные Скарфом, были усовершенствованы на основе более тонких методов рестарта и гомотопии Мерриллом [46, 49] и Ивзом и Сайгалом'[14, 16]. Для понимания этих более эффективных.алгоритмов следует познакомиться с понятием триангуляции и симплициального приб- лижения, тогда как Скарф делает упор на понятие примитивного множества. Эти лекции имеют целью познакомить более широкую аудиторию с самы- ми последними методами неподвижной точки и их применениями. Один такой подход основан на триангуляциях. Поэтому работы Скарфа цити- руются здесь в меньшей степени, чем они того вообще заслуживают. Кроме того, в своем изложении мы ограничились только приложениями к отыска- нию экономических равновесии и решению задач оптимизации. Хансен и Купманс [28] применяют методы неподвижной точки к вычислению инвариантного оптимального объема основных фондов в модели эконо- мического роста. Применения к теории игр обсуждаются в работах Скарфа [56, 58], Шепли [59] и Гарсия, Лемке и Люта [24]. В работах Аллговера [1] и Джеппсона [31] используются алгоритмы неподвижной точки для отыскания различных решений граничных задач. Бесконечномерные случаи обсуждают Фрейденфельдс [21] и Уилмут [73]. Теорема Шаудера о про- екциях (Фрейде нфельдс [21] и Смарт [61]) показывает, каким образом можно получить конечномерную аппроксимацию. Настоящее изложение проводится исключительно в терминах конечномерных пространств. Самые последние достижения, которые мы не смогли отразить, это теории ориента- ции Шепли [60], Лемке и Гротцингера [44], Тодда [66] и, в наиболее общем виде, Ивза [15] и Ивза и Скарфа [17], а также усовершенствова- ния алгоритмов и анализ сходимости Сайгала [53, 54]. Ивз [15] приводит обширную библиографию по проблеме. Книга построена следующим образом. В главе I дается классическое (неалгоритмическое) доказательство теоремы Брауэра, основанное на лемме Шпернера, и таким образом читатель подводится к некоторым 5 ПРЕДИСЛОВИЕ основным понятиям. Несколько приложений теоремы Брауэра описано в главе 11. Формальное изложение метода триангуляции приводится в главе III вместе с описанием некоторых важных частных триангуляции, которые используются в главе IV в алгоритмах вычисления приближений к неподвижным точкам непрерывных функций. Прикладные задачи из главы II служат для обоснования необходимости перехода от функций к точечно-множественным отображениям. В главах V и VI параллельно рассуждениям из шав I и II доказана и применяется теорема Какутани о неподвижной точке. В главе VII описан алгоритм для-вычисления непод- вижных точек по Какутани. Этот алгоритм и алгоритмы из главы IV неэф- фективны, если требуется хорошая аппроксимация. В главах VIII и IX мы описываем более сложные алгоритмы типа рестарт и гомотопии. Для алгоритмов типа гомотопии требуются специальные триангуляции, при- водимые в главе X. Наконец, в главе XI описаны некоторые меры, которые могут быть использованы для сравнения различных триангуляции при их использовании для вычисления неподвижных точек. В книгу включено много специально подобранных упражнений, направ- ленных на то, чтобы помочь читателю лучше усвоить излагаемый материал. Некоторые численные примеры приводятся в тексте. Предполагается, что читатель знаком с математическим анализом и линейным програм- мированием, в том числе с методом лексикографического разрешения вырожденности. Предполагаются известными также условия Куна - Так- •кераиз нелинейного программирования. Рукопись возникла из курса по вычислению неподвижных точек, кото- рый автор читал в Корнелльском университете весной 1975 года. Автор благодарит Майкла Коснара, Пьера Дежа, Прэдипа Дьюби, Этьена Лута, Сигео Муто, Боба Ровински и Прэкеша Шеноя за подготовку превосход- ных записей лекций. Национальный научный фонд по контракту СК-42092 оказал финансовую поддержку при написании рукописи. Автор благода- рен Кэти Кинг за прекрасную работу по перепечатке рукописи. Наконец, автор выражает благодарность своей жене Марине за поддержку и помощь. Майкл Тодд Глава 1 ТЕОРЕМА БРАУЭРА 1.1. Эта, по-видимому, наиболее знаменитая теорема о неподвижной точке утверждает, что непрерывная функция, отображающая и-клетку в себя, оставляет, по крайней мере, одну точку неподвижной. Голландский математик Л. Брауэр доказал этот результат в 1912 г. [5], используя тео- рию степени отображения. Эквивалентную теорему в случае дифферен- цируемых функций доказал ранее Боль [4], использовавший теорему Гри- на. В большей степени, чем существование неподвижных точек, нас интере- сует их вычисление; мы будем применять разработанный в более позднее время подход, основанный на чисто комбинаторной лемме Шпернера [62]. Этот подход является наиболее близким к алгоритмам, которые мы бу- дем разрабатывать, и механизм этого подхода окажется впоследствии очень полезным. Однако, чтобы избежать некоторых громоздких деталей, мы вначале дадим только интуитивное представление о симплексе и три- ангуляции. Строгое изложение содержится в главе III. В этом параграфе мы приводим формулировку теоремы Брауэра. В па- раграфе 1.2 показано, что достаточно привести доказательство для стан- дартного симплекса; там же приводятся некоторые примеры, подска- зывающие различные методы доказательства. В параграфе 1.3 мы сводим теорему Брауэра к лемме Шпернера, доказываемой в параграфе 1.4. 1.1.1. Определение. Функция h называется гомеоморфизмом, если она представляет собой однозначное отображение на, и обе функции h и Ь.~\ непрерывны. Замкнутой h-клеткой называется гомеоморфное отображение шара В", т.е. С — замкнутая п-клетка, если существует го- меоморфизм/г: В"-> С. 1.1.2. Теорема (Брауэр). Пусть С - замкнутая п-клетка, и пусть f: С ->• С непрерывна. Тогда f имеет неподвижную точку, т.е. существует точка д:*е Стакая, 4Tof(x*) =х*. 1.2. В этом параграфе мы покажем, что достаточно доказать теоре- му 1.1.2, когда С - стандартный симплекс, и приведем некоторые при- меры необходимости этих условий и возможные методы доказатель- ства. 1.2.1. Определение. Стандартный симплекс S" есть выпуклая оболочка векторов и°, v\,... , v" в R", т.е. S" = {х G R Уl ^х = l}. При г ? Ло, 5," обозначает грань S", противоположную v', т.е. {х ? S"\x, = о}, и границей S" является Э5" U,g/v 5,". Ниже будет показано, что S" есть замкнутая и-клетка, но для того, чтобы дать почувствовать это определение интуитивно, мы вначале вы- делим один подкласс, допускающий простую интерпретацию: 7 ЛИТЕРАТУРА 1. А 11 g о w e r E.L. Application of a Fixed Point Search Algorithms to Nonlinear Prob- lems having Several Solutions. In: Fixed Points: Algorithms and Applications. S. Kara- mardian (ed.), Academic Press, to appear. 2. Arrow K.J. and Hahn F.H. General Competitive Analysis. San Francisco: Hol- den-Dey,1971. 3. В e r g e С. Topological Spaces (translated by E.M. Patterson). - New York: MacMil- lan,1963. 4. В о h 1 P. liber die Bewegung eines Mechanischen Systems in der Nahe einer Gleichge- wichtslage. - 1. Reine Angew. Math., 127,1904,179-276. 5. Brouwer L.E.J. Uber Abbildung von Mannigfaltigkeiten. - Math. Ann., 71, 1910, 97-115. 6. С о h e n D.I.A. On the Sperner Lemma. - J. Comb. Theory, 2,1967,585-587. 7. С о 111 e R.W. Nonlinear Programs with Positively Bounded Jacobinas. — J. SIAM Appl. Math., 14,1,1966,147-158. • 8. Dantzig G.B. Linear Programming and Extensions. - Princeton, N.J.: Princeton University Press, 1963,621 pp. (Рус с к и и перевод: Дж. Д а н ц и г. Линей- ное программирование, его применения и обобщения. — М.: Прогресс, 1966). 9. E a v e s B.C. Nonlinear Programming Vis Kakutani Fixed Points. — Working Paper No. 294, Center for Research in Management Science, University of California, Berkeley, 1970. 10. Eaves B.C. An Odd Theorem. - Proc. AMS, 26,1970, 509-513. 11. Eaves B.C. On the Basic Theory of Complementarity. - Mathematical Program- ming, 1,1,1971,68-75. 12. Eaves B.C. Computing Kakutani Fixed Points. - SIAM J. of Appl. Math., 21, 2, 1971,236-244. 13. Eaves B.C. The Linear Complementarity Problem. - Management Science, 17,9, 1971,616-634. 14. Eaves B.C. Homotopies for Computation of Fixed Points. — Mathematical Pro- gramming, 3,1, 1972,1-22. 15. Eaves B.C. A Short Course in Solving Equations with PL Homotopies. - Department of Operations Research, Stanford University, September 1975. 16. Eaves B.C. and S a i g a 1 R. Homotopies for Computation of Fixed Points on Un- bounded Regions. - Mathematical Programming, 3,2,197-2, 225-237. 17. Eaves B.C. and Scarf H. The Solution of Systems of Piecewise Linear Equati- ons. •- Cowled Discussion Paper, No. 390, Yale University, 1975, 67 pp. 18. F a n К. Simplicial Maps from an Orientable n-Pseudomanifold into S"1 with the Oc- tahedral Triangulation. - J. Comb. Theory, 2,4,1967, 588-602. 19. Fisher M.L. and G о u 1 d F.J. A Simplicial Algorithm for the Nonlinear Comple- mentarity Problem. - Mathematical Programming, 6, 3,1974, 281-300. 20. Fisher M.L.,, Gould F.J. and Т о lie J.W. A new Simplicial Approximation Algorithm with Restarts: Relations Between Convergence and Labelling. - In: Fixed Points: Algorithms and Applications, S. Karamardian (ed.). Academic Press, to appear. 21. FreidenfeldsJ. Fixed-Point Algorithms and Almost-Complementary Sets. - TR 71-17. Operations Research House, Stenford University, 1971. 105 ЛИТЕРАТУРА 22. F r e i d e n f e 1 d s J. A Set Intersection Theorem and Applications. - Mathematical Programming, 7, 2, 1974, 199-211. 23. FreudenthalH. Simplizialzerlegungen von Beschrankter Flachheit. - Annals of Mathematics, 43, 3, 1942, 580-582. 24. Ga.rcia С.В., Lemke C.E. and Luethi H. Simplicial Approximation of an Equilibrium Point for Non-Cooperative ./V-Person Games. - In: Mathematical Program- ming/Ed: T.C. Hu and S.M. Robinson. - New York - London: Academic Press, 1973, 227-260. 25. Gochet W., Loute E. and So low D. Comparative Computer Results of Three Algorithms for Solving Prototype Geometric Programming Problems. - CORE Reprint 212, Belgium (1974). 26. Gould F.J. and Т о lie J.W. A Unified Approach to Complementarity in Optimi- zation. - Discrete Math., 7, 1974, 225-271. 27. Gould F.J. and Т о 11 e J.W. Finite and Constructive Conditions for a Solution to f(x) = 0. - Center for Mathematical Studies in Business and Economics, Report 7515, University of Chicago, March 1975. , 28. H a n s e n Т. and Koopmans T.C. On the Definition and Computation of a Capital Stock Invariant under Optimization. - J. Economic Theory, 5, 3, 1972, 487- 523. 29. H a n s e n T. and Scarf H. On the Applications of a Recent Combinatorial Algorithm. - Cowles Foundation Discussion, Paper No. 272, Yale University, 1969. 30. H i r s с h M.W. A Proof of the Nonretractibility of a Cell onto Its Boundary. - Proc. of AMS, 14, 1963, 364-365. •31. Jeppson M.M. A Search for the Fixed Points of a Continuous Mapping. - In: Mathematical Topics in Economic Theory and Computation/Ed.: R.H. Day and S.M. Robinson (1972), 122-129. 32. К a k u t a n iS. A Generalization of Brouwer's Fixed Point Theorem. - Duke Math. J.,8, 1941,457-459. 33. KaramardianS. The Complementarity Problem. - Mathematical Programming, 2,1972,107-129. 34. KaramardianS. (Ed.). Fixed Points: Algorithms and Applications. - Proc..Conf. on Computing Fixed Points with Applications, Clemson University, Clemson, South Carolina, 1975. 35. Kellogg R.B., LrT.Y. and Y о r k e J. A Constructive Proof of the Brouwer Fixed Point Theorem and Computational Results.'— Unpublished paper. University of Maryland and University of Utah, 1975, 20 pp. 36. K n a s t e г В., K u г a t о w s k i C. and Mazurkiewicz S. Ein Beweis des Fixpunktsatzes fun n-dimensionale Simplexe. - Fund. Math., 14, 1929, 132-137. 37. K u h n H.W. Some Combinatorial Lemmas in Topology. - IBM J. Research and Deve- lop, 4, 5, 1960, 518-524. 38. К u h n H.W. Simplicial Approximation of Fixed Points. Proc. Nat. Acad. Sci. USA, 61,1968,1238-1242. 39. Kuhn H.W. Approximate Search for Fixed Points. - In: Computing Methods in Optimization Problems - 2. New York: Academic Press, 1969. 40. Kuhn H.W. How to Compute Economic Equilibria by Pivotal Methods. - Dept. Econ. Math., Princeton University, 1975, 25 pp. 41. Kuhn H.W. and MacKinnon J.G. The Sandwich Method for Finding Fixed Points. - J. Optimization Theory and Applications, 17, 1975. 42. Lefsch.etz S., Introduction to Topology. - Princeton: Priceton University Press, 1949. 43. Lemke C.E. Recent Results on Complementarity Problems. - In: Nonlinear Pro- gramming/Ed: J.B. Rosen, O.L. Mangasarian, and K. Ritter. - New York: Academic Press, 1970, 349-384. 44. Lemke C.E. and Grotzinge f-S.K. On Generalizing Shapley's Index Theory to Labelled Pseudo Manifolds. - Rensselaer Polytechnic Institute, 1974. 106 ЛИТЕРАТУРА 45. Lemke C.E. and H о w s о n J.T. Jr. Equilibrium Points of Bimatrix Games. - SIAM J. on Appl. Math., 12, 2, 1964,413-423. 46. Люстерник Л.А. Выпуклые фигуры и многогранники. - М.:Фиэматгиэ, 1956,212с. 47. Маг a P.S. Triangulations of a Cube. - M.S. Thesis. - Fort Collins, Colorado: Colo- rado State University, 1972. 48. M e r г i 11 O.H. Applications and Extensions of an Algorithm that Computers Fixed Points of Certain Non-Empty, Convex, Upper Semi-Continuous Point to Set Mappings, TR 71—7. - Dept. Industrial Engineering, University of Michigan, 1971. 49. M e г r i 11 O.H. Applications and Extensions of an Algorithm that Computers Fixed Points of Certain Upper Semi-Continuous Point to Set Mappings. - Ph. D. Dissertation, Dept. of Ind. Engineering, University of Michigan, 1972, 228 pp. 50. M о r e J. Coercivity Conditions in Nonlinear Complementarity Problems. - SIAM Review, 16, 1,1974, 15pp. 51. R о с k a fe 11 а г R.T. Convex Analysis. - Princeton: Princeton University Press, 1970. (Русский перевод:Рокафеллар Р. Выпуклый анализ. - M.: Мир, 1973.) 52. S a i g a 1 R. Investigations into the Efficiency of Fixed Point Algorithms. - In: Fixed Points: Algorithms and Appliacations/S. Karamardian (ed.). Academic Press, to appear. 53.^S a i g a 1 R. On Paths Generated by Fixed Point Algorithms, in preparation. 54. S a i g a 1 R. On the Convergence Rate of Algorithms for Solving Equations that are Based on Complementarity Pivoting, in preparation. 55. Saigal R., S о 1 о w D. and Wolsey L.A. Comparative Study of Two Algo- rithms to Compute Fixed Points over Unbounded Regions, presented at the 8th Mathe- matical Programming Symposium, Stanford (1975). 56. S с a r f H. The Core of an A'-Person Game. - Econometrica, 35,1,1967, 50-69. 57. Scarf H. The Approximation of Fixed Points of a Continuous Mapping. - SIAM J. Appl. Math., 15,5, 1967, 1328-1343. 58. S с а г f H.E. and Hansen T. Computation of Economic Equilibria. - New Haven, Yale University Press, 1973, 249 pp. 59. Shapley L.S. On Balanced Games Without Side Payments. - In: Mathematical Programming/Ed.: T.C. Hu and S.M. Robinson, Academic Press, New York - London (1973), 261-290. 60. Shapley L.C. A Note on the Lemke- Howson Algorithm. - Mathematical Program- ming Study, 1, 1974, 175-189. 61. Smart D.R. Fixed Point Theorems. - Cambridge: Cambridge University Press, 1974. 62. Sperner E. Neuer Beweis fur die Invarianz der Dimensionzahl und des Gebietes. - Abh. Math. Sem. Univ. Hamburg, 6. 63. Т о d d M.J. A Generalized Complementary Pivoting Algorithm. Mathematical Pro- gramming, 6, 3, 1974, 243-263. 64. T odd M.J. Union Jack Triangulations. - TR 220, Dept. Operations Research, Cor- nell University. - In: Fixed Points: - Algorithms and Applications/Ed.: Stepan Kara- mardian, Academic Press, 1975. 65. T odd M.J. On Triangulations for Computing Fixed Points. - TR 234, Department of Operations Research, Cornell University 1974, 33 pp. 66. T odd M.J. Orientation in Complementary Pivot Algorithms. - TR 249, Dept. Ope- rations Research, Cornell University, 1975, 22 pp. 67. Т о d d M.J. Improving the Convergence of Fixed Point Algorithms. - TR 276, Dept. Operations Research, Cornell University October 1975. 68. Tompkins С.В. Sperner's Lemma and Some Extensions. - In: Applied Combi- natorial Mathematics, E.F. Beckenbach (ed.), Wiley, New York. 1964. (Русский пе- ревод: ТомпкянсЧ. Лемма Шпернера и некоторые ее обобще- ния. - В сб.: Прикладная комбинаторная математика. - M.: 1968, 243 - 287. 69. Tucker A.W. Some Topological Properties of Disk and Sphere. - Proc. First Cana- dian Math. Congress, 1945, 285-309. 107 ЛИТЕРАТУРА 70. U z a w a H., Walras' Existence Theorem and Brouwer's Fixed-Point Theorem. - Eco- nomic Studies Quarterly, 13,1. 71. Вертгейм Б.А. О приближенном определении неподвижных точек непре- рывных отображений. - ДАН СССР, 191, № 1, 1970, 9-11. 72. Whitney H. Geometric Integration Theory. - Princeton: Princeton University Press. - 1957. (Русский перевод: УитниХ. Геометрическая теория ин- тегрирования. - М.: ИЛ, 1960.) 73. Witmuth R.J. The Computations of Fixed Points. - Dept. Operations Research, Stanford University, Ph.D. Thesis, 1973. 74. W о 1 s е у L.A. Convergence, Simplicial Paths and Acceleration Methods for Simpli- cial Approximation Algorithms for Finding a Zero of a System of Nonlinear Equations. - CORE Discussion Paper No. 7427, Belgium (1974). ДОПОЛНЕНИЕ ЛИТЕРАТУРА, ДОБАВЛЕННАЯ РЕДАКТОРОМ ПЕРЕВОДА 1. Д е б р е Ж. Четыре аспекта математической теории экономического равновесия. - УМН, 1977, 198,131-144. 2. А 11 g о w e r E.L. Numerische Approximation von Losungen nichtlinea- rer Randwertaufgaben mit mehren Losungen. - Z. Angew. Math. Mech., 19'7^, 54,T206-T207. 3. А 11 g о we г Е., G е о г g К. Simplicial and Continuation Methods for Approximating Fixed Points and Solutions to Systems of Equations. - SIAM Review, 1980,22, 28-85. 4. А 11 g о w е г E.L., ClaschoffK.,Peitgen H.-O, eds. Nume- rical Solution of Nonlinear Equations. Lecture Notes on Mathematics. — Berlin: Springer-Verlag, 1981. 5. A 11 g о w e r E.L., McCormick S.F. Newton's Method with Mesh Refinements for Numerical Solution of Nonlinear Equations. - Z. Angew. Math. Mech„ 1976, 56, 65-73. 6. A w о n i у i S.A., Т о d d M.J. An Efficient Simplicial Algorithm for Computing a Zero of a Convex Union of Smooth Functions. - Math. Progr., 1983,25,83-108. 7. В а г a n у I. Borsuk's Theorem throughComplementary Pivoting. -Math. Progr., 1980, 18, 84-88. 8. В i 11 n e r L. Simplicial Methods for the Solution of Systems of Nonlinear Equations. - Z. Angew. Math. Mech. 1976, 56, 65-73. 9. В r о о k s P.S. Infinite Retrogression in the Eaves—Saigal Algorithm. — Math. Progr., 1980, 19,313-327. 10. С h а г n e s А., G а г с i a C.B., L e m k e C.E. Constructive Proofs of Theorems Relating to F (x) = y, with Applications. — Math. Progr., 1977, 12, 328-343. 11.Cottle R.W., Da ntzig G.B. Complementary Pivot Theory of Ma- thematical Programming. - Lin. Alg. Appl., 1968, 1,103-125. 12. Eaves B.C. Computing Stationary Points. - Math. Progr., Study, 1978, 7,1-14. 13. Eaves B.C. A Finite Algorithm for the Linear Exchange Model. - J. Math. Econ., 1976, 3, 197-203. 14. E a v e s B.C., Scarf H. The Solution of Systems of Piecewice Linear Equations. - Math. Oper. Res., 1976, 1,1-31. 15. E a v e s B.C. Solving Piecewice-linear Convex Equations. — Math. Progr. Study,1974, 1,96-119. • 16. F о r s t e r W., ed. Numerical Solution of Highly Nonlinear Problems. - Amsterdam: North Holland, 1980,-pp. 439. 109 ДОПОЛНЕНИЕ 17. F я г s t e r W. Fixed Point Algorithms: Background and Estimates for Implementation on Array Processors. — Z. Angew. Math. Mech., 1979, 59, 55-57. IS.Forster W. A Fixed Point Algorithm for Arbitrary Regions. - Z. Angew. Math. Mech., 1980, 60.T288-T289. 19. G a r с i a C.B. A Hybrid Algorithm for the Computation of Fixed Po- ints. - Manag. Sci., 1976, 22, 606-612. 20. G a r с i a C.B. Computation of Solutions to Nonlinear Equations under Homotopy Invariance. - Math. Oper. Res., 1977,2, 25-29. 21. G a r с i a C.B., Gould F.J. A Theorem on Homotopy Paths. - Math. Oper. Res., 1978, 3, 282 289. 22. G а г с i a C.B., Gould F.J. Scalar Labelings for Homotopy Paths. - Math. Progr., 1979,17,184-197. 23. G a r с i a C.B., Gould F.J. Relations Between Several Path Following Algorithms and Local and Global Newton Methods. - STAM Review 1980, 22,263-274. • 24. G а г с i a C.B., Z a n g w i 11 W.I. Finding All Solutions to Polynomial Systems and Other Systems of Equations. - Math. Progr., 1979, 16,159-176. 25. van der Н e у d e n L. A Variable Dimension Algorithm for the Linear Complementarity Problem. - Math. Progr., 1980,19,328-346. 26. van der H e у d e n L. Restricted Primitive Sets and Simplicial Subdivi- sions with Arbitrary Refinement Factors. - Math. Oper. Res., 1982, 3, 383-^01. 27. van der H e у d e n L. A Refinement Procedure for Computing Fixed Points Using Scarfs Primitive Sets. - Math. Oper. Res., 1982,7,295-313. 28. К о j i m a M. Computational Methods for. Solving the Nonlinear Comp- lementarity Problem. - Keyo Eng. Rep., 1974, 27,1 -41. 29.Kojima M. Studies in Piecese-Linear Approximations of Piece-wise С 1 Mapping in Fixed Points and Complementary Theory. - Math. Oper. Res., 1978, 3,17-36. 30. К о j i m a "M. On the Homotopic Approach to Systems of Equations with Separable Mappings. - Math. Progr. Study, 1978,7,170-184. 31.К о jim a M., Mizuno S. Computation of All Solutions to a System of Polynomial Equations. - Math. Progr., 1983, 5,131-157. 32. К о j i m a M., N is h i n о H., A r i m a N. A PL-Homotopy for Fin- ding All the Roots of a Polynomial. - Math. Progr., 1979,16, 37-62. 33. К о j i m a M., S a i g a 1 R. On the Relationship Between Conditions that Insure a PL-Mapping is a Homeomorphism. - Math. Oper. Res., 1980, 5, 101-109. 34. К о j i m a M., Y a m a m о t о Y. Variable Dimension Algorithms: Basic Theory, Interpretations and Extensions of Some Existing Methods. — Math. Progr., 1982, 24, 177-215. 35. van der Laan G., Talman A.J.J. A Restart Algorithm for Compu- ting Fixed Points without Extra Dimension. - Math. Progr., 1979,17,74-84. 36. van der Laan G., -T a 1 m a n A.J.J. A Class of Simplicial Restart Fixed Point Algorithms without an Extra Dimension. — Math. Progr., 1981, 20,33-^8. 110 ДОПОЛНЕНИЕ 37. van der Laan G. Symplicial Fixed Point Algorithms: - Amsterdam: Mathematical Centre, 1980. 38. P e i t g e n H.-O. Functional Differentional Equations and Approxima- tion of Fixed Points. — Lecture Notes in Mathematics. — N.Y.: Springer, 1979.. 39. R e i s e r P. A Modified Integer Labeling for Complementary Algo- rithms. -Math. Oper. Res., 1981,6, 129-139. 40. S a i g a 1 R. Fixed Point Computing Methods. - Encyclopedia of Com- puter Science and Technology, v. 8. - N.Y.: Marcel Dekker Inc., 1977. 41. S a i g a 1 R. On the Convergence Rate of Algorithms for Solving Equa- tions that are Based on Methods of Complementary Pivoting. - Math. Oper. Res., 1977,2,108-124. 42. S a i g a 1 R. On Piecewise Linear Approximation to Smooth Mappings. - Math. Oper. Res., 1979,4,153-161. 43. S a i g a 1 R., Т о d d M.J. Efficient Acceleration Techniques for Fixed Point Algorithms. - SIAM J. Numer. Anal., 1978,15,997-1007. 44. S о 1 о w D. Homeomorphisms of Triangulations with Applications to Computing Fixed Points. - Math. Progr., 1981,20,213-224. 45. Talman A.J.J. Variable Dimension Fixed Point Algorithms and Tri- angulations. - Amsterdam: Mathematical Centre, 1980. 46. Т о d d M.J. Improving the Convergence of Fixed Point Algorithms. - Math. Progr Study, 7,1978,151-169. 47. Т о d d M.J. On the Jacobian of a Function at a Zero Computed by a Fixed Point Algorithm. - Math. Oper. Res., 1978, 3.126-132. 48. Т о d d M.J. Piecewise-Linear Paths to Minimize Convex Functions May Not Be Monotonic. - Math. Progr., 1979, 17, 106-108. 49. Т о d d M.J. A Note on Computing Equilibria in Economies with Acti- vity Analysis Model of Production. - J. Math. Econ. 1979,6, 135-144. 50. Т о d d MJ. Exploiting Structure in Piecewise Linear Homotopy Algo- rithms for Solving Equations. - Math. Progr., 1980,18, 233-247. 51. Т о d d M.J. A Quadratically Convergent Fixed Point Algorithm for Economic Equilibria and Linearly Constrained Optimization. — Math. Progr., 1980,18,11-26. 52. Т о d d M.J. Traversing Large Pieces of Linearity in Algorithms that Solves Equations by Following PL Paths. - Math. Oper. Res., 1980,5, 242-257. •53. Т о d d M.J., W г i g h t A.H. A Variable-Dimension Algorithms that' Solve Equation by Following Piesewise-Unear Paths. - Numer. Funct. Analys. Optimiz., 1980,2,155-186. 54. T u у Н. Pivotal Methods for Computing Equilibrium Points: Unified Approach and Restart Algorithm. - Math. Progr., 1979,16,210-227. 55.Watson L.T. Solving the Nonlinear Complementarity Problem by a Homotopy Method. - SIAM J. Contr. Optimiz., 1979,17,36-46., .56. W r i g h t A.H. The Octhaedral Algorithm, a New Simplicial Fixed Point Algorithm. - Math. Progr., 1981, 21,47-69. 57.Yamamoto Y. A New Variable Dimension Algorithm for the Fixed Point Problem. - Math. Progr., 1983, 25,329-342. 58. Z a n g w i 11 W.I. An Eccentric Barycentrie Fixed Point Algorithm. — Math. Oper. Res., 1977, 2,343-359. Ill