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

Академия наук- Украины " 6 ОИнститут кибернетики имени В. М. Глушкова

1; м -

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

К АЛ ЖАНОВ Марат Умирбекович

РАЗРАБОТКА ЧИСЛЕННЫХ ЛИЛЛЯ ВАРИАЦИОННЫХ Ь И ЗАДАЧИ НЕЛИНЕЙНОЙ ДОГ.

01.01.09 — математическая кибернетик».

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

ОВ РЕШЕНИЯ ЛЕНСТВ ЯИТЕЛЬНОСТИ

Киев 1994

Д;:сссртацкл лзляется рукопись- - - ■ -

Работа выполнена в Институте кибернетики имени В. М. Глушкова АН Украины.

Научный руководитель: академик АН Украины

ПШЕНИЧНЫЙ Б. Н.

Официальные оппоненты: доктор физико-математических

наук, профессор ГУПАЛ А. М.,

кандидат физико-математических наук НЕНАХОВ Э. И.

Ведущая организация: Киевский государственный универси-,

тет.

/V С '

Защита состоится ¿2-- 199 ^ г. в —

часов на заседании специализированного совета Д016.45.01 при Институте кибернетики имени В. М. Глушкова АН Украины по адресу:

252207 Киев 207, проспект Академика Глушкова, 40.

С диссертацией можно ознакомиться в научно-техническом архиве института.

Автореферат разослан ^^^^—1У^/г.

Ученый секретарь специализированного совета

СИНЯВСКИЙ В. Ф.

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

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

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

Основные цела работы

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

- г -

образом:

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

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

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

осуществить проверку, эффективности предложенных методов решения на тестовых примерах.

Метода исследования , , ■

Всо численные метода, предложенные автором, строго обоснованы.

' В доказательствах использованы результаты классической ; теории экстремума, математического программирования, аппарата вычисли-, тельной математики и теории матриц. Часть методов проверена в ходе вычислительных экспериментов и решения тестовых примеров.

Научная новизна

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

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

Полученные результата распространены на задачу дополнительности.

Практическая ценность

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

номикн, тэхники, военного дела и др.

Апробация работы

Основные результаты работы неоднократно докладывались и обсуждались па сеетлнарах, провода,мх научным советом АН Украины по проблеме " Кибернетика", на семинаре отдела "Вычислительные метода оптимизации " Института кибернетика имени В.М.* Глуккова АН Утаит, на научном сет-шаре Кустанайского государственного университета (Кустанай, сентябрь 1993 г.) и на международном конгрессе ПЬ компьютерным системам и прикладной ма-' тематика (Санкт-Петербург, июль 1993 г.), других научных семинарах и конференциях.

Публикации

По теме диссертации опубликованы 3 работы. Структура и объем работы

Работа состоит из введения, трех глав, заключения,- приложения и списка цитируемой литературы, состоящей из 90 наименований. Объем работы составляет 91 страницу-

Содержание работы

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

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

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

Другим традиционным подходом к решению моделей равновесия является нелинейная оптимизация . Кахдый из упомянутых

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

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

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

Определение I.I. Пусть X - непустое подмножество Rn, ? - отображение из Rn в себя. Задачей вариационного неравенства, обо-обозначаемой VI(X,F), является нахоздедае вектора х*€ X , такого, чтобы

т

1Чх*) (У - х®-> 5» О для всех у еХ, (I.I)

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

Задача нелинейной дополнительности NCP - особый случай задачи •VI(X.F) .

Определение 1.2. Пусть Р - отображение Rn в себя. Задачей нелинейной дополнительности, обозначаемой НСР(Р), является нахождение вектора х*Ч R^, такого, что

F(x*) € R" и F(x*)V= О . (1.2)

В определении 1.2 и во всем последующем изложении R" означает

неотрицательный ортант Rn. При F(x), являющейся аффиной функцией х, например F(x) = q + Мх для некоторого данного вектора q с й" и матрицы М е Я"331 задача NCP(F) сводится к задаче линейной дополнительности, обозначаемой LCP(q,M>.

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

Следующая глава диссертации посвящена построению численных алгоритмов решения вариационных неравенств и задачи о дополнительности. В §2.1 предложен итеративный алгоритм решения, доказана и обоснована сходимость предложенного алгоритма при условии, что отображение F является сильно монотонным, гарантирующим существование и единственность решения. Этот алгоритм ' представляет некоторую модификацию метода линеаризации Б.Н.Пше-

ничн01чз.

В дальнейшем будем рассматривать пространство n-мерных векторов Лп, так что, если х с Rn, то х - вектор-столбец с компонентами х1, 1=1,...,п. Пусть F:Rn—»R11 отображение Rn в Rn, а И - выпуклое множество. Под решением вариационного неравенства понимается нахождение такой точки х € М . что

о

(F(xo), х - хо) > О V х € и , (2.1)

где (х,у) - скалярное произведете векторов х и у. Обычную евклидову норму вектора х обозначим |х|.

Пусть теперь для у € К

К„(у)= (р € R11 : р = Мх'- у).

\ > О, х € II)

- конус возможных направлений к II в точке у. Так как сопряае1шнй ему. конус имзат вид

то, очевидно, соотношение (2.1) мокат быть переписано в эквивалентной форме:

Обратим теперь внимание на то, что различные задачи могут быть приведены к форме (2.2):

п ' *

а) пусть М = Fr. Тогда легко видеть,.'что Ку (zq) = О и (2.2) приобретает вид P(XQ> = 0, т.е'. сводится к решению система нелинейных уравнений;

б) если Г(х) - гладкая выпуклая функция и Р(х) = .1 (х), где

i (х) - градиент функции 1 , то (2.2) превращается в соотношение . *

1 (х) £ Кй(хо), что означает, что %Q - точка минимума I на мнокестве Н;

в) если К = f£J - неотрицательный ортант пространства R0,

то нетрудно подсчитать, что К^СУ) = (q i 0:<y,q) =0}.' Поатому (2.2 ) могао переписать в зиде хо £ 0, F(xq) > 0, (х0,?(х0)) » О, т.е. хо - решение з^ачм дополнительности;

г) пусть ч>(х,у) - гладкая выпукло-вогнутая функция х е

у € Вт, а а и В - выпуклые множества в Rn и Rra. Точка ( *0.У6) является седловой, если

Км (у) = iq: (p,q) > 0, р € %(у)),

(2.2)

ф(Х.У0) > ф(20.У0> > 4>i3t0,У), X € к, у е В,

. • * .

что эквивалентно соотношениям <Р^и0»У0) € Кд(хо); - фу(хо,уй) £

И = к X В с Rn+m • Теперь ясно, что условие седловой точки

?<Vyo> € КМ(ЗСо'Уо>'

и ее поиск сводится и некоторой системе вариационных неравенств.

Перейдем к более конкретной постановке задачи. Предположим, что ? - сально монотонное дифференцируемое отображение, т.е.

(?(х) - ?(у), х- у) > jijx - у|г , ц > О, (2.3) а матрица производных

ГвМх>)

? (X)» I _С

¡вХу ) 1=1,...,п ,

3=1,...,п

удовлетворяет условии Липшица в любой компактной области. С учетом дифференцируемости F нетрудно показать, что неравенству (2.3) можно придать локальный вид

(Р'(х)р,р) > Шр|г . (2.4)

В данном виде это соотношение в основном и будет использовано. Пусть теперь множество Ы задано системой неравенств

М =» { х € Rn : f^(x) < 0, ш),

причем Н - ограничено, и существует такая точка z, что it(2) <-7, 7 > О для всех Ul,...,m - выпуклы, дважды дифференцируемы и их'производные удовлетворяют услоеи» Липшица. Градиента функций IL будем обозначать Г (х), а матрицу, вторых производных

Основой предлагаемого в § 2.1 алгоритма служит следующая вспомогательная задача:

Так как в силу выпуклости - у » Гь(2) ? flW + (Г£(х),и-х), '1=1,...,т, то ограничения задачи (2.5) всегда совместны, и она все гда имеет единственное решение р(х).

В дальнейшем'нам понадобятся две леммы. Лемма 2.1,'Точка х0 является решением. вариационного неравенства тогда и только тогда, когда р(хо)= 0 . Лемма 2.2. Справедлива оценка

где - множители Куна - Таккера, соответствующие ограничениям вспомогательной задачи (2.5).

Положим теперь m(x).= maxíf^x),!, (x),...,ím(x)>, r0(x)sQ. Сформулируем алгоритм. Пусть х0 - начальная точка, с»т(х0), а- Н > о . выбрано достаточно большим (смысл последних слов будет разъяснен несколько шрсо). Положим Ф^(х) = ср(х) - íím(x).

Пусть точка х^ m(xk) < с, уже построена. Решаем задачу квадратичного программирования (2.5) при х=хк. Ее решение р^) обозначим рк , а вектор множителей Куна - Таккера - \к. Выберем шаговый множитель о^ по следующему правилу: начиная с oo=t, делим его пополам до первого удовлетворения неравенств

ш(хк + арк) < с, где К > О - некоторое число. Полученное а обозначим с^ и положим хк+1 = хк + акрк. Итерация закончена. Теорема 2.1 Состроенная последовательность сходится к решению поставленной задачи о Вариационных неравенствах, если число Н удовлетворяет неравенству

v(xk+apk,A.k) - Hm(xk + apk) > <fy(x) + cfrqpj2, (2.6)

h > j \í(x),

v x e (x:m(xKc).

(2.7)

Предложенный алгоритм решает вариационные неравенства в общем виде , т.е когда целевая функция и ограничения носят нелинейный характер. Именно в этом случае следует ожидать наибольшего эффекта от применения данного метода. Однако ого использование в линейном случав также не лишено смысла. В §2.2 получены результаты, соответствующие линейным вариационным неравенствам. Заметим, что линейные вариационные неравенства' обладают своими специфическими особенностями, которые позволяют существенно упростить условия применения алгоритма и, следовательно, усилить"конечные результаты. В частпости, доказана сходимость за конечное число шагов.

Напомним, что если FiR"—>Rn и М - выпуклое множество в Нп, то решение вариационного неравенства сводится к нахождению* такой точки е М, что

(Fix,,),у - х„> > О, V 'у € М . (2.8)

В §2.2 рассматривается случай, когда F(x) = Fqx + с,

М=Сх:Ах-Ь«0), (2.9)

где ?0 - п х п матрица; А - ш х п - матрица; b е R?

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

Предположение 2.1. Матрица Fo сильно монотонна, т.е.'

(Fo р, р) » ц|р|г,

где (* ,') - скалярное произведение; | | - евклидова норма.

Согласно известным результатам, теории необходимых условий экстремума, в рассматриваемом случае соотношнение (2.8 ) эквивалентно выполнению условий : существует такой вектор е Rm, что

- to -

F(XJ + A*\° »0, * 0, (, AX. - b> » 0, (2.10)

Ax, - b < 0.

Введем теперь ал едущие обозначения. Пусть aj с Rn, вектор-строка определяет 1-е неравенство в (2.9), т.е.

I *

(а^, х ) - bt < ¡3

Если J - некоторое подмно!юство индексов из И,т), то Aj - матрица IJ I х п , где IJ I- число индексов в J , а матрица А^ составлена из строк , i с J .

Известно, что если выполнено предположение 2.1 , то решение вариационного неравенства х. единственно. Пусть

J„ = £ i: (at, хш) - bt = О ) .

Предположение 2.2. В соотношениях (2.10) > 0 , i е J^ и всё векторы Зтнейно независимы.

Все последующее изложение без дополнительных оговорок предполагает выполнение предположений 2.1 и 2.2 .

Шройдом теперь к построении'численного метода решения задачи (2.8). Согласно изложенному в предыдущем параграфе, вспомогательная задача может' быть сформулирована в следующем виде;

rn^n { (p,F(x)) + flpj2: Ар + Ах - b < 0 ). (2.II)

Она имеет единственное решение р(х), и пусть J(x) - множество индексов С тех неравенств в задаче (2.II), которые выполняются как равенство i € J(x), если

(а^, р(х) + х) - Ь^ = о,

т.е. Aj(x)(I + Р(х)) " bJ(x> * 0# (2Л2)

рассмотрим окрестность решения х„ и запишем для нее систему

щнойннх уравнений: .

р + F(X) + A^Xj, = 0. \г*Р + - bj, = 0. (2.13)

где - вектор размерности |J»| .

(Гемма 2.3. При - сделанных предположениях существует такая' экрастность решения система вариационных неравенств, в которой вектор р, полученный из решения системы (2.13), есть решение вспомогательной задачи f2.II).

(¡формулируем теперь предпагаемый алгоритм. Так., как системы ограничений в задаче (2.9) линейна, то без , ограничения общности !'от:о считать» что начальная точка хо Удовлетворяет .этой систбме. Д: sea, если точка х с Ы , а в силу (2.II) х + р(х) € М. то

(1 - о)х + а(х + р(х)) >= х +'ар(я) € М

при а € (0,11. Поэтов все построенные шгэ точки последовательности ( х^} будут принадлежать допустимой области М . Это позволяет модифицировать предложенный в 52.1 алгоритм. Он приобретает следующий вид: положим

v(x,M = - £ 1?(х> + A *\|V>, Ах - b). ' (2.14)

Пусть точка х € Ц уже построена, р(х) - соответствуадее ей решение вспомогательной задачи, а А. € Rm- соответствующие множители. Лагранжа. вычислим индексное множество .

J(x) = { i € H.mJ : (at,x + р(х)) - bt = о >. (2.15)

Решаем систему линейных уравнений относительно х и \J(3t):

.tlx) * = 0, (2.16)

если

Лгсх,* - Ь,(ж> = О, (2.17,

- 12 -

.АГ-Ъ^О, >.J( » О, _ (2.18

то х = х - решение вариационных неравенств.

Если одно из условий (2.18) не выполнено, то перехода в следующую точку х + ар(х), где шаг а определяется по слодувдоыу правилу начиная с единицы, дробям его' пополач до шршго удовлетворения' неравенства

v(x + ар(х),А.) > ф(х) + агЩр(х)|г, К > О. (2.19;

*

Если применить предложенный алгоритм, тчтт о точки хо, то т получим некоторую последовательность точек хк,-К = 0,1,... . Теорема 2.2. Драдкоканный алгоритм сходятся за конотаоо число шагов, ¥7е. найдется такое к, что x¿ - pecare» спзт-а вариационных неравенств (2.8).

В {2.3 результаты предыдущих разделов распространены на задачу дополнительности.

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

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

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

Напомним, для заданной функции F: Rn—>ft" связанная с пай задача дополнительности заключается в нааоздеиш такой точки. i ( И", для которой

X > О, ?(х) » О , Х^Р(х) » О . (2.20)

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

min(F(x), p+4- ||p!P:x+p^O}, (2.21)

P 1

ii показана ограниченность последовательности хь, что обо-сиоиьшает сходимость алгоритма.

Сформулируем в явном виде получившийся алгоритм в задаче дополнительности.

Пусть Хо^О — начальная точка. Если точка хь^О уже построена, то х!к+1 = х%—c^min (х*к, FJ(xk)), а ак выбирается

дроблением единицы до первого выполнения неравенства

ф(хк+акрк) ^ф(хк)+ак2К11рк112.

Таким образом, результаты предыдущих разделов распространены на задачу дополнительности. Аналогично §2.1, §2.2 обоснована! и доказана сходимость предложенного алгоритма.

В последней главе приведены результаты числовых примеров задачи вариационных неравенств и нелинейной дополнительности, на которых бил апробирован предложенный во 2-й главе алгоритм. Важность предложенного алгоритма эффективно продемонстрирована для вычисления экономического равновесия спроса и предложения и представлена числовым примером олигополии нескольких фирм в §3.1. Вопросы численной реализации алгоритма приведены на конкретных тестовых примерах в §3.2. Все ра.чочи выполнены на персональной ЭВМ, совместимой с IBM PC-XT. Алгоритм реализован на языке ФОРТРАН-77. Приведенные в §3.1, §3.2 примеры иллюстрируют тот факт, что предложенный в данной диссертационной работе алгоритм является достаточно эффективным средством решения практических задач, формулируемых в терминах ва-j-.'■ а ионных неравенств и задач!! дополнительности. Более того, алгоритм обладает глобальной сходимостью в том смысле, что сходится из любого начд чь::о! о приближения.

Основные результаты работы

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

2. Полученные результаты распространены на линейный случай задач!! вариационных неравенств; доказана конечность предложенного алгоритма при условии сильной регулярности решения и сильной монотонности оператора.

3. Полученные результаты распространены на задачу дополнительности.

4. Основные положения работы проиллюстрированы на тестовых примерах задачи вариационных неравенств и задачи нелинейной дополнительности с результатами численных- расчетов.

Основные результаты диссертации опубликозаны в следующих работах:

1. Пшеничный Б. Н„ Калжанов М. У. Метод линеаризации для решения вариационных неравенств // Кибернетика и системный анализ. — 1992. — № 6. — С. 48—55.

2. Сосновский А. А., Калжанов М. У. Конечномерные вариационные неравенства и задачи нелинейной дополнительности: теория, алгоритмы и приложения. — Киев, 1993. — 24 с. — (Препр. / Ин-т кибернетики имени В. М. Глушкова АН Украины; 93-21).

3. Калжанов М. У. Численная реализация подхода, основанная на использовании вариационных неравенств для определения равновесия олигополии // Разработка и использование информационных технологий в системах управления. — Киев : Ин-т кибернетики имени В. М. Глушкова АН Украины, 1993. — С. 47—50.

Подл, в печ. 15.02.94. Формат 60x84/16. Бум. тип. №2. Офс. печ. Усл. печ. л. 0,70. Усл. кр.-отт. 0,82. Уч.-изд. л. 1,0. Тираж 100 экз. Заказ 262.

Редакционно-издательский отдел с полиграфическим участком Института кибернетики имени В. М. Глушкова АН Украины "252207, Киев 207, проспект Академика Глушкова, 40.