автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему:Решение вариационного неравенства алгоритмами неподвижных точек

На правах рукописи

□ОЗОБ2ВБ4

Матвеев Михаил Николаевич

РЕШЕНИЕ ВАРИАЦИОННОГО НЕРАВЕНСТВА АЛГОРИТМАМИ НЕПОДВИЖНЫХ ТОЧЕК

Специальность 05 13 01 " Системный анализ, управление и обработка информации"

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических наук

Москва-2007

003062664

Работа выполнена на кафедре экономики Московского физико-технического института (государственного университета)

Научные руководители

Официальные оппоненты

кандидат физико-математических наук, допент

Кривцов Валерий Евгеньевич

доктор физико-математических наук, доцент

Иванов Григорий Евгеньевич

доктор технических наук, профессор

Поляк Борис Теодорович

доктор физико-математических наук, профессор Антипин Анатолий Сергеевич

Ведущая оргапизация Цептральпый экономико-математический институт РАН

Защита состоится 28 мая 2007 г в 11 00 на заседании диссертационного совета Д 002 086 02 при Институте системного анализа РАН по адресу 117312, г Москва, пр-т 60-Летия Октября, д 9

С диссертацией можно ознакомиться в библиотеке Института системного анализа РАН

Автореферат разослан 18 апреля 2007 г

Ученый секретарь /> у доктор технических наук, профессор

диссертационного совета ./г Пропой Анатолий Иванович

1 Общая характеристика работы

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

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

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

Ряд методов решения указанных задач при различных условиях описан, например, в работах Б Т Поляка, Ф П Васильева и А С Антипина Однако эти методы предполагают, как правило, выпуклость функций и множеств В настоящей работе решение данной проблемы исследуется без предположения о выпуклости функций Для этого используется идея перебора симплексов, во многом похожая на идею симплициального поиска минимума функции, развитую в работах А П Дамбраускаса п АС Рыкова

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

з

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

Целями исследования являются

1 построение универсальных целочисленных алгоритмов поиска стационарных точек,

2 построение симплициальных рестрат-алгоритмов переменной размерности, которые использовали бы в своей работе симплексы малой размерности, реализующие траектории приближенные к кусочно-линейным,

3 построение симплициальных рестарт-алгоритмов поиска стационарной точки на произвольном множестве, заданном ограничениями Ах ^ Ъ

4 тестирование построенных алгоритмов

Для достижения указанных целей были поставлены и решены следующие основные задачи

1 анализ существующих целочисленных рестарт-алгоритмов с целью выявления взаимодействия их основных компонент ,

2 анализ основных принципов построения триангуляций, которые используются в алгоритмах поиска неподвижных точек,

3 исследование конструктивных различий целочисленных и векторных алгоритмов ,

4 разработка общей схемы целочисленного алгоритма на произвольном ограниченном многограннике,

5 применение общей схемы для построения высокоэффективных целочисленных алгоритмов поиска стационарных точек на К^ ,

6 исследование области применимости общей схемы,

7 применение общей схемы для построения высокоэффективных целочисленных алгоритмов поиска стационарных точек на множестве, заданном ограничениями вида Ах ^ Ь,

8 экспериментальное сравнение существующих и вновь построенных алгоритмов

Объектом исследования являются алгоритмы поиска стационарных точек

Предмет исследования- симплшшальные целочисленные рестарт-алгоритмы переменной размерности

Информационная база исследования включает базы данных, анализ литературных источников, данные численного тестирования ряда алгоритмов поиска

4

неподвижных точек, опубликованные в журнале 'Математическое программирование'

Методологической и теоретической основой исследования являлся системный подход в сочетании с дедуктивным и индуктивным методами научного познания При решении конкретных задач широко использовались методы теории многогранников, комбинаторики, линейной алгебры

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

1 Построен 2л целочисленный алгоритм для нахождения стационарных точек на К12, являющийся аналогом классического векторного алгоритма Райта

- одного из самых высокоэффективных векторных алгоритмов

2 Построен 3^ — 1 целочисленный алгоритм для нахождения стационарных точек на К*4, являющийся аналогом векторного алгоритма Коджимы и Ямамото

- самого многолучевого из всех существующих алгоритмов

3 Построен целочисленный алгоритм для поиска стационарных точек на произвольном множестве, заданном ограничениями вида Ах ^ 6, являющийся аналогом векторного алгоритма Тальмана и Ямамото

Для каждого из этих методов разработаны программные пакеты на языке С++ Для алгоритма 3 такой пакет написан впервые, а пакеты для алгоритмов 1 и 2 оказывается гораздо быстрее своих предшественников и впервые демонстрируют возиожность эффективно работать на задачах, размерность которых исчисляется тысячами переменных

Теоретическая значимость исследования состоит в том, что его ходе получены следующие результаты

1 предложен новый способ триангуляции пространства и многогранника,

2 применено новое индуктивное описание использующейся в исследовании триангуляции Куна,

3 обобщено понятие аппроксимации, использующееся в существующих целочисленных алгоритмах,

4 введено понятие сильной и слабой аппроксимации, необходимое для построения новых алгоритмов,

5 описан общий способ построения алгоритма по произвольному наперед заданному многограннику

6 построен критерий существования многогранника, порождающего заданное разбиение пространства на многогранные конусы,

7 построена 'регулярная триангуляция' куба,

8 построена 'регулярная триангуляция' октаэдра,

5

9 обоснована интерпретация целочисленного алгоритма для поиска стационарных точек на многограннике как обобщения симплекс-метода, 10 доказана сходимость квазиградиентного метода к равповесию по Нэхну в модели рыночного ценообразования

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

Апробация результатов исследования Работа обсуждалась на научных семинарах специализации 'Теоретические и прикладные проблемы инноваций' кафедры общей экономики МФТИ, кафедры высшей математики МФТИ, отдела теории автоматического управления ИПУ РАН, отдела прикладных проблем оптимизации ВЦ РАН, лаборатории теории и численных методов оптимизации ЦЭМИ РАН, направления математических основ информатики, управления и системного анализа ИСА РАН, кафедры оптимального управления факультета ВМК МГУ Основные результаты диссертации опубликованы в 4-х печатных работах

2 Основное содержание исследования

В первой главе описаны постновка задачи работы и общий подход, применяемый в работе для ее решения

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

(1) {х*,д(х'))>(х,д(х*))

для всех х £Е С Неравенство (1) называется вариационным неравенством, а точка х* называется стационарной точки функции д на множестве С Стационарная точка на всем пространстве определяется условием д{х*) = 0 Такая точка будет называться нулевой

Методами решения являются симплициальные рестарт-алгоритмы переменной размерности, использующие целочисленные метки

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

б

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

Если необходимо найти стационарную точку функции д па ограниченном множестве С, задаваемом линейными ограничениями, то выполнимость третьего условия также не накладывает никаких дополнительных требований на функцию д В противном случае для обеспечения сходимости в диссертационном исследовании на функцию д накладывается дополнительное требование Это требование состоит в том, что при некотором М > 0 для любого х 6 ||х||2 > М, где ||х||2 = \/(х,х), должно быть выполнено условие

(2) (д(х),х)^ О

В общем случае выполнение условия (2), обеспечивает сходимость алгоритмов неподвижной точки при достаточно высокой мелкости триангуляций, что представляется не вполне удобным с вычислительной точки зрения Однако если дополнительно предположить, что функция д представима в виде д(х) = /(х) — х, где функция / отображает достаточно удаленные от начала координат точки в некоторое ограниченное множество, то для одного из построенных в работе алгоритмов это предположение позволяет доказать сходимость при любой мелкости разбиений

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

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

Лемма 1. Пусть где /3, = а, + 1, обозначает куб с диагональю [а,(3], координаты вершин которого определяются условием аг хг ^ /Зг Пусть иг, г е 1 д,, обозначает г-ый единичный вектор И пусть множество включает, для всех перестановок п = 7г(1), ,ж(сГ), симплексы, являющиеся выпуклой оболочкой точек Уо{^),у\{к), где уо(тс) = а, а уг{тт) =

уг_1 (7г) + !(„(,), г € 1 <1, Тогда есть триангуляция куба С£

7

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

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

Наконец, в этой главе описаны в адаптированном виде два 'классических' алгоритма неподвижных точек целочисленный 2й алогоритм ван дер Лаана и Тальмана и векторный алгоритм Райта Описаны их конструктивные особенности и различия в поведении их траекторий

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

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

Пусть Т - конечное множество выпуклых многогранных конусов, таких что

1 каждый из конусов Т является острым, то есть имеет, 0-мерную грань -начало координат О,

2 объединение конусов из Т совпадает с

Будем называть Т веером, если пересечением любых двух конусов из Т является их общая собственная грань

Лучами веера Т будем называть множество одномерных граней конусов веера Т Если каждый конус веера Т содержит в точности 6 л>чей веера, то веер Т называется симпшщиальным Если каждый луч веера Т принадлежит в точности й конусам этого веера, то веер Т называется простым (см рис 1) Пусть простой веер Т> состоит из N конусов К\, , Кн Пусть х - произвольная вершина некоторой триангуляции Поставим в соответствие вершине х метку 1{х) = п, такую что п = тт{ш € 1 N \ }{х) — х 6 Кт }, где / - непрерывная функция, неподвижную точку которой необходимо найти Предположим, что в процессе работы алгоритм находит симплекс, не обязательно полномерный, вершины которого жь несут метки пг, ,п3, такие что П3г^1КП( = 0 (см рис 2)

Очевидно, что если симплексы триангуляции являются достаточно мелкими, то вершины хь , х3 лежат достаточно близко друг к другу Соответственно,

8

о

Рис 1 Пример веера Т, который является одновременно простым и симплициальным

Рис 2 Аппроксимация неподвижной точки при использовании целочисленных меток, й = 2, 1{х\) = 3, 1(х2) = 6

в силу непрерывности функции /, векторы /(хг) — х„ г е 1 у, отличаются друг от друга достаточно мало В работе доказано следующее утверждение

Лемма 2. Пусть Ку и многогранные конусы, такие что К\ ПК2 = { О }, и пусть х 6 К\, у 6 К2 Тогда для любого е > 0 найдется 5 > 0, такое что из Ца; - 2/Ц2 < & следует ЦгЦг ^ е, ||у||2 < е

Как следствие можно заключить, что если векторы }{хг) — хг, г 6 1 у, принадлежат различным конусам из V и пересечение этих конусов есть начало координат, то эти векторы с необходимостью должны быть близки к нулю Таким образом, любая из вершин найденного симплекса может служить приближением неподвижной точки функции /

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

Пусть полномерный выпуклый ограниченный многогранник РвК'' содержит во внутренности начало координат О Веером граней Тр многогранника Р будем называть множество конусов, натянутых на {(I — 1)-мерные грани Р

9

Рис 3 Веер граней Тр многогран- Рис 4 Нормальный веер Л/р мно-ника Р и его лучи гогранника Р

Построение веера граней показано на рис 3 Лучами веера граней являются конусы, натянутые на вершины многогранника Р Нетрудно видеть, что веер граней симплициального многогранника также является симплициальным Применительно к атгоритмам неподвижной точки веер граней определяет разбиение пространства Ш* сначала на конусы веера, а затем конусов веера на симплексы и таким образом задает возможное 'движение' алгоритма

В наибольшей степени это касается лучей веера В частности, вдоль одного из лучей веера граней алгоритм покидает начало координат О в процессе поиска неподвижной точки Эта особенность лежит в основе классификации алгоритмов неподвижной точки Так, например, й + 1 алгоритм ван дер Лаана и Тальмана имеет <14-1 луч(ей), а 2(1 алгоритм - 2с1 лучей

Пусть многогранник Р имеет N вершин р\, ,рн Нормальным конусом многогранника Р в вершине р,, г 6 1 N, называется множество

{пеГ* | (щрг) = тахх&р{п,х) }

Иным словами, в нормальный конус А^ входят все векторы п — (щ, ,па), такие что линейная функция пгХ1 4- + плха достигает своего максимума на многограннике Р в вершине рг

Нормальным веером Лр многогранника Р называется множество конусов {ЖР1, }, где рь , рдг — вершины многогранника Р Построение нор-

мального веера показано на рис 4 Нетрудно видеть, что, если многогранник Р симплициален, то нормальный веер Р является простым - это свойство нормального веера симплициального многогранника используется для генерации целочисленных меток

ю

Использование веера граней симплициального многогранника для триангуляции пространства, а его нормального веера для вычисления целочисленных меток, в сочетании с общими принципами построения целочисленного алгоритма ван дер Лаана и Тальмана, приводит к следующей общей схеме алгоритма с целочисленными метками

Пусть / —> - непрерывная функция, для которой существует некоторое М > О, такое что для любого х ё Кй, || х ||г > М, имеет место неравенство II/0е) Иг < М П>сть Р - полномерный выпуклый ограниченный симплици-альный многогранник Р в такой что вершины Р1, ,рх многогранника Р заданы, а сам Р содержит во внутренности начало координат О

Разбивая каждый конус веера граней Т многогранника Р на симплексы с некоторой заданной, одинаковой для всех конусов, мелкостью определяющей на сколько частей должен быть разбит каждый из векторов р!, мы получим в результате 'сшитое' из разбиений отдельных конусов совокупное разбиение пространства на симплексы (см рис 5,6)

Поставим в соответствие каждой вершине симплексов триангуляции !Р некоторое целое число, метку, из множества {1 Ы}, используя следующее правило Пусть х - некоторая вершина, тогда метка 1[х) этой вершины есть число г, такое что

(3) г = шш{з 6 Агдтахкех л'{ (/(х) - х,рк) }

]

Очевидно, что условие 1(х) = г в частности означает, что вектор f(x) — х принадлежит конусу АГР, нормального веера V многогранника Р

Стартуя из начала координат симплициальный алгоритм неподвижной точки генерирует последовательность симплексов переменной размерности до тех пор пока не найдет симплекс, не обязательно полномерный, вершины которого XI, , х3, 1 < ] ^ й + 1, несут метки , г3, такие что

(4) П^Л,,, = О

Условие (4) является условием останова алгоритма Из рис 2 следует, что любая точка симплекса, удовлетворяющего условию останова, является приближением неподвижной точки функции /

При доказательстве сходимости алгоритма в исследовании выделены два случая Один из них соответствует доказательству, принятому в литератзфе Этот случай не накладывает никаких дополнительных ограничений на многогранник Р, но требует, чтобы мелкость разбиения была достаточно высокой

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

11

3 3

Рис 5 Типичная траектория пело- Рис 6 Траектория, для которой численного алгоритма для восьми- условие останова выполнилось на гранника симплексе неполной размерности

вершин р1 и у>2 > принадлежащих одной грани, выполнено условие (5) (рьр2)^0

В частности, такому условию удовлетворяет один из многогранников, которые используются для построения алгоритмов в диссертапионном исследовании

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

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

12

Идея построения первой реализации основана на триангуляции Куна пространства Эта триангуляция разбивает поверхность единичного куба так, как это показано на рис 7 Понятно, что, если найти способ систематического 'вытягивания' вершин куба вдоль лучей, выходящих из начала координат, примерно таким образом, как это сделано на рис 7, то грани полученного симпли-циального многогранника будут описаны триангуляцией Куна В то же время вершины этого многогранника будут, очевидно, описаны векторами ненулевых знаков

В исследовании эта идея доведена до логического завершения В частности, 1оказана справедливость следующего утверждения

Теорема 1. Пусть векторы в' определяются по векторам в формулой

= +

где к - количество отрицательных компонент вектора в Тогда многогранник С", определенный как выпуклая оболочка векторов в' для всех векторов ненулевых знаков в, является симплициальным

В результате построен новый 2й алгоритм, являющийся целочисленным аналогом 'классического' векторного алгоритма Райта При этом оказалось, что по результатам вычислений целочисленный алгоритм существенно превосходит векторный

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

Теорема 2 Пусть векторы е' определяются по векторам е формулой

е' = (1 + ^)в,

где к - количество ненулевых компонент вектора е Тогда многогранник О', определенный как выпуклая оболочка векторов е' для всех векторов ненулевых знаков е, является симплициальным

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

13

Рис 7 Построение симплициаль- Рис 8 Барицентрическое разбие-ного многогранника из куба ние поверхности октаэдра

Сложность доказательства этой теоремы оправдывается отличными результатами Целочисленный 3d—1 алгоритм, полученный в результате применения общей схемы к построенному таким образом симплициальному многограннику, является, в отличие от Iй целочисленного алгоритма, пространственно высоко симметричным Оказалось, что это обстоятельство приводит к превосходным вычислительным характеристикам 3d — 1 алгоритма

Четвертая глава посвящена особой, третьей реализации общей схемы Эта реализация предложена для случая линейных ограничений, заданных в виде Ах < 6

Специфика этого случая состоит в том, что вершины многогранника Р = { х | Ах ^ Ь } не являются априори заданными Поэтому для вычисления целочисленных меток в этом случае необходимо использовать стандартную процедуру симплекс-метода

Пусть, например, алгоритм стартует из некоторой точки v и метка этой точки соответствует вершине рг Тогда после триангуляции линейного сегмента (рг, v] с выбранной мелкостью алгоритм начинает движение от стартовой точки v к вершине pi следующей точкой, для которой нужно определять метку, становится точка х\ (см рис 9)

Очевидно, что для точки xi необходимо найти вершину многогранника Р, максимизирующую функцию {g(xi),x} - мы получаем задачу линейного программирования Если решение этой задачи симплекс-методом вновь дает вершину рх, то алгоритм продолжает смещаться к точке pi вдоль сегмента [pj, г>] следующей точкой становится точка жг

В точке Х2 все повторяется еще раз Если очередное использование симплекс-метода вновь дает вершину pi, то алгоритм смещается еще дальше к рх Если

14

simplex-method

x0 = v

algorithm

Рис 9 Движение алгоритма вну- Рис 10 Чередование щагов алго-три многогранника в начале рабо- ритма с шагами симплекс-метода ты

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

Нетрудно видеть, что при работе на многограннике каждый шаг алгоритма поиска стационарной точки чередуется с решением задачи линейного программирования (см рис 10) Таким образом, реализация общей схемы целочисленного алгоритма для многогранника может быть рассмотрена как обобщение симплекс-метода для случая нелинейных функций

В пятой главе представлены результаты численного тестирования построенных алгоритмов

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

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

Таблица 1 Сходимость известных алгоритмов и 2у и новых алгоритмоз 21 и 31 для проблемы КУ2

КУ2 (-2,3) (0,3) (2,3) (-2,5) (2,5) (-2,7) (2,7) (2,10) (2,20)

12 243 133 183 5149 564 9586 4935 35019 1415968

2У 167 163 95 604 288 2521 4263 67793 -

21 113 109 143 552 277 2195 547 1038 41444

31 89 85 43 146 193 166 300 755 20843

В вычислениях сравнивались между собой четыре алгоритма целочисленный алгоритм ван дер Лаана и Тальмана (обозначается как 12), векторный алгоритм Райта (обозначается как 2у) , новый целочисленный 2й алгоритм, (обозначается как 21), и, наконец, новый целочисленный 3^ — 1 алгоритм (обозначается как З1)

Работа алгоритмов прекращалась, когда каждая из компонент функции д становилась меньше Ю-4 Вычисления проводились для разных стартовых точек и размерностей Все компоненты стартовых точек выбирались одинаковыми В результатах вычислений для обозначения стартовой точки и размерности задачи используется запись (х, (Г) с целыми числами х и где число х обозначает величину компонент стартовой точки, а число й - размерность задачи Результаты вычислений, суммарные количества шагов, необходимые для достижения заданной точности, сведены в таблицу 1

Как следует из этой таблицы, новые алгоритмы 21 и 31 демонстрируют доминирующее, кратное превосходство над известными алгоритмами 12 и 2у Это превосходство составляет 2-4 раза при размерности <1 = 3 и увеличивается до 10-30 раз при размерностях ¿ = 10,20

Помимо случая невысоких размерностей и сильно нелинейных функций в исследовании также тестировался случай высоких размерностей и так называемых слабо нелинейных функций, характерный для задач, возникающих в области экономического моделирования Вычислительные эксперименты показали, что 21 и 31 алгоритмы работают в этом случае в диапазоне размерностей от 0 до 20000, при этом число шагов, за которое они сходятся к решению с точностью до 10~4 практически не зависит от размерности и составляет несколько сотен для 21 алгоритма и несколько десятков для З1 алгоритма

Такая хорошая сходимость объясняется тем, что на слабо нелинейных задачах траектории 21 алгоритма являются практически кусочно-линейными, а траектории З1 алгоритма - попросту всегда кусочно-линейными (состоящими из одномерных симплексов) Поэтому их сходимость не зависит от размерности

Более того, в работе рассмотрена модель рыночного ценооборазования определяемая следующими отношениями

/ I \ Е

У-'г = 0,1),, П, = рт, - СЫг, р = К I Уг П, = (р - са,К = -МХЛ -са« Ь'»=п«(г'1. IV/),

где и), ии,- объемы закупок и выпусков г-го участника, а, - скалярный коэффициент, опредетающий его технологию иП,- его прибыль Цены на рынке сырья и продукции обозначаются как сир Параметры К и Е лежат в диапазонах К > О, Е < 0 Оказалось, что равновесие в этой модели можно приблизить с помощью градиентного метода В работе доказана справедливость следующего утверждения

Теорема 3 Пусть

1

2 0 < а ^ а» = (к(1-Е) (1 + Е^а,^ , где е - основание натурагьных логарифмов,

3 -у"^1 =уп + Лип, где

д„п _ [а|М1п_£! Ьп(1 + - са>] - Рп-саг> 0, 1

г \aKEv?, рп - саг ^ О,

где |И = иег= и,/|М|, г € 1 I

Тогда сходится к V, 6 Ж+

В результате для данной модели удалось сравнить работу новых алгоритмов с градиентными методами Оказалось, что благодаря кусочно-линейному строению траекторий траекторий 21 и 31 алгоритмы намного опережают не только других представителей своего класса, но и градиентные методы

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

3 Основные результаты исследования

1 Разработаны целочисленные алгоритмы, намного превосходящие по своей вычислительной эффективности своих векторных предшественников

17

2 Разделение аппроксимации на сильную и слабую, введенное в исследовании, приводит к существенному ускорению работы целочисленного алгоритма и придает ему большую гибкость - возможность настройки на различные режимы работы

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

4 Результаты тестирования показали эффективность новых методов по сравнению с известными В том числе новые алгоритмы конкурируют по скорости с градиентными методами и способны работать с задачами очень высоких (»1000) размерностей

5 Вычисление стационарных точек нелинейных функций на множестве Ах

Ь может быть сделано с помощью стандартной процедуры линейного симплекс-метода

4 Список опубликованных работ по теме диссертации

1 МН Матвеев Процедура "нащупывания" точки Нэша — Сборник трудов ВНИИСИ - М ВНИИСИ 1991, N9 - стр 21-33

2 М Н Матвеев Использование целочисленных меток в алгоритмах поиска неподвижных точек - Динамика неоднородных систем - М КомКнига 2006, N10,-стр 118-124

3 М Н Матвеев Критерий существования многогранника, порождающего заданный веер - Динамика неоднородных систем - М КомКнига 2006, N10, -стр 125-136

4 М Н Матвеев Построение симплициального многогранника из куба -Проблемы вычислений в распределенной среде распределенные приложения, коммуникационные системы, математические модели и оптимизация Труды ИСА РАН - М КомКнига 2006, N25, - стр 212-216

Подписано в печать 11 04 2007 г Исполнено 13 04 2007 г Печать трафаретная

Заказ № 289 Тираж 70 экз

Типография «11-й ФОРМАТ» ИНН 7726330900 115230, Москва, Варшавское ш , 36 (495) 975-78-56 www autoreferat ru

Глава 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) с алгоритмом нахождения стационарных точек при линейных ограничениях непосредственно на уровне вычислений.

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.