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

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

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

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

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

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

F (x) > О&bdquo-, (1) x, F (x)) = 0.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 = 4. *G Jk

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

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

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

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

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

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

2. гр (х) — 0 в том и только том случае, когда х является решением НЗД, то решение НЗД сводится к оптимизационной задаче т1пх€й" Од

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

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

Сглаживающие методы имеют интересную связь с методами внутренней точки. Например, в случае сведения НЗД к решению системы нелинейных уравнений с применением сглаживающей функции Фишера-Бурмейстера, решение полученной системы уравнений эквивалентно поиску решения, удовлетворя ю щего уеловиям центрального пути——-хi > 0, Fi{x) > 0, XiFi (x) = /i /i = 1, п.

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

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

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

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

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

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

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

Считается, что решение ЛЗД [z*, 2/*] является невырожденным в том смысле, что точки х* и у* представимы в виде х* = У* = [У?, У*], где а£, у? G Hfc, х?, у? 6 причем х? > 0Ь х? = Оп-к, У? = О*, у? > 0п-к.

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

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

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

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

Глава 2 посвящена разработке варианта метода, относящегося к классу методов внутренней точки и основанного на идее наискорейшего спуска. Метод строится с использованием допустимого варианта барьерно-проективного метода, предложенного в первой главе, поэтому сначала приводятся дискретные схемы непрерывных аналогов. Используя схему Эйлера для интегрирования системы (4), приходим к следующим рекуррентным соотношениям:

Xk+i = D (xk){e-ak[ln + MTG-l (xk, yk)(In-M)D (xk)]yk}, Ук+i = D (yk) {е — ак [ln — G~l{xk, ук) (/" - М) D{yk)] хк), где е — n-мерный вектор, состоящий из единиц, ак — шаг перемещения (ак > 0). Допустимая начальная пара [xq, у о] берется строго внутренней, т. е. удовлетворяет условиям Xq > 0″, уо > 0п. Показывается, что если [я*, г/*] — невырожденное решение ЛЗД, то найдется такое а*, что для

7 т = -D (x)L + Q (x.v)(I"-М)П (х)}и. всех постоянных 0 < < а* все последующие пары являются строго внутренними и итеративный процесс (5) локально линейно сходится к

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

IR" = {х € IR": хг > 0, г? 1, п} — неотрицательный ортант в IRnж, у) = х%Уг ~~ евклидово скалярное произведение;

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

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

1п — единичная матрица порядка п;

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

А~1 — матрица, обратная к А

D{x) — диагональная матрица с вектором х на диагонали- ||аг|| — евклидова норма вектора хЦжЦоо = maxi

Заключение

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

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

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

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

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

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

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