Содержание к диссертации
Введение
ГЛАВА I. Модифицированные функции лагранжа в выпуклой задаче поиска седовых точек с ограничениями ... 19
1.1. Метод штрафных функций в задачах математического программирования 19
1.2. Определение и некоторые свойства слабых модифицированных функций Лагранжа (СМФЛ) 25
1.3. Модифицированные функции Лагранжа (МФЛ)... 37
1.4. Двойственные модификации функции Лагранжа 43
1.5. Регуляризированный вариант модифицированной функции Лагранжа 54
1.6. Двойственные градиентные методы поиска седловых точек 63
1.7. Модифицированные функции Лагранжа в задаче выпуклого программирования 71
ГЛАВА 2. Модифицированные функции лагранжа в невыпуклой задаче поиска седовых точек с ограничениями 81
2.1. Вспомогательные сведения и постановка задачи... 81
2.2. Двойственные методы поиска строгой локальной седловой точки 87
2.3. Диагональные двойственные алгоритмы 104
2.4. Прямые методы поиска строгой локальной седловой точки 110
2.5. Точная штрафная функция в задаче поиска строгой локальной седловой точки с ограничениями ... 118
2.6. Симметричная модификация функции Лагранжа 127
2.7. Алгоритмы отыскания строгой локальной седловой точки, использующие симметричную МФЛ 142
2.8. Задача поиска локальных седловых точек с ограничениями-неравенствами 147
Заключение 153
Приложение 1. Модифицированные функции лагранжа в много критериальных задачах оптимизации 154
Приложение 2 160
Литература 171
- Определение и некоторые свойства слабых модифицированных функций Лагранжа (СМФЛ)
- Регуляризированный вариант модифицированной функции Лагранжа
- Точная штрафная функция в задаче поиска строгой локальной седловой точки с ограничениями
- Алгоритмы отыскания строгой локальной седловой точки, использующие симметричную МФЛ
Введение к работе
I. Большое число практических задач, возникающих в экономике, науке и технике, в математической постановке приводят к задачам оптимизации, в связи с чем за последние годы наблюдается быстрое развитие теории оптимизации. В настоящее время эта область исследования операций включает в себя многочисленные разделы, среди которых линейное, выпуклое, стохастическое программирование, оптимальное управление и др.
К настоящему времени отысканию седловых точек посвящено значительное количество работ, в которых приведены необходимые и достаточные условия существования седловых точек, предложены численные методы ОСТ, рассмотрены многие другие вопросы. Вместе с тем характерной чертой, присущей всем этим исследованиям является то, что поиск седловых точек осуществляется на множествах достаточно простой структуры, например, на всем пространстве, параллелепипеде и т.п.
Напомним в этой связи, что МФЛ называют конструкцию, которая, с одной стороны, обобщает основные характеристические свойства классической функции Лагранжа, с другой - обладает по сравнению с последней некоторыми преимуществами. Первое обычно означает, что исходная задача математического программирования может быть сведена к отысканию седловых (или экстремальных) точек МФЛ, второе - то, что с помощью МФЛ можно строить эффективные численные методы (классическая функция Лагранжа, как известно, с этой точки зрения является не очень удобной). Естественно, что столь общие соображения породили весьма разнообразные варианты МФЛ в задаче условной оптимизации.
В частности, первые разновидности, так называемые двойственные МФЛ, были предложены в работах [67,73] . На базе этих МФЛ в указанных работах, а также в [ 23, 37, 46-48, 64, 70, 78, 79] были разработаны двойственные методы решения задачи нелинейного программирования.
МФЛ другого типа - прямые МФЛ, а также вопросы, связанные с их использованием в численных методах были рассмотрены в [ 6,23] .
В этих же работах [, 23] была введена и симметричная модификация функции Лагранжа, обобщающая прямой и двойственный типы МФЛ.
Для всех перечисленных результатов общим являлось то, что исходная задача сводилась к отысканию седловых точек МФЛ. Между тем отыскивать седловые точки гораздо сложнее, чем точки экстремума. Исходя из этого очень полезной представляется МФЛ, предложенная в [55,5&] , поскольку исходная задача равносильна отысканию точки экстремума этой функции. С ее помощью [49-51,57,68] удалось построить ряд алгоритмов решения задачи нелинейного программирования, в том числе глобально сходящихся.
Необходимо также упомянуть тесно связанную с МФЛ точную штрафную функцию, на основе которой (см. [59 63\ ) были предложены численные методы, эквивалентные \49 51, 79] в определенном смысле методам МФЛ.
Для задачи выпуклого программирования самой удобной оказалась двойственная модификация функции Лагранжа, а также использующий ее двойственный градиентный метод. Этим вопросам были посвящены работы [1, 10-16,17,40,65,66,69,74-77} .
Метод Эрроу-Гурвица, также использующий двойственную МФЛ в задаче выпуклого программирования, исследован в [9,29-31] .
МФЛ прямого типа в выпуклых задачах изучалась в [/ ] .
Указанная литература, конечно, не исчерпывает всех вопросов, связанных с МФЛ. Назовем хотя бы первую и, по-видимому, единственную монографию, посвященную данной тематике [52] , а также работы [24,25,45,80] . Вместе с тем, в ней достаточно полно отражены вычислительные аспекты применения МФЛ в экстремальных задачах.
В настоящей работе, развивая этот подход, мы рассмотрим модифицированные функции Лагранжа в задаче поиска седловых точек с ограничениями (0.1), а также численные методы решения (0.1), использующие МФЛ.
3. диссертация состоит из введения, двух глав, заключения и двух: приложений.
Подобно тому, как в задаче условной оптимизации методы МФЛ рассматриваются отдельно для случаев выпуклого и нелинейного (невыпуклого) программирования, мы разделили исследование задачи ОСТ с ограничениями на два этапа. Первый этап (глава I) посвящен изучению частного случая задачи (0.1) при дополнительных предположениях вогнутости по х и выпуклости по и критерия rfx,u) , вогнутости ограничений g.fx), І-1,Ш \ h; (и), У=/, Я » а также выпуклости и компактности множеств X , / . На втором этапе (глава 2) рассматривается общая задача ОСТ с ограничениями без указанных предположений.
Первая глава целиком посвящена изучению вопросов, связанных с применением МФЛ в вогнуто-выпуклой задаче ОСТ с ограничениями. В качестве вспомогательного инструмента в дальнейшем используется установленная в § I.I связь между МФЛ и методом штрафных функций. В § 1.2 вводится понятие слабой модифицированной функции Лагранжа (СМФЛ), как наиболее общей конструкции, сохраняющей свойства обычной функции Лагранжа (0.3). Особо важными представляются ШФЛ следующего специального вида
В приложении I понятие МФЛ вводится в задаче многокритериальной (векторной) оптимизации (0.4).
Некоторые из предложенных в диссертации алгоритмов были реализованы на ЭВМ. Результаты решения с их помощью тестовых задач приведены в приложении 2.
Содержание диссертации отражено в работах [81-85].
Основные результаты работы состоят в следующем:
в связи с необходимостью решения задачи отыскания седловых точек с ограничениями для нее введено понятие модифицированной функции Лагранжа (МФЛ) и установлена взаимосвязь между решениями исходной задачи и седловыми точками МФЛ;
построены различные классы МФЛ - двойственные, прямые, симметричные, на основе которых предлагаются соответствующие методы решения исходной задачи. Доказана сходимость предложенных алгоритмов, глобальная в случае вогнуто-выпуклой задачи, локальная в общем случае;
-получены оценки сходимости, а также проведено сравнение некоторых из указанных алгоритмов между собой. Численные методы реализованы на ЭВМ, исследована их практическая сходимость при решении ряда тестовых задач.
Определение и некоторые свойства слабых модифицированных функций Лагранжа (СМФЛ)
Таким образом лемма 1.5 для задачи (1.6) утверждает фактически, что выполняется (І.І4). Объединяя теорему 1.4 и лемму 1.5, получим следующий результат.
Пусть имеются функции : /? х М —-- R1, п : R Л —- R . Для того, чтобы Т fw) из (I.I2) являлась (ШЖ произвольной задачи (1.6), а также выполнялось (I.I4), причем значения (І.ІЗ) и (І.І4) совпадали, необходимо и достаточно соблюдения ограничений АІ-А4.
Пусть дана функция T(w) вида (I.I2) и задача (1.6). Тогда ограничения AI-A4 необходимы и достаточны для того, чтобы она была вогнутой по (х, А) , выпуклой по (ц,/и) $ и выполнялось соотношение (I.I4), причем значения (І.ІЗ) и (І.І4) совпадали. Доказательство. Напомним, что в теореме 1.4 была установлена эквивалентность условий АІ-АЗ, с одной стороны, и вогнутости по (хл X) , выпуклости по (Ujju) функции Т fw) , с другой. Достаточность теоремы будет полностью доказана, если вспомнить лемму 1.5. Остается, таким образом, показать необходимость условия А4, а это, в свою очередь, нетрудно сделать, если рассмотреть те же самые примеры, что и в теореме 1.4. Теорема доказана. В результате объединения теорем 1.4, 1.6 можно теперь сформулировать утверждение, которое является фактически новым определением (МШ для функций вида (I.I2). Пусть дана задача (1.6) и функции :/? х M- R, o:R A- -R. Вогнутая по /be,А] и выпуклая по ((l,ju) функция Т(w) вида (I.I2) определяет (МШ задачи (1.6) тогда и только тогда, когда для нее выполняется (I.I4) и значения (I.I3) и (I.I4) совпадают. 3. Мы установили с помощью (МШ связь между исходной задачей (1.6) и соотношением двойственности (I.I4). Однако в (1.6), как уже отмечалось, существует седловая точка, поэтому было бы интересным выяснить, когда обладает седловой точкой и Tfw) . Оказывается это возможно сделать, правда не для всех СШВД, а для некоторого подкласса этого семейства. Упомянутый подкласс получается с помощью дополнительного ограничения, накладываемого на функции и п А5. Для любого Ze/?+ найдется такое JU&M f что Z (Q,fl) Z,Q при всех оф R+ ; аналогично, для любого te /?_ найдется такое Х А , что Ч(НЛ\) t,h при всех h4R+ . Отметим, что из А5 вытекает вторая часть условий А4. Лемма 1.6. Пусть выполняются ограничения AI-A5, Пх ) удовлетворяет условию Липшица на произведении компактов X х Y , функции (}i 1 hi непрерывны, имеют место условия регулярности (1.10) min ( Н-Рр( 5) хфВ где p 0 . Тогда найдутся такие /і/ є М , Л єЛ , что - 35 max men Ffx,и) = max mln 5 up Inl Tfw). xeA иєВ d xeX yeY ІШІІУІІ fyU\\ju \\ Доказательство. Напомним, что T(W)=Ffx,y) +% (yfx),ju) -h jfh(y), A) и зафиксируем x єХ . Тогда из условий леммы согласно теореме 1.2 получим, что для некоторого Л є Л mln {Ffx,и)+ $up nfh(ціХ)} = mln Г(х,ц). yeY l 7 1ШМ L J иєВ Аналогично и функция ffx) = mln дир {F(xu)h(h(u),X)\ 3 І/ЄУІШ І\ І l 7 L 7 удовлетворяет условиям теоремы 1.2, поэтому найдется такое Ju eM , что max\i(x) + in/ z(qfx))/u)}= max іfx) . xeX U H/tlMljul J хе A Таким образом max mln Ffx,и) - max ffx) = max Lnj U (x)+ хєА уєв хєА осєХ \\ju\Mju \\ і-$( ?&),№)}=maDC i-uf mln бар Tfw)=max 57 J J xex Jjpktiju ll yeY ІШІХ ІІ оеєх mln in/ tup T(w)=max men tup in/ Tfw) ueYlljuNljul //A/K//A // осєХ ueY /МЫ/Л // \\JU\HWJU4 Лемма доказана. Лемма 1.6 носит вспомогательный характер и используется в доказательстве следующей теоремы. Теорема 1.8. Предположим, что в задаче (1.6) выполняются ПІ.І и условия регулярности (І.Ю); функции z и h непрерывны соответственно по ju и А и удовлетворяют AI-A5. Для того, чтобы (х U ) являлась седловой точкой Г(эс,и) на Ах В необходимо и достаточно существования \ єЛ , JU GM таких, что [(х \ )] (ц ,пі ) ] является седловой точкой Tfw) вида (I.I2). Доказательство вполне аналогично доказательству теоремы 1.3, которое имеется в Таким образом, ограничения AI-A5 выделяют в семействе СМФЛ класс таких функций Т (W) , для которых на множестве (Х Л)Х (Y M) существует седдовая точка. Кроме того, теорема 1.8 очевидно означает не что иное, как обобщение теоремы 1.3, а значит и теоремы Куна-Таккера, для слабых модифицированных функций Лагранжа в задаче (1.6). Из теоремы 1.8 вытекает еще одно следствие. Напомним, что конусом допустимых направлений произвольного замкнутого выпуклого множества X в точке хеХ называется замыкание Кх (ос) конуса Кх (ос) ={ъ- = А(х-х)\X Q, осеХ) ж обозначим через Кх (х) конус, сопряженный к Кх(х) .
Регуляризированный вариант модифицированной функции Лагранжа
Рассмотрим двойственную функцию { () из d»36), обладающую, как установлено в 1.4, свойствами БІ-БЗ. Нетрудно видеть, что достаточно положить г] (x,U,\,ju) из предыдущей теоремы равной j (\,ju) , т.е. не зависящей от ос и U , чтобы выполнялись все условия этой теоремы. Таким образом, алгоритм (1.54) сведется к двум последним строкам (1.58), откуда следует выполнение второго из требуемых соотношений
Что касается первого равенства, то пусть Z - произволь ная предельная точка последовательности {2-К}к о Из (1.58) тогда вытекает, что eZ (в ) , то есть является седловой точкой . Последнее же, как было по казано в ходе доказательства леммы 1.8, влечет за собой z eZ f что и требовалось. Теорема доказана. Отметим, что условие теоремы &І=ф эквивалентно условию непустоты седлового множества WT Wffl. Tlw) . Достаточным условием теоремы, следовательно, будет являться условие регулярности (1.10) в исходной задаче (1.6). Второй вариант двойственного градиентного метода естественно назвать прокс-методом [36] или двойственным методом с регуляризацией. Пусть W = (х, Ц, А,/// - произвольная точка из R х R . Обозначим через 2 седловую из (1.51) на Xх Y . Очевидно, что Z# (w) единственна при любом w . Алгоритм состоит в построении последовательности УКН=І/К-ЧГ4(І/ -ІГ), (1.59) где r O,fr=o,/,...Eo6 oo,?::cef0,2Mi), Туєґо,2//,г), постоянные L,j ВЗЯТЫ из (1.50). Теорема 1.20. Пусть седловое множество функции Лагранжа Z (w) непусто, тогда алгоритм (1.59) сходится к некоторой седловой точке L (w). Доказательство. Очевидно, что из представления (I.5I) функции М следует Обозначая теперь можно переписать (1.59) в виде причем нетрудно видеть, что в силу ГІ-ГЗ Таким образом, (1.59) приведен к виду (1.54), что позволяет воспользоваться теоремой І.І8. Последняя вместе с теоремой І.І7 дает требуемый результат о сходимости (1.59). Теорема доказана. В частности, алгоритм (1.59) приобретает особенно простой вид,, если взять olj fx) = Их \\Z/2,c/z fy) = Ну IIz/2 . Шаги x t ty можно брать равными единице, в итоге (1.59) запишется следующим образом В последней записи наиболее ясно проявляется сходство методов (1.58) и (1.59): в обоих внешние итерации осуществляются по двойственным переменным, а вспомогательные подзадачи решаются относительно прямых переменных. 3. Кратко отметим особенности алгоритмов (1.58), (1.59). Очевидно с точки зрения сходимости предпочтительнее (1.59), поскольку он сходится к точке в отличие от (1.58). Кроме того, гораздо большие преимущества по сравнению с (1.58) ргохнлетод (1.59) обеспечивает с точки зрения решения вспомогательной задачи. Дей - 70 ствнтельно, вспомогательная задача в (1.59), состоящая в отыскании седловой точки сильно вогнуто-выпуклой функции, гораздо проще аналогичной задачи в (1.58) [7, 20 ] . Особо при этом стоит отметить следующий важный случай, когда можно непосредственно оценить II 2 - ZR II в (1.59). Лемма I.I3. [20] . Цусть дана функция S (сем) , дифференцируемая, сильно вогнутая по х и сильно выпуклая по U на произведении выпуклых замкнутых множеств X, У , причем константа сильной вогнутости по х и сильной выпуклости по U одна и та же, равная Л . Предаоложш также, что градиент функции S удовлетворяет условию Липшица с постоянной с Тогда последовательность {і? } к о » определяемая по формулам х + =9Гх fa +rSx(z% с шагом Те (0,4- А /с ) , сходится к седловой точке 2 функции S (Е) со скоростью геометрической прогрессии, т.е. II zK-z ЫъкМ II z -z ll, г (т)= co/?ste (ofi). Доказательство. Очевидно, что для J (осм) справедливо неравенство Так как 0 Т 4А/С2 , то 0 7(Т) 1 , и, следовательно из последнего неравенства вытекает утверждение леммы, а также требуемая оценка. Лемма доказана. Таким образом, лемма 1,13 применима в алгоритме (1.59), если градиенты функций /"!#/, hj в исходной задаче (1.6) удовлетворяют условию Липшица. 1.7. Модифицированные функции Лагранжа в задаче выпуклого программирования. I. Приведенные выше результаты касались модифицированных функций Лагранжа в исходной задаче (1.6) - задаче поиска седловых точек. Поскольку частным случаем этой задачи является задача выпуклого программирования и, с другой стороны, модифицированные функции Лагранжа были первоначально введены именно в задаче выпуклого программирования, было бы интересным выяснить, во что трансформируются наши результаты в этом случае и сравнить их с известными [//,/3-/5] . Положим в (1.6) Г(х,д) = Г(х) ,hfy) ЕО при всех зсєХ, иєУ , где X - выпуклый компакт, и рассмотрим задачу найти ос є А , і Далее, определение 1.3 ММ, данное нами, также совпадает с определением МШ из [/4,15]. Однако, главное - это та система ограничений, которые накладываются на функцию (Qtju) Сравнивая полученные выше результаты с аналогичными, можно отметить ослабление требований на г . Так, рассматривая (МШ, мы не использовали никаких ограничений, кроме AI-A4 ( 1.2), в отличие от [ 13] . В частности, в теоремах 3 и 5 из [13 ] , оказывается, достаточно требовать лишь соблюдения AI-A4.
Точная штрафная функция в задаче поиска строгой локальной седловой точки с ограничениями
Доказательство следует из теоремы 4 [4-3, с.47\ , поскольку условия теоремы оказываются достаточными для того, чтобы, с одной стороны, х являлась точкой изолированного локального максимума функции F(XM ) на множестве А и, с другой стороны, и - точкой изолированного локального минимума F(ос и) на В .
Всюду далее мы будем считать функции F, q-L, /ь дважды непрерывно дифференцируемыми. Кроме того, нам потребуются следующие предположения. П2.І. Существует точка w , являющаяся стационарной для L , то есть Lw (w ) = 0 ; П2.2. Матрицы дх (х ) , Л» /y j имеют максимальный ранг каждая; П2.3. Lxx(w )xyx О для любого хфоідх (ґх )х=о, Lyy (w ) у,(/ »0 для любого у+О, hy fy )у=0; П2.4. Гессианы Г, QL, h; удовлетворяют локальному условию Липшица в некоторых окрестностях точек х , и . Согласно теореме 2.5 условия 112.1, П2.3 означают, что мы требуем достаточных условий второго порядка строгой локальной седловой точки. Для удобства введем обозначения прямых z = (x\ UT)T R R? , и двойственных 6=(\T,JUT)TGR XR переменных функции Лагранжа. 2.2. Двойственные методы поиска строгой локальной седловой точки. Модифицированные функции Лагранжа, которые мы хотели ввести для задачи (2.II), могут иметь различный вид, в зависимости от - 88 типа строящихся на их основе алгоритмов, двойственные алгоритмы используют ММ следующего вида т п T(w)=Lfir)- rZ V(qL(x})+(r% Щ( /)) , (2.12) где (Ґ положительный числовой параметр, а V - дважды непрерывно дифференцируемая функция действительного переменного. Относительно У будем предполагать выполненными требования: ФІ. т (t) = 0 тогда и только тогда, когда t— О ; Ф2. Ч "(о) 0 ; ФЗ. Ч11 удовлетворяет условию Липшица в окрестности нуля. Замечание. В условии Ф2 можно без ограничения общности считать, что If" (о) = / . В противном случае достаточно нормировать функцию Ц , при этом ввиду наличия параметра (Ґ в (2.12) МФЛ не изменится. Всюду ниже мы будем предполагать это требование выполненным. В качестве примеров фіункций т укажем следующие: Через Tf (а) мы будем обозначать вектор-столбцы с элементами 7], і =/,/г, где а=(аи...,ак)Т вектор произвольной размерности к и через Ун (а) диагональные матрицы, с элементами Y (di) на диагонали. Рассмотрим двойственный метод первого порядка - последовательность {w }K 0 строится по правилу: a) ZKH- (х , ЦК+1) лежит в некоторой малой окрестности и определяется из условия \\Tx(xK1 !xK,/K)lkmin{ /cf15K\\ Ц(х ) II}, [II T fXf) Umin{ l(f,5K\\ %(h(9n)«}, (2.13) - 89 -где \Y }к2.0,{Ок}к 0 неотрицательные и ограниченные последо вательности; к+1 б) A" =AV(r % U ju juWffgfx ")). (2.14) к+1 Нетрудно видеть из (2.13), что гЛТ" есть приближенное (а при Ук точное) решение z(6) вспомогательной задачи Гн (г, 0) = 0 (2.15) относительно z . С учетом этого становится очевидным, что (2.14) это метод простой итерации (2.4), примененный для решения системы Таким образом, внешние итерации в методе (2.13), (2.14) осуществляются по двойственным переменным, тогда как прямые переменные Z= (ос, и) отыскиваются на каждом шаге в результате решения вспомогательной задачи. Этим объясняется и название алгоритма - двойственный. двойственные градиентные методы впервые были предложены для решения задачи нелинейного программирования [37, 46, 47 ] . Это были первые алгоритмы, связанные с использованием МВД, воз-никпше как обобщение методов штрафных функций и функции Лагранжа. Докажем некоторые вспомогательные утверждения, обозначив
Матрицы A ((f) обратимы для достаточно больших значений (Ґ . Более того, семейство матриц А (сґ) равномерно ограничено, то есть существует такая постоянная М о , что при всех сґ достаточно больших \\А ((Ґ) II4 М .
Алгоритмы отыскания строгой локальной седловой точки, использующие симметричную МФЛ
Двойственные алгоритмы первого и второго порядков, которые мы рассмотрели в предыдущем параграфе, включают в себя решение на каждом шаге вспомогательной задачи. Отсюда следует, что, применяя для ее решения какой-либо известный итерационный метод, нам придется на каждом шаге делать огромное количество внутренних итераций.
В отличие от этих алгоритмов в диагональных двойственных методах делается лишь по одной внутренней итерации на каждом шаге. Смысл термина "диагональный" (см. [78,79] ) можно пояснить следующим образом. Пусть 1 = (і , J ) I ,/=0,/,...} , где (С,]) соответствует і -й внутренней итерации при решении і -й вспомогательной задачи. Тогда двойственные методы будут соответствовать пробеганию по строкам всего множества I , в то время как диагональные двойственные методы - пробеганию лишь главной диагонали.
Рассмотрим сначала диагональный метод Ньютона - строится Диагональный метод совпадает с методом Ньютона, примененным для решения системы В (W, Сґ) =0 при достаточно больших (Ґ . Доказательство. Пусть дана система В[]№,(ґ) = 0 . Применяя метод Ньютона, получим wKH=W + A W , где /\l (w AW К=-В (w О1). Иначе говоря, л W есть решение системы где аргумент wK опущен. Нетрудно видеть, что первые два уравнения можно переписать то есть они совпадают с п.б) диагонального метода Ньютона. Остается определить A SK , а это делается, как уже отмечалось, по формулам (2.35), где 6=-B(wf f) , а Л/(\х/,(ґ) вычислена в точке wK . Цри этом для достаточно больших (Ґ матрицы Аі,А2,Аз- Аї,&іі Bz из (2 36)» вычисленные в точке W , а также M(w?tf) невырождены (это можно показать анало- гично лемме 2.8). Очевидно, что то же самое справедливо для всех этих матриц, вычисленных в точке W , лежащей достаточно близко к w . Таким образом, определение л б совпадает с п.а) диагонального алгоритма. Теорема доказана. Как следствие из теоремы 2.8 получаем следущее утверждение. Теорема 2.9. Пусть выполнены условия П2.І-П2.4, тогда существует такое Т& О , что при всех сґ ( диагональный метод Ньютона локально сходится с квадратичной скоростью. Для доказательства достаточно обратиться к теореме 2.2. Рассмотрим теперь квазиньютоновский вариант диагонального метода. Он совпадает с алгоритмом диагонального метода Ньютона во всем за исключением того, что вместо Тгг используется некоторая ее аппроксимация. Скорость сходимости при этом снижается до сверхлинейной, характерной для квазиньютоновских методов. Введем матрицу, аналогичную N(w\cr) из (2.32), где Вк некоторое приближение 7 z (W ) . В частности мы будем использовать для построения последовательности матриц { к}к 0 методы Бройдена (2.9) и Пауэлла-Бройдена (2.10). Таким образом, квазиньютоновский диагональный метод состоит такой, что: в построении последовательности а) Вк =6 +А9 , где Л6 определяется по формулам (2.35),
Можно показать аналогично теореме 2.9, что этот метод совпадает с алгоритмом который решает систему уравнений B(W, r)=o . Как видно из (2.43), метод (2.44) отличается от обычных квазиньютоновских алгоритмов решения нелинейных систем уравнений тем, что в нем аппроксимируется не вся матрица производных Л/(\Х/,сґ)= Ву/(Щ(ґ) а лишь ее верхний левый угол. Смысл такой аппроксимации становится ясным, если учесть, что как раз именно левый верхний угол N(w, f) содержит вторые производные исходных функций задачи (2.II), тогда как вся остальная часть М(ЧУ,Сґ) содержит лишь первые производные. В итоге в алгоритме (2.44) можно обойтись вычислением лишь первых производных.
Пусть выполнены условия П2.І-П2.3, последовательность матриц \Рк$к о СТР0ИТСЯ по формулам Бройдена (2.9) или Пауэлла-Бройдена (2.10), причем В0 предполагается достаточно близкой к Tzz(w ) Тогда найдется такое (Ґк О , что при всех (Ґ сґк алгоритм (2.44), а значит и диагональный квазиньютоновский метод, локально сходятся со сверхлинейной скоростью.
Доказательство проведем аналогично [7 5] . Обозначим для простоты через W,W,B,B , соответственно, w , WK+ , BK,BK+i и покажем сначала, что (2.44) сходится с линейной скоростью. Дія ЭТОГО нам нужно определить некоторую окрестность Uточки (W %z (w )) в пространстве RPxRhRnxRmxL(RPxR% RpxR ) , где L (RPxRV, RfiR?) - пространство матриц, задающих линейные отображения из
