Барьерно-проективные методы для задач дополнительности тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

Введение

Список основных обозначений

1 Барьерно-проективный метод для линейных задач дополнительности

1.1 Устойчивый вариант барьерно-проективного метода

1.2 Допустимый вариант метода.

1.3 Нелокальное поведение допустимого варианта метода

2 Барьерно-проективный метод с наискорейшим спуском для линейных задач дополнительности

2.1 Дискретные варианты барьерно-ироективного метода

2.2 Метод наискорейшего спуска.

2.3 Конечная локальная сходимость.

2.4 Правые части в особых парах.

2.5 Модифицированный барьерно-проективный метод с наискорейшим спуском.

2.6 Конечная нелокальная сходимость метода.

3 Барьерно-проективный метод для нелинейной задачи дополнительности

3.1 Нелинейная задача дополнительности.

3.2 Первый вариант метода.

3.3 Второй вариант метода.

3.4 Итеративные процессы.

4 Вычислительные эксперименты

4.1 Задача распределенного равновесия.

4.2 Реализация устойчивого варианта барьерно-проективного метода.

4.3 Численная реализация допустимого варианта барьерно-проективного метода и метода с наискорейшим спуском

4.4 Вычислительные эксперименты с модифицированным методом наискорейшего спуска.

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

Задачи дополнительности тесно связаны с двумя другими задачами математического программирования: решением вариационных неравенств и нахождением неподвижных точек. Теоремы существования и методы решения двух последних задач используются в теории задач дополнительности. И наоборот, идеи и специальные методы, разработанные для задач дополнительности, применяются для решения вариационных неравенств и для нахождения неподвижных точек [36, 41, 52, 64]. Обычно в литературе вариационные неравенства и задачи дополнительности рассматривают вместе. Это связано главным образом с тем обстоятельством, что задачи дополнительности являются важным частным случаем вариационных неравенств.

Вариационные неравенства стали изучаться в 1960-х годах, начиная с работы Дж. Стампаккьи. В эти же годы были опубликованы первые труды в этой области [59, 73, 74, 91]. Родоначальником теории вариационных неравенств стало вариационное исчисление. Исследования конечномерных вариационных неравенств и нелинейных задач дополнительности (НЗД) начались также в первой половине 1960-х годов, но в отличие от бесконечномерных вариационных неравенств, они имеют происхождение в области математического программирования. Впервые НЗД была сформулирована в докторской диссертации Р. Коттла, основные результаты которой опубликованы в [37].

В последние десятилетия значительно вырос интерес к задачам дополнительности. Это связано с возможностью их применения для исследования и решения экономических, транспортных и других проблем, а также поиска равновесных состояний в игровых постановках. Подход, основанный на решении задач дополнительности, позволил создать и развить новые эффективные алгоритмы. Результаты многочисленных исследований в этом направлении представлены в фундаментальных монографиях Р. Коттла, Ж. Панга, Р. Стоуна [40], Ф. Факкинея, Ж. Панга [45], П. Харкера, Ж. Панга [57] и Ж. Панга [83]. В отечественной литературе наибольший интерес представляет учебное пособие Л.Д. Попова [26], в котором содержатся материал и упражнения по теории, методам и экономическим приложениям линейных и нелинейных задач дополнительности, а также конечномерным вариационным неравенствам. Методы решения конечномерных вариационных неравенств, частным случаем которых являются задачи дополнительности, представлены также в работе И.В. Коннова [22].

Для заданной функции F : IRn IR" связанная с ней задача дополнителыюсти состоит в нахождении такой точки х £ IRn, для которой х > 0П,

F{x) > 0n, (1) х, F(x)) = 0.

Здесь (х, F{x)) — евклидово скалярное произведение векторов в Ип. Если F(x) = Мх + q, где М — квадратная матрица порядка п, q G IRn, то задача становится линейной задачей дополнительности (ЛЗД).

ЛЗД является весьма общей постановкой, к решению которой сводятся многие оптимизационные и равновесные задачи. Известна тесная связь ЛЗД с задачей квадратичного программирования (ЗКП). А именно, если существует решение ЗКП с симметричной матрицей и с линейными ограничениями типа неравенства, то условия Каруша-Куна-Таккера (ККТ) определяют ЛЗД, в которой матрица М является бисим-метричной. Обратно, всегда можно поставить в соответствие линейному случаю задачи (1) ЗКП, причем, если допустимое множество в последней не пусто, то данная ЗКП обязательно имеет решение. Изучая ККТ-пары для ЗКП, можно исследовать вопросы существования и единственности решения ЛЗД. Отметим также, что к решению ЛЗД сводятся многие другие проблемы, например, биматричные игры, линейные задачи рыночного равновесия [48]. Поэтому методам решения ЛЗД уделяется много внимания.

К настоящему времени для решения ЛЗД разработано большое количество численных методов различных классов [4, 40]. Среди них особое место принадлежит итеративным методам (см., например, [32, 68]). Следует отметить методы симплексного типа, а также методы, заменяющие решение ЛЗД решением систем уравнений, полученных с использованием функций дополнительности [61]. В последние годы большое развитие получили методы внутренней точки, обобщающие соответствующие методы решения задач линейного программирования. Настоящая работа посвящена барьерно-проективным методам решения ЛЗД и НЗД, относящихся к классу методов внутренней точки. Рассмотрим более детально наиболее известные на данный момент методы решения ЛЗД.

Во многих работах, посвященных решению ЛЗД, либо исследуются границы применимости метода Лемке, либо предлагаются его обобщения [39, 43, 53, 72, 87, 88, 96, 97]. В основном варианте метода Лемке [70] рассматривается расширенная задача дополнительности, которая получается после введения вспомогательной скалярной переменной xq. А именно, вводится обозначение у = Мх + dx о + q, где d - произвольный вектор с положительными компонентами. На первой итерации все компоненты вектора х приравниваются нулю, а гго > 0 выбирается так, чтобы при этом уг > 0,г Е 1,п и для одного из номеров, например i = г, имело место равенство уг = 0. На каждом шаге алгоритма одна из небазисных переменных увеличивается или неограниченно (в этом случае алгоритм останавливается, не получив решения), или до тех пор, пока одна из базисных переменных не обратится в нуль. Понятно, что должна увеличиваться переменная, дополнительная к той (с тем же индексом, но из другого вектора), которая на предыдущей итерации вышла из базиса. Как только из базиса выводится переменная Хо, мы получаем решение задачи дополнительности.

Помимо метода Лемке есть другие методы решения ЛЗД. Прежде всего нужно отметить метод Коттла-Данцига [38] и метод Мурти [81] (последний метод называют также методом типа Барда). В методе Коттла-Данцига на каждой итерации находятся такие величины х и у = Mx + q, что хг > 0, хгуг = 0, г £ 1,п. Вычисления начинаются со значений х = 0 и проводятся таким образом, чтобы число отрицательных компонент вектора у убывало. В методе Мурти по итерациям выполняются только условия хгуг = 0, г Е 1,п. Пусть г - наименьший индекс, при котором одна из переменных хг, уГ отрицательна. Эта отрицательная переменная заменятся в базисе ее дополнительной. Сходимость обоих методов доказана в предположении, что М - это Р-матрица, т.е. матрица, в которой все главные миноры положительны. Оба метода в дальнейшем были обобщены на случай нелинейной задачи дополнительности.

В последнее время, с повышением требований к размерности задачи, возросла роль методов внутренней точки в решении задач дополнительности. Этот подход был распространен на задачи дополнительности исходя из известных одноименных методов решения задач математического программирования. К примеру, один из первых алгоритмов внутренней точки для решения обобщенной ЛЗД, предложенный в [78], является переносом соответствующего метода решения задач линейного программирования [92]. Одновременно с ним был разработан подобный метод для решения ЛЗД [85], для глобальной сходимости которого требуется, чтобы матрица М принадлежала классу положительных полуопределенных матриц. Впоследствии метод был распространен на класс Р*-матриц [28, 62], который в действительности совпадает с классом достаточных матриц согласно классификации Р. Коттла. Для достаточных матриц из хг(Мх)1 < О V г 6 1,п следует что хг(Мх)г = О V г G 1 ,п, то же самое справедливо для транспонированной матрицы Мт. В последнем методе на каждой итерации требуется разложение двух матриц, в то время как улучшенному методу [86] достаточно разложения одной матрицы, что повышает скорость его сходимости до сверхлинейной.

Очень хорошие результаты по скорости сходимости получены в [65], предложенный в этой работе алгоритм находит решение в случае положительно полуопределенной матрицы М. Однако по сравнению с предыдущими методами алгоритм требует, чтобы стартовая точка принадлежала допустимому множеству, тем не менее этот факт нисколько не умаляет достоинств предложенного метода. Другой метод [66], в котором цель каждой итерации - минимизировать специальным образом подобранную потенциальную функцию, применим для класса Р-матриц. Для того, чтобы найти точку, такую что для выбранного е > 0 выполняется хту < е, вводится в рассмотрение потенциальная функция ж, у) = р1пхту-^2^хгуг, где р = р{п) > п. Направление движения выбирается в новом пространстве, полученном трансформацией основного пространства путем линейного масштабирования, результатом которого является равенство единице всех компонент точек х и у. На каждой итерации шаг градиента выбирается исходя из идеи минимизации потенциальной функции в новом пространстве, после чего идет возврат в основное пространство.

Наконец, стоит упомянуть исследования С. Райта в разработке методов внутренней точки для задач дополнительности. Предложенный им алгоритм [103], является модификацией метода для решения задач линейного программирования [108]. При заданной начальной точке (я(ь2/о)Т > Огп, итеративный процесс получает последовательность точек {хк,Ук)т > 0гп, причем выбор точки измеряется близостью функции качества ф{х, у) = хту + ||у - Мх - q\\ к нулю. Очевидно, что пара (ж*,?/*) является решением ЛЗД тогда и только тогда, когда (х*,у*)т > 0гп и = 0. В отличие от [108], в случае, когда значение функции качества становится меньше заданного порогового ф > 0, вводится понятие быстрого шага дискретизации, призванного ускорить сходимость.

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

Первый вычислительный метод для этого класса задач предложил Р. Коттл [37]. Запишем систему (1) в форме х > 0„, у> 0П,

У = F(x)t (2) х, у) = 0.

Для применимости метода делается предположение о невырожденности задачи, т.е. в любом решении х,у системы уравнений у = F(x) самое большее п из 2п компонент могут обращаться в нуль. Также предполагается, что отображение F : ]Rn —> ]Rn дифференцируемо и его якобиан J(x) положительно ограничен, т.е. существует такое 6, 0 < S < 1, что для всех х G IRn каждый главный минор матрицы J{x) лежит между 5 и J"1. В соотношении у = F{x) переменные у называются базисными, а переменные х - небазисными. Основной операцией в методе Коттла является обмен местами базисной и небазисной переменных хг,уг, который осуществляется следующим образом. Уравнение уг = Fr(x) разрешается относительно хг. Полученное выражение xr = <pr(x\.,xr-\yr,xr+\.,xn) подставляется в уравнения у1 = Fl(x), г ф г. Новые базисные переменные снова обозначаются у, а небазисные х. Итерации алгоритма организованы таким образом, что число отрицательных базисных переменных не увеличивается. Метод Коттла находит решение за конечное число итераций.

Другой важный класс методов для решения НЗД — это методы симплексного типа. Поскольку доказательство теорем существования решения для НЗД опирается на факт существования неподвижной точки некоторого отображения, то естественно ожидать, что для решения НЗД оказались пригодными методы, ранее применявшиеся для отыскания неподвижных точек. Действительно, методы симплексного поиска, которые предложили Фишер, Гулд и Толле [50, 51], решают задачу (1) при самых широких условиях, обеспечивающих существование решения.

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

1. для любых х, и, х фи существует номер г = i(x, и) такой, что х* - и1){Е\х) - F\u)) > 0;

2. для любого подмножества номеров J С {1,., п} и любого заданного вектора у система уравнений у1 = Г(х), i € J, уг = х\ i ф. J разрешима относительно неизвестных х.

В [55] предложен алгоритм, который обобщает на случай нелинейных Р-функций алгоритм Мурти [81]. В нем J1 С {1,.,п} выбирается произвольным образом. Пусть уже найдено Jk, и — решение системы нелинейных уравнений (3) при у = О, J = Jk. В этом случае точка Zk определяется по формулам

4 = 4> *G

Если > 0, то решение найдено, в противном случае, пусть г - наименьший индекс, для которого zrk < 0. При г G Jk полагаем Jk+1 = Jk\ {г}, а при г £ Jk полагаем Jk+1 = Jk\J{r}. Показано, что если F является Р-функцией, то алгоритм Мурти находит решение задачи дополнительности за конечное число итераций.

В [56] предложен итерационный алгоритм

Xk+i = ®к(хк + P[-F(xk)}+), где [ ]+ означает выделение неотрицательной части функции, число /? > 0 вычисляется из определенного условия. Начальное приближение х\ Ф 0 берется в множестве

W = {x\x> 0, (x,F(x)) = 0}, а параметр ось > 0 выбирается так, чтобы xk+i G W. В алгоритме предполагается, что F(0) не является отрицательным вектором, так как в противном случае имеется очевидное решение х = 0. Сходимость метода доказана при довольно жестких условиях: функция F должна быть непрерывно дифференцируемой, якобиан J(x) - симметричная матрица, удовлетворяющая условию {u,J(x)u) > 7||u||2 для всех х,и > 0 и некоторого 7 > 0.

Проективные методы основаны на том, что вектор х* является решением НЗД в том и только том случае, когда он удовлетворяет уравнению с неподвижной точкой х = (х- ^F(x))+, где 7 > 0 - произвольная константа, z+ - евклидова проекция вектора z на неотрицательный ортант. Классические проективные методы обладают глобальной сходимостью для достаточно малых 7 в случае, когда F -сильно монотонная и всюду липшицева функция [31]. Некоторые модификации [63, 82] проективных методов ослабляют требование с сильной монотонности функции до простой монотонности. Наконец, предложены способы выбора параметра 7 на каждой итерации так, что становится возможным снять требование достаточной малости константы 7 и лип-шицевости функции F [89, 90].

Важным классом методов для решения НЗД являются подходы, использующие функции качества. Если функция ф : IRn —> 1R обладает следующими свойствами:

1. ф(х) > 0 для всех х G IRn,

2. ф(х) = 0 в том и только том случае, когда х является решением НЗД, то решение НЗД сводится к оптимизационной задаче minx6ian ф{х). Однако наиболее известные функции качества, такие как неявная функция Лагранжа, предложенная Мангасарианом и Солодовым [76], функция качества Фишера-Бурмейстера [46] и штрафная функция Фишера-Бурмейстера [33], не являются дважды дифференцируемыми функциями, поэтому к ним нельзя напрямую применять классические методы оптимизации. Основным вкладом функций качества является их использование для получения глобальной сходимости различных алгоритмов решения НЗД.

В настоящее время большое развитие получил подход к решению НЗД (а также других классов задач дополнительности), основанный на сведении задачи с помощью так называемых функций дополнительности к решению систем гладких или кусочно-гладких уравнений и в дальнейшем применении различных современных модификаций метода Ньютона. Среди функций дополнительности наибольшей популярностью пользуются функция естественной невязки, функция Фишера-Бурмейстера [49], штрафная функция Фишера-Бурмейстера [33], а также дифференцируемая на всем пространстве функция, введенная Евтушенко и Пуртовым [18]. Известны множество других функций дополнительности [75, 94]. Большинство из них являются негладкими функциями, в связи с чем предложены способы их сглаживания путем введения сглаживающего параметра fi > 0. Сглаживающие методы используют обычный метод Ньютона для решения системы нелинейных уравнений, идея заключается в том, чтобы в ходе итерационного процесса свести сглаживающий параметр к нулю. Данные методы обладают как локальной, так и глобальной сходимостью [34, 35, 58, 61, 77, 93].

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

Xi > 0, Fi(x) > 0, XiFiix) = /j, Vi = 1, п.

Методы внутренней точки для решения НЗД впервые были предложены в 1989 году Кожима, Мизуно и Нома [67]. Условно все методы внутренней точки можно разделить на две категории: методы, требующие от стартовой точки принадлежность допустимому множеству, и методы, позволяющие брать начальную точку вне множества допустимости. Как правило, более жесткое требование к начальной точке дает выигрыш в скорости работы алгоритма, с другой стороны, в случае нелинейных задач поиск точки, принадлежащей допустимому множеству, может оказаться весьма нетривиальной задачей. В последние годы было предложено множество различных методов, принадлежащих классу методов внутренней точки [30, 54, 79, 98, 104, 105], они отличаются количеством линейных систем, которые надо решить на каждой итерации, выбором направления поиска следующей точки, выбором шага. Широкий обзор методов внутренней точки можно посмотреть в книгах [104, 106].

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

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

• провести аналитическое исследование методов;

• исследовать поведение методов на тестовых примерах.

Работа состоит из введения, четырех глав, заключения, списка использованных источников и приложения.

В первой главе диссертации дается постановка ЛЗД, формулируются предположения о свойствах матрицы М и характере пары, являющейся решением задачи, в рамках которых будет проводиться дальнейшее исследование. Для построения основного варианта барьерно-проективного метода [6] используется устойчивый барьерно-проективный метод, предложенный ранее для решения задач линейного и нелинейного программирования [19, 44]. По существу, данным методом решается эквивалентная задача квадратичного программирования. Непрерывный вариант метода задается системой обыкновенных дифференциальных уравнений, причем решение ЛЗД является положением равновесия для этой системы. На основе теоремы Ляпунова об устойчивости по первому приближению доказывается, что решение ЛЗД является экспоненциально устойчивым положением равновесия для данной системы уравнений. Отсюда следует, что предложенный непрерывный метод обладает локальной сходимостью.

Считается, что решение ЛЗД [ж*, у*] является невырожденным в том смысле, что точки х* и у* представимы в виде х* - у* = [у*,у?], где х*,у* G И*, rrf,^ G JRn~\ причем я? > 0*, х? = 0nfc, у? = Ofc, у? > 0п-к.

Особый интерес вызывает частный случай этого метода, в котором все пары являются допустимыми. Пусть D{z) — диагональная матрица с вектором z на диагонали и пусть матрица G(x, у) имеет следующий вид

G(x,y) = MD{x)MT + D{y).

Непрерывный вариант метода описывается следующей системой обыкновенных дифференциальных уравнений: где Q(x,y) = MTG~1(x,y), In — единичная матрица порядка п. Локальная сходимость допустимого варианта метода следует из локальной сходимости основного варианта.

Рассматриваются свойства предложенных методов. В том числе, особое внимание уделяется исследованию нелокального поведения допустимого варианта метода. Показывается, что при выполнении определенных условий сильной невырожденности, для того, чтобы пара [х, у] была стационарной точкой системы (4), необходимо и достаточно, чтобы она была угловой точкой множества допустимости.

Глава 2 посвящена разработке варианта метода, относящегося к классу методов внутренней точки и основанного на идее наискорейшего спуска. Метод строится с использованием допустимого варианта барьерно-проективного метода, предложенного в первой главе, поэтому сначала приводятся дискретные схемы непрерывных аналогов. Используя схему Эйлера для интегрирования системы (4), приходим к следующим рекуррентным соотношениям: xk+i = D(xk) {е - ак [ln + MTG~l(xk, ук) (/„ - М) D{xk)] ук} , ук+1 = D(yk) {е - ак [ln - G~l(xk, ук) (/„ - М) D(yk)] хк} , где е — n-мерный вектор, состоящий из единиц, ак — шаг перемещения (ак > 0). Допустимая начальная пара [жо, у о] берется строго внутренней, т.е. удовлетворяет условиям xq > 0п, уо > 0П. Показывается, что если [я*,?/*] — невырожденное решение ЛЗД, то найдется такое а*, что для dx

-D{x) [In + Q(x, y){In - M)D{x)] y, -D(y) [In - G-\x,y){In - M)D(y)} x dt ay dt

4) всех постоянных 0 < < а* все последующие пары являются строго внутренними и итеративный процесс (5) локально линейно сходится к [ж*, у*].

Цель состоит в том, чтобы рассмотреть модификацию метода (5), обладающую конечной нелокальной сходимостью. Если шаг о^ в (5) на каждой итерации выбирается таким образом, чтобы Xk+i > 0П и Ук+i > 0П, то все пары [хк, ук],к >0 оказываются допустимыми. Это дает возможность взять шаг максимально возможным из условия минимизации значения билинейной функции V(x,y) = утх вдоль направлений перемещений, разумеется, не позволяя новым точкам покидать ортант И". Однако в том случае, когда Хк или у к оказываются на границе ор-танта 1R", рекуррентные соотношения (5) становятся непригодными для расчетов из-за наличия эффекта "прилипания". Данный эффект заключается в том, что, в силу соотношений (5), любая нулевая компонента х\ вектора Хк или любая нулевая компонента у^ вектора ук не могут в дальнейшем стать положительными. У отображений, стоящих в правых частях соотношений (5), могут появиться дополнительные неподвижные точки, не являющиеся решением задачи. Поэтому требуется изменить численную схему (5), чтобы устранить указанный недостаток.

С этой целью рассматривается модифицированный вариант барьерно-проективного метода с наискорейшим спуском. Он отличается от основного направлениями, вычисляемыми в парах, являющихся стационарными точками системы (4). Предлагается определять в таких парах направления в измененных точках. Это приводит к тому, что особые пары, за исключением решения задачи, перестают быть стационарными точками итеративного процесса. Геометрически подсчет правых частей в измененных точках может быть интерпретирован как сдвиг одного из ограничений хг > 0 или уг > 0 в этой паре. Для задач линейного программирования аналогичный прием применялся в [107]. Доказывается конечная нелокальная сходимость модифицированного варианта метода.

Глава 3 посвящена нелинейной задаче дополнительности. Так как НЗД является важным частным случаем вариационного неравенства, то основные результаты, касающиеся существования и единственности решения НЗД, связаны с соответствующими результатами для вариационных неравенств. Вначале приведена постановка НЗД и даны некоторые сведения из теории НЗД: основные определения, классы рассматриваемых функций, некоторые условия существования решения, а также свойства множества решений.

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

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

В Главе 4 представлены результаты вычислительных экспериментов, которые проводились с целью тестирования предложенных методов для решения ЛЗД и сравнения их эффективности. В качестве тестовой задачи размерности п = 10 взят численный пример прикладной равновесной задачи, ранее сформулированной в [29], которая в результате преобразований принимает вид линейной задачи дополнительности с положительно определенной матрицей М и ненулевым вектором q. Модель распределенного равновесия представлена в виде ориентированного графа, вершины которого представляют собой некоторые множества производителей/потребителей, а дуги - транспортные пути, по которым может перевозиться груз. Закон сохранения продукта, условия неотрицательности транспортируемого продукта, условия стабильности цен и законы ценообразования - составляют ЛЗД.

Предложенные в диссертации методы для решения ЛЗД реализованы в среде MATLAB. Численные реализации методов протестированы на тестовых примерах разных размерностей: от п = 2 до п = 150.

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

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

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

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

В приложении А приведены некоторые из примеров (небольшой размерности), использовавшихся для тестирования методов.

В работе используются некоторые сведения из матричного анализа. Подробное изложение теории матриц можно найти, например, в книгах [3, 5, 15, 23, 27].

Основные результаты диссертации опубликованы в четырех работах [б, 7, 8, 9] и доложены на:

• международных научных конференциях [13, 99, 100, 101, 102];

• всероссийских научных конференциях [10];

• научных конференциях МФТИ [11, 12, 14].

Автор выражает глубокую признательность своему научному руководителю и наставнику Виталию Григорьевичу Жадану за постановку задачи, ценные советы, постоянную поддержку и внимание к работе.

Список основных обозначений

IRn — n-мерное евклидово пространство; ж1,а?2, .,хп] — вектор х G IRn с координатами xl,i € 1,п;

И" = {х 6 IR" : хг > 0, i G 1, п} — неотрицательный ортант в 1R1 а;, ?/) = 1 ж V ~ евклидово скалярное произведение;

0П = [0,0] — нулевой n-мерный вектор;

Опт ~ нулевая матрица размеров п х га; е — n-мерный вектор, состоящий из единиц; п — единичная матрица порядка п;

Ат — транспонированная матрица Л;

Л-1 — матрица, обратная к А;

D(x) — диагональная матрица с вектором х на диагонали; х\\ — евклидова норма вектора х; rc||oo = maxi<i<n \хг\ — чебышевская норма вектора х\

Л|| — норма матрицы Л, согласованная с нормой в пространстве ров; fvX — граница множества X; ej — j-й единичный орт; 0 — пустое множество; ak — шаг дискретизации.

Заключение

В заключение кратко сформулируем основные результаты работы.

1. Разработан барьерно-ироективный метод для решения линейных задач дополнительности (ЛЗД) с положительно определенной матрицей. Доказаны локальная сходимость и устойчивость метода.

2. Разработан новый метод для решения ЛЗД, основанный на идее наискорейшего спуска. Исследованы свойства метода.

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

4. Предложенные методы обобщены для решения нелинейной задачи дополнительности.

5. В качестве приложения рассмотрена задача распределенного равновесия.

6. Исследовано поведение методов на тестовых примерах.

1. Базара М., Шетти К. Нелинейное программирование. Теория и алгоритмы. // М.: Мир, 1982.

2. Бакушинский А.Б. Методы решения монотонных вариационных неравенств, основанные на принципе итеративной регуляризации. // Журнал вычислительной математики и математической физики. 1977. Т. 17. № 6. С. 1350-1362.

3. Беллман Р. Введение в теорию матриц. // М.: Наука, 1969.

4. Берщанский Я.М., Мееров М.В. Теория и методы решения задач дополнительности // Автоматика и телемеханика. № 6. С. 5-31.

5. Воеводин В.В., Кузнецов Ю.Ф. Матрицы и вычисления. // М.: Наука, 1984.

6. Втюрина М.В., Жадан В.Г. Барьерно-градиентные методы для линейных задач дополнительности. // Сообщения но прикладной математике. Препринт. М.: ВЦ РАН, 2003. 31 с.

7. Втюрина М.В., Жадан В.Г. Свойства непрерывного варианта барьерно-градиеитного метода в допустимой области для линейных задач дополнительности. // Моделирование процессов управления. М.: МФТИ, 2004. С. 149-154.

8. Втюрина М.В., Жадан В.Г. Барьерно-проективный метод с наискорейшим спуском для линейных задач дополнительности. // Журнал вычислительной математики и математической физики. 2005. Т. 45. № 5. С. 792-812.

9. Втюрина М.В. Численная реализация барьерно-проективных методов для линейных задач дополнительности. // Процессы и методы обработки информации. М.: МФТИ. 2006. С. 93-103.

10. Втюрина М.В., Жадан В.Г. Об одном варианте барьерно-проективного метода для решения линейной задачи дополнительности. // Тезисы всероссийской конференции "Проблемы оптимизации и экономические приложения". Материалы конференции. Омск. 2003. С. 119.

11. Втюрина М.В., Жадан В.Г. Метод внутренней точки с наискорейшим спуском для линейной задачи дополнительности. // Труды XIII

12. Байкальской международной школы-семинара "Методы оптимизации и их приложения". Т. 1. Математическое программирование. Иркутскмк: Изд-во ИСЭМ СО РАН. 2005. С. 113-118.

13. Гантмахер Ф.Р. Теория матриц. // М.: Наука, 1988.

14. Демидович Б.П. Лекции по математической теории устойчивости. // М.: Наука, 1967.

15. Евтушенко Ю.Г. Методы решения экстремальных задач и их применение в системах оптимизации. // М.: Наука, 1982.

16. Евтушенко Ю.Г., Пуртов В.А. Достаточные условия для минимума в задачах нелинейного программирования. // Доклады АН СССР. 1984. Т. 278. № 1. Р. 24-26.

17. Евтушенко Ю.Г., Жадан В.Г. Барьерно-проективные методы для решения задач нелинейного программирования. // Журнал вычисл. матем. и матем. физ., 1994. Т. 34. №5. С. 669-684.

18. Зыкина А.В. Решение обратной нелинейной задачи дополнительности. // Труды XIII Байкальской международной школы-семинара "Методы оптимизации и их приложения". Т. 1. Математическое программирование. Иркутскмк: Изд-во ИСЭМ СО РАН. 2005. С. 215220.

19. Измаилов А.Ф., Солодов М.В. Численные методы оптимизации. // М.: Физматлит, 2003.

20. Коннов И.В. Методы решения конечномерных вариационных неравенств. // Курс лекций. Казань: ДАС. 1998.

21. Ланкастер П. Теория матриц. // М.: Наука, 1978.

22. Олжабаев Б.Т., Данильченко Т.Н. Экономическое равновесие и задачи линейной дополнительности. // Препринт ВЦ АН СССР, 1991.

23. Дж. Ортега, В.Рейнболдт. Итерационные методы решения нелинейных систем уравнений со многими неизвестными. // М.: Мир, 1975.

24. Попов Л.Д. Введение в теорию, методы и экономические приложения задач о дополнительности. // Учеб. пособие. Екатеринбург: Изд-во Уральского университета. 2001.

25. Р. Хорн, Ч. Джонсон. Матричный Анализ. // М.: Мир, 1989.

26. Anitescu М., Lesaja G., Potra F.A. An infeasible-interior-point predictor-corrector algorithm for the P*-Geometric LCP. // Applied Mathematics and Optimization. 1997. V. 36. № 2. P. 203-228.

27. Asmuth R., Eaves B.C., Peterson E.L. Computing economic equilibria on affine networks with Lemke's algorithm. // Mathematics of operations research, 4 (1979), P. 209-214.

28. Bellavia S., Macconi M. An inexact interior-point method for monotone NCP. // Optimization methods and software. 1999. V. 11-12. P. 211241.

29. Bertsekas D.P., Tsitsiklis J.N. Parallel and distributed computation: numeriacal methods. // Prentice-Hall. New Jersey. 1989.

30. Burke J.M., Xu S. The global linear convergence of non-interior path-following algorithm for linear complementarity problems. // Mathematics of Operations Research. 1998. V. 23. P. 719-734.

31. Chen В., Chen X., Kanzow C. A penalized Fischer-Burmeister NCP-function: theoretical investigation and numerical results. // Preprint 126. Institute of applied mathematics. University of Hamburg. 1997.

32. Chen X., Qi L., Sun D. Global and superlinear convergence of the smoothing Newton method and its application to general box constrained variational inequalities. // Mathematics of computation. 1998. V. 67. P. 519-540.

33. Chen X., Ye Y. On homotopy-smoothing methods for variational inequalities. // SIAM Journal on control and optimization. 1999. V. 37. P. 589-616.

34. Cottle R.W. Complementarity and variational problems. // In: Symposia mathematica. N.Y. Acad. Press. 1976. V. 19. P. 177-208.

35. Cottle R.W. Nonlinear programs with positively bounded jacobians. // Journal of the society for industrial and applied mathematics. 1966. V. 14. P. 147-158.

36. Cottle R.W., Dantzig G.B. Complementary pivot theory of mathematical programming. // Linear algebra and its applications. 1968. V. 1. № 1. P. 103-125.

37. Cottle R.W., Dantzig G.B. A generalization of the linear complementarity problem. // Journal of combinatorial theory. 1970. V. 8. № 1. P. 79-90.

38. Cottle R.W., Pang J.-S., Stone R.E. The linear complementarity problem. // Boston: Academic press, Inc., 1992.

39. Cryer C.W., Dempster M.A.H. Equivalence of linear complementarity problems and linear programs in vector lattice Hilbert spaces. // SIAM J. Control and Optimiz. 1980. V. 18. № 1. P. 76-90.

40. Dirske S.P., Ferris M.C. MCPLIB: A collection of nonlinear mixed complementarity problems. // Optimization methods and software. 1995. V. 5. P. 319-345.

41. Evers J. More with the Lemke complementarity algorithm. // Mathematical programming. 1978. V. 15. № 2. P. 214-219.

42. Evtushenko Yu.G., Zhadan V.G. Stable barrier-projection and barrier-newton methods in linear programming. // Computational Optimization and Applications. 1994. V. 3, № 4. P. 289-304.

43. Facchinei F., Pang J.-S. Finite-dimentional variational inequalities and complementarity problems. // N.Y.: Springer, 2003

44. Facchinei F., Soares J. A new merit function for nonlinear complementarity problems and a related algorithm. // SIAM Journal on optimization. 1997. V. 7. P. 225-247.

45. Ferris M.C., Kanzow C. Complementarity and related problems: A survey. // Handbook of applied optimization. Oxford University Press. New York. 2002. P. 514-530.

46. Ferris М.С., Pang J.-S. Engineering and economic applications of complementarity probems. // SIAM Review. 1997. V. 39. P. 669-713.

47. Fischer A. A special Newton-type optimization method. / / Optimization. 1992. № 24. P. 269-284.

48. Fisher M.I., Gould F.J. A simplical algorithm for the nonlinear complementarity problem. // Mathematical programming. 1974. V. 6. № 3. P. 281-300.

49. Fisher M.I., Tolle J.W. The nonlinear complemetarity problem: existence and determination of solutions. // SIAM J. Control and Optimiz. 1977. V. 15. № 4. P. 612-624.

50. Freidenfelds J. Almost-complementary path in the generation complementarity problems. // In: Fixed points / Algorithms and applications. N.Y. Acad. Press. 1977. P. 225-247.

51. Garcia C.B. A note on a complementary variant of Lemke's method. // Mathematical programming. 1976. V. 10. № 1. P. 134-136.

52. Gasparo M.G., Pieraccini S., Armellini A. An infeasible interior-point method with nonmonotonic complementarity gaps. // Optimization methods and software. 2002. V. 17. P. 561-586.

53. Habetler G.J., Kostreva M.M. On a direct algorithm for nonlinear complementarity problems. // SIAM J. Control and Optimiz. 1978. V. 16. № 3. P. 504-511.

54. Habetler G.J., Prise A.L. An iterative method for generalized nonlinear complementarity problem. // Journal of optimization theory and applications. 1973. V. 11. № 1. P. 36-48.

55. Harker Р.Т., Pang J.-S. Finite-dimensional variational inequality problems: A survey of theory, algorithm and applications. // Mathematical programming. 1990. V. 48. P. 161-220.

56. Harker P.T., Xiao B. Newton's method for nonlinear complementarity problem: a B-differentiable equation approach. // Mathematical programming. 1990. V. 48. P. 339-357.

57. Hartman P., Stampacchia G. On some nonlinear elliptic differential functional equations. // Acta mathematica. 1966. V. 115. P. 153-188.

58. Hock W., Schittkowski K. Test examples for nonlinear programming codes. // Lecture notes in economics and mathematical systems. Vol. 187. Springer. 1981.

59. Izmailov A.F., Solodov M.V. Superlinearly convergent algorithms for solving singular equations and smooth reformulations of complementarity problems. // SIAM Journal on optimization. 2002. V. 13. № 2. P. 386-405.

60. Ji J., Potra F.A., Sheng R. A predictor-corrector method for solving the P*-matrix LCP from infeasible starting points. // Reports on computational mathematics 55. Department of mathematics, The university of Iowa. USA. June 1994.

61. Khobotov E.N. A modification of the extragradient method for the solution of variational inequalities and some optimization problems. // Journal of computational mathematics and mathematical physics. 1987. V. 27. P. 1462-1473.

62. Kojima М. Computational methods for solving the nonlinear complementarity problem. // Keio engineering reports. Yokohama. Keio university. 1974. V. 27. № 1. P. 1-41.

63. Kojima M., Megiddo M., Noma Т., Yoshise A. A unified approach to interior point algorithms for linear complementarity problems. // Lecture notes in computational science. 1991.

64. Kojima M., Megiddo M., Ye Y. An interior point potential reduction algorithm for the linear complementarity problem. // Mathematical Programming. 1992. V. 54. P. 267-279.

65. Kojima M., Mizuno Sh., Noma T. A new continuation method for complementarity problems with uniform P-functions. // Mathematical programming. 1989. V. 43. P. 107-113.

66. Kojima M., Mizuno Sh., Yoshize A. A polinomial-time algorithm for a class of linear complementarity problems. // Mathematical programming. 1989. V. 44. P. 1-26.

67. Konnov I.V. A combined relaxation method for nonlinear variational inequalities. // Optimization methods and software. 2002. V. 17. № 2. P. 271-292.

68. Lemke C.E. Bimatrix equilibrium points and mathematical programming. // Management Science. 1965. V. 11. № 7. P. 681689

69. Lemke C.E. Recent results on complementarity problems. // In: Nonlinear programming. 1970. P .349-384.

70. Lemke С.Е. Some pivot schemes for the linear complementarity problem. // Mathematical programming study. 1978. V. 7. P. 15-35.

71. Lions J.L., Stampacchia G. Variational inequalities. // Communications on pure and applied mathematics. 1967. V. 20. P. 493-519.

72. Mancino O.G., Stampacchia G. Convex programming and variational inequalities. // Journal of optimization theory and applications. 1972. V. 9. P. 3-23.

73. Mangasarian O.L. Equivalence of the complementarity problem to a system of nonlinear equations. // SI AM Journal of applied mathematics. 1976. V. 31. P. 89-92.

74. Mangasarian O.L., Solodov M.V. Nonlinear complementarity as unconstrained and constrained minimization. / / Mathematical Programming. 1993. V. 62. P. 277-297.

75. Mangasarian O.L., Solodov M.V. A linearly convergent derivative-free descent method for strongly monotone complementarity problems. // Computational optimization and applications. 1999. V. 14. P. 5-16.

76. Mizuno S., Jarre F., Stoer J. A unified approach to infeasible-interior-point algorithms via geometrical linear complementarity problem. // Preprint № 213. Mathematish Institute der Universitat Wiirzburg, Germany. April 1994.

77. Monteiro R.D.C., Pang J.-S. On two interior-point mappings for nonlinear semidefinite complementarity problems. // Mathematics of operations research. 1998. V. 23. P. 39-60.

78. Monteiro R.D.C., Pang J.-S., Wang Т. A positive algorithm for the nonlinear complementarity problem. // SIAM Journal on Optimization. 1995. V. 5. P. 129-148.

79. Murty K.G. Note on a Bard-type scheme for solving the complementarity problem. // Opsearch. 1974. V. 11. № 2-3. P. 123130.

80. Nagurney A. Network economics — a variational inequality approach. // Kluwer academic publishers. Netherlands. 1993.

81. Pang J.S. Complementarity problems. // Handbook in global optimization. Kluwer academic publishers. Boston. 1994.

82. Potra F.A., Sheng R. A modified 0(nL) infeasible-interior-point algorithm for LCP with quadratic convergence. // Reports on computational mathematics 54. Department of mathematics, The university of Iowa. USA. April 1994.

83. Potra F.A., Sheng R. A superlinearly convergent infeasible-interior-point algorithm for degenerate LCP. // Technical report. Department of mathematics, The university of Iowa. USA. 1995.

84. Ravindran A. Computational aspects of Lemke's complementary-algorithm applied to linear programs. // Opsearch. 1970. V. 7. № 4. R 241-262.

85. Sargent R.W.H. An efficient implementation of the Lemke algorithm and its extension to deal with upper and lower bounds. // Mathematical programming study. 1978. V. 7. P. 36-54.

86. Solodov M.V., Svaiter B.F. A new projection method for variational inequality problems. // SIAM Journal on control and optimization. 1999. V. 37. P. 765-776.

87. Solodov M.V., Tseng P. Modified projection-type methods for monotone variational inequalities. // SIAM Journal on control and optimization. 1996. V. 34. P. 1814-1830.

88. Stampacchia G. Variational inequalities. // In: Theory and applications of monotone operators. 1969. P. 101-192.

89. Stoer J. The complexity of an infeasible interior-point path- following method for the solution of linear programs. // Optimization methods and software. 1994. V. 3. P. 1-12.

90. Subramanian P.K. Gauss-Newton methods for the complementarity problem. // Journal of optimization theory and applications. 1993. V. 77. P. 467-482.

91. Sun D., Qi L. On NCP-functions. // Computational optimization and applications. 1999. V. 13. P. 201-220.

92. S.Wang, X.Q.Yang, K.L.Teo. A Unified Gradient Flow Approach to Constrained Nonlinear Optimization Problems // Computational Optimization and Applications. 2003. V. 25, № 1-3. P. 251-268.

93. Todd M.J. Extension of Lemke's algorithm for the linear complementarity problem. // Optimization theory and applications. 1976. V. 20. № 4. P. 397-416.

94. Tomlin J.A. Robust implementation of Lemke's method for the linear complementarity problem. // Mathemetical programming study. 1978. V. 7. P. 55-60.

95. Tseng P. An infeasible path-following method for monotone complementarity problems. // SIAM J. Optimization. 1997. V. 7. P. 386-402.

96. Vtyurina M., Zhadan V. Barrier-Projective Methods for Linear Complementarity problem. // Operations Research 2003. Annual International Conference of the German Operations Research Society. University of Heidelberg. September 3-5. 2003. P. 121.

97. Vtyurina M., Zhadan V. Finite Barrier-Projection Methods for Linear Complementarity Problem. // Optimization 2004. 5th International Conference on Optimization. University of Lisbon. July 25-28. 2004. P. 81.

98. Vtyurina M., Zhadan V. Interior-point Method for the Linear Complementarity Problem. // 4th Moscow International Conference on Operations Research. Moscow. September 21-24. 2004. P. 235-238.

99. Vtyurina М., Zhadan V. Barrier-Projection Method with Steepest Descent for the Linear Complementarity Problem. // Operations Research 2005. International Scientific Annual Conference. University of Bremen. September 7-9. 2005.

100. Wright S.J. An infeasible-interior-point algorithm for linear complementarity problems. // Mathematical Programming. 1994. V. 67. № 1. P. 29-52.

101. Wright S.J. Primal-Dual interior-point methods. // SIAM Phyladelphia. 1997.

102. Wright S.J., Ralph D. A superlinear infeasible-interior-point algorithm for monotone complementarity problems. // Mathematics of operations research. 1996. V. 21. P. 815-838.

103. Ye Y. Interior-point algorithms: theory and analysis. // John Wiley and Sons. New York. 1997.

104. Zhadan V.G. Dual Barrier-Projection and Barrier-Newton Methods in Linear Programming. // System Modelling and Optimization. 1995. P. 502-510.

105. Zhang Y. On the convergence of an infeasible interior-point algorithm for linear programming and other problems. // Technical report. Department of mathematics and statistics. University of Maryland. April 1992.