Структуры нелинейных вырожденных отображений и их применение к построению численных методов тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

АКАДЕМИЯ НАУК СССР ШЧИСЛИТЕЛЬНЫЙ ЦЕНТР

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

ТРЕТЬЯКОВ Алексей Анатольевич

УДК 519.6

СТРУКТУРЫ НЕЛИНЕЙНЫХ ВЫРОЖДЕННЫХ ОТОБРАЖЕНИЙ И ИХ ПРИМЕНЕНИЕ К ПОСТРОЕНИЮ ЧИСЛШНЫХ МЕТОДОВ

01.01.09 - математическая кибернетика

АВТОРЕФЕРАТ диссертации на соискание ученой степени доктора физико-математических наук

г/г

л/

Москва - 1987

Р/с збгЧот-

Работа выполнена в Институте проблем кибернетики Академии наук СССР.

Официальные оппоненты

доктор физико-математических наук,профессор Р.Ф.Габасов, доктор физико-математических' наук Ф.С.Васильев, доктор физико-математических наук, профессор В.К.Леонтьев.

Ведущая организация

- Ордена Ленина Институт кибернетики им. В.М.Глушкова АН УССР

Защита диссертации состоится "_"_1988г.

в " " часов на заседании специализированного совета Д.002.32.02 при Шчислительном центре АН СССР по адресу: 117967.Москва 1СП-1,ул. Вавилова 40.

С диссертацией можно ознакомиться в библиотеке ВЦ АН

СССР.

Автореферат разослан "_"_1987г.

Учёный секретарь специализированного совета к.ф.-м.н. С

С.М.Швартин

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

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

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

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

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

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

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

1. Аппарат для описания множества нулей отображения//*,) (или описание множества решений уравнения в вырожденном случае).

2."Методы исследования вырожденных задач.

3. Конструкции схем для построения численных методов решения вырожденных нелинейных уравнений.

рсх> = 0 (I)

и экстремальных задач вида

(2)

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

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

Большинство задач вырожденного типа сводятся либо к решению уравнения (I), либо к решению- экстремальной задачи вида (2), где отображение ¡- имеет нерегулярную структуру, т.е. выровдается в решении ЗС*~ :

хт р'с**;* у о)

Здесь : Х-7*" ) Р :Х-> У, X, У~ Ь ~ пространства, Лтр(х*) - образ оператора с.*) . Условие (3) - это основное условие вырожденности или нерегулярности, Поэтому в дальнейшем задачи (I) и (2) будем называть вырожденными, если выполнено условие (3). Наличие регулярной структуры у отображения р позволило достаточно полно описать свойства Р в (I), (2) и построить эффективные методы решения, основанные на идеях линеаризации.

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

Степень новизны и значимости результатов исследования. Описание структуры множества нулей отображения Р(эс) ■ составляет основу как теории экстремальных задач, так и теории построения численных методов. В невырожденном случае это тео-

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

1. Дано описание множества нулей отображения Р(х) в ,

/

случае вырождения оператора первой производной в решении.

2. Сформулирована и доказана теорема о неявной функции в вырожденном случае.

3. Введено понятие р -регулярности отображения Р и на его основе получено обобщение известней теоремы Люстерника -на вырожденный случай.

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

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

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

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

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

Апробация работы. Результаты работы докладывались:

1. На всесоюзных школах, конференциях и семинарах.

2. На семинаре Научного Совета по проблемам кибернетики АН УССР - "Математические метода в исследовании операций" в 1983 г.

3. На Советско-Болгарском семинаре по численным методам в 1987 г. в г. Варна.

4. На семинаре отдела Вычислительной математики при Президиуме АН СССР в 1986 г.

5. На научно-исследовательском семинаре кафедры исследования операций факультета ВМиК МГУ им. М.В.Ломоносова в 1Э86 г.

6. На научно-исследовательском семинаре ИПК АН СССР в 1987 г.

7. На научном семинаре кафедры общих проблем управление мехашпсо-математического факультета МГУ им. M. В. Ломоносова в 1985-1986 гг.

8. На Ломоносовских чтениях МГУ в 1982, 1983, 1984 гг.

9. На научном семинаре НИВЦ МГУ в 1985 г.

По результатам работы выпущен препринт Научного Совета по комплексной проблеме "Кибернетика" АН СССР в 1987 г.

Реализация. Методы, разработанные в диссертации использовались:

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

2. При разработке в ШК АН СССР пакета программ минимизации ГТКпт. Рас.к для персональных компьютеров типа ЕС-1841.

3. При разработке библиотеки оптимизации для Супер-ЭВМ в ИПК АН СССР.

Работа выполнена в рамках НИР ИПК АН СССР по теме "Математическое обеспечение Супер-ЭВМ, методы и алгоритмы для решения больших задач".

Результаты, изложенные в диссертации являются частью курса лекций "Математическое программирование", читаемого на факультете БМиК МГУ им. М.В.Ломоносова.

Структура и объем работы. Диссертация состоит их трех глав, введения и заключения.

В первой главе дается общее исследование вырожденных нелинейных отображений.

На основе результатов первой главы во второй главе проводится построение конструктивных схем для решения нелинейных уравнений вида (I). В третьей главе, на основе результатов первых двух глав, дается описание и схемы методов решения вырожденной задачи условной минимизации с ограничением типа' равенств.

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

СОДБРЕАНИЕ РАБОТЫ

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

Первая глава посвящена общему исследованию свойств решения уравнения (I). Дается описание структуры множества нулей отображения F0х-) - в вырожденном случае. Основополагающую роль играет введенное понятие р -регулярного отображения р в точке СС* и теорема I.I.I. На основе конструкций, заложенных в понятии р -ре1улярности и теоремы I.I.I проводится построение и обоснование численных методов решения операторных уравнений и задач оптимизации с особенностями. На основе этого понятия появилась возможность сформулировать содержательные условия оптимальности в вырожденных задачах.

Введем цредварительно некоторые обозначения. Пусть С'(1С) - множество отображении, имеющих в непрерывные производные до р -го порядка включительно, peSE, , ^, - множество положительных целых чисел. Г - оператор производной р -го порядка отображения Fi Х^ Y в точке х* . X, У- в> - пространства. Р(Х, Y) - пространство непрерывных полилинейных отображений степени р.действую-

щих из В -пространства X в В -пространство у ^(Х^ХЧХ.У) . - значение

полилинейного отображения F(P)(pc*) на наборе элементов

Ух,..., .поэтом

Оператор F(Pfoc*)[z] £ о£(Х,У) так ае как и F ЬС .

|W FСр)(эс*) = {хFCp)(x*)[xlP= ©}.

(Х.%) = <f(oc)+{y} f(pc)y ( где ^ _ дейст_

вие линейного функционала у€ У * на /^JC Л\(а*).= [осеXj F(OC) = FCx*)^),

ТР М [г ех| + га) £ >А(_х*)3Шсх\

СПХ) - { f € cfx) I III 'ос) - f 'См; 11 * L- \\cc-y ||P }.

Lin(M) - подпространство минимальной размерности содоржа-

^ щее множество /М £

Fi(3C) -¿-я стррка матрицы F(OC.) .

Определение.Будем говорить, что отображение F С

Fecp(x),

F^jpC^fyk-J^l, гдеЛ/V -В- пространства, является р -регулярным (p€3:L,) в точке ЗГ* , если для любых h € Лет. FCp\x.*) h*{€) выполнено соотношение

f(p>oc*)[hjp^x- Т. (4)

Сформулируем основной результат диссертации.

Теорема I.*' Пусть ){, Е> - пространства, 2/ - окрестность точки ос* , р - непрерывно-дифференцируемое по Фреше до р -го порядка включительно отображение 1А- в У • удовлетворяющее условию г ы

Г (зс*)= с, . (5)

Предположим, что р - р - регулярно в точке X* . Тогда

"ПМ(Х*)= Ке^ р<р)сх*)/ (6)

Эта теорема является обобщением известной теоремы Люстерника на вырожденный случай.

Во втором параграфе проводится исследование структуры отображения Р для вырождения вида

ч. Гл1 (V)

П Кег РСК)(0Сл) * {0} у

которое имеет принципиальное значение при построении достаточных условий оптимальности высших порядков для задач условной оптимизации вида (2) в регулярном, но выроязденном случае, т.е.; когда не выполнены достаточные условия экстремума 2-го порядка, а именно, существует элемент Ь б Кеч. такой, что

(8)

^Нумерация теорем автореферата отлична от нумерации диссертации.

где (эс.*у*) — точка, удовлетворяющая необходимым условиям экстремума

О)

Такого типа экстремальные задачи также будем называть вырожденными, поясняя при этом характер выровдения.Доказанная в этом параграфе теорема о р - касательном конусе позволяет получить оценки скорости сходимости методов типа штрафных функций, модифицированных функций Лагранжа и др. для задач нелинейного про1раммирования в вырожденном случае ( см. гл. III § 2 ).Основной результат второго параграфа содержится в следущей теореме.

Теорема 2. Цусть^у* В - пространства, U - окрестность точки Х.*~ , отображение Fi FC С X) , регулярно в точке jC* .Тогда

ЪММ = n tW F°°(x*) (Ю)

существуют такие ¡окрестность U'^U точки X.* .число

5>0 и отображение У—»-■ЗСОО множества в , что

f(t+x(?))= (п)

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

Теорема 3. Пусть выполнены условия теоремы I и

SUP IliF^LhTTlHK.iod)

WMl=i • (12)

Тогда существуют окрестность и'С 1С. точки Эс*~ . число Е>с и отображение множества Ы.' в 2С

такие, что ,

II хс?) ц ^ <Г- ц р с?)- р сX.*)у 6 г/!

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

В пятом параграфе на основе результатов, полученных в §§ 1-4, дается описание общего случая вырождения, когда

р'(эР'(эс*)щыР. (13)

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

Разложим пространство У в прямую сумму подпространств

где "У^ - подпространство минимальной размерности, содержащее множество рСг>С;::с*)-»Х1.=Л1Г)

Xг= (X© .. .©Уг-,■ Х-х) ;

Обозначим ^ (ос) = /\-FCx.) :Х~+Уг - Здесь

ортопроектор на

Определение. Будем говорить, что отображение из класса С ) является р -регулярным в точке ¿¡с*, если для лкхЗых /> « Л Кег Г'Сж") 4 ¿0} =

I К ГРЗ -г г-

¡г №.. Ж(14)__

В отличии от определения на с.8, здесь р(/<\/ЬсК-^Р-*-. Основные результаты, связанные с описанием общего случая вырождения, сформулированы в следующих двух теоремах.

Теорема 4. Пусть V ~ конечномерные евклидовы пространства, 11 - окрестность точки ос* , Я - непре-рквно-дифференцируемое до р - го порядка включительно отображение множества V. в У " Р ~ регулярно в точке

ОС*. Тогда

Р

Т4М(гс*)= ПКе*_1, (ос*).

1-Х } х

Теорема 5. Пусть выполнены условия предыдущей теоремы. Тогда существует окрестность и'с 11, точки ос* , число 8> С и отображение У—>■ Х^^ множества "Ы-' в^С такое, что

||*00|| « ^(И^ (5)11+ уеи'.

В диссертации теоремы 4 и 5 доказаны для В -пространств. В шестом параграфе первой главы рассматриваются условия

оптимальности высших порядков для абсолютно вырожденного случая р ^(ЭС.*) = 0 -> К= ±,Р~Л- , а также для регулярного случая, когда не выполняются достаточные условия экстремума 2-го порядка.

Пусть (Х*^*) точка Лагранжа, т.е. выполнено соотношение (9). Основной результат устанавливающий необходимые и достаточные условия оптимальности Р -го порядка сформулирован в следующей теореме.

Теорема 6. Пусть в задаче (2)^У - В> -пространства, ■) регулярно в точке ос* и

П Ке-иРсю(х")*{<0}, п Кеч (К)

К=1

Если ос £ ioС min {(2)} , то для любого элемента

к£ кЛ Кег :

либо

что

либо существует такое четное ^ ,

V __($)

Если же, кромеСтбгХт^в точке Яагранжа (эс* "

к € Кет, Р'Сэс») х КвиР"(х«-)

de)

(17)

(18)

и для всех ^ е{д.,р} существуют такие четные (за-

висящие от ), что

К € П ке^Ъс^Кехр^Ъс*), (19)

то

X*" € востьп{(2)]

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

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

В первом параграфе на основе понятия р - регулярности ГЗ

изучаются свойства методов тша Ньютона

,ЗСки = Хк-{р'СзсоР(Хк)

при решении вырожденных систем уравнений

р*(ро— ф , (21)

Р-Е^-^Е^ > где Ек. ~ конечномерное евклидово пространство размерности К. , отображение Р вырождено в решении ОС* > т.е. Тт Р'Сх.*)ФЕп • Показывается, что при наличии усиленного условия р -регулярности в решении ОС* , т.е., если существует число К > с :

«К,Ь€Егъди\=1,

в случае абсолютного вырождения =

юеет место оценка скорости сходимости метода (20):

где ® < Кл. < £ .

Существует большое число работ посвященных анализу скорости сходтости метода Ньютона в общем случае вырождения уравнения (I). В § I показывается, что даже в случае сущесг-вования обратного оператора в окрестности точки ОС *, сходимости может не быть. Это еще раз подтверждает необходимость создания, новых конструкций методов, учитывающих специфику вырожденных отображений для решения уравнений (I). Этому вопросу посвящен второй параграф.

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

решения вырожденных уравнений

F(jc)~<d, f'e^en. . <22>

Приведем главную конструктивную схему методов решения уравнений вида (22).

Схема. Имеется точка ¿С к . На К+1 -й итерации вычисляется Ьк и ЭСк+л. '»

F'C*K).hK = D, II Кк 1\=±, (23)

Хк+1= у F (Ре*} , (24)

Здесь Рк - ортопроектор на (X m F (ОС*.)) 7 hK6 F'CXk) . Причем, так как Кег р'С-ЗС*)* ((D) ,то не ограничивая общности, считаем разрешимым уравнение (23) при ЦккЦ=4-.

Пусть dimKe-u F'(Xk) = dim Ke^F'tx*) . Прежде, чем сформулировать теорему о сходимости введём понятие достаточного условия Р -регулярности отображения f в точке X*. Считаем, что f € ср*1(> fек^-еп. .

Определение. Будем говорить, что отображение f удовлетворяет достаточному условию р -регулярности в точке ОС* , если

1НкМ

К Ken-iiW) , ЦК 11=1 .

Отметим, что в случае Р=2. это условие означает ограниченность оператора {f'C*-*)* Р^ для всех

ib

К е Кеги РЧх») , II к 11 = 1. Пусть и£ (х*) = г эсе Е^ | II Х- х-И & Е} .

Основной результат о сходимости метода сформулирован в следующей теореме.

Теорема 7. Пусть /""£ с *(£п.) и в точке ¿С* выполнено достаточное условие 2-регулярности. Тогда существует такое, что при ¿/с(х.*) метод (23-24) сходится, причем имеет место оценка скорости сходимости

(25)

Бо втором параграфе приводится схема вида ( И к £ Кеч. Р(ХК))

Хк^ = Хк - (Г'СХк) + Р"СЭСк)11кТ-

для решения уравнения (22) и формулируются условия, гарантирующие геометрическую скорость сходимости этого метода:

Второй параграф заканчивается описанием процедуры решения уравнения (I) в случае К-ед. Р (X«) = .

Приведем схему решения уравнения р"0О=<3 в общем

случае, когда Ж/п Аел. Р (оск)=*= Жт /С-ел. р '(ос Пусть (хк)= (эсО Ц , I. = .

Считаем, что [хк)+ 0 . Обозначим через р/(хк) проекцию

на ((ог к) ,г= = £и | г =• £ ^

а через

Р (х*) матрицу Срх(х*),~у Гт&А, РьиМ,.-;?» (Хк)} , где ^.'р^Л*-' > (-Х-*-) - набор векторов

16

соответствующий любому максимальному набору линейно независимых векторов Fl(OC*)3 Fir, (ос*) . При выполнении достаточного условия 2-регулярностй в точке ЭС.*~ Еекторы Fi СХ-к.)-) ., 0ек-) ~ эт0 максимальный набор векторов, удовлетворяющих соотношению

/Оч>linoc^ic';

где J> (Хк)J L (X (Хк)^ ^) ~ это расстоя-

ние Ьт j^ (ре*.) до h (хкJ, i'uri; iV z) . Приведем схему метода решения уравнения FM-Ю в общем случае:

хк« = зск - {f 'coc^^p^f^ljb^f

а л ^ у»

где Рк и Рк ортопроекторы на1тг (Х^) и (imF'(x^)) Г А'

a h к 6 F (Хк), ЦЬк ||= 1 • Применение этой схемы также даст сходимость последовательности к решению ЭС* с квадратичной скоростью сходимости, аналогично теореме 7.

В третьем параграфе рассматривается модификация ускоренного метода Ньютона для решения вырожденных уравнений (I).

Четвертый параграф посвящен решению вырожденной задачи безусловной минимизации

u4, ОС6 Е п., (26)

когда Y= X*, Еи. - Здесь

Обосновывается применение градиентного метода для решения задачи (28), строящегося согласно схеме

ЗСк- о^УСЗСО, (2?)

со специальным выбором величины шага о/к . Доказывается сходимость и оценка скорости сходимости минимизирующей последовательности {ак} вида:

(28)

||Х„-ЭС*\| $ , те Ж.

Здесь ^€ С1>Р(ЕП) ^

, С*, Сг >0 - независимые конс-

танты.

Третья глава посвящена решению задачи условной оптимизации вида

Р(ос)= 4),

р : в предположениях вырожденнос-

ти решения ОС*" , т.е.

- либо' Егт,,

- либо существуют такие € /" » что

х';х(к*,г)сьзг=о7 (29)

где (ЭС*у*) - точка Лагранжа, т.е. выполнено соотношение (9) .

Как известно, одним из распространенных методов решения задачи условной минимизации является метод штрафных функций,

который заключается в безусловной минимизации функционала

Л (ас, с;= ifC*)+C-y~CxJ,C><P,

1 г- , , , ^ (ЗС)

yirx;= 21 1к(х)1 у

Основные свойства этого метода обосновываются при выполнении, так называемого условия у~ - мажорируемости допустимого множества.

Определение. Будем говорить, что ограничения -fi (эс)

1— 1,пх или f ~ мажорируемы в точке x ё){ ()

если существуют числа dl>j) , <5~>t0 такие, что при всех ос € u.s сх) справедливо неравенство

tTlQX l-fi(x.)l^ oL'jo(oc,X)r

i - L,m ^

или

iif(x) u*ot-j>(x,x)f;

В случае невырожденности, как это следует из теоремы Люстер-ника, будет иметь место 1-мажорируемость.

В первом параграфе показано, что в вырожденных задачах из условия р -регулярности следуем р -мажорируемость ограничений ^ (х) , i=l,m . Этот результат отражён в следующей теореме.

г* 1=44

Теорема 8. Пусть F 6 С (в. и f - /э-регулярна в точке ос* • Тогда отображение f - р -мажорируемо в точке ЗС*~ .

Второй параграф посвящен исследованию задачи (2) в вырожденном, но регулярном случае, т.е. f'(2c-*~)'eh — ern >а

IW %»хк (dc*y*) =* {€}.

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

^с-осмиказ;. (3D

при с + «=», к >0, е CktftnU M(JC,C.) ,ХеЕп.

В третьем параграфе цредлагается метод решения задачи (2) в нерегулярном случае, т.е.f когда Tm Em.

Обозначим'

Тк Ох.) = F (ос.) + Рк • F'(x)[ К кЗ } (32)

где Ьк 6 ken. F'(X Д h £ Ken. F'(x*), ||h|| = |1М1 = ±3 P> Рк ~ ортопроекторы на (1m F'Ct*")) и(Х(п F'(Xk))X соответственно. Считаем, что dim Кеч. F '(х к)=<i/tm Ке г f'(oc .Пусть

(ъу)=+ <У> % Ш>, z = (х, у).

Предположим, что' для любого

выполнено условие

KeA. {f'M +■ РхF'H-h} £ 1лп(Кл. Ft**) П (33)

п Ke-uPVix*)) _

Тогда для Х*€. 0<х.ти\(ц(эс)\{:(х.)^с} найдется такой, что

и задача (2)-(3) сводится к решению уравнения (34). Пусть Ьо € Кеа р'бОСо), IIЬо 11 = 1.

Схема. По точке строим .удовлетво-

ряющее условию

Кк € огд^ {ц Ьо- Ь 111 ¡1 Ьк || = 1 }

и переходим к по формуле

x I 9>к)т

Ко)

. (35)

Теореме 9. Пусть Г 6 С- п) • Для отображения Г выполнено условие 2-регулярности в точке X. * , условие (33)

Ь € Ке^ Ф'(Х*).

Тогда существует £>(0 такое, что при любом

последовательность (35) сходится к . причем справедли-

ва оценка

-к+1

(36)

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

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

Основные результаты диссертации состоят в следующем:

1. Разработана конструкция р -регулярности. На основе этого дано описание множества решений уравнений )= О для отображения р: ~у~ с нерегулярной структурой, т.е. 1т И, ХУ-В- пространства.

2. На основе понятия р -регулярности получено обобщение известной теоремы Люстерника на вырожденный случай, что имеет существенное значение в теории решения экстремальных задач с особенностями,

3. формулированы и доказаны достаточные условия оптимальности р -го порядка в случае вырожденности решения X* задач условной минимизации с ограничениями типа равенств.

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

Полученные результаты включены в курс лекций "Математическое программирование", читаемых на факультете Вычислительной математики и кибернетики МГУ.

Методы, разработанные в диссертации, использованы:

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

2. При разработке в ИПК АН СССР пакета программ минимизации Iflitvt Pack Для персональных компьютеров типа EC-I84I.

3. При разработке библиотеки оптимизации для Супер-ЗВМ в ИПК АН СССР.

Публикации по теме диссертации. Всего по теме диссертации опубликовано 32 работы. Основные результаты опубликованы в следующих статьях:

1. Третьяков A.A. Необходимые и достаточные условия оптимальности. р -го порядка. - М., КВМ и №?, В 2, 1985.

2. Третьяков A.A. Теорема о неявной функции в вырожденных задачах. - М., УМН, т.42, В.5, 1987.

3. Третьяков A.A. Две схемы нелинейного метода оптимизации в экстремальных задачах. - М., ЖВМ и И, В 7, 1984.

4. Третьяков A.A. Критерии регулярности множеств в задачах оптимизации. //Численный анализ на ФОРТРАНе. - Изд-во МГУ, 1980.

5. Третьяков A.A. О сходимости метода Ньютона в вырожденных задачах. //Оптимизация и управление. - М., Изд-во МГУ, 1983.

6. Третьяков A.A. Некоторые схемы методов решения вырожденных экстремальных задач. //Оптимизация и управление. - М., Изд-во МГУ, 1985.

7. Денисов Д.В., Третьяков A.A. Описание структуры.вырожденных функциональных систем и методы их решения. //Методы и алгоришы в численном анализе. - М., Изд-во МГУ, 1984.

8. Денисов Д.В.,- Карманов В.Г., Третьяков A.A. Ускоренный'метод Ньютона для решения функциональных уравнений. -ДАН СССР, т. 208,' 1985. '

9. Денисов Д.В., Третьяков A.A. Вырожденные экстремальные задачи. Условие оптимальности решения. //Исследование операций И АСУ. Je 24. - Киев, Изд-во КГУ, 1984.