Содержание к диссертации
Введение
1 Биматричные игры и d.c. максимизация 20
1.1 Основные определения и свойства биматричных игр 21
1.2 Некоторые известные методы поиска ситуаций равновесия 27
1.2.1 Вполне смешанные ситуаций равновесия 27
1.2.2 Исчерпывающий поиск 28
1.2.3 Перебор носителей стратегий 30
1.2.4 Биматричные игры и целочисленное линейное программирование 30
1.2.5 Связь с матричными играми 31
1.2.6 Перебор квадратных подматриц 32
1.3 Задача дополнительности и метод Лемке-Хаусона 34
1.4 Биматричные игры и математическое программирование 40
1.5 Постановка задачи d.c. максимизации и локальный поиск 43
1.6 Условия глобальной оптимальности 47
1.7 Стратегия глобального поиска 50
1.8 Сходимость стратегии глобального поиска 54
1.9 О разрешающих наборах 56
2 Основы поиска ситуаций равновесин в биматричной игре 60
2.1 D.C, представление целевой функции 60
2.2 Условия глобальной оптимальности 64
2.3 Локальный поиск 66
2.4 Алгоритм глобального поиска . 74
2.5 Решение задачи уровня 77
2.6 Вычисление интервала одномерного поиска 81
2.6.1 Поиск левой границы 7- 81
2.6.2 Поиск правой границы 7+ 81
2.7 Построение аппроксимации поверхности уровня 84
3 Численный поиск ситуаций равновесия 90
3.1 Особенности первого вычислительного эксперимента 90
3.2 Этап 1, Тестирование алгоритма глобального поиска 93
3.3 Этап 2. Решение случайно сгенерированных задач небольших размерностей 95
3-4 Этап 3. Выбор наилучшей аппроксимации поверхности уровня 101
3.5 Этап 4. Поиск ситуаций равновесия в играх большой размерности .105
3.6 Этап 5. Решение серий биматричных игр 108
3.7 Модификация алгоритма глобального поиска 110
3.8 Второй вычислительный эксперимент 113
Заключение 120
Приложение 122
Список литературы 126
- Основные определения и свойства биматричных игр
- Задача дополнительности и метод Лемке-Хаусона
- D.C, представление целевой функции
- Особенности первого вычислительного эксперимента
Основные определения и свойства биматричных игр
Нетрудно видеть, что при д{х) = 0 задача d.c. максимизации (0.0.7) обращается в задачу выпуклой максимизации (0.0.5), так что последняя явл-яется частным случаем (0.0.7). Аналогично задача с d.c. ограничениями (0.0.8) при /(х) = 0 обращается в задачу (0.0.б) на дополнении выпуклого множества, которая, таким образом, оказывается частным случаем (0.0.8). Итак, можно сказать, что простейшие задачи d.c. программирования (0.0.7) и (0.0.8) согласно предложенной классификации являются основными.
Заметим, что любая невыпуклая экстремальная квадратичная задача (т.е. задача, в которой целевая функция и функции, задающие ограничения типа равенств и неравенств, являются квадратичными) может быть отнесена к одному из вышеперечисленных классов, поскольку любая квадратичная функция в зависимости от знаков своих собственных значений является либо выпуклой, либо вогнутой, либо d.c. функцией. Таким образом, можно сказать, что приведенная классификация является исчерпывающей на классе невыпуклых квадратичных задач оптимизации. Более того, задачи с d.c. структурой играют важную роль в невыпуклой оптимизации как с теоретической точки зрения, так и ввиду огромного количества приложений.
Пионером в изучении свойств d.c. функций является А.Д. Александров [1,2]. Этой проблемой также занимались Е.М. Ландис [38] и П. Хартман [97]. Некоторые более поздние работы по d.c. структурам можно найти в [100, 104, 131, 143, 145].
Что касается общепринятых методов решения задач d.c. программирования, как уже говорилось, они пришли из дискретной оптимизации и совершенно не учитывают специфику и структуру задачи. Другой подход к решению подобных задач был развит в работах А.С. Стрекаловского. На основе предложенных условий глобальной оптимальности для четырех приведенных выше классов задач [71], [74]-[78], им и его учениками были разработаны стратегии глобального поиска для решения многих актуальных теоретических и прикладных задач оптимизации [37, 72, 73, 79, 80]. Особо следует отметить работы А.А. Кузнецовой по решению NP-трудной задачи дискретной оптимизации — поиск максимальной клики в неориентированном графе [112], а также работу Т.В. Яковлевой по решению задач об одномерном и многомерном рюкзаках [82].
Настоящая диссертационная работа посвящена поиску ситуаций равновесия по Нэшу в биматричных играх, который основан на равносильности задачи поиска равновесия и решения невыпуклой задачи d.c. максимизации. Актуальность данного направления исследований определяется необходимостью разработки математического аппарата поиска равновесных ситуаций, а также решения игровых задач посредством методов невьшуклой оптимизации с исследованием их сходимости и численной проверкой их эффективности. Опишем подробно содержание работы.
Диссертация состоит из введения, трех глав, заключения и приложения. В каждой главе используется своя нумерация параграфов, предложений, лемм, теорем, замечаний и формул. В первой главе представлены обзор методов исследования и решения биматричных игр (БИ), а также элементы подхода, разработанного А-С.Стрекаловским для решения задач d.c. программирования. В 1.1 приведена постановка биматричной игры, основные определения и формулируются основные свойства БИ. Некоторые из них даются с доказательствами. Далее, в 1.2 представлено несколько известных подходов к исследованию биматричных игр. В 1.3 подробно описан самый популярный метод отыскания равновесий в биматричных играх — метод Лемке-Хаусона. 1.4 посвящен подходу В.М. Мухамедиева к решению биматричной игры на базе теоремы эквивалентности задачи поиска ситуаций равновесия и отыскания глобального решения в билинейной невьшуклой задаче математического программирования. Оказывается, что последняя может быть рассмотрена как задача d.c. максимизации. Поэтому, в 1.5 приводится постановка задачи d.c максимизации, и изучается вопрос о локальном поиске в такой задаче. Затем, в 1.6 представлены необходимые и достаточные условия для глобального решения (УГО), установлена их связь с классическими условиями оптимальности, а также показано алгоритмическое свойство предложенных условий. В 1.7 рассматривается стратегия глобального поиска (СГП), заключающаяся в последовательном решении более простых подзадач и основанная на условиях глобальной оптимальности. В 1.8 приводится доказательство сходимости стратегии глобального поиска к глобальному решению исследуемой задачи. Особое внимание обращается на согласование констант решения различных подзадач. Здесь также вводится одно из главных новых понятий — определение разрешающего набора в задаче d.c. максимизации.. Наконец, в 1.9 рассматривается ослабление понятия разрешающего набора и доказываются некоторые его свойства. Вторая глава диссертации посвящена исследованию невыпуклой задачи математического программирования, глобальное решение которой дает точку равновесия по Нэшу в биматричной игре. В 2.1 приведены два варианта d.c. разложения целевой функции задачи, которые использовались при ее решении. В 2.2 доказаны условия глобальной оптимальности в терминах исследуемой задачи. 2.3 посвящен важнейшей составляющей глобального поиска — локальному поиску. Для поиска критической точки в исследуемой задаче предложена модификация метода Б.М. Мухамедиева из [40]. На основе условий глобальной оптимальности в 2.4 представлен алгоритм глобального поиска в рассматриваемой задаче. В последующих параграфах главы (2.5—2.7) проведено подробное решение подзадач, возникающих при реализации стратегии глобального поиска: решение задачи уровня, вычисление интервала одномерного поиска и самый важный момент — построение аппроксимации поверхности уровня. В третьей главе описываются вычислительные эксперименты по решению большого числа различных биматричных игр с анализом полученных результатов. 3.1 посвящен общим особенностям первого вычислительного эксперимента. Затем, в 3.2-3.6 по этапам рассмотрены его результаты по решению известных и произвольно сгенерированных биматричных игр различных размерностей. Приведены таблицы численного решения задач и дан их анализ.
Задача дополнительности и метод Лемке-Хаусона
Алгоритм Лемке-Хаусона перебирает с помощью последовательности преобразований (1.3.16) fc-почти полные дополняющие допустимые базисы для некоторого заданного к, на каждом шаге строя матрицу Т3 = I — qB VBI, а также имея в памяти список текущих базисных индексов и их соответствие столбцам матрицы Т5.
Схема всего алгоритма состоит в следующем. Процесс начинается с вырожденного решения и — (0, ). Базис, построенный после первого преобразования, будет получен добавлением либо индекса к7 либо индекса к -f (m -- п) и будет являться Аг-почти полным дополняющим допустимым базисом. Далее» если мы находимся в fc-почти дополняющем допустимом базисе Ь, который не является дополняющим, тогда новый элемент базиса будет равен либо /, либо I -f (m + «), где / — исключаемый из базиса В индекс. В частности, новый элемент будет равен /, если из базиса-был исключен 1 + (т +п) (соответственно I + (т + п), если был исключен /). Если элемент базиса, исключаемый на текущем шаге, равен к или к + (т + п), тогда новый базис будет дополняющим, а соответствующее ему решение искомым невырожденным решением задачи (LCP). В противном случае новый базис опять получится Ыгачти дополняющим допустимым, и процесс будет продолжен. Более подробное описание алгоритма с конкретными правилами выбора индексов можно найти в [10, 91].
Замечание 113.1 Если требуется отыскать несколько точек равновесия в бимат-ричной игре, описанный процесс можно запустить заново не с вырожденного решения, а с найденного невырожденного. В этом случае в результате может быть вычислено еще одно равновесие. Этот процесс можно продолжать до тех пор, пока снова не будет получено вырожденное решение задачи (LCP).
Геометрически, когда мы добавляем элемент в базис, мы перебираем грани множества точек, определенных с помощью уравнения Vu — q и условий щ = 0, для всех /, отличных от добавляемого, и не лежащих в базисе В. Точка, соответствующая базису В, является одной конечной точкой грани, а решение, соответствующее новому базису, — другой. Формулы пересчета базиса, приведенные выше, являются реализацией этого процесса.
Для большинства задач описанная процедура всегда позволяет найти единственный базис, определяющий другую конечную точку грани. Однако, в общем случае может случиться так, что несколько компонент вектора и одновременно получаются равными нулю и, следуя алгоритму, каждая из этих компонент должна быть удалена из базиса. Процедура для решения этой проблемы предлагается в [91]. В [10] и [91] также доказывается конечность описанного алгоритма и приводятся условия, при которых алгоритм не зацикливается.
Описанный алгоритм Лемке-Хаусона, как упоминалось во введении, является одним из самых популярных инструментов поиска одной ситуации равновесия в би-матричных играх. С его помощью могут быть найдены ситуации равновесия в играх размерности до 96 х 96 (см. [121]). К недостаткам метода можно отнести узкоспециа-лизированность, т.е. неприменимость к более широкому классу игр и невозможность получения некоторых точек равновесия даже при старте из различных дополняющих допустимых решений (см. замечание 1.3.1 и пример в 3.2). Кроме того, исследования эффективности метода Лемке-Хаусона показывают [135], что для некоторого класса биматричных игр, количество точек, просматриваемых в процессе решения, экспоненциально зависит от размерности задачи.
D.C, представление целевой функции
Во второй главе были рассмотрены все основные элементы реализации стратегии глобального поиска в задаче (Р) как для разложения целевой функции (2.1.1), так и для разложения (2.1.6). В этом параграфе описан первый вычислительный эксперимент в целом, проведенный на основе представленной выше теоретической базы. Все его этапы ниже рассмотрены более подробно, с приведением численных результатов и их анализом. Отметим, что предложенный алгоритм поиска ситуации равновесия по Нэшу в биматричной игре не накладывает никаких ограничений на элементы матриц А к В. При проведении первого вычислительного эксперимента решено достаточно большое количество биматричных игр различной размерности. На всех этапах локальный поиск производился с помощью модифицированного метода Б.М. Мухамедиева, описанного в 2.3 (задачи линейного программирования на его шагах решались методом опорного конуса [36]), задача уровня решалась аналитически (2.5), 7- и 7+ были найдены методами, описанными в 2.6, а построение аппроксимации поверхности уровня производилось с помощью множеств, представленных в 2.7. Величина щ вычислялась с использованием формулы (1.7.8). Представим краткую характеристику и цель каждого этапа эксперимента.
Первый этап. Прежде всего было произведено решение нескольких небольших классических задач, которые были найдены в различных источниках [58, 62, 83, 87, 99, 120, 144]. Цель первого этапа — показать принципиальную работоспособность предлагаемой методики решения биматричных игр на конкретных примерах с известными точками равновесия.
Второй этап. Далее была построена серия сгенерированных случайным образом игр с прямоугольными матрицами размерностей (2 х 2), (2 х 3), (2 х 4) и так далее до (10 х 10) по одной задаче каждой размерности (всего 81 задача). Подробное решение этих задач проводилось с целью оценить их сложность (время решения, количество полученных в процессе решения критических точек), а также продемонстрировать возможности алгоритма по решению случайно сгенерированных задач с любым сочетанием числа чистых стратегий у игроков. К тому же, для проверки гипотезы о независимости работы алгоритма глобального поиска от начального приближения, решение этих задач проводилось из двух стартовых точек.
Для решения задач первых двух этапов использовалась только аппроксимация поверхности уровня Dirl.
Третий этап. Затем производилось решение серии из 100 задач размерности (10 х 10) с использованием всех описанных в 2.7 аппроксимаций поверхности уровня и их комбинаций. Здесь была поставлена цель выбрать наилучшее сочетание аппроксимаций, которое использовалось далее при решении больших задач.
Эксперименты на всех вышеописанных этапах также производились параллельно с использованием двух d.c. представлений целевой функции задачи (Р). На четвертом этапе эксперимента решались случайно сгенерированные задачи с квадратными матрицами размерности от {11 х 11) с использованием лучшего представления целевой функции, выбранного на основе анализа результатов предыдущих этапов, и с применением лучшего сочетания аппроксимаций поверхности уровня. Задачи с квадратными матрицами были выбраны, как наиболее сложные. Цель этого этапа эксперимента — решить задачу как можно большей размерности.
Наконец, на последнем этапе первого вычислительного эксперимента производилось решение серий игр с квадратными матрицами размерностей от (2 х 2) до (32 х 32). Здесь требовалось оценить долю решенных (когда найдена точка, в которой с заданной точностью достигается оптимальное значение целевой функции) и нерешенных задач, а также ее изменение при возрастании размерностей биматрич-ных игр.
Если не оговорено особо, стартовая точка для задач на всех этапах выбиралась следующим образом: Легко видеть, что точка, построенная таким образом, будет допустимой. Далее, с целью уменьшить влияние машинных ошибок округления при построении множества индексов на пятом шаге алгоритма глобального поиска вместо условия g(u ,v3,as,pt) 7 проверялось условие Значение параметра и варьировалось на разных этапах эксперимента. Если положить v = 0.0, то алгоритм будет работать быстро, но при этом возрастает число нерешенных задач. При увеличении v количество нерешенных задач уменьшается, но при этом возрастает время получения глобального решения, поскольку условие (3.1.2) становится менее жестким и увеличивается мощность множества индексов. Одномерный поиск по 7 осуществлялся самым простым способом — наложением сетки значений на отрезок [7-,7+] ПРИ А 7 = (7+ 1-)1 Ч с последующим перебором этих значений. Параметр q, также как и t/, изменялся. Кроме того, на некоторых этапах вычислительного эксперимента решение одной задачи производилось с исполь зованием различных аппроксимаций поверхности уровня., т.е. алгоритм глобального поиска запускался несколько раз. В представленных ниже таблицах численных результатов используются следующие обозначения: № — номер задачи; т — количество чистых стратегий у игрока 1; п — количество чистых стратегий у игрока 2; 7- — левая граница отрезка изменения 7; 7+ — правая граница отрезка изменения -у; FQ — значение целевой функции в начальной точке (стартовое значение); Fm — наилучшее полученное значение целевой функции; х — оптимальная стратегия игрока 1; у оптимальная стратегия игрока 2; а, — оптимальный выигрыш игрока 1; /?« — оптимальный выигрыш игрока 2; hoc — количество запусков процедуры локального поиска; St — количества различных полученных критических точек; и — текущее значение параметра щ q — текущее значение параметра q; Imp — количество запусков алгоритма глобального поиска; Dir — используемое множество направлений; Т — общее время решения задачи или серии задач. Итак, общие свойства численного решения задач и используемые обозначения представлены. Перейдем к описанию особенностей и результатов каждого этапа вычислительного эксперимента в отдельности.
Особенности первого вычислительного эксперимента
Первое, что стоит отметить по результатам, представленным в таблице 5 — определенное влияние стартовой точки на процесс получения решения задач. Несмотря на то, что во всех задачах, как при использовании первого d.c. разложения, так и при использовании второго, с заданной точностью получено оптимальное значение целевой функции Fm — 0.0, по сравнению с результатами таблицы 4, в большинстве случаев изменилось количество запусков процедуры локального поиска, а в нескольких задачах и количество пройденных алгоритмом критических точек. Самое главное, для того чтобы получить решение задачи №44 при использовании первого d.c. разложения, потребовалось изменить значение параметра , оно было установлено равным 100, т.е. здесь использовалось более густое разбиение отрезка [7-,7+] (этот результат отмечен в таблице 5 курсивом). Во всех остальных случаях изменения параметров не потребоаалось.
Так же, как и в таблице 4, жирным шрифтом отмечены задачи, где количество пройденных алгоритмом критических точек для различных d.c. разложений не идентично. Здесь во время работы алгоритма при использовании первого d.c. представления в 30-ти задачах было получено две критических точки, в восьми задачах — три, в двух задачах — четыре. Для второго d.c. представления эти значения равны соответственно 28, 10 и 2. Здесь, также как и ранее, можно высказать предположние об определенном проигрыше в эффективности второго разложения целевой функции по сравнению с первым.
Несмотря на то, что значение целевой функции в начальной точке на этом этапе эксперимента в 76 задачах из 81 было меньше, чем на предыдущем этапе (т.е. дальше от глобального решения), количество задач, решенных только с помощью одного локального поиска увеличилось до 41. К тому же, общее число различных критических точек, пройденных алгоритмом, по сравнению с результатами таблицы 4, для первого разложения уменьшилось с 97 до 92, а для второго — со 100 до 94. Это означает, что второе начальное приближение, с точки зрения достижения глобального решения в рассматриваемой серии задач, для алгоритма глобального поиска проще, чем первое. Таким образом, можно видеть, что возможности достижения глобального решения с помощью алгоритма глобального поиска не зависят от выбора стартовой точки. Но при этом могут различаться параметры алгоритма и промежуточные результаты. При численном решении задач этого параграфа, в отличие от первых простых задач, особо отметим большое влияние параметров алгоритма q и v на достижение конечного результата. Это влияние не было предсказано теоретически, здесь проявляются известные особенности решения задач на вычислительных машинах.
Целью третьего этапа вычислительного эксперимента, описанного в этом параграфе является выбор аппроксимации поверхности уровня, которая позволяет решать биматричные игры с достаточной точностью и высокой скоростью. Для решения поставленной задачи использовались все множества направлений, описанные в 2.7. Тестирование аппроксимаций производилось на серии из 100 случайно сгенерированных задач размерности (10 х 10),
Также как и ранее, параллельно проводились эксперименты с использованием двух разложений целевой функции. Программы были реализованы в системе Delphi 6.0, расчеты проводились на компьютере PentiumIII-550. Точность решения задач, так же, как и ранее, была равна 10 7.
Остановимся на способе выбора параметров алгоритма глобального поиска q и v. На предыдущем этапе вычислительного эксперимента было отмечено, что изменение этих параметров может повлиять на исход всего глобального поиска. Наиболее надеж 101
ными значениями этих величин, которые были подобраны экспериментально, оакза-лись следующие: q = 100; и = 0.15. Однако, такой выбор параметров существенно замедляет решение тех задач, где для достижения глобального решения не требуется таких больших значений параметров. Для того чтобы увеличить скорость решения задач и при этом не потерять в надежности, было принято решение реализовать последовательное автоматическое изменение параметров алгоритма. Для параметра q экспериментально были выбраны значения 10 и 100; для параметра v — 0.00, 0.03, 0.15. Самым быстрым способом решения задач в этом случае является реализация алгоритма при q — 10 и v = 0.00, самым медленным — при q = 100 и и = 0.15. Последовательно производились шесть запусков алгоритма глобального поиска (со всеми комбинациями параметров).
Результаты решения задач с использованием десяти аппроксимаций поверхности уровня и их комбинаций представлены в таблицах б и 7 (для первого и второго d.c. разложений соответственно). Кроме обозначений, введенных выше, используются следующие: UnS — количество нерешенных задач в серии; гтах — максимальная невязка для нерешенных задач; "avr — средняя невязка по нерешенным задачам, а в колонках hoc и Т приведены суммарные значения соответствующих величин для всех 100 задач. Отметим также, что 25 из 100 сгенерированных задач решаются сразу на 1 шаге стратегии глобального поиска, и при их решении аппроксимации поверхности уровня участия не принимают. По результатам первой части этого этапа эксперимента, где при решении использовалось только одно множество направлений, можно отметить, что самой неэффективной при использовании двух разложений целевой функции оказалась аппроксимация на основе столбцов матрицы В и строк матрицы А, в то время как аппроксимация на основе столбцов матрицы А и строк матрицы В отработала удовлетворительно. Этот момент достаточно любопытен, однако его теоретическое объяснение пока не найдено и предоставляет поле для аналитических исследований.
