Решение вариационного неравенства алгоритмами неподвижных точек тема диссертации и автореферата по ВАК РФ 05.13.01, кандидат физико-математических наук Матвеев, Михаил Николаевич

• Матвеев, Михаил Николаевич
• кандидат физико-математических наук
• 2007

Оглавление диссертации кандидат физико-математических наук Матвеев, Михаил Николаевич

Глава 1. Введение

1.1. Задачи работы и методы их решения

1.2. Обзор развития симплициальных алгоритмов неподвижной точки

Введение диссертации (часть автореферата) на тему «Решение вариационного неравенства алгоритмами неподвижных точек»

1.1. Задачи работы и методы их решения

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

1.1.1. Стационарные, нулевые и неподвижные точки. Стационарной точкой функции д : С Rd на множестве CcRd называется точка х* € С, такая что

1.1.1) (х\д(х*))>(х,д(х*)) для всех жеС, где {•, •) обозначает скалярное произведение. В частности, если множество С совпадает с M.d, то д{х*) = 0 и х* называется нулевой точкой функции д. Бели функция д представима в виде д(х) = f(x) — х, то fix*) = х* и точка х* € С называется неподвижной точкой функции /.

Примеры стационарных точек приведены на рис. 1.1.1, 1.1.2. Нетрудно видеть, что условие (1.1.1) геометрически означает принадлежность вектора д(х*) нормальному конусу Nc(x*) к множеству С в точке х*, который определяется как совокупность векторов у, таких что (у, х - х*) ^ 0 для всех х € С. Очевидно, что для точек, принадлежащих внутренности множества С, нормальный конус состоит из единственного вектора - d-мерного нуля, в то время как для точек, лежащих на границе С, этот конус представляет множество векторов, направленных 'от' множества С.

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

9(* i)

Nc(x*i) fan g(x*2) = 0 g(x*2) = 0 С С

Рис. 1.1.1. Стационарные точки х\ Рис. 1.1.2. Стационарные точки х\ и х\ для множества С = { х \ х2 ^ и для множества С = { х | Ах < г2}. Ь}. градиент некоторой функции р : С R1, легко видеть, что условие (1.1.1) стационарной точки функции д на С совпадает с условием первого порядка локального максимума (минимума) функции р на С. Таким образом, в число задач, решение которых может быть получено предлагаемыми в работе методами, включаются любые задачи на максимизацию (минимизацию) на множестве С, при условии, что это множество, как на рис. 1.1.2, задано системой линейных уравненией и неравенств.

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

Задача нахождения нулевых точек функции д или неподвижных точек функции / в том случае, если множество С совпадает с Ша, является не только производной от некоторой задачи максимизации, но также имеет не уступающее по важности и широте самостоятельное значение. Действительно, нулевая точка функции д есть ни что иное как решение в общем случае нелинейной системы уравнения д(х) = 0 при минимуме требований, накладываемых на функцию д (эти требования будут подробно рассмотрены в данном параграфе ниже). Возможность эффективного численного решения такой системы всегда была и остается для науки крайне актуальной.

Предлагаемые в работе методы нахождения нулевых точек по сравнению с существующими методами того же класса позволяют уменьшить как число шагов так и время вычисления более чем на порядок (!): примерно в 10 раз на каждые 10 единиц размерности d (см. результаты численных экспериментов в главе 5).

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

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

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

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

Отметим также, что предлагаемые в работе алгоритмы, представляют собой не строго детерминированные процедуры. Конструктивные особенности этих алгоритмов (см., например, описание сильной и слабой аппроксимации в главе 3) допускают широкие вариации настроек. Это придает предлагаемым алгоритмам гибкость. Если какую-либо задачу не удается решить с одними настройками, то она вполне может быть решена с другими. В таком случае многое определяется опытом, навыками и знанием специфики каждой конкретной задачи.

1.1.3. Алгоритмы отыскания неподвижных точек. Решение задач оптимизации опирается обычно на выпуклость и гладкость функций (см., например, [98, 87]). В данной работе используется подход более близкий к сим-плициальному поиску (см. [90, 99]). Однако в отличие от симплициального поиска останов алгоритма осуществляется комбинаторно. Методами, которые используются в работе для приближенного вычисления стационарных (нулевых, неподвижных) точек, строятся на основе алгоритмов отыскания неподвижных точек, а точнее той их разновидности, которая в литературе называется сим-плициальными целочисленными рестарт-алгоритмами переменной размерности.

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

Что касается симплициальных целочисленных рестарт-алгоритмов переменной размерности, то они могут быть в общем виде описаны следующим образом. Слово 'симплициальный' означает, что алгоритм использует в процессе своей работы разбиение множества С на отдельные ячейки - симплексы (см. рис. 1.1.3, 1.1.4). Перебирая некоторым образом, один за другим, симплексы разбиения, симплициальный алгоритм находит за конечное число шагов симплекс, удовлетворяющий некоторому условию останова. Условие останова сформулировано таким образом, что точки найденного симплекса могут служить приближением стационарной (нулевой, неподвижной) точки с точностью, задаваемой мелкостью разбиения.

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

Рис. 1.1.3. Фрагмент разбиения и изменение размерности симплексов в процессе работы алгоритма.

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

Слово 'рестарт-' означает, что алгоритм может стартовать с любой вершины разбиения, то есть, симплекса нулевой размерности. Это позволяет сначала найти приближение стационарной (нулевой, неподвижной) точки, используя разбиение на 'крупные' симплексы: с плохим приближением, но за счет малого количества шагов. Затем, повысив мелкость разбиения, можно перезапустить алгоритм с вершины, найденной на предыдущем шаге, в надежде, что приближение с более высокой точностью будет найдено где-то вблизи от этой вершины и таким образом алгоритму не придется затрачивать большое количество шагов, двигаясь к этому приближению через мелкие симплексы издалека (см. рис. 1.1.4).

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

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

Если необходимо найти стационарную точку функции д на ограниченном множестве С, задаваемом линейными ограничениями, то выполнимость третьего условия также не накладывает никаких дополнительных требований на функцию д. Действительно, множество С является в данном случае выпуклым ограниченным многогранником, разбиение которого на симплексы с любой наперед замкнутой мелкостью может быть выполнено конечным образом (см. описание триангуляций ниже в параграфе 2.1).

Однако в том случае, если множество С не является ограниченным, тем более если нужно найти нулевую точку д или неподвижную точку / на Rd, для выполнимости третьего условия поведение функций д и / асимптотически, то есть в некоторой удаленности от начала координат, должно удовлетворять некоторым специальным техническим требованиям. В основном эти требования были впервые сформулированы в [45], однако они могут очень существенно различаться в силу того, что их главная задача - не столько характеристика функций, сколько обеспечение сходимости алгоритма.

Существует, тем не менее, не совсем строгая, но достаточно устоявшаяся интерпретация этих требований по отношению к функции /, неподвижную точку которой необходимо найти. В соответствии с этой интерпретацией, при достаточно существенном удалении от начала координат в направлении х, вектор f(x) — х должен быть 'направлен' в сторону, противоположную х (см. рис. 1.1.5,1.1.6). В данной работе для обеспечения сходимости алгоритмов предполагается, что функция / такова, что при некотором М > О для любого х € Kd, ЦхЦг > М, где ЦхЦг = у/{х,х), выполнено условие

1.1.2) (/(х)-х,х)^0.

Рис. 1.1.5. Асимптотическое пове- Рис. 1.1.6. Асимптотическое поведение функции /(ж) - х = а. дение функции f(x)-x, 'обеспечивающее' сходимость симплициальных алгоритмов.

В общем случае условие (1.1.2) обеспечивает сходимость алгоритмов неподвижной точки при достаточно высокой мелкости триангуляций (см, например, [51]), что представляется не вполне удобным с вычислительной точки зрения. Поэтому для одного из алгоритмов, предложенных в работе сходимость доказывается при дополнительном предположении, согласно которому функция / отображает достаточно удаленные от начала координат точки в некоторое ограниченное множество - условие (1.1.2) выполнено в этом случае автоматически. В сочетании с тем, что сам этот алгоритм являются достаточно 'многолучевыми' (см. описание конструкции алгоритмов в отсутствии ограничений в параграфе 3.3), такое предположение позволяет доказать сходимость при любой мелкости разбиений. В следующем разделе данного параграфа показано, что в задаче нахождения равновесия по Нэшу в модели рыночного ценообразования оба предположения на функцию /, как слабое так и сильное, оказываются выполнеными.

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

Пусть с обозначает цену на рынке сырья; р - цену на рынке продукции; I

- число участников; г - номер участника, г € 1: /; сц - технологию г-го участника ; Wi - количество сырья, закупаемое г-ым участником на рынке сырья; €{

- долю г-ro участника на рынке продукции; Ilj - прибыль г-го участника; Vi

- количество продукции, продаваемое г-ым участником на рынке продукции; v = (щ,- ■. ,vj) - вектор количеств продукции; ||г?|| - суммарное количество продукции, продаваемое на рынке продукции,

1М1 = 1> 1=1

Относительно рынков будем предполагать:

1. цена на рынке сырья постоянна: с = const;

2. спрос на рынке продукции характеризуется постоянством эластичности Е цены р по суммарному объему продаж v:

Интегрируя, получаем:

1.1.4) P = K\\v\\E, где К = const.

Доля 6i участника i на рынке продукции определяется отношением

1.1.5) ei = vi/\\v\\.

Количество сырья Wi, закупаемое участником г на рынке сырья, связано с количеством продукции Vi, производимой этим участником, с помощью коэффициента Oi, характеризующего его технологию, следующим образом:

1.1.6) Wi = (LiVi. Прибыль Пг участника г выражается формулой

1.1.7) Пi=pvi~ cwi.

В соответствии с (1.1.6) каждый участник распоряжается только одной независимой переменной - выпуском и* 6 [0, +оо) и, следовательно, используя (1.1.4) и (1.1.6), можно переписать (1.1.7) в виде:

1.1.8) Ui = (р-cajvi = ~щ = •' •

Определение 1.1.1. Вектор v ф 0 назовем нетривиальной точкой Нэша, если

П i(v)= sup ni(vi,.,vi-lfx,vi+1,.,vi),iel:l.

0,+oo)

Помимо нетривиальной точки Нэша в модели может существовать также тривиальная, равная 0. Однако в точке v = 0 величины р, е*, и П, не определены, поэтому этот случай должен быть рассмотрен особо.

Определение 1.1.2. Будем называть вектор v = 0 тривиальной точкой Нэша, если для всех i G 1 : / выполнено равенство: lim ni(0,.,0,i;<,0,.,0) = sup П*(0,.,0,ж,0,.,0).

Дифференцируя (1.1.8) по Vi, используя (1.1.3) и (1.1.5), мы получаем, что v является нетривиальной точкой Нэша тогда и только тогда, когда v является решением системы х ^ (р( 1 + Евг) -cai = 0, р-са{> 0, i;i = 0, p-cai^0.

Определим компоненты gi{v),. ,gi(v) функции д(1?) = g{vi,.,vj) для v > 0 как g.(v) = (-(КЛГ1 Ь(1 + Еъ) - cat], р-ац> 0, а для остальных значений v = (vi,.,vi) определим компоненты gi(v) как sign(vi)p(juij,., |г>/|).

Переобозначив вектор v = (vi,., vj) выпусков через х = (xi,., xj), мы получим непрерывную функцию д(х), определенную на пространстве Е7. Так как при p—ca,i >0 компоненты этой функции представляют собой левые части системы (1.1.9), умноженные на — (КЕ)-1 то векторы модулей компонент нулевых точек функции д описывают обе (как нетривиальную, так и тривиальную) точки Нэша в рассмотренной выше модели.

Пусть /(ж) = д(х)+х, тогда д(х) = f(x) — х и нулевые точки д совпадают с неподвижными точками /. При этом для достаточно удаленных от нуля значений х мы, очевидно, имеем p—cai ^ 0 и, следовательно, f(x) = 0, что полностью соответствует рассмотренным ранее требованиям на /, при которых в данной работе доказывается сходимость алгоритмов в отсутствии ограничений. Таким образом, равновесие по Нэшу в описанной модели может быть вычислено одним из алгоритмов, построенных в данной работе для поиска стационарных точек в отсутствии ограничений.

Заметим, что в модели присутствуют ограничения на выпуски Vi ^ 0, неявно учтенные в системе (1.1.9) случаем р-ссч ^ 0. Для введения в нее дополнительных ограничений, скажем, ограничения ||и|| < V по пропусной способности рынка продукции, следует, строго говоря, переопределить точки Нэша. Однако рассматривать такое введение на уровне модели нет необходимости - для нахождения таких точек Нэша достаточно использовать производные функций прибылей (1.1.8) с алгоритмом нахождения стационарных точек при линейных ограничениях непосредственно на уровне вычислений.

Список литературы диссертационного исследования кандидат физико-математических наук Матвеев, Михаил Николаевич, 2007 год

1. E.L. Allgower and К. Georg, Simplicial and continuation methods for approximating fixed points and solutions to systems of equations, S1.M Review 22 (1980), 28-85.

2. K.J. Arrow and G. Debreu, Existence of an equilibrium of a competitive economy, Econometrica 22 (1954), 265-290.

3. R.J. Aumann and B. Peleg, Von neumann-morgenstern solutions to cooperative games without side payments, Bulletin of American Mathematical Society 66 (I960), 173-179.

4. D.I.A. Cohen, On the sperner lemma, Journal of Combinatorial Theory 2 (1967).

5. O.J.C. Cornielje and G. van der Laan, The computation of quantity-constrained equilibria by virtual taxes, Economics Letters 22 (1986), 1-6.

6. G. Debreu, Theory of value, Yale University Press, New Haven, 1959.

7. T.M. Doup and A.J.J. Talman, A new variable dimension algorithm to find equilibria on the product space of unit simplices, Mathematical Programming 37 (1987), 319-355.

8. T.M. Doup, G. van der Laan, and A.J.J. Talman, The (2n+1 — 2)-ray algorithm: a new simplicial algorithm to compute economic equilibria, Mathematical Programming 39 (1987), 241-252.

9. J.H. Dreze, Existence of an exchange equilibrium under price rigidities, International Economic Review 16 (1975), 301-320.

10. B.C. Eaves, Homotopies for computation of fixed points, Mathematical Programming 3 (1972), 1-22.13. , Computing stationary points, Mathematical Programming Study 7 (1978), 1-14.

11. B.C. Eaves and R. Saigal, Homotopies for the computation of fixed points on unbounded regions, Mathematical Programming 3 (1972), 225-237.

12. G. Ewald, Combinatorial convexity and algebraic geometry, Springer, New York, 1996.

13. H, Freudenthal, Simplizialzerlegungen von beschrdnkter flachheit, Annals of Mathematics 43 (1942), 580-582.

14. R.W. Freund and M.J. Todd, A constructive proof of tucker's combinatorial lemma, Journal of Combinatorial Theory Ser. A 30 (1981), 321-325.

15. D. Gale, Equilibrium in a discrete exchange economy with money, International Journal of Game Theory 13 (1984), 61-64.

16. D. Gale and L.S. Shapley, College admissions and the stability of marriage, American Mathematical Monthly 69 (1962), 9-15.

17. C.B. Garcia, A hybrid algorithm for the computation of fixed points, Management Science 22 (1976), 606-613.

18. R.E. Gomory, Outline of an algorithm for integer solution to linear programs, Bulletin of American Mathematical Society 64 (1958), 275-278.

19. Branko Griinbaum, Convex polytopes, Interscience, London, 1967.

20. Т. Hansen, On the approximation of a competitive equilibrium, Ph.d. thesis, Department of Economics, Yale University, New Haven, 1968.

21. M.W. Hofkes, A simplicial algorithm to solve the nonlinear complementarity problem on Sn x R!p, Journal of Optimization Theory and Applications 67 (1990), 551-565.

22. T. Ichiishi, Alternative version of shapley's theorem on closed coverings of a simplex, Proceedings of the American Mathematical Society 104 (1988), 759-763.

23. T. Ichiishi and A. Idzik, Closed covers of compact convex polyhedra, International Journal of Game Theory 20 (1991), 161-169.

24. K. Kaneko and Y. Yamamoto, The existence and computation of competitive equilibria in markets with an indivisible commodity, Journal of Economic Theory 38 (1986), 118-136.

25. M. Kaneko, The central assignment game and the assignment markets, Journal of Mathematical Economics 10 (1982), 1483-1504.

26. R.B. Kellogg, T.-Y. Li, and J.A. Yorke, A constructive proof of the brouwer fixed point theorem and computational results, SIAM Journal on Numerical Analysis 13 (1976), 473483.

27. A.S. Kelso and V.P. Crawford, Job matching coalition formation and gross substitutes, Econometrica 60 (1982), 1483-1504.

28. B. Knaster, C. Kuratowski, and C. Mazurkiewicz, Ein beweis des fixpunktsatzes fur n-dimensionale simplexe, Fundamenta Mathematical 14 (1929), 132-137.

29. T. Koopmans and M.J. Beckman, Assignment problems and the location of economic activities, Econometrica 25 (1957), 53-76.

30. H.W. Kuhn, Some combinatorial lemmas in topology, IBM J. Research and Development 4 (1960), 518-524.

31. Simplicial approximation of fixed points, Proceedings of National Academy ofScience, U.S.A. 61 (1968), 1238-1242.39. , Approximate search for fixed points, Computing Methods in Optimization Problems2 (1969), 199-211.

32. H.W. Kuhn and J.G. MacKinnon, The sandwich method for finding fixed points, Journal of Optimization Theory and Applications 17 (1975), 189-204.

33. S. Lefschetz, Introduction to topology, Princeton University Press, Princeton, 1949.

34. C-E. Lemke, Bimatrix equilibrium points and mathematical programming, Management Science 11 (1965), 681-689.

35. C.E. Lemke and J.T. Howson, Equilibrium points of bimatrix games, SIAM Journal on Applied Mathematics 12 (1964), 413-423.

36. Peter McMullen, Duality, sections and projections of certain euclidean tilings, Geometriae Dedicata 49 (1994), 183-202.

37. O.H. Merrill, Applications and extensions of an algorithm that computes fixed points of certain upper semi-continuous point-to-set mappings, Ph.d. thesis, Department of Industrial and Operations Engineering, University of Michigan, Ann Arbor, 1972.

38. H. Midonick, The treasury of mathematics: 1, Penguin Books, Harmondsworth, 1968.

39. R.B. Myerson, Refinements of the nash equilibrium concept, International Journal of Game Theory 7 (1978), 73-80.

40. J. Nash, Equilibrium points in n-person games, Proceedings of National Academy of Science U.S.A. 36 (1950), 48-49.

41. C.H. Papadimitriou and H. Steiglitz, Combinatorial optimization: Algorithms and complexity, Prentice-Hall, Englewood Cliffs, 1982.

42. M. Quinzii, Core and competitive equilibria with indivisibilities, International Journal of Game Theory 13 (1984), 41-60.

43. P.M. Reiser, A modified integer labeling for complementarity algorithms, Mathematics of Operations Research 6 (1981), 129-139.

44. Konstantin Rybnikov, Stresses and liftings of cell-complexes, Discrete Comput. Geometry 21 (1999), 481-517.

45. L.S. Shapley, On balanced games without side payments, in: Mathematical Programming (T.C. Hu and S.M. Robinson, eds.), Academic Press, New York, 1972, pp. 261-290.

46. L.S. Shapley and H. Scarf, On cores and indivisibilities, Journal of Mathematical Economics 1 (1974), 23-37.

47. L.S. Shapley and M. Shubik, The assignment game i: the core, International Journal of Game Theory 1 (1972), 111-130.

48. G.C. Shephard, Diagrams for positive bases, J. London Math. Soc. 2 (1971), no. 4, 165-175.63. -, Spherical complexes and radial projections of polytopes, Israel J. Math. 9 (1971),no. 2, 257-262.

49. J.B. Shoven and J. Whalley, Applying general equilibrium, Cambridge University Press, Cambridge, 1992.

50. E. Sperner, Neuer beweis fur die invarianz der dimensionszahl und des gebietes, Abhandlungen aus dem mathematischen Seminar Universitat Hamburg 6 (1928), 265-272.

51. A.J.J. Talman and Y. Yamamoto, A simplicial algorithm for stationary point problems on polytopes, Mathematics of Operations Research 14 (1989), 383-399.

52. A.W. Tucker, Some topological properties of disk and sphere, in: Proceedings of the first Canadian Mathematical Congress, University of Toronto Press, Toronto, 1946, pp. 285-309.

53. A.H. van den Elzen, Adjustment processes for exchange economies and noncooperative games, Lecture Notes in Economics and Mathematical Systems 402 (1993).

54. G. van der Laan, Simplicial approximation of unemployment equilibria, Journal of Mathematical Economics 9 (1982), 83-97.

55. B.L. van der Waerden, Geometry and algebra in ancient civilizations, Springer-Verlag, Berlin, 1983.

56. P.M. White, A.S. Caplin, and L. Van der Heyden, Scarf's procedure for integer programming and a dual simplex algorithm, Mathematics of Operations Research 10 (1985), 439-449.

57. H. Scarf (with the collaboration of T. Hansen), The computation of economic equilibria, Yale University Press, New Haven, 1973.

58. A.H. Wright, The octahedral algorithm, a new simpiicial fixed point algorithm, Mathematical Programming 21 (1981), 47-69.

59. Y. Yamamoto and Z. Yang, The (n + 1 )2Tn-ray algorithm: a new simpiicial algorithm for the variational inequality problem on R™ X Sn, Annals of Operations Research 44 (1993), 93-113.

60. Z. Yang, Simpiicial fixed point algorithms and applications, Ph.D. dissertation, Tilburg University, Tilburg, 1996.

61. Computing equilibria and fixed points, Kluwer Academic Publishers, Boston, 1999.

62. G.M. Ziegler, Lectures on polytopes, Springer, New York, 1995.

63. А.Д. Александров, Выпуклые многогранники, Гос. Изд. Тех.-Теор. Лит., Москва, 1950.

64. А. Бренстед, Введение в теорию выпуклых многогранников, Мир, Москва, 1988.

65. С.А. Вавилин, Оптимизационные методы в задачах оценивания научно-технического прогресса, Дис. на соиск. учен, степени канд. физ.-мат. наук (05.13.02), Институт системного анализа, Москва, 1985.

66. Ф.П. Васильев, Численные методы решения экстремальных задач, Наука, Москва, 1980.

67. Ф.П. Васильев и А,Ю. Иваницкий, Линейное программирование, Факториал, Москва, 1998.

68. Е.Г. Гольштейн и Д.Б. Юдин, Линейное программирование, Физматгиз, Москва, 1963.

69. А.П. Дамбраускас, Симплициальный поиск, Энергия, Москва, 1979.

70. М.Н. Матвеев, Модель рыночного ценообразования, Моделирование процессов обработки информации и управления Междуведомственный сборник (1990), 113-118.

71. X. Никайдо, Выпуклые структуры и математическая экономика, Мир, Москва, 1972.

72. Е.Я. Павловская, И. Г. Поспелов, and К. Г. Скрипкин, Точка Нэша и общественно необходимые затраты труда в хозяйстве, препринт, 1988.

73. Б.Т. Поляк, Введение в оптимизацию, Наука, Москва, 1983.

74. А.С. Рыков, Поисковая оптимизация. Методы деформируемых конфигураций, Физма-тлит, Москва, 1993.

75. Т. Хансен и Г. Скарф, О приложениях нового комбинаторного алгоритма, Математическая экономика: Равновесные модели, оптимальное планировав и управление (ред. B.C. Митягин), Мир, Москва, 1974, 143-169.

76. М.Дж. Тодд, Вычисление неподвижных точек и приложения к экономике, Наука, Москва, 1983.