Эффективная реализация ускоренного метода решения вариационных неравенств

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

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Datum:	2014
Hauptverfasser:	Александрова, В.М., Соболенко, Л.А.
Format:	Artikel
Sprache:	Russian
Veröffentlicht:	Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України 2014
Schriftenreihe:	Системні дослідження та інформаційні технології
Schlagworte:	Нові методи в системному аналізі, інформатиці та теорії прийняття рішень
Online Zugang:	http://dspace.nbuv.gov.ua/handle/123456789/85559
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:	Эффективная реализация ускоренного метода решения вариационных неравенств / В.М. Александрова, Л.А. Соболенко // Системні дослідження та інформаційні технології. — 2014. — № 3. — С. 119-129. — Бібліогр.: 15 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-85559
record_format	dspace
spelling	irk-123456789-855592015-08-08T03:01:52Z Эффективная реализация ускоренного метода решения вариационных неравенств Александрова, В.М. Соболенко, Л.А. Нові методи в системному аналізі, інформатиці та теорії прийняття рішень Построен нелокально сходящийся алгоритм решения вариационных неравенств с сильно монотонным оператором и выпуклыми ограничениями-неравенствами, обладающий высокой скоростью сходимости. Метод основан на совмещении глобального алгоритма первого порядка, использующего итерационную последовательность в пространстве прямых переменных, с методом Ньютона решения системы Куна-Таккера вариационных неравенств в окрестности решения. Выполнена эффективная реализация предложенного алгоритма. Рассмотрены вычислительные аспекты, связанные с двумя трудоемкими подзадачами сформулированного алгоритма — задачей квадратичного программирования и решением системы нелинейных равенств. Реализация метода опробована на решении вариационных неравенств с непотенциальным оператором. Проведен сравнительный анализ работы ускоренного алгоритма и алгоритма первого порядка. Высокая скорость сходимости предложенного алгоритма подтверждена результатами вычислительного эксперимента. Побудовано нелокально збіжний алгоритм розв’язання варіаційних нерівностей з сильно монотонним оператором і опуклими обмеженнями-нерівностями, що має високу швидкість збіжності. Метод грунтується на поєднанні глобального алгоритму першого порядку, що використовує ітераційну послідовність у просторі прямих змінних, з методом Ньютона розв’язання системи Куна-Таккера варіаційних нерівностей в околі розв’язку. Виконано ефективну реалізацію запропонованого алгоритму. Розглянуто обчислювальні аспекти, пов’язані з двома трудомісткими підзадачами сформульованого алгоритму — задачею квадратичного програмування і розв’язанням системи нелінійних рівностей. Реалізація методу випробувана на розв’язанні варіаційних нерівностей з непотенційним оператором. Проведено порівняльний аналіз роботи прискореного алгоритму та алгоритму першого порядку. Висока швидкість збіжності запропонованого алгоритму підтверджено результатами обчислювального експерименту. A nonlocally converging algorithm for solving variational inequalities with strongly monotone operator and convex constraints-inequalities has been constructed. The algorithm has a high rate of convergence. The method is based on a combination of the global first-order algorithm that uses an iterative sequence in the space of direct variables with Newton's method of solving the Kuhn-Tucker conditions of variational inequalities in the neighborhood of the solution. The effective implementation of the proposed algorithm has been performed. The computational aspects associated with the two time-consuming subtasks of a presented algorithm — the quadratic programming problem and solving a system of nonlinear equations have been considered. The implementation of the method has been tested by solving the variational inequalities with a nonpotential operator. A comparative analysis of the accelerated algorithm and the first order algorithm has been performed. The high convergence of the proposed algorithm has been confirmed by the results of computational experiments. 2014 Article Эффективная реализация ускоренного метода решения вариационных неравенств / В.М. Александрова, Л.А. Соболенко // Системні дослідження та інформаційні технології. — 2014. — № 3. — С. 119-129. — Бібліогр.: 15 назв. — рос. 1681–6048 http://dspace.nbuv.gov.ua/handle/123456789/85559 519.8 ru Системні дослідження та інформаційні технології Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
topic	Нові методи в системному аналізі, інформатиці та теорії прийняття рішень Нові методи в системному аналізі, інформатиці та теорії прийняття рішень
spellingShingle	Нові методи в системному аналізі, інформатиці та теорії прийняття рішень Нові методи в системному аналізі, інформатиці та теорії прийняття рішень Александрова, В.М. Соболенко, Л.А. Эффективная реализация ускоренного метода решения вариационных неравенств Системні дослідження та інформаційні технології
description	Построен нелокально сходящийся алгоритм решения вариационных неравенств с сильно монотонным оператором и выпуклыми ограничениями-неравенствами, обладающий высокой скоростью сходимости. Метод основан на совмещении глобального алгоритма первого порядка, использующего итерационную последовательность в пространстве прямых переменных, с методом Ньютона решения системы Куна-Таккера вариационных неравенств в окрестности решения. Выполнена эффективная реализация предложенного алгоритма. Рассмотрены вычислительные аспекты, связанные с двумя трудоемкими подзадачами сформулированного алгоритма — задачей квадратичного программирования и решением системы нелинейных равенств. Реализация метода опробована на решении вариационных неравенств с непотенциальным оператором. Проведен сравнительный анализ работы ускоренного алгоритма и алгоритма первого порядка. Высокая скорость сходимости предложенного алгоритма подтверждена результатами вычислительного эксперимента.
format	Article
author	Александрова, В.М. Соболенко, Л.А.
author_facet	Александрова, В.М. Соболенко, Л.А.
author_sort	Александрова, В.М.
title	Эффективная реализация ускоренного метода решения вариационных неравенств
title_short	Эффективная реализация ускоренного метода решения вариационных неравенств
title_full	Эффективная реализация ускоренного метода решения вариационных неравенств
title_fullStr	Эффективная реализация ускоренного метода решения вариационных неравенств
title_full_unstemmed	Эффективная реализация ускоренного метода решения вариационных неравенств
title_sort	эффективная реализация ускоренного метода решения вариационных неравенств
publisher	Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України
publishDate	2014
topic_facet	Нові методи в системному аналізі, інформатиці та теорії прийняття рішень
url	http://dspace.nbuv.gov.ua/handle/123456789/85559
citation_txt	Эффективная реализация ускоренного метода решения вариационных неравенств / В.М. Александрова, Л.А. Соболенко // Системні дослідження та інформаційні технології. — 2014. — № 3. — С. 119-129. — Бібліогр.: 15 назв. — рос.
series	Системні дослідження та інформаційні технології
work_keys_str_mv	AT aleksandrovavm éffektivnaârealizaciâuskorennogometodarešeniâvariacionnyhneravenstv AT sobolenkola éffektivnaârealizaciâuskorennogometodarešeniâvariacionnyhneravenstv
first_indexed	2025-07-06T12:49:51Z
last_indexed	2025-07-06T12:49:51Z
_version_	1836901929478782976
fulltext	 В.М. Александрова, Л.А. Соболенко, 2014 Системні дослідження та інформаційні технології, 2014, № 3 119 УДК 519.8 ЭФФЕКТИВНАЯ РЕАЛИЗАЦИЯ УСКОРЕННОГО МЕТОДА РЕШЕНИЯ ВАРИАЦИОННЫХ НЕРАВЕНСТВ В.М. АЛЕКСАНДРОВА, Л.А. СОБОЛЕНКО Построен нелокально сходящийся алгоритм решения вариационных нера- венств с сильно монотонным оператором и выпуклыми ограничениями- неравенствами, обладающий высокой скоростью сходимости. Метод основан на совмещении глобального алгоритма первого порядка, использующего ите- рационную последовательность в пространстве прямых переменных, с мето- дом Ньютона решения системы Куна-Таккера вариационных неравенств в ок- рестности решения. Выполнена эффективная реализация предложенного алгоритма. Рассмотрены вычислительные аспекты, связанные с двумя трудо- емкими подзадачами сформулированного алгоритма — задачей квадратичного программирования и решением системы нелинейных равенств. Реализация ме- тода опробована на решении вариационных неравенств с непотенциальным оператором. Проведен сравнительный анализ работы ускоренного алгоритма и алгоритма первого порядка. Высокая скорость сходимости предложенного алгоритма подтверждена результатами вычислительного эксперимента. ВВЕДЕНИЕ К вариационным неравенствам (в.н.) конечной размерности сводятся многие задачи математического программирования — задачи оптимизации, линей- ной и нелинейной дополнительности, отыскания седловых точек, которые возникают в экономических, транспортных, физических, технических и со- циальных исследованиях. Наиболее полно численное решение в.н. конечной размерности пред- ставлено в [1–4]. Многие алгоритмы для решения в. н. основаны на решении последовательности линеаризованных в.н. на исходном нелинейном множе- стве. Они включают как методы первого порядка — проекционные методы, так и методы второго порядка — ньютоновского и квазиньютоновского ти- пов. Вспомогательная задача этих алгоритмов состоит в минимизации ли- нейного или квадратичного функционала на исходном множестве, поэтому практическое применение этих алгоритмов возможно в случае, когда мно- жество имеет достаточно простую структуру, например, является многог- ранником. Кроме этого, недостатком этих методов является то, что все они, за исключением проекционных, сходятся к решению лишь с хорошего начального приближения. Современным подходом к решению в.н. является построение экви- валентной оптимизационной задачи [5–7], для решения которой можно применить хорошо развитый аппарат математического программирования. Здесь основная трудность состоит в том, что эквивалентные оптимизацион- ные задачи, как правило, сложны с вычислительной точки зрения. Они либо требуют перехода к целевым функциям большей размерности [5], либо к недифференцируемым функциям [1, 2], либо функциям, требующим вы- числения проекции некоторой точки на исходное множество  [6]. В.М. Александрова, Л.А. Соболенко ISSN 1681–6048 System Research & Information Technologies, 2014, № 3 120 В [7] построен глобальный алгоритм решения в.н. с непотенциальным оператором на основе эквивалентной оптимизационной задачи в исходном пространстве [8], решение которой, в силу ее специфики, можно заменить последовательным решением квадратичных подзадач в исходном простран- стве в сочетании с одномерной минимизацией некоторой штрафной функ- ции. Недостатком этого метода является то, что он обладает лишь линейной скоростью сходимости в окрестности решения. Цель статьи — эффективное построение нелокально сходящегося ал- горитма решения в.н., обладающего квадратичной скоростью сходимости в окрестности решения и использующего итерационный процесс по пере- менной в исходном пространстве. ПОСТАНОВКА ЗАДАЧИ И ПРЕДВАРИТЕЛЬНЫЕ СВЕДЕНИЯ Решение в. н. состоит в нахождении такой точки nx R* , что , 0 ),(  xxxxF (1) где nxF R)( , nx R , а  , — обозначение скалярного произведения векторов nR . Относительно оператора F и множества  будем предполагать, что выполняются следующие условия:  оператор nnxF RR :)( непрерывно дифференцируем и сильно монотонен: 22 ,)( pMppxFpm  , ,0 mM ,, npx R (2) где матрица Якоби )(xF  удовлетворяет условию Липшица, \|\|\|\|  — евкли- дова норма вектора в ;nR  множество nR ограничено и задано в виде: ,},...,1,0)({ \| lixhRx i n  (3) где lixhi ,...,1),(  — выпуклые дважды непрерывно дифференцируемые функции такие, что матрицы вторых производных lixhi ,...,1),(  удовле- творяют условию Липшица;  градиенты )(),( xIixhi  линейно-независимы в решении задачи (1), где }0)(\|,...,1{)( **  xhlixI i — множество активных в точке x ог- раничений, а соответствующие ограничениям множители Лагранжа поло- жительны: )(,0 * xIii  (условия регулярности ограничений). Обозначим: )(xH — ln -матрица со столбцами lixhi ..., ,1 ),(  , lR — вектор множителей Лагранжа, l xh R)( — вектор c компонента- ми .,...,1),( lixhi  Эффективная реализация ускоренного метода решения вариационных неравенств Системні дослідження та інформаційні технології, 2014, № 3 121 Задача (1) при условиях (2), (3) имеет единственное решение x , удов- летворяющее системе равенств: ,,...,1,0)( ,0)()( * *** lixh xHxF i i     (4) а для активных в точке x ограничений следующей системе: ,0)(ˆ ,0ˆ)(ˆ)( ***   xh xHxF  (5) где )(ˆ xH — \|)(\| xIn -матрица; \|)(\| ** )(ˆ,ˆ xIxh R ; \|)(\| xI — количество элементов множества .)(xI Поэтому решить исходную задачу (1)–(3) можно путем совмещения глобально сходящегося алгоритма для определения окрестности, в которой набор активных ограничений не меняется, с быстросходящимся алгоритмом решения системы равенств (5) в этой окрестности, например, методом Нью- тона. Итерация метода Ньютона решения системы (5) имеет вид:                       ˆˆ 0)(ˆ )(ˆ)( )( 1 1)( 1 kk kk kk xIi i kk xx xH xHxhxF k T k k   . )(ˆ ˆ)(ˆ )(           k kkk xh xHxF  (6) В качестве глобально сходящегося метода решения (1)–(3) возьмем метод градиентного типа, сформулированный в [7]. Метод основан на пере- ходе от в.н. (1) к эквивалентной оптимизационной задаче вида: ),(min x x   (7)             l i i i xhxHxFx 1 2 )()()( 2 1 min)(   . (8) В силу специфики задачи (7), (8), ее решение сводится к последователь- ной минимизации функции )()()( 2 1 ),( 1 2 xhxHxFx i l i i    по пере- менным , а затем по переменным .x Минимизация по  функции ),(  x является задачей квадратичного программирования, и ее решение ),,(minarg  kk x  находится стандартными методами при фикси- рованной точке kx . В силу двойственности переменных x и  направление убывания ),(  x в пространстве переменных x определяется как            )()( 1 ki l i k i kk xhxFp  или из решения прямой задачи квадратичного программирования: В.М. Александрова, Л.А. Соболенко ISSN 1681–6048 System Research & Information Technologies, 2014, № 3 122 .,...,1,0),()(\|\|\|\|\| 2 1 ),(min 2         lipxhxhppxF kikik p nR (9) Вектор ,kp в свою очередь, является направлением убывания в точке kx штрафной недифференцируемой функции )(),(),( xNhxx kkN   , где )}(...,),(,0{max)( 1 xhxhxh l , при условии, что . 1    l i i kN  Для ускорения этого метода объединим его с методом Ньютона реше- ния системы (5). Аналогичная проблема ускорения метода линеаризации в окрестности решения была решена для задач нелинейной условной опти- мизации в [9, 10], а схема алгоритма для в.н. предложена в [11]. АЛГОРИТМ РЕШЕНИЯ Сформулируем ускоренный алгоритм решения вариационных неравенств (1)–(3). Выберем произвольными начальное приближение , 0 nx R кон- станту ),1 ;0(  точность решения 0  — маленькое число; ,00  ,0 0 C 0 0 N — достаточно большие числа. Обозначим множества },)()( \| ..., ,1 { )(    x hxhlixI i ,}0),()()( { )(0  pxhxh\|xIixI ii .0 Пусть ,kx k C , k  , k N для ...,1,0 k уже построены. Найдем .1kx Шаг 1 (определение направления в прямом пространстве и двойствен- ных переменных по градиентному методу). Решаем прямую (9) и двой- ственную (8) задачи квадратичного программирования в точке kx для ог- раничений из множества )( kxI k . Пусть задачи (9), (8) имеют решения соответственно )( kxpp k  , )( k ii k x  . Если  \|\|\|\| k p , то kx — решение задачи (1). Конец алгоритма. Если kk Cp \|\|\|\|  , то полагаем kk CC 1   и переходим к шагу 4. Если kk Cp \|\|\|\|  , то переходим к шагу 2. Если задача (9) не имеет решения, то уменьшаем k и повторяем шаг 1. За несколько дроблений k либо находим решение задачи (9), либо убежда- емся, что ограничения вспомогательной задачи несовместны, а задача (1) не имеет решения. Конец алгоритма. Шаг 2 (определение направления в прямом пространстве по методу Ньютона). Вычисляем k d , решая систему уравнений: , )(ˆ ˆ)(ˆ )( 0)(ˆ )(ˆ)( )( '' )( 1 ' 0                                k kkk k T k kk xh xHxF r d xH xHxhxF kk xIi i kk    (10) Эффективная реализация ускоренного метода решения вариационных неравенств Системні дослідження та інформаційні технології, 2014, № 3 123 где )(ˆ ; )(ˆ \|)(0\| k kx k I k xHxh  R — \|)(\| 0 kk xIn  -матрица со столбцами ),( k xhi ),( 0 kk xIi  n d R  , . \|)(0\| kx k I r  R Если система (10) не имеет решения, то полагаем \|\|\|\| 1 kk pC   и пе- реходим к шагу 4. Если решение системы найдено, то переходим к шагу 3. Шаг 3 (анализ приближения, полученного по методу Ньютона). Пола- гаем kk dxx  . (11) В точке x для k  решаем задачу (9). Если ограничения задачи (9) несовместны или в процессе ее решения потребовалось изменить , то полагаем ,\|\|\|\| 1 kk pC   kk  1 и перехо- дим к шагу 4. Если задача (9) имеет решение )(xpp  , вычисляем .\|\|\|\| p Если выполняется неравенство ,\|\|\|\| \|\|\|\| k pp  (12) то в качестве следующего приближения выбираем точку, полученную по методу Ньютона: полагаем , 1 xx k   ,\|\|\|\| 1 pC k   , 1  kk NN kk  1 . Конец итерации. Если неравенство (12) не выполняется, то полагаем ,\|\|\|\| 1 kk pC   kk  1 и переходим к следующему шагу. Шаг 4 (вычисление нового приближения по градиентному методу). Определяем коэффициент штрафа. Пусть    )( )( kxIi i kkxY   . Если )( 1 kk xYN  , то полагаем ,)(2 kk xYN  если ,)( 1 kk xYN  то полагаем 1 - 1 2   kk NN  , ...,1 до тех пор, пока не выполнится условие ,)( 1 kk xYN  тогда 12  kk NN . Коэффициент штрафа стабилизируется в пределах .)(2)( kkk xYNxY  Выбираем шаговый множитель вдоль направления k p из релакса- ции штрафной функции ,)(),(),( xhNxx kkkN k   где  )(xh .)}(...,),(,0{max 1 xhxh l Начиная с ,1  дробим его путем деления попо- лам до выполнения условия: ,),(),( 22 kkkkNkkkN pxpx k   находим k . Полагаем . 1 kkkk pxx   Конец итерации. При сделанных предположениях относительно оператора ),(xF функ- ций ограничений ),(xhi li ..., ,1  , матриц )(xF  и lixhi ..., ,1 ),(  в окрест- В.М. Александрова, Л.А. Соболенко ISSN 1681–6048 System Research & Information Technologies, 2014, № 3 124 ности решения x матрица системы (10) не вырождена, а переход от k x к 1k x осуществляется по формуле (11), что гарантирует квадратичную ско- рость сходимости итерационной последовательности [9, 10]. ВЫЧИСЛИТЕЛЬНЫЕ АСПЕКТЫ Двумя трудоемкими подзадачами сформулированного алгоритма являются задача квадратичного программирования (9) и решение системы (10). Оче- видно, что от эффективности их решения во многом зависит эффективность решения исходной задачи. Поэтому рассмотрим способы решения и вычис- лительные аспекты, возникающие в процессе их решения, более подробно. Метод, которым будем решать задачу (9), относится к семейству мето- дов активного набора. Основная идея методов этого типа состоит в следую- щем. Задача квадратичного программирования с ограничениями- неравенствами заменяется на последовательное решение подзадач с ограни- чениями-равенствами. Для этого вводится рабочий список — список огра- ничений задачи (9), интерпретируемых в процессе поиска решения как ра- венства. В него будет входить только часть ограничений. Эти ограничения определяют некоторую грань многогранного множества, описываемого ли- нейными неравенствами задачи (9). Находим минимум на этой грани. Полу- ченная точка либо является решением задачи (9), если множество ограниче- ний из рабочего списка совпадет с множеством активных ограничений в решении, либо возможен переход на некоторую новую грань, после чего процедура поиска повторяется. Среди методов активного набора выделяют два направления — методы прямого и двойственного активного набора [12]. В методах первого типа итерационная последовательность начинается и все время удерживается в допустимой области, при этом от итерации к итерации значение целевой функции уменьшается, пока не достигнет минимума. Итерационная последовательность методов двойственного активного набора начинается с недопустимой точки безусловного минимума квадра- тичной функции и, увеличивая значение целевой функции, последовательно удовлетворяет всем ограничениям задачи. Второй способ предпочтительней, поскольку нахождение безусловного минимума в случае выпуклой квадра- тичной функции более просто, чем нахождение какой-нибудь допустимой точки множества. В численных экспериментах, которые проводились авторами, вспомо- гательная задача (9) решалась двойственным методом активного набора [13]. В этом алгоритме предусмотрено одновременное вычисление решения по прямым и двойственным переменным, что требует решения систем ли- нейных уравнений. Для решения систем уравнений во вспомогательных за- дачах использовались матричные преобразования — разложение Холецкого и QR -факторизация, с помощью которых матрицы приводились к треуголь- ному виду. Решение систем уравнений таким способом, в отличие от проце- дур исключения Гаусса, является численно устойчивым [12]. Эффективная реализация ускоренного метода решения вариационных неравенств Системні дослідження та інформаційні технології, 2014, № 3 125 Напомним, что разложение Холецкого позволяет симметричную поло- жительно определенную nn -матрицу G представить в виде: ,TLLG  где L — нижняя треугольная матрица размерности nn . Кроме того, если диа- гональные элементы L выбираются положительными, то разложение един- ственно. Элементы L можно определять по строкам и по столбцам. Если матрицу L определять по строкам, то элементы i -й строки вычисляются из следующих соотношений: ....,,1,,1...,,1, 2/11 1 2 1 1 nilglij l llg l i k ikiiii jj j k jkikij ij                  Ортогонaлизация ( QR -факторизация) — это преобразование произ- вольной qn -матрицы B ранга q к верхнетреугольному виду, т.е.        0 qR QB , где qR — верхняя треугольная матрица размерности ,qq 11 PPPQ qq    — ортонормальная nn -матрица, определяемая эле- ментарными матрицами Хаусхолдера qPP ,,1  . Матрица Хаусхолдера — матрица вида: , \|\|\|\| 2 2v vv EP T n  где ,nv R nE — единичная nn -матрица. Из определения матрицы P следует, что она воздействует на векторы с сохранением евклидовой нормы, т.е. \|\|\|\| Pb \|\|\|\| b . Для двух не совпадающих векторов nbb R, таких, что \|\|\|\|\|\|\|\| bb  , всегда можно подобрать преобразование Хаусхолдера ,P которое преобра- зует один вектор в другой, т.е. . \|\|\|\| ,2 \|\|\|\| 2 22 bv v bv bb v vv EPb T n          Из по- следнего соотношения следует, что, если ,0, bv то ,bPb  кроме того, если для некоторых i таких, что ,0iv то .ii bb  Для преобразования матрицы B к верхней треугольной матрица 1P подбирается так, чтобы 1-й столбец матрицы B преобразовать в вектор ,0,...,0, 1 2 1 T n i ib           т.е. обнулить все компоненты, кроме первой. Соответст- венно, iP подбирается так, чтобы в i -м столбце преобразованной матрицы B обнулить компоненты с индексами ni ,...,1 не меняя компоненты с ин- дексами 1,...,1 i . Среди ортогональных преобразований выделяют плоские повороты Ги- венса. Поворот Гивенса используется для обнуления какой-нибудь одной компоненты вектора b и задается матрицей Хаусхолдера с вектором ,v у которого только две ненулевые компоненты .)00( T ji v  Матрица Гивенса, соответствующая плоскому повороту, имеет вид: В.М. Александрова, Л.А. Соболенко ISSN 1681–6048 System Research & Information Technologies, 2014, № 3 126                   1000 000 010 000 0001 ),(    cs sc j i Q ji ji , где ,122  sc ,cosc ,sins для некоторого угла . Умножение вектора b слева на рассматриваемую матрицу ),( jiQ изменит только i -ю и j -ю компоненты вектора. Угол  подбирают так, чтобы обнулить j -ю ком- поненту вектора ,b например, чтобы преобразовать вектор ...,...,,0( ibb  T jb )0...,,..., в вектор T iji rbQ )0...,,0...,,...,,0(),(  , где .)( 2/122 jii bbr  Суть процедуры рассмотрим на примере матрицы Гивенса, размерно- сти 22  . Чтобы определить параметры ортогонального преобразования 2/12 2 2 11 1 2 1 )(, 0 , bbr r b b q cs sc q                     , необходимо вычислить \|}\|\|,{\|max 21 bb , 2/12 2 2 1 11 )(sign                        bb br , 1 1 r b с  , 1 2 r b s  . Плоские повороты Гивенса в алгоритме решения вспомогательной за- дачи квадратичного программирования (9) используются для пересчета QR -факторов матриц систем уравнений при добавлении ограничения в ра- бочий список или при удалении ограничения из него. Рассмотрим пересчет QR -факторов на примере матрицы .B Рассмот- рим добавление 1q -го столбца в факторизованную матрицу ,B т.е. пусть . 0 2 1        b bR QB q Чтобы получить треугольную матрицу ,1qR необходимо преобразовать вектор qnRb 2 в вектор       0  , где , 2/1 1 2 2             qn i i b т.е. необ- ходимо обнулить в векторе qnRb 2 все компоненты, кроме первой. Это можно сделать либо одним ортонормальным преобразованием Хаусхолдера, либо последовательным применением матриц плоского поворота Гивенса, обнуляя компоненты вектора ,nRb начиная с n -й компоненты. Обозна- чим Q ~ — произведение матриц Гивенса, соответствующее этим преобразо- ваниям. В результате имеем: , 0 00 0 0 ~ 0 0~ ;~ 0 0~ 1 1 2 1 22                                     q q qqq R dR d dR Q E QBQ Q E Q  Эффективная реализация ускоренного метода решения вариационных неравенств Системні дослідження та інформаційні технології, 2014, № 3 127 где ))1,(())2),(1(())1),(2((2 ~  nnnnqq QQQQ  , 1qR — треугольная  )1(q )1(  q -матрица, qE — единичная qq -матрица. Если l -й столбец вычеркивается из преобразованной матрицы ,B то , 0       K QB где K — матрица размерности )1(  qq вида         T SR K l 0 1 , 1lR — треугольная матрица размерности )1()1(  ll , T — верхний Хес- сенберг размерности .)()1( lqlq  Поддиагональные элементы матри- цы T можно обнулить последовательностью )( lq  матриц плоского пово- рота. Обозначим Q — произведение матриц Гивенса, соответствующее этим преобразованиям. Тогда , 00 00 00 3 1              qn l E Q E Q , 0 00 0 1 1                     q l R T SR QQBQ где ))1(),(())2(),1(())1(),((3  qnqnqnqnlqnlqn QQQQ  , 1qR — треуголь- ная, 1lE , qnE  — единичные матрицы соответствующих размерностей. ЧИСЛЕННЫЙ ЭКСПЕРИМЕНТ Прикладные модули предложенного в данной статье ускоренного алгорит- ма, реализованы в виде классов на языке C# для платформы NET 3.5, кото- рые включают: класс для решения вспомогательной квадратичной задачи (9), класс для решения системы (10) методом Ньютона, класс для решения в.н. методом [7], вспомогательные классы для задания входных параметров и функций задачи, класс для вывода результатов решения, класс для графи- ческого представления данных в процессе решения и, собственно, класс для ускоренного алгоритма. Как и ожидалось, предложенный алгоритм дает значительное ускорение, по сравнению с алгоритмом первого порядка [7]. Работа алгоритма тестировалась на примерах из работ [14, 15]. На рисунке представлены графики зависимости величины \|\|\|\| p от но- мера итерации для метода [7] и предложенного ускоренного алгоритма на примере решения задачи из [15]:                    3323 13223 2232 63223 )( 43 2 2 2 1 43 2 221 2 1 43 2 21 2 1 43 2 221 2 1 xxxx xxxxxx xxxxx xxxxxx xF , }4,....,1,0{  ixi , начальное приближение — точка ,)1,1,1,1(0 Tx  решение — точка .)5,0;0;0;65,0(* Tx  В.М. Александрова, Л.А. Соболенко ISSN 1681–6048 System Research & Information Technologies, 2014, № 3 128 Стремление к нулю нормы вектора p является признаком сходимости итерационной последовательности алгоритма к решению задачи (1) по пе- ременной x . Как показал анализ работы алгоритмов, ускоренный алгоритм получает решение задачи за 8 итераций (7 итераций по методу первого по- рядка [7] и одна итерация по методу Ньютона), в то время, как методу пер- вого порядка для достижения решения с заданной точностью понадобилось 34 итерации. В представленной алгоритмической схеме решение двух вспомогатель- ных задач предусмотрено с 1-й итерации, но решение системы равенств на шаге 2 и последующую проверку полученного решения на шаге 3 можно исключить на начальных итерациях путем введения дополнительного управляющего параметра [10]. ВЫВОДЫ Рассмотрены конечномерные выпуклые в.н. с непотенциальным операто- ром. Предложена алгоритмическая схема построения последовательности приближений kx , которая сходится к решению в.н. с любого начального приближения с квадратичной скоростью. Результирующая итерационная последовательность строится на основании последовательностей точек, по- лучаемых двумя методами — глобальным методом первого порядка, пред- ложенного в [7], и локальным методом решения системы необходимых ус- ловий в.н. в окрестности решения. Выбор очередного приближения контролируется применением управляющей последовательности kC , кото- рая не позволяет выбирать приближение, полученное по методу Ньютона, если это приводит к увеличению \|\|\|\| kp . Все рассматриваемые в работе алгоритмы реализованы в виде классов C# для платформы NET 3.5. Реализации вспомогательных задач — задачи квадратичного программирования и решения системы уравнений методом Ньютона, включают численно устойчивые процедуры матричных разложе- Рисунок. Сравнение сходимостей рассматриваемых методов: а — сходимость ме- тода первого порядка, б — сходимость ускоренного метода Приближение Норма Р: Номер итерации Количество итераций Номер итерации Приближение Норма Р: Количество итераций а б Эффективная реализация ускоренного метода решения вариационных неравенств Системні дослідження та інформаційні технології, 2014, № 3 129 ний. В работе кратко изложена суть используемых матричных разложе- ний — представление симметричной положительно определенной матрицы в виде произведения двух треугольных матриц (разложение Холецкого), ор- тонормальное преобразование произвольной матрицы и приведение ее к верхнетреугольному виду QR( -факторизация), а также пересчет факторов разложений матриц с помощью плоских поворотов Гивенса. Представлены результаты тестирования реализованных алгоритмов на решении в.н. с несимметричной матрицей Якоби. Численные эксперименты и сравненительный анализ алгоритмов, наглядно подтверждают высокую скорость сходимости предложенного алгоритма. ЛИТЕРАТУРА 1. Facchinei F., Pang J.-S. Finite-Dimensional Variational Inequalities and Comple- mentarity, Volume I. — Springer, 2003. — 728 p. 2. Facchinei F., Pang J.-S. Finite-Dimensional Variational Inequalities and Comple- mentarity, Volume II. — Springer, 2003. — 702 p. 3. Xiao B., Harker P.T. A nonsmooth Newton method for variational inequalities, I:Theory // Math.Progr. — 1994. — 65, № 2. — P. 151–194. 4. Бакушинский Я. М., Поляк Б. Т. О решении вариационных неравенств // Докл. АН СССР. — 1974. — 219, № 5, — С. 1038–1041. 5. Панин В.М., Александрова В.М. Нелокальный квазиньютоновский метод решения выпуклых вариационных неравенств // Кибернетика и систем. анализ. — 1994. — № 6. — С. 78–91. 6. Fukushima, M. Equivalent differentiable optimization problems and descent methods for asymmetric variational inequality problems // Math. Progr. — 1992. — 53, № 2. — P. 99–110. 7. Александрова В.М., Шубенкова И.А. Об усовершенствовании метода решения вариационных неравенств // Кибернетика и системный анализ. — 2013. — № 2. — С. 150–156. 8. Данилин Ю.М., Шубенкова И.А. Оптимизация и решение выпуклых вариаци- онных неравенств // Системні дослідження та інформаційні технології. — 2003. — № 3. — С. 66–74. 9. Пшеничный Б.Н. Метод линеаризации. — М.: Наука, 1983. — 136 с. 10. Соболенко Л.А. Ускоренные модификации метода линеаризации. — Деп. ВИНИТИ 7525. — В.89. — 1989. — 35 с. 11. Александрова В.М. Ускоренный метод решения вариационных неравенств // Теория оптимальных решений. — Киев: Ин-т кибернетики им. В.М. Глушкова НАН Украины, 1995. — С. 8–13. 12. Гилл Ф., Мюррей К., Райт М. Практическая оптимизация. — М.: Мир, 1985. — 509 с. 13. Goldfarb D, Idnani A. A numerically stable dual method for solving strictly convex quadratic problem // Math. Progr. — 1983. — 27, № 1. — P. 1–33. 14. Fukushima M. A relaxed projection method for variational inequalitities // Math. Progr. — 1986. — 35, № 1. — P. 58–70. 15. Taji K., Fukushima M., Ibaraki T. A globally convergent Newton method for solving strongly monotone variational inequalities // Math. Progr. — 1993. — 58, № 3. — P. 369–383. Поступила 21.03.2013

Эффективная реализация ускоренного метода решения вариационных неравенств

Institution

Ähnliche Einträge