Проекционные методы решения нелинейных вариационных неравенств

Розглядаються скінченновимірні варіаційні нерівності з сильно монотонним оператором та числові методи їх розв’язання. Вивчаються проекційні методи першого порядку з лінеаризацією обмежень, які базуються на апараті квадратичного програмування. Доведена нелокальна збіжність до розв’язку і лінійна швид...

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	2002
Автори:	Панин, В.М., Лаврина, Т.В.
Формат:	Стаття
Мова:	Russian
Опубліковано:	Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України 2002
Назва видання:	Системні дослідження та інформаційні технології
Теми:	Методи оптимізації, оптимальне управління і теорія ігор
Онлайн доступ:	http://dspace.nbuv.gov.ua/handle/123456789/50227
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:	Проекционные методы решения нелинейных вариационных неравенств / В.М. Панин, Т.В. Лаврина // Систем. дослідж. та інформ. технології. — 2002. — № 2. — С. 103-117. — Бібліогр.: 10 назв. — рос.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-50227
record_format	dspace
spelling	irk-123456789-502272013-10-09T03:05:29Z Проекционные методы решения нелинейных вариационных неравенств Панин, В.М. Лаврина, Т.В. Методи оптимізації, оптимальне управління і теорія ігор Розглядаються скінченновимірні варіаційні нерівності з сильно монотонним оператором та числові методи їх розв’язання. Вивчаються проекційні методи першого порядку з лінеаризацією обмежень, які базуються на апараті квадратичного програмування. Доведена нелокальна збіжність до розв’язку і лінійна швидкість збіжності в його околі. Рассматриваются конечномерные вариационные неравенства с сильно монотонным оператором и численные методы их решения. Изучаются проекционные методы первого порядка с линеаризацией ограничений, основанные на аппарате квадратичного программирования. Установлена нелокальная сходимость к решению и линейная скорость сходимости в его окрестности. Finite-dimesional variational inequalities with a strongly monotone operator and numerical methods for their solution are considered. First order projectional methods with linearisation of constraints based on quadratical programming are studied. Nonlocal convergence to solution and geometrical convergence in its neighborhood are proved. 2002 Article Проекционные методы решения нелинейных вариационных неравенств / В.М. Панин, Т.В. Лаврина // Систем. дослідж. та інформ. технології. — 2002. — № 2. — С. 103-117. — Бібліогр.: 10 назв. — рос. 1681–6048 http://dspace.nbuv.gov.ua/handle/123456789/50227 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	2002
topic_facet	Методи оптимізації, оптимальне управління і теорія ігор
url	http://dspace.nbuv.gov.ua/handle/123456789/50227
citation_txt	Проекционные методы решения нелинейных вариационных неравенств / В.М. Панин, Т.В. Лаврина // Систем. дослідж. та інформ. технології. — 2002. — № 2. — С. 103-117. — Бібліогр.: 10 назв. — рос.
series	Системні дослідження та інформаційні технології
work_keys_str_mv	AT paninvm proekcionnyemetodyrešeniânelinejnyhvariacionnyhneravenstv AT lavrinatv proekcionnyemetodyrešeniânelinejnyhvariacionnyhneravenstv
first_indexed	2025-07-04T11:48:09Z
last_indexed	2025-07-04T11:48:09Z
_version_	1836716854507208704
fulltext	© В.М.Панин, Т.В.Лаврина Системні дослідження та інформаційні технології, 2002, 2 103 УДК 518.9 ПРОЕКЦИОННЫЕ МЕТОДЫ РЕШЕНИЯ НЕЛИНЕЙНЫХ ВАРИАЦИОННЫХ НЕРАВЕНСТВ В.М. ПАНИН, Т.В. ЛАВРИНА Рассматриваются конечномерные вариационные неравенства с сильно монотонным оператором и численные методы их решения. Изучаются проекционные методы первого порядка с линеаризацией ограничений, основанные на аппарате квадратичного программирования. Установлена нелокальная сходимость к решению и линейная скорость сходимости в его окрестности. ПОСТАНОВКА ЗАДАЧИ Вариационные неравенства (в.н.) включают в себя задачи оптимизации, дополнительности, отыскания седловых точек, решение нелинейных уравнений. Возросшее к ним внимание объясняется множеством моделей экономического равновесия, описываемых с помощью в.н. Наиболее полно численные методы решения конечномерных в.н. представлены в [ ]31− , описание равновесных моделей приведено в [ ]3 . Настоящая статья является обобщением работ [ ]5,4 по численному решению в.н. Решением в.н. 0)),( ≥− yxyF на множестве nR⊂Ω называется точка Ω∈x такая, что Ω∈∀≥− xxxxF ,0),( * , (1) где , — скалярное произведение векторов в nnn RRxFR →:)(; . Далее { }lixgRx i n ,,1,0)(\| …=≤∈=Ω — ограниченное множество, содержащее внутреннюю точку ;,,1,0)(: lixgx i …=<−≤ δ функции )(xgi и )(xF достаточно гладкие, при этом )(xgi выпуклы, а )(xF — сильно монотонный оператор: для любых nRyx ∈, 0,,)( 22 >≥≤≤ mMxMxxyFxm x . (2) Сформулированную задачу назовем в.н. (1), (2). Всюду векторы { } )(,)()(),(,, ' 1 xgxgxgxFx i l ii ==λ рассматриваются как вектор-столбцы; nI — единичная )( nn× -матрица; верхний индекс T означает транспо- нирование; iCC, , iαα , — стандартные обозначения положительных констант. Производная по аргументу u вектор-функции ts RRuf →:)( обозначается )(ufu , что согласуется с общепринятым обозначением В.М. Панин, Т.В. Лаврина ISSN 1681–6048 System Research & Information Technologies, 2002, 2 104 якобиана вектор-функции )(uf как матрицы )( st × со строками )(uf ui . Для скалярной функции 1:)( RRuf s → запись )(ufu означает вектор- строку, а )(uf ′ — вектор-столбец: )()( ufuf T u=′ . Решение x в.н. (1), (2) единственно, а необходимые условия первого порядка являются также достаточными и имеют вид [1–3]: ,,,1,0)(,0)()( **** lixgxgxF i iT x …===+ λλ (3) где { }liR il ,,1,0\|* …=≥∈=Λ∈ + λλλ ; Λ — множество векторов Лагранжа λ . В существующих методах численного решения в.н. (1), (2) – так называемых методах оптимизационного подхода – приближения к решению определяются как kk xx =+1 , где kx — решение вспомогательной задачи оптимизации Ω∈−−+ xxxxxHxF kkkk ,),( 2 1)(min (4) с `симметричной матрицей T kk HH = такой, что для любых nRp∈ ,,1,0,0,, 22 …=>≥≤≤ kaApAppHpa k (5) A и a — константы. К методам оптимизационного подхода с различным выбором матрицы T kk HH = можно отнести следующиех [1–3]: HH k = — проекционные методы, H — постоянная матрица ; kk DH = — линеаризованный метод Якоби, kD — диагональная часть матрицы )( kx xF ; 2/))()(( k T xkxk xFxFH += — симметричный метод Ньютона. Нелокально сходящимися среди них являются только проекционные методы, в которых kx — решение вспомогательной задачи ,,),( 2 1)(min Ω∈−−+ xxxxxHxF kkkα (6) а значение 0>α постоянно и должно удовлетворять требованию 1)( 2/12/1 <− −− HxFHI kxn α [3]. Скорость сходимости к решению проек- ционных методов является линейной, т.е. не ниже убывающей геометрической прогрессии [3].В частности, таким алгоритмом является известный метод проекции градиента ))((1 kkk xFxx α−Π= Ω+ , в котором nk IH = , а выбор α подчинен условию 1)( <− kxn xFI α , ΩΠ — оператор проектирования на Ω . Проекционные методы решения нелинейных вариационных неравенств Системні дослідження та інформаційні технології, 2002, 2 105 С точки зрения реализации такие проекционные методы обладают двумя существенными недостатками. 1. Если функции )(xgi нелинейны, то вспомогательную задачу (6) нельзя решить за конечное число вычислений, и линейная скорость сходимости является нереализуемой. 2. Для определения α необходимо вычислять не только матрицу 2/1−H , но и матрицу )( kx xF во всех точках Ω∈kx ( или оценить константу Липшица для )(xF на Ω ), что, как правило, нереально. Эти недостатки отсутствуют в алгоритме проекционного типа с матрицей nk IH = , предложенном Пшеничным в [4] .Задачи (4) или (6) заменены в нем на задачу квадратичного программирования (з.к.п.) ,,,)( 2 1)(min kkkkk x xxxxxHxF Ω∈−−+ (7) ,,,1,0,)()(\| ⎭⎬ ⎫ ⎩⎨ ⎧ =≤−′+=Ω lixxxgxgx kkikik … которая, в отличие от (4), (6) может быть точно решена за конечное число вычислений стандартными средствами. Алгоритм [4] строит последовательность )(1 kkkkk xxxx −+=+ α . Значение kα определяется в нем, исходя из условия релаксации ( убывания ) некоторой штрафной функции за конечное число вычислений )(xF , )(xgi , ),(xgi′ не прибегая к вычислению матриц )(xFx , )(xgi ″ и к их оценке в области Ω (или, что то же, не требуя задания константы Липшица для )(xF , )(xgi′ ). Однако скорость сходимости xxk → в [4] не установлена. Приведем общий подход к построению эффективных численных методов проекционного типа со вспомогательной задачей (7). Отметим, что требование симметричности kH в (7) не является ограничительным, поскольку при несимметричной kH вместо задачи (7) можно рассматривать эквивалентную ей с матрицей 2/)( T kk HH + , которая симметрична. ОПТИМИЗАЦИОННЫЙ ПОДХОД И ЭКВИВАЛЕНТНАЯ ЗАДАЧА ОПТИМИЗАЦИИ Эквивалентной оптимизационной задачей (э.о.з.) для в.н. (1), (2) назовем такую задачу оптимизации Ω∈Θ xx ,)(min , (8) которая среди множества своих решений (стационарных точек) содержит решения (стационарные точки) исходного в.н. В качестве целевой функции )(xΘ в [ ]6 предложена следующая: В.М. Панин, Т.В. Лаврина ISSN 1681–6048 System Research & Information Technologies, 2002, 2 106 xyxyxHxFx y −−−−=Θ Ω∈ ,))(( 2 1)(max)( . (9) Очевидны трудности численного решения э.о.з. (8), (9) , когда ограничения в (1) нелинейны, поскольку функцию )(xΘ нельзя вычислить точно, не говоря уже об отыскании ее производных по направлению в точках итерационного процесса. Построим э.о.з., свободную от недостатков э.о.з. (8), (9). Заменим з.к.п. (7) в текущей точке xxk = эквивалентной ей: ⎥⎦ ⎤ ⎢⎣ ⎡ ≤+−− 0)()(\|,)( 2 1,)(max pxgxgppxHpxF x p . (10) Ее решение )(xp единственно, поскольку )(xH удовлетворяет аналогу (5). Пусть )(xλ — двойственное решение задачи (10) и )(,)()( 2 1)(,)()( xpxpxHxpxFx −−=Θ — (11) ее оптимальное решение. Покажем., что задача (8), (11) является э.о.з. для в.н. (1), (2). Зафиксируем точку x и рассмотрим функцию Лагранжа для (10): pxgxgppxHxFpxW x )()(,,)( 2 1)(),,( +−+−= λλ . По теореме Куна-Таккера ),,(maxmin))(),(,()(),,(minmax λλλ λλ pxWxxpxWxpxW pp ++ Λ∈Λ∈ ==Θ= . (12) Для текущего +Λ∈λ обозначим )),,(,(),,(max),( λλλλϕ xpxWpxWx p == , где ),,(maxarg),( λλ pxWxp p = . Согласно правому неравенству (12), произ- водная 0)),,(,( =λλxpxWp , т.е. 0)(),()()( =++ λλ xgxpxHxF T x . (13) Использование (13) в выражении для ),,( λpxW дает )(,),(),,()( 2 1),( xgxpxpxHx λλλλϕ −= . (14) Получим другое представление для ),( λϕ x . Введем обозначение λλ )()(),( xgxFxL T xx +≡ . Оно является исключением из принятого выше правила обозначений, поскольку, во-первых, ),( λxLx — вектор-столбец, а, во-вторых, нижний индекс x здесь не означает, вообще говоря, Проекционные методы решения нелинейных вариационных неравенств Системні дослідження та інформаційні технології, 2002, 2 107 дифференцирования по x . На основании (13) ),()(),( 1 λλ xLxHxp x −−= , и вместо (14) можно записать )(,),(),,()( 2 1),( 1 xgxLxLxHx xx λλλλϕ −= − . (15) Согласно правому неравенству (12), +Λ∈=Θ λλϕ λ ),,(min)( xx . Этот минимум достигается в точке )(xλλ = , поскольку в соответствии с (12) по определению седловой точки { })(),( xxp λ имеет место =Θ )(x ))(,())(,,(max xxxpxW p λϕλ ≡= . Таким образом, ,))(,(),(min)( xxxx λϕλϕ λ ==Θ +Λ∈ (16) и задача оптимизации (8), (11) превращается в следующую: найти ⎥⎦ ⎤ ⎢⎣ ⎡ −= − Λ∈Ω∈Λ∈Ω∈ ++ )(,),(),,()( 2 1minmin),(minmin 1 xgxLxLxHx xx xx λλλλϕ λλ , (17) в которой внутренний минимум по λ достигается, согласно (16), на решениях )(xλ двойственной к (10) задачи. Задача (17) эквивалентна в.н. (1), (2). Действительно, в решениях Ω∈x̂ задачи (17) все слагаемые функции ),( λϕ x (15) неотрицательны и равны нулю, что означает выполнение условий (3), т.е. ˆ xx = . Обратное очевидно. Э.о.з. (17) отличается от э.о.з. (8), (9) возможностью ее эффективного численного решения. Для того, чтобы убедиться в этом, изучим ее свойства. Зафиксируем T kkk HHx =, в (7) и пусть )(, kkk xx λλ = — ее прямое и двойственное решения, kkk xxp −= . Поскольку ),(min λϕ kx по +Λ∈λ достигается в точке kλ , то для решения э.о.з. (17) можно применить схему декомпозиции, минимизируя ),( λϕ x сначала по +Λ∈λ при фиксированном kx , а затем — по x при фиксированном kλ . Считая kλ найденным, рассмотрим задачу Ω∈xx k ,),(min λϕ . Для нее недифференцируемой штрафной функцией является, как известно, функция )(),(),( xgNxx kkN ++=Φ λϕλ , (18) где { } 0,)(,,)(,0max)( 1 >=+ Nxgxgxg l… — коэффициент штрафа. Обозначим kkkN px ∂Φ∂ /),( λ ее производную по направлению kp в точке kx ; [ ]T k T k T k xz λ,= , { }0)(\|)( ≤=− ki xgik , { }0)(\|)( >=+ ki xgik . Лемма 1. Имеет место оценка kkkN pz ψ−≤∂Φ∂ /)( , (19) В.М. Панин, Т.В. Лаврина ISSN 1681–6048 System Research & Information Technologies, 2002, 2 108 где )2()1( kkk ψψψ += , ,,)()1( kkkxxk ppzL=ψ ∑ ∑ − + + ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎣ ⎡ −+−= )( )( )2( )()()( k k ki i kkki i kk xgxgNxg λλψ . Доказательство. Из необходимых условий экстремума для з.к.п. (7) следует )(1 kxkk zLHp −−= , kkkxkk pxgxg λλ ,)()(, −= . (20) Тогда, с учетом симметричности матрицы 1− kH , kkkxxkkxkk T xx k kxkxk ppzLpzLHzL p zLzLH ,)(,)()( )(,)( 2 1 1 1 −== ∂ ∂ − − , ∑ ∑ − + +== ∂ −∂ )( )( )()()(, )(, k k ki i kki i kkk k kk xgxgxg p xg λλλ λ , где слева фигурируют производные по направлению kp . Оценим kk pxgN ∂∂ + /)( . Пусть { })()(\|,,1,0 kkik xgxgliR +=∈= … , где 0)(0 ≡xg . Так как lixgpxg kikki ,,1,0,)(,)( …=−≤′ , то )())((max),)(max/)( kki Ri kki Ri kk xgNxgNpxgNpxgN kk + ∈∈ + −=−≤′=∂∂ . (21) Суммируя (21) с предыдущими производными по направлению, приходим к (19). Лемма доказана. Связь между )( kN zΦ и kψ устанавливает Лемма 2. Пусть симметричная матрица kH в (7) удовлетворяет (5). Тогда )(1 kNk zΦ≥ −γψ , { }1)2(;1max −= mAγ . (22) Доказательство. Из (2) вытекает MMpMppzLpm kkkkxxk ≥≤≤ ,,)( 22 , (23) причем величина M ограничена, если ограничена последовательность { } +Λ×⊂ n k Rz . На основании первого равенства (20) =− )(,)(1 kxkxk zLzLH kkk ppH ,= и, используя последовательно правое неравенство из (5) и левое — из (23), получим Проекционные методы решения нелинейных вариационных неравенств Системні дослідження та інформаційні технології, 2002, 2 109 )1(1121 ,)()(,)( kkkkxxkkxkxk mAppzLmApAzLzLH ψ−−− =≤≤ . Поэтому из выражений для )(, kNk zΦψ следует ≤+≤+=Φ −− )2()1(1)2(1 )2()(,)( 2 1)( kkkkxkxkkN mAzLzLHz ψψψ [ ] { } kkk mA ψγψψ =+≤ −1)2()1( )2(;1max . Лемма доказана. Из нее и из леммы 1 вытекает Следствие. Если N удовлетворяет условию ∑ + ≥ )(k i kN λ , (24) то 0)(/)( 1 ≤Φ−≤∂Φ∂ − kNkkN zpz γ . (25) Действительно, условия (23), (24) влекут 0≥kψ , и (25) следует из (19), (22). ОБЩИЕ СВОЙСТВА МЕТОДОВ ОПТИМИЗАЦИОННОГО ПОДХОДА Предварительно приведем общие свойства любого метода, использующего следующее аппроксимирующее в.н.: 0,)()( ≥−−+ kkkkk xxxxHxF , kx Ω∈∀ , (26) в котором матрица kH удовлетворяет (5), но необязательно симметрична (напомним, что kx — решение в.н. (26)). Необходимые условия первого порядка для него имеют вид 0)( =+ kxkk zLpH , [ ] ,,,1,0,)()( lipxgxg kkiki i k …==′+λ (27) где kkk i k xxp −=≥ ,0λ . Отметим, что условия оптимальности для з.к.п. (7) являются частным случаем в.н. (26) ( системы (27)) при T kk HH = . Лемма 3. Пусть { }kx — ограниченная последовательность, матрица kH удовлетворяет (5). Тогда решения в.н. (26) ограничены: 1Cpk ≤ 2Ck ≤λ . Доказательство. Так как функции )(xgi выпуклы, то kx Ω∈Ω∈ . Полагая в (26) xx = и учитывая kkk pxx += , получаем kkkkkkkkk xxpHpxxxFppH −+−−≤ ,,)(, . В.М. Панин, Т.В. Лаврина ISSN 1681–6048 System Research & Information Technologies, 2002, 2 110 Вместе с (5) это влечет [ ] CpxxAxFpa kkkk +−+≤ )(2 , откуда CxCp kk ≤≤ ,1 . Скалярно умножая первое равенство (27) на xxk − и учитывая остальные равенства (27), получаем =−+−=−+ xxpxgxxpHxF kkkk T xkkkk ,)(,)( λ ∑ ∑ = = −≤≤−+= l i l i i ki i kkkxkk xgxxxgxg 1 1 )()()()(, λδλλ . (28) Отсюда следует 20 )( CpHxFxxC kkkkk ≤+−≤λ . Лемма доказана. Лемма 3 не использует симметричности матрицы kH и относится к аппроксимирующему в.н. (26). В частном случае, когда в качестве (26) выступают условия оптимальности з.к.п. (7) с матрицей nk IH = , ограниченность kλ установлена в [4]. Результат [4] несложно обобщить на случай nk IH ≠ . Для полноты изложения приведем это обобщение. Лемма 4. Пусть { }kx — ограниченная последовательность и матрица T kk HH = в (7) удовлетворяет (5). Тогда 21 , CpC kk ≤≤λ . Доказательство. При фиксированном kxx = на основании (16), (12) =−≥==Θ ),,(),,(max)()( kkkkk p kk xxxWpxWzx λλϕ kkkk xxxxHxF −−−−= ,)( 2 1)( [ ]∑ = −′+− l i kkiki i k xxxgxg 1 ,)()(λ . (29) По аналогии с (28) в последней сумме δ−≤−′+ kkiki xxxgxg ,)()( . Очевидно также, что для величины )(xΘ , определяемой (11), справедливо )(,)( 2 1, 2 1,)(max)( 1 kkkkk p k xFxFHppHpxFx −=⎥⎦ ⎤ ⎢⎣ ⎡ −−≤Θ . Так как матрица 1− kH , как и kH , симметрична и удовлетворяет аналогу (5), то отсюда следует Cxk ≤Θ )( . Теперь из (29) легко вытекает 1Ck ≤λ , тогда ограниченность 2Cpk ≤ является следствием первого равенства (20). Лемма доказана. Сформулируем критерий сходимости алгоритмов с аппроксими- рующим в.н. (26) и отдельно — для его частного случая, когда используется з.к.п.(7) с матрицей T kk HH = . Проекционные методы решения нелинейных вариационных неравенств Системні дослідження та інформаційні технології, 2002, 2 111 Предложение 1. Если { }kx — ограниченная последовательнось и матрица kH в (26) удовлетворяет (5), то условие 0→kp )0( =kp необходимо и достаточно для того, чтобы )( ** xxxx kk =→ . Оно вытекает из леммы 3 и из условий (3), являющихся необходимыми и достаточными условиями первого порядка. Предложение 2. Если { }kx — ограниченная последовательность, матрица T kk HH = в з.к.п. (7) удовлетворяет (5), а коэффициент N — требованию (24), то каждое из условий 0)(,0 →Φ→ kNk zψ необходимо и достаточно для того, чтобы xxk → . Оно легко следует из условий (3) и того факта, что все составляющие величин kkN z ψ,)(Φ неотрицательны вследствие (23), (24) и (5). ПРОЕКЦИОННЫЙ МЕТОД: ФОРМУЛИРОВКА, СВОЙСТВА Пусть 0x — произвольное начальное приближение из )1;0(; ∈εnR и gC — любые константы, HHxgC kg => + ,)( 0 — постоянная симметричная матрица, удовлетворяющая (5). Опишем k -ю итерацию метода ,,1,0,1 …=+=+ kpxx kkkk α считая точку kx и значение 1−kN найденными. Шаг 1. Решить задачу (7) при HH k = и найти kkk xxp −= и kλ . Если 0=kp , то xxk = — процесс закончен; если 0≠kp — переход к шагу 2. Шаг 2. Найти коэффициент штрафа :kN ∑∑ +∈+∈ − = ⎪⎭ ⎪ ⎬ ⎫ ⎪⎩ ⎪ ⎨ ⎧ = )0( 00 )( 1 2,2,max i i ki i kkk NNN λλ . Шаг 3. Определить kα как наибольшее из чисел ,,1,0,2 …== − ssα при котором одновременно начинают выполняться неравенства gkk Cpxg ≤++ )( α , (30) ),()1(),( 2 kkNkkkN xpx λαελα Φ−≤+Φ , (31) где N — текущее kN . Найти kkkk pxx α+=+1 ; конец итерации. Свойства алгоритма устанавливает Теорема 1. Сформулированный метод сходится к решению в.н. (1), (2) по прямым и двойственным переменным, xxk → Λ→kλ . Каждая итерация метода осуществляется за равномерно ограниченное (по k ) число вычислений и 0>≥ αα k . При 0kk ≥ значение NNk = постоянно и справедливы оценки линейной скорости сходимости: В.М. Панин, Т.В. Лаврина ISSN 1681–6048 System Research & Information Technologies, 2002, 2 112 k kkN qCx 0),( ≤Φ λ , k k qCp 11≤ , k k qCxx 12* ≤− , (32) где )1;0(∈q — константа, 2/1 1 qq = . Доказательство. Сначала проведем обоснование правила выбора kα в алгоритме. Имеем ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎣ ⎡ ′′+′+=+ = + kkikikkiki li kk ppxgpxgxgpxg ,)( 2 ,)()(max)( 2 ,...,0 ααα , (33) где ikx — промежуточные точки разложения в ряд Тейлора. Обозначим [ ] lipxgxgg kkiki i k ,...,0,,)()(max)( =′+= αα . Из выпуклости )(αkg следует )()())0()1(()0()( kkkkkk xgxggggg ++ −≤−+≤ ααα , где учитывалось, что 0)1( ≤kg вследствие выполнения ограничений в (7). Теперь из (33) имеем при любом ]1;0(∈α 2/)()()( 22 kgkkkk pTxgxgpxg ααα +−≤+ +++ , (34) где gT — мажоранта для )(xgi′′ на отрезке [ ] lixx kk ,...,1,; = . Поэтому неравенство (30) справедливо, по крайней мере, для достаточно малых 0>α . Используя доказательство леммы 1, получаем ≤+ ),( kkk px λαϕ [ ] 2/)(,)()( 22 , kkkkkkxxk pTxgppzLz ϕαλαϕ ++−≤ , (35) где учитывалась отрицательная определенность матриц ϕTxgi ;)(′′− — мажоранта для ),( kxx x λϕ на [ ]kk xx , . В качестве ϕT может выступать удвоенная константа Липшица для ),( kx x λϕ , если в задаче (1), (2) непрерывность )(,)( xgxF ixx ′′′ ослабить требованием существования константы Липшица для )(xFx , )(xgi′′ . На основании (34), (35) и (22) ≤+−≤Φ−+Φ 2 2 2 )(),( kkkNkkkN pTzpx αψαλα 2 2 1 2 )( kkN pTz αγα +Φ−≤ − , (36) Проекционные методы решения нелинейных вариационных неравенств Системні дослідження та інформаційні технології, 2002, 2 113 где gTNTT += ϕ . Так как 0)( >Φ kN z в точках xxk ≠ , то отсюда вытекает (31), по крайней мере, для достаточно малых 0>α . Итак, процедура определения kα в алгоритме является обоснованной. Из gk Cxg ≤+ )( вытекает ограниченность { }kx , поскольку множество { }gCxgx ≤+ )(\| ограничено. Поэтому kλ и kp ограничены ( лемма 4)), величина NNk = постоянна при 0kk ≥ и удовлетворяет (24); ϕTTT g ,, — константы, не зависящие от k . Получим оценку снизу для kα . На основании (34) gkggkk CpTCpxg ≤+−≤++ 2/)1()( 22ααα , если 12 )(2 −≤ kg pTCα . Это означает, что (30) выполняется при указанных α . Установим, при каких α выполняется (31). Из (36) вытекает ≤Φ−+Φ )(),( kNkkkN zpx λα )( )(2 )()( 2 2 12 kN kN k kN z z pT z Φ−≤ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎣ ⎡ Φ −Φ−≤ − αεγαα при условии, что величина в квадратных скобках не меньше, чем ε . Последнее имеет место для [ ] 12 ))(2()(2 − +ΦΦ≤ kkNkN pTzz εγα . Таким образом, процедура определения kα гарантирует получение значений ⎪⎭ ⎪ ⎬ ⎫ ⎪⎩ ⎪ ⎨ ⎧ +Φ Φ ≥ ))(2( )( ;;1min 22 kkN kN k g k pTz z pT C εγ α . Здесь [ ] 01 12 >≥ − αkg pTC вследствие ограниченности kp . Далее, из 2/,)( kkkN ppHz ≥Φ и из (5) следует 12 )(2 −Φ≤ azp kNk . (37) Поэтому 0 )(2))(2( )( 22 >= + ≥ +Φ Φ α εγεγ Ta a pTz z kkN kN . (38) В итоге αα ≥k , где 0>α — константа.. Теперь из неравенства (31), рассматриваемого при kαα = , вытекает ,0)( →Φ kN z откуда xxk → , 0→kψ (предложение 2) и ,0 Λ→→ kkp λ , что очевидно. В.М. Панин, Т.В. Лаврина ISSN 1681–6048 System Research & Information Technologies, 2002, 2 114 Установим оценки скорости сходимости (32). На основании (16) )(),( ,111 kkNkkN xx λλ +++ Φ≤Φ . Вместе с (31) это дает ≤Φ + )( 1kN z )( kN zq Φ≤ , 1)(1 2 <−= αεq . При этом, как легко заметить, 2αα = , когда 0→kp . Если 0k — наименьший номер итерации с установившимся NNk = , то при 0kk ≥ приходим к первой из оценок (32): 0 0 0 0 )(,)()( 00 k kN kkk kNkN qzCqCqzz −− Φ==Φ≤Φ . Вследствие (37) отсюда вытекает вторая оценка (32) со значениями 1,)/2( 2/1 1 2/1 01 <== qqaCC . Наконец, при 0kk >>ρ с учетом предыдущей оценки ∑ ∑∑ − = ∞ = − = − =≤≤≤− 1 1 1 11111 1 1 ρρ ρ ki ki k ii ki ik q q CqCqCpxx . Переходя здесь к пределу xx →ρ при ∞→ρ , получаем последнюю оценку (32) со значением 1 112 )1( −−= qCC . Теорема доказана. Сравнивая алгоритм с методом Пшеничного [4], отметим, что в последнем вместо (31), (24) фигурируют соответственно ,)(),( 22 kkNkkkN pzpx αελα −Φ≤+Φ ⎪⎭ ⎪ ⎬ ⎫ ⎪⎩ ⎪ ⎨ ⎧ = ∑ = − l i i kkNN 1 1 2,max λ , (39) где 0>ε — произвольная константа и nk IH = в (7). Понятно, что неравенство (24) выполняется при меньших, чем в (39) значениях N . Это влечет уменьшение T и увеличение 2α в (38), чем обеспечивается снижение величины q в оценках (32). Если некоторые ограничения 0)( ≤xg j линейны, причем 0)( 0 ≤xg j , то коэффициент штрафа N «не накапливает», в отличие от [4], значений j kλ по процессу, поскольку 0)( ≤kj xg при всех …,1,0=k (если lj ,,1…= , то 0=N ), что также ведет к убыстрению сходимости процесса. Покажем теперь, используя теорему 1, что алгоритм Пшеничного [4] обладает линейной скоростью сходимости. Заменим первое неравенство (39) более общим T kkkNkkkN HHppHzpx =−Φ≤+Φ ,2/,)(),( 2αελα , (40) совпадающим с (39) при nIH = . Этот алгоритм отличается от описанного выше (шаг 1 – шаг 3) лишь выбором kα из условия проверки неравенства Проекционные методы решения нелинейных вариационных неравенств Системні дослідження та інформаційні технології, 2002, 2 115 (40) вместо (31). Для краткости назовем его проекционным методом (40), а рассмотренный выше — соответственно проекционным методом (31). Теорема 2. Если 1<ε , то для проекционного метода (40) справедливы все утверждения теоремы 1. Доказательство. Обозначим kβ шаговые множители проекционного метода (40) kkkk pxx β+=+1 и примем εε = в (31). Поскольку ≥Φ )( kN z 2/, kk ppH≥ , то из (31) вытекает (40), так что процедура определения kβ в методе (40) является обоснованной. Из сравнения (31) и (40) следует ααβ ≥≥≥ kk1 . На основании (40) ,0 xxp kk →→ (предложение 1 ). Установим оценки скорости сходимости. В точке kx , достаточно близкой к x , возможны две ситуации: 1. )(, )2( kkk oppH ψ= . Оценим сначала величину kα . Вследствие (23) имеем ,)( )2(2 kk op ψ= )()( )2(22 kkkx opHzL ψ== и из выражений для kkN z ψ,)(Φ следует )()( )2()2( kkkN oz ψψ +=Φ , )( )2()2( kkk o ψψψ += . Поэтому +Φ= )( kNk zψ ))(( kN zo Φ+ , ))((2 kNk zop Φ= и для любого 1≤α <Φ+Φ−=+− ))(()( 2 2 2 kNkNkk zozpT ααψα )()( 2 kNkN zz Φ−≤Φ−< αεαε . Используя это соотношение в первом неравенстве (36), приходим к (31) при любом ]1;0(∈α , что гарантирует в алгоритме получение 1=kα вблизи точки *x . Поскольку kk αβ ≥≥1 , то 1== kk αβ . Тогда из доказательства теоремы 1 вытекает )()( 11 kNkN zqz Φ≤Φ + , 111 <−= εq . 2. 0,, )2( >≥ CCppH kkk ψ . С учетом выражения для )( kN zΦ имеем )( 2 , 2 1, )2( kNkkkkk zCCppHppH Φ≥+≥ ψ , где { }2/;1min CC = . Тогда из (40) следует )(2/)()(),( 2 2 kNkNkkNkkkkN zqzCzpx Φ≤Φ−Φ≤+Φ βελβ , где 12/)(1 2 2 <−= Cq αε . В итоге в любой точке kx алгоритма (40) при 0kk ≥ выполняется { } 1;max,)()( 211 <=Φ≤Φ + qqqzqz kNkN , откуда следуют все оценки (32). Теорема доказана. В.М. Панин, Т.В. Лаврина ISSN 1681–6048 System Research & Information Technologies, 2002, 2 116 ЗАМЕЧАНИЯ 1. Опираясь на лемму 1, можно вместо (31) или (40) использовать следующее неравенство, обычно применяемое в условной оптимизации: )1;0(,)(),( ∈−Φ≤+Φ εψαελα kkNkkkN zpx (41) и по приведенной методике доказать все утверждения теоремы 1. Однако такой алгоритм безперспективен, поскольку, в отличие от приведенных выше, требует для определения kα вычисления kψ , т.е. вычисления )( kxx zL , и является весьма трудоемким алгоритмом второго порядка. В то же время замена kψ в (41) на kk ppH , или на )( kN zΦ , а также одновременное ( вместе с α ) дробление ε означают переход от (41) к менее трудоемкому неравенству (40) или, соответственно, к (31). Для задачи отыскания седловой точки выпукло-вогнутой функции, являющейся частным случаем в.н., неравенство (39) при отыскании kα было предло- жено в [7]. 2. Условие (2), а точнее — (23), для проекционных методов существенно не только при установлении оценок (32), но и для сходимости к решению. Они неприменимы, вообще говоря, для решения вырожденных задач ( 0=m в (2)). В частном варианте вариационных неравенств — в задачах оптимизации — проекционные методы сохраняют сходимость за счет использования самой специфики оптимизационной задачи, а именно, за счет потенциональности оператора )(xF , т.е существования функции )(0 xf , определяющей оператор )()( 0 xfxF ′= . Так, в методе линеаризации Пшеничного [8] сходимость к решению ( вырожденных ) задач оптимизации устанавливается за счет определения kα из условия релаксации штрафной функции )()()(~ 0 xgNxfxN ++=Φ , использующей )(0 xf . Модификация правила выбора kα метода линеаризации [8] ( аналогичная использованию (41)) позволила установить [9] оценки скорости сходимости процесса: линейную — при условии (2) и оценку )( 1−ko по функционалу )(~ xNΦ — в случае вырождения выпуклой задачи оптимизации. Для численного решения монотонных (с вырождением) в.н. разрабатываются специальные подходы ( методы итеративной регуляризации, экстраградиентный метод и другие ) [2, 10 ]. ЛИТЕРАТУРА 1. Harker P.T., Pang J.S. Finite-dimensional variational inequality and nonlinear complementarity problems:a survey of theory, algorithms and application // Math. Progr. — 1990. — 48, N 2. — P. 161–220. 2. Панин В.М., Скопецкий В.В., Лаврина Т.В. Модели и методы конечномерных вариационных неравенств // Кибернетика и системный анализ.— 2000. — № 6. — С. 47–61. Проекционные методы решения нелинейных вариационных неравенств Системні дослідження та інформаційні технології, 2002, 2 117 3. Nagurney A. Network economics : a variational inequality approach. — Norvell : Kluver akad. publ., 1993. — 326 p. 4. Пшеничный Б.Н, Калжанов М.У. Метод решения вариационных неравенств // Кибернетика и системный анализ. — 1992. — № 6. — С. 48–55. 5. Панин В.М., Александрова В.М. Линейная сходимость метода решения вариационных неравенств // Кибернетика и системный анализ. — 1994. — № 3. — С. 176–180. 6. Jia Hao Wu, Florian M., Marcotte P. A general descent framework for the monotone variational inequality problem // Math. Progr. — 1993. — 61, N 3. — P. 281–300. 7. Данилин Ю.М., Панин В.М. О некоторых методах поиска седловых точек // Кибернетика. — 1974. — № 3. — С. 119–124. 8. Пшеничный Б.Н. Метод линеаризации. — М.: Наука, 1983. — 136 с. 9. Панин В.М. Оценки сходимости двух методов линеаризации // Докл. АН УССР. Сер. А. — 1984. — № 5. — С. 77–79. 10. Гольштейн Е.Г., Третьяков В.М. Модифицированные функции Лагранжа. — М.: Наука, 1989. — 400 с. Поступила 20.03.2002

Проекционные методы решения нелинейных вариационных неравенств

Репозитарії

Схожі ресурси