Содержание к диссертации
Введение 3
Список основных обозначений 21
1 Барьерно-проективный метод для линейных задач допол
нительности 22
Устойчивый вариант барьерно-проективного метода .... 23
Допустимый вариант метода 34
Нелокальное поведение допустимого варианта метода ... 36
2 Барьерно-проективный метод с наискорейшим спуском
для линейных задач дополнительности 45
Дискретные варианты барьерно-проективного метода ... 46
Метод наискорейшего спуска 48
Конечная локальная сходимость 53
Правые части в особых парах 58
Модифицированный барьерно-проективный метод с наискорейшим спуском 60
Конечная нелокальная сходимость метода . 70
3 Барьерно-проективный метод для нелинейной задачи до
полнительности 78
3.1 Нелинейная задача дополнительности 79
Оглавление 2
Первый вариант метода 86
Второй вариант метода 94
Итеративные процессы 99
4 Вычислительные эксперименты 104
Задача распределенного равновесия 105
Реализация устойчивого варианта барьерно-проективного метода 112
Численная реализация допустимого варианта барьерно-проективного метода и метода с наискорейшим спуском . . 118
Вычислительные эксперименты с модифицированным методом наискорейшего спуска 122
Заключение 125
Список использованных источников 126
А Тестовые задачи 140
АЛ Задачи для тестирования методов 140
А.2 Задачи для тестирования модифицированного метода с
наискорейшим спуском 144
Введение к работе
В своей основной постановке задача дополнительности состоит в нахождении пары точек в n-мерном пространстве, связанных определенной функциональной зависимостью. При этом координаты искомых точек должны быть неотрицательны, и в каждой паре соответствующих координат не более чем одна величина может быть отлична от нуля.
Задачи дополнительности тесно связаны с двумя другими задачами математического программирования: решением вариационных неравенств и нахождением неподвижных точек. Теоремы существования и методы решения двух последних задач используются в теории задач дополнительности. И наоборот, идеи и специальные методы, разработанные для задач дополнительности, применяются для решения вариационных неравенств и для нахождения неподвижных точек [36, 41, 52, 64]. Обычно в литературе вариационные неравенства и задачи дополнительности рассматривают вместе. Это связано главным образом с тем обстоятельством, что задачи дополнительности являются важным частным случаем вариационных неравенств.
Вариационные неравенства стали изучаться в 1960-х годах, начиная с работы Дж. Стампаккьп. В эти же годы были опубликованы первые труды в этой области [59, 73, 74, 91]. Родоначальником теории вариационных неравенств стало вариационное исчисление. Исследования конечно-
Введение
мерных вариационных неравенств и нелинейных задач дополнительности (НЗД) начались также в первой половине 1960-х годов, но в отличие от бесконечномерных вариационных неравенств, они имеют происхождение в области математического программирования. Впервые НЗД была сформулирована в докторской диссертации Р. Коттла, основные результаты которой опубликованы в [37].
В последние десятилетия значительно вырос интерес к задачам дополнительности. Это связано с возможностью их применения для исследования и решения экономических, транспортных и других проблем, а также поиска равновесных состояний в игровых постановках. Подход, основанный на решении задач дополнительности, позволил создать и развить новые эффективные алгоритмы. Результаты многочисленных исследований в этом направлении представлены в фундаментальных монографиях Р. Коттла, Ж. Панга, Р. Стоуна [40], Ф. Факкинея, Ж. Панга [45], П. Харкера, Ж. Панга [57] и Ж. Панга [83]. В отечественной литературе наибольший интерес представляет учебное пособие Л.Д. Попова [26], в котором содержатся материал и упражнения по теории, методам и экономическим приложениям линейных и нелинейных задач дополнительности, а также конечномерным вариационным неравенствам. Методы решения конечномерных вариационных неравенств, частным случаем которых являются задачи дополнительности, представлены также в работе И.В. Коннова [22].
Для заданной функции F : Шп —> IR" связанная с ней задача допол-
Введение
нителыюсти состоит в нахождении такой точки х Є IRn, для которой
х > 0П,
F{x) > 0„, (1)
(х, F(x)) = 0.
Здесь (х, F(x)) — евклидово скалярное произведение векторов в Ип. Если F(x) = Мх + q, где М — квадратная матрица порядка п, q Є Hn, то задача становится линейной задачей дополнительности (ЛЗД).
ЛЗД является весьма общей постановкой, к решению которой сводятся многие оптимизационные и равновесные задачи. Известна тесная связь ЛЗД с задачей квадратичного программирования (ЗКП). А именно, если существует решение ЗКП с симметричной матрицей и с линейными ограничениями типа неравенства, то условия Каруша-Куна-Таккера (ККТ) определяют ЛЗД, в которой матрица М является бисим-метричной. Обратно, всегда можно поставить в соответствие линейному случаю задачи (1) ЗКП, причем, если допустимое множество в последней не пусто, то данная ЗКП обязательно имеет решение. Изучая ККТ-пары для ЗКП, можно исследовать вопросы существования и единственности решения ЛЗД. Отметим также, что к решению ЛЗД сводятся многие другие проблемы, например, биматричные игры, линейные задачи рыночного равновесия [48]. Поэтому методам решения ЛЗД уделяется много внимания.
К настоящему времени для решения ЛЗД разработано большое количество численных методов различных классов [4, 40]. Среди них особое место принадлежит итеративным методам (см., например, [32, 68]). Следует отметить методы симплексного типа, а также методы, заменяющие решение ЛЗД решением систем уравнений, полученных с использовани-
Введение
ем функций дополнительности [61]. В последние годы большое развитие получили методы внутренней точки, обобщающие соответствующие методы решения задач линейного программирования. Настоящая работа посвящена барьерно-проективным методам решения ЛЗД и НЗД, относящихся к классу методов внутренней точки. Рассмотрим более детально наиболее известные на данный момент методы решения ЛЗД.
Во многих работах, посвященных решению ЛЗД, либо исследуются границы применимости метода Лемке, либо предлагаются его обобщения [39, 43, 53, 72, 87, 88, 96, 97]. В основном варианте метода Лемке [70] рассматривается расширенная задача дополнительности, которая получается после введения вспомогательной скалярной переменной xq. А именно, вводится обозначение
у = Мх + dxo + q,
где d - произвольный вектор с положительными компонентами. На первой итерации все компоненты вектора х приравниваются нулю, а гго > 0 выбирается так, чтобы при этом уг > 0,г Є 1,п и для одного из номеров, например і = г, имело место равенство yr = 0. На каждом шаге алгоритма одна из небазисных переменных увеличивается или неограниченно (в этом случае алгоритм останавливается, не получив решения), или до тех пор, пока одна из базисных переменных не обратится в нуль. Понятно, что должна увеличиваться переменная, дополнительная к той (с тем же индексом, но из другого вектора), которая на предыдущей итерации вышла из базиса. Как только из базиса выводится переменная хо, мы получаем решение задачи дополнительности.
Помимо метода Лемке есть другие методы решения ЛЗД. Прежде всего нужно отметить метод Коттла-Данцига [38] и метод Мурти [81] (по-
Введение
следний метод называют также методом типа Барда). В методе Коттла-Данцига на каждой итерации находятся такие величины х и у = Mx + q, что хг > О, хгуг = О, і Є 1,п. Вычисления начинаются со значений х = 0 и проводятся таким образом, чтобы число отрицательных компонент вектора у убывало. В методе Мурти по итерациям выполняются только условия хгуг = 0, і Є 1,п. Пусть г - наименьший индекс, при котором одна из переменных хг, ут отрицательна. Эта отрицательная переменная заменятся в базисе ее дополнительной. Сходимость обоих методов доказана в предположении, что М - это Р-матрица, т.е. матрица, в которой все главные миноры положительны. Оба метода в дальнейшем были обобщены на случай нелинейной задачи дополнительности.
В последнее время, с повышением требований к размерности задачи, возросла роль методов внутренней точки в решении задач дополнительности. Этот подход был распространен на задачи дополнительности исходя из известных одноименных методов решения задач математического программирования. К примеру, один из первых алгоритмов внутренней точки для решения обобщенной ЛЗД, предложенный в [78], является переносом соответствующего метода решения задач линейного программирования [92]. Одновременно с ним был разработан подобный метод для решения ЛЗД [85], для глобальной сходимости которого требуется, чтобы матрица М принадлежала классу положительных полуопределенных матриц. Впоследствии метод был распространен на класс Р*-матриц [28, 62], который в действительности совпадает с классом достаточных матриц согласно классификации Р. Коттла. Для достаточных матриц из хг(Мх)г < О V і Є 1,п следует что хг(Мх)г = О V г Є 1,п, то же самое справедливо для транспонированной матрицы Мт. В по-
Введение
следнем методе на каждой итерации требуется разложение двух матриц, в то время как улучшенному методу [86] достаточно разложения одной матрицы, что повышает скорость его сходимости до сверхлинейной.
Очень хорошие результаты по скорости сходимости получены в [65], предложенный в этой работе алгоритм находит решение в случае положительно полуопределенной матрицы М. Однако по сравнению с предыдущими методами алгоритм требует, чтобы стартовая точка принадлежала допустимому множеству, тем не менее этот факт нисколько не умаляет достоинств предложенного метода. Другой метод [66], в котором цель каждой итерации - минимизировать специальным образом подобранную потенциальную функцию, применим для класса Р-матриц. Для того, чтобы найти точку, такую что для выбранного є > 0 выполняется хту < є, вводится в рассмотрение потенциальная функция
/(ж,у) = plnxTy -J^lnzy,
где р = р{п) > п. Направление движения выбирается в новом пространстве, полученном трансформацией основного пространства путем линейного масштабирования, результатом которого является равенство единице всех компонент точек х и у. На каждой итерации шаг градиента выбирается исходя из идеи минимизации потенциальной функции в новом пространстве, после чего идет возврат в основное пространство.
Наконец, стоит упомянуть исследования С. Райта в разработке методов внутренней точки для задач дополнительности. Предложенный им алгоритм [103], является модификацией метода для решения задач линейного программирования [108]. При заданной начальной точке (#(ь2/о)Т > Огп, итеративный процесс получает последовательность точек {хк,Ук)т > Огп, причем выбор точки измеряется близостью функции
Введение
качества
ф(х, у) = хту + \\у -Ых- q\\
к нулю. Очевидно, что пара (ж*,?/*) является решением ЛЗД тогда и только тогда, когда (х*,у*)т > 0гп и 0(ж*,г/*) = 0. В отличие от [108], в случае, когда значение функции качества становится меньше заданного порогового ф > 0, вводится понятие быстрого шага дискретизации, призванного ускорить сходимость.
Основные подходы к решению НЗД, такие как проективные методы, методы, использующие функции качества, методы, основанные на сведении НЗД к решению систем нелинейных уравнений, сглаживающие методы, методы внутренней точки и другие наиболее актуальные в настоящее время методы описаны в [47].
Первый вычислительный метод для этого класса задач предложил Р. Коттл [37]. Запишем систему (1) в форме
х > 0„, у > 0П,
У = F(x)t (2)
(х, у) = 0.
Для применимости метода делается предположение о невырожденности задачи, т.е. в любом решении х, у системы уравнений у = F(x) самое большее п из In компонент могут обращаться в нуль. Также предполагается, что отображение F : И" —* Жп дифференцируемо и его якобиан J(x) положительно ограничен, т.е. существует такое 6, 0 < S < 1, что для всех х Є Нп каждый главный минор матрицы J(x) лежит между 5 и J"1. В соотношении у = F{x) переменные у называются базисными, а переменные х - небазисными. Основной операцией в методе Коттла является обмен местами базисной и небазисной переменных хг,уг, который
Введение
осуществляется следующим образом. Уравнение ут = Fr(x) разрешается относительно хг. Полученное выражение
хт = ч?(х\ ...,xr-\yr,xr+\...,xn)
подставляется в уравнения у1 = Fl(x), г ф г. Новые базисные переменные снова обозначаются у, а небазисные х. Итерации алгоритма организованы таким образом, что число отрицательных базисных переменных не увеличивается. Метод Коттла находит решение за конечное число итераций.
Другой важный класс методов для решения НЗД — это методы симплексного типа. Поскольку доказательство теорем существования решения для НЗД опирается на факт существования неподвижной точки некоторого отображения, то естественно ожидать, что для решения НЗД оказались пригодными методы, ранее применявшиеся для отыскания неподвижных точек. Действительно, методы симплексного поиска, которые предложили Фишер, Гулд и Толле [50, 51], решают задачу (1) при самых широких условиях, обеспечивающих существование решения.
Подобно линейному случаю, другие методы решения НЗД предложены для некоторых специальных классов функций. Ряд методов разработан для Р-функций, которые обладают следующими двумя свойствами:
1. для любых х, и, х фи существует номер г = г(х, и) такой, что
{Xі - и1){Е\х) - F\u)) > 0;
2. для любого подмножества номеров J С {1,..., п} и любого заданного
вектора у система уравнений
уг = жг, і . J
Введение
разрешима относительно неизвестных х.
В [55] предложен алгоритм, который обобщает на случай нелинейных Р-функций алгоритм Мурти [81]. В нем J1 С {1,...,п} выбирается произвольным образом. Пусть уже найдено Jk, и Xk — решение системы нелинейных уравнений (3) при у = О, J = Jk. В этом случае точка Zk определяется по формулам
4 = 4. ie Jk-
Если Zk > 0, то решение найдено, в противном случае, пусть г - наименьший индекс, для которого zrk < 0. При г Є Jk полагаем Jk+1 = Jk\ {г}, а при г . Jk полагаем Jk+1 = Jk\J{r}. Показано, что если F является Р-функцией, то алгоритм Мурти находит решение задачи дополнительности за конечное число итераций.
В [56] предложен итерационный алгоритм
Хк+1 = к(Хк + P[-F(Xk)}+):
где [ ]+ означает выделение неотрицательной части функции, число /? > 0 вычисляется из определенного условия. Начальное приближение Х\ ф 0 берется в множестве
W = {x\x>0, (x,F(x)) = 0},
а параметр сек > 0 выбирается так, чтобы Хк+і Є W. В алгоритме предполагается, что Р(0) не является отрицательным вектором, так как в противном случае имеется очевидное решение х = 0. Сходимость метода доказана при довольно жестких условиях: функция F должна быть непрерывно дифференцируемой, якобиан J(x) - симметричная матрица, удовлетворяющая условию {u, J(x)u) > 7ІМІ2 Для всех х,и > 0 и некоторого 7 > 0.
Введение
Проективные методы основаны на том, что вектор х* является решением НЗД в том и только том случае, когда он удовлетворяет уравнению с неподвижной точкой
х = (х- 4F(x))+,
где 7 > 0 - произвольная константа, z+ - евклидова проекция вектора z на неотрицательный ортант. Классические проективные методы обладают глобальной сходимостью для достаточно малых 7 в случае, когда F -сильно монотонная и всюду липшицева функция [31]. Некоторые модификации [63, 82] проективных методов ослабляют требование с сильной монотонности функции до простой монотонности. Наконец, предложены способы выбора параметра 7 на каждой итерации так, что становится возможным снять требование достаточной малости константы 7 и лип-шицевости функции F [89, 90].
Важным классом методов для решения НЗД являются подходы, использующие функции качества. Если функция ф : К —> JR обладает следующими свойствами:
ф(х) > 0 для всех х Є ГО/1,
ф(х) = 0 в том и только том случае, когда х является решением
нзд,
то решение НЗД сводится к оптимизационной задаче minx6iR»^(:r). Однако наиболее известные функции качества, такие как неявная функция Лагранжа, предложенная Мангасарианом и Солодовым [76], функция качества Фишера-Бурмейстера [46] и штрафная функция Фишера-Бурмейстера [33], не являются дважды дифференцируемыми функциями, поэтому к ним нельзя напрямую применять классические методы
Введение
оптимизации. Основным вкладом функций качества является их использование для получения глобальной сходимости различных алгоритмов решения НЗД.
В настоящее время большое развитие получил подход к решению НЗД (а также других классов задач дополнительности), основанный на сведении задачи с помощью так называемых функций дополнительности к решению систем гладких или кусочно-гладких уравнений и в дальнейшем применении различных современных модификаций метода Ньютона. Среди функций дополнительности наибольшей популярностью пользуются функция естественной невязки, функция Фишера-Бурмейстера [49], штрафная функция Фишера-Бурмейстера [33], а также дифференцируемая на всем пространстве функция, введенная Евтушенко и Пуртовым [18]. Известны множество других функций дополнительности [75, 94]. Большинство из них являются негладкими функциями, в связи с чем предложены способы их сглаживания путем введения сглаживающего параметра [і > 0. Сглаживающие методы используют обычный метод Ньютона для решения системы нелинейных уравнений, идея заключается в том, чтобы в ходе итерационного процесса свести сглаживающий параметр к нулю. Данные методы обладают как локальной, так и глобальной сходимостью [34, 35, 58, 61, 77, 93].
Сглаживающие методы имеют интересную связь с методами внутренней точки. Например, в случае сведения НЗД к решению системы нелинейных уравнений с применением сглаживающей функции Фишера-Бурмейстера, решение полученной системы уравнений эквивалентно поиску решения, удовлетворяющего условиям центрального пути
Х{ > 0, Fi(x) > 0, xiFiix) = /j, Vi = 1, п.
Введение
Методы внутренней точки для решения НЗД впервые были предложены в 1989 году Кожима, Мизуно и Нома [67]. Условно все методы внутренней точки можно разделить на две категории: методы, требующие от стартовой точки принадлежность допустимому множеству, и методы, позволяющие брать начальную точку вне множества допустимости. Как правило, более жесткое требование к начальной точке дает выигрыш в скорости работы алгоритма, с другой стороны, в случае нелинейных задач поиск точки, принадлежащей допустимому множеству, может оказаться весьма нетривиальной задачей. В последние годы было предложено множество различных методов, принадлежащих классу методов внутренней точки [30, 54, 79, 98, 104, 105], они отличаются количеством линейных систем, которые надо решить на каждой итерации, выбором направления поиска следующей точки, выбором шага. Широкий обзор методов внутренней точки можно посмотреть в книгах [104, 106].
В данной работе для решения задач дополнительности предлагается новый метод, относящийся к классу методов внутренней точки. В отличие от упомянутых методов внутренней точки в нем используется градиентный спуск. Цель диссертационной работы:
разработать новые барьерно-проективные методы решения задач дополнительности, в том числе основанные на идее наискорейшего спуска;
провести аналитическое исследование методов;
исследовать поведение методов на тестовых примерах.
Работа состоит из введения, четырех глав, заключения, списка использованных источников и приложения.
Введение
В первой главе диссертации дается постановка ЛЗД, формулируются предположения о свойствах матрицы М и характере пары, являющейся решением задачи, в рамках которых будет проводиться дальнейшее исследование. Для построения основного варианта барьерно-проективного метода [6] используется устойчивый барьерно-проективный метод, предложенный ранее для решения задач линейного и нелинейного программирования [19, 44]. По существу, данным методом решается эквивалентная задача квадратичного программирования. Непрерывный вариант метода задается системой обыкновенных дифференциальных уравнений, причем решение ЛЗД является положением равновесия для этой системы. На основе теоремы Ляпунова об устойчивости по первому приближению доказывается, что решение ЛЗД является экспоненциально устойчивым положением равновесия для данной системы уравнений. Отсюда следует, что предложенный непрерывный метод обладает локальной сходимостью.
Считается, что решение ЛЗД [ж*, у*] является невырожденным в том смысле, что точки х* и у* представимы в виде
х* = [х?,х?], У* = [у*,У?],
где х? ,уВ Є И*, rrf,^ Є JRn~\ причем
я?>0ь zf = On_fc, 3/? = 0fc, y?>0n-k.
Особый интерес вызывает частный случай этого метода, в котором все пары являются допустимыми. Пусть D{z) — диагональная матрица с вектором z на диагонали и пусть матрица G(x, у) имеет следующий вид
G(x,y) = MD{x)MT + D{y).
Введение
Непрерывный вариант метода описывается следующей системой обыкновенных дифференциальных уравнений:
— = -D(x)[In + Q(x,y)(In-M)D{x)]y,
и (^)
J = -D(y)[ln-G-\x,y)(In-M)D(y)]x,
где Q(x,y) = MTG~1(x,y), In — единичная матрица порядка п. Локальная сходимость допустимого варианта метода следует из локальной сходимости основного варианта.
Рассматриваются свойства предложенных методов. В том числе, особое внимание уделяется исследованию нелокального поведения допустимого варианта метода. Показывается, что при выполнении определенных условий сильной невырожденности, для того, чтобы пара [х, у] была стационарной точкой системы (4), необходимо и достаточно, чтобы она была угловой точкой множества допустимости.
