Непрерывные методы минимизации с переменной метрикой тема автореферата и диссертации по математике, 01.01.07 ВАК РФ

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ им. М.В. Ломоносова

ФАКУЛЬТЕТ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ И КИБЕРНЕТИКИ

РГЗ од

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

(- П УДК 519.6.517.988.68:519.853.6

АМОЧКИНА ТАТЬЯНА ВЛАДИМИРОВНА НЕПРЕРЫВНЫЕ МЕТОДЫ МИНИМИЗАЦИИ С ПЕРЕМЕННОЙ МЕТРИКОЙ

01.01.07 — вычислительная математика

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

МОСКВА — 1997

Работа выполнена на кафедре математической физики факультета Вычислительной математики и кибернетики Московского государственного университета им. М.В. Ломоносова.

Научные руководители:

доктор физико-математических наук,

профессор ВАСИЛЬЕВ Ф.П.

доктор физико-математических наук, ведущий научный сотрудник АНТИПИН A.C.

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

доктор физико-математических наук,

профессор БОБЫЛЕВ H.A.

кандидат физико-математических наук, старший научный сотрудник ИЗМАЙЛОВ А.Ф.

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

Институт системных исследований РАН.

Защита диссертации состоится г. в 15.30 на заседании специали-

зированного совета Д.053.05.37 по математике при МГУ по адресу: 119899, Москва ГСП Воробьевы горы, МГУ, факультет вычислительной математики и кибернетики, ауд. 685. С диссертацией можно ознакомиться в библиотеке факультета ВМиК МГУ. Автореферат разослан" " 1997 г.

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

(УССшХ еи-моисеев

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Разработка методов решения экстремальных задач является одним из интенсивно развивающихся направлений вычислительной математики. Важным классом методов минимизации является класс непрерывных методов, в которых процесс минимизации описывается дифференциальными уравнениями. Интерес к непрерывным методам стимулируется, с одной стороны тем, что при исследовании сходимости траекторий непрерывных процессов к точке равповесия можно широко использовать развитый в теории дифференциальных уравпений аппарат, с другой стороны тем, что эти методы оставляют свободу при выборе методов численного интегрирования получающихся дифференциальных уравнений и определяют таким образом целый класс дискретных методов, которые не так просто обнаружить, оставаясь в рамках привычных представлений, павязавных итеративной оптимизацией. До сих пор в литературе много внимания уделялось непрерывным методам первого порядка, изучались также непрерывные методы проекции градиента второго, третьего и четвертого порядков. Здесь можно упомянуть работы В.И. Венеда, М.В. Рыбашова, Ю.Г. Евтушенко, В.Г. Жадана, Б.Т. Поляка, Н.А.Бобылева, С.К. Коровина, A.C. Антипина, М. Ковач, А. Недич и других.

Ряд хорошо известных непрерывных и итерационных методов минимизации основан на замечательном свойстве антиградиента: направление наибыстрейшего убывания целевой функции в точке совпадает с направлением аптиградиента в этой точке. Хорошо известны непрерывный градиентный метод первого порядка, метод "тяжелого шарика", описываемый дифференциальным уравнением второго порядка, непрерывный аналог метода Ньютона. A.C. Антипиным были впервые предложены непрерывные методы минимизации, содержащие оператор проектирования. Идеи построения непрерывных алгоритмов минимизации с оператором проектирования нашли свое продолжение и обобщение в трудах А. Недич: были разработаны непрерывные алгоритмы второго, третьего и четвертого порядков.

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

пространстве можно задать новое скалярное произведение и соответствующую ему метрику. Поэтому методы такого типа в литературе называются методами с переменной метрикой или методами с "растяжением пространства". То, что на этом пути можно добиться существенного ускорения сходимости, подтверждается, например, хорошо известным методом Ньютона, где в качестве матрицы. — параметра метода — берется матрица вторых производных целевой функции. Однако, метод Ньютона обычно применяют в тех случаях, когда вычисление матрицы вторых производных не представляет трудностей. Для решения задач минимизации существует также целый ряд квазиныотоповских методов, в которых матрица — параметр метода — выбирается близкой к матрице вторых производных. Сюда можно отнести, например, метод Девидона-Флетчера-Пауэлла, метод Стеффенсена и другие.

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

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

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

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

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

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

— научном семинаре кафедры оптимального управления факультета ВМиК МГУ под руководством проф. Васильева Ф.П.;

— научно-исследовательском семинаре кафедры математической физики факультета ВМиК МГУ под руководством проф. Денисова A.M.;

— IY Международной научной конференции "Многокритериальные и игровые задачи при неопределенности" в Орехово-Зуево (8-14 сентября 1996 г.)

Публикации. Основные результаты диссертации опубликованы в работах [1]-[5], перечисленных в конце автореферата.

Структура и объем работы. Диссертация состоит из введения, трех глав, двух приложений и списка литературы, включающего 82 наименования. Объем работы составляет 151 страницу машинописного текста.

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

В диссертации рассматривается задача минимизации

J(u) — inf, и е U, (1)

где U — заданное выпуклое замкнутое множество из евклидова пространства Е", функция J(u) выпукла и дифференцируема на Е". Предполагается, что

1. = mf J(u) > -оо, U, = {и е U | J(u) = J,} Ф 0. (2)

A.C. Антипиным и Ф.П. Васильевым впервые был предложен и исследован непрерывный метод проекции градиента с переменной метрикой, описываемый следующим дифференциальным уравнением; первого порядка ("О непрерывном методе минимизации с переменной метрикой". Известия ВУЗов. Математика, 1995, N 12(403), С. 3-9)

u'{t) + u(t) = P°{u[t)\u{t) - 7(i)CT1(u(t))J'(u(t))), t > 0, u(0) = «о, (3)

где и0 — какая-либо фиксированная точка из Еп, G(u) — для каждого и с Еп симметричная положительно определенная матрица, w — P^i-U\z) — проекция точки 2 на множество U в метрике G(u), определяемая условиями:

w € U, < G(u)(w - z),w - г >= mf < G(u)(t> - z),v - г >; (4)

VfzU

функция y(t) >0 — параметр метода.

В первой главе диссертации впервые предложен и исследован метод проекции градиента второго порядка с переменной метрикой, обобщающий метод (3)

ß(t)G-\u(t))u"(t) + u'(t)+u(t) =

= P®(u(i))(u(i) - y(t)G'l(u(t))J'(u(t))), t > 0, u(0) = «о, u'(0) = иг,

где щ,щ 6 E" — заданы, -у(t),ß(t) — параметры метода. Метод (5) в случае, когда G(u) = I — единичная матрица, изучался А. Недич ("Непрерывные и дискретные методы минимизации высокого порядка". Дисс... канд. физ.-матем. наук, МГУ им. М.В.Ломоносова, 1994.)

Следующая теорема дает достаточные условия сходимости метода (5). Теорема 1. Пусть

1)17 — выпуклое и замкнутое множество из Е"; функция J (и) выпукла, непрерывно дифференцируема на Е", и ее градиент удовлетворяет условию Липшица

И J'(u) - J'{v)II < L\\u- ид, £ L-const < +oo;

выполнено условие (2);

2) G(u) — симметричная положительно определенная матрица для каждого фиксированного и € Е", причем известно, что существует сильно выпуклая дважды дифференцируемая функция Ф(м) такая, что

G(u) = tf"(u), mj|u||2 << G(u)v,v >< M||v|(2 V u,v e E",

где Мит — постоянные, M > т > 0;

3) параметры 7(0) ß(t) метода (5) таковы, что

<y(t)eC[0,+oQ), ß(t) е C2[0,-foo),

ß'(t) < 0, ß"(t) > 0, 7l > 7(í) > То > 0, í > 0,

Km /3(í) = ß„ > 0,

Пусть и = u(t), t > 0 — траектория уравнения (5). Тогда существует точка urja е {/,, такая что

Шп(Hu"(Oll +11"'(Oll +||u(t) - «»И) =0,

+00

j (Ilü"(s)||2 + !|«'(s)||2 +/3"(s)||u(s) - Uoo||2)^ < +«,. 0

Техника, которая использовалась при доказательстве этой и других теорем, является развитием техники Антипина A.C., Васильева Ф.П., Недич А. из упомянутых выше работ.

Если функция J(u) сильно выпукла и функции 7(0, ßif) удовлетворяют более жестким требованиям, чем в теореме 1, го можно дать оценки скорости сходимости процессов (3), (5). Напомним, что функция J(u) называется сильно выпуклой, если существует постоянная ц > 0 такая, что

/(ац+( 1 - a)v) < a J [и) + (1 - a)J{v) - а(1 - а)||| и - t>||2,

при всех u,v с Е", 0 < а < 1. Тогда верны Теорема 2. Пусть

1) выполнены условия 1), 2) теоремы 1; функция J(u) сильно выпукла с константой сильной выпуклости ц > 0;

2) функция 7(t) и число р таковы, что

2d

О < р < 2тп, 0 < 7о < y(t) < t> 0.

L + fi

Пусть и = u(i), t > 0 — траектория уравнения (3). Тогда для любого щ б Е" выполнена оценка:

КО - М2 < ~ vtf(h(t))-\ t > О,

где h(t) = exp(fb(s)ds), b(s) = ^(1 - и, — решение задачи (1).

Теорема 3. Пусть

1) выполпены условия 1), 2) теоремы 1; функция J(u) сильно выпукла на Е" с константой сильной выпуклости /I > 0;

2) функции y(t),ß(t) и число р таковы, что

ß{t) е С2[0,+оо), /7(f) > 0, ß'(t) < 0, ß"(t) > 0, t > 0, lim ß{t) = ßoo>0,

t—*OQ

0 <p< f, 0 <70 <7(0 < fa,

M2 - 4a(t)ß(t) > 0, m-p- ß(t) - 2ß(t)f(t) > 0,

ß"(t) + 2/3'(t) + f'(t)ß(t) > 0, t> 0,

где

g(t) = 2T(tHl- ffl.

Пусть и = u(t), t > 0 — траектория уравнения (5). Тогда верна оценка

- ".II2 < С(А(0)-1> « > 0,

i

где h(t) — exp (f f(s)ds), С — постоянная, о

Как известно, задача (1) неустойчива к возмущениям исходных данных J(u), U и для ее решения нужно применять методы регуляризации. Следуя работам А.Н. Тихонова, Ф.П. Васильева, A.B. Вакушияского, A.B. Гончарского и других, в работе проведена регуляризация вышеупомянутых методов. Методы регуляризации в работе рассмотрены для задачи

J{u) - Inf, u б U, ^

и = {u е ий I Si (и) < 0, i = 17?, gt(u) = 0, % = ¡ + l,s}, где U0 — заданное выпуклое замкнутое множество из некоторого гильбертова пространства Н, функции J (и), <?;(«) определены и дифференцируемы по Фреше на всем пространстве Н.

В первой главе исследованы также методы регуляризации, основанные на методах (3), (5) в сочетании с методом штрафных функций. Для учета ограничений типа равенств и неравенств из (6) будем пользоваться простейшей штрафной функцией:

Д«) = £№))', U е Я, р > 1, (7)

¡=i

где gf = тах{^,-,0}, г — T^J, =| д, |, i = l+l,s. При сделанных предположениях функция Р(и) из (7) дифференцируема по Фрепге па Н. Предположим, что вместо точных значений градиентов J'(u),P(u) нам известны их приближения J'(u, i),.T"(u, i), зависящие от параметра t > 0. Регуляризовашше варианты непрерывных методов (3), (5), соответственно, имеют вид:

«'(О + «СО = ^{"(<))К0 - l(^-\u(t))Tt{u{tl t)), t > О, u(0) = «о, (8)

¡3{t)G-\u{t))v!'{t) + u'(i) + u(f) =

= <u(,)) WO - 7(t)G->(u(t))n(u(t), 0), « 2 0. (9)

u(0) = u0, u'(0) = uj,

где гга, Wi — заданные точки из Н; T((u,t) = J'{u,t) + A(t)P(u,t) + a(t)u, и e Я, t > 0 — приближение градиента функции Тихонова T(u,t) = J (и) + A(t)P(u) -f ~a(i)||«||2, и e H, t > 0; A{t),y(t),P{t),a(t) — параметры методов. В диссертации доказаны теоремы сходимости методов (8), (9). Приведем одну из теорем. Теорема 4. Пусть выполнены условия:

1) С/ — выпуклое замкнутое множество из гильбертова пространства Я, функции J(u),gi(u),... ,дя(и) выпуклы и дифференцируемы по Фреше на Я; градиенты функций J(u),P(u) удовлетворяют условию Липшица

max(|| J'(u) - J»||, ||Р» - P»ll) < L\\u - и|| V u,v 6 Я;

i .... функция Лаграшка L(u,Л) = J(u) + Y, Kg,(и), ue U0, A e Ло ={\e E': А; > 0,i = l,i)

имеет седловую точку (и,, Л") е Ua х Л0, го есть L(u„, А) < L(u,, А*) < L(u, А*), и е Ue, А е

Л0;

2) приближения J'(u, i), f (и, t) градиентов P'(u) непрерывны по и при всех i > 0, измеримы по t при всех и с Н и

maxfll J'{u,t)~ /'(^il.ll^C".4)- ■Р'С«)!!) < «(*)(! +N!), «е Я, i > 0; (10)

3) оператор G(u) — линейный самосопряженный положительно определенный для каждого и а Н\ существует дважды дифферецируемая сильно выпуклая функция $(«) такая, что

Ф"(и) = G(u). m||v||2 << G{u)v,v >< Л%||2 V u,v е Я, 8

M > m > О — постоянные;

4) параметры <*(£),ß(t),S(t),7(4), A(t) метода (9) таковы, что

a(t),/3(t),-y(t) 6 С2[0,-Н»), 6(t) e С[0,-н»), A{t) е СЧ0,+~), a(t) > 0, 7(t) > 0, A(t) > 0, ß(t) > О, q'(í) < 0, ß'(t) < 0, i(t) < 0, A'(t) > О,

A(t) - вогнутая функция, a"(í) > 0, ß"(t) > 0, y'(t) > О, i > О, Hm (a(í) + 7 (t) + 6(t) +■ (¿(í))"1 + y(t)A(t)) = 0, lim (ЖМИ + g'W+^'W- + . УС) Л - л

Iim a(t)Ax!^ = +CO, lim /J(í) = /?«,, О < < m.

í—>00 í—»00

Пусть и = u(t), t > О — решение задачи (9). Тогда

lim (НО - + И"'(«)11 +1!«"(01!) = 0. (И)

где и» б U„ И и. I) = ínf ||tt|| — нормальное решение задачи (6), причем сходимость в (11) «б

равномерная относительно выбора J'(u,t),P'{u,t) из (10).

В теореме 4 предполагалось, что значения градиентов J'(u),P'(u) в любой фиксированной точке « g Я может быть вычислено с любой наперед заданной точностью 6(t) в смысле неравенства (10). Одпако, в практических задачах исходные данные чаще всего задаются с погрешностью, остающейся больше некоторого фиксированного положительного числа. В рассматриваемой задаче (6), более реальным, чем (10) представляется следующее условие: при каждом фиксированном u е Я вместо точною значения J'(u),P'(u) могут быть вычислены их приближения J'6(u),PÍ(u) такие, что

maxflUK«) - J'(«)||,ИЯ(«0 - /"(«Oll) < ¿(I + B«l|), (12)

при всех м б Я, где S > 0 — известное число. Тогда процесс (9) можно заменить следующим процессом

ß(t)G-1(u(t))u"(t) + u'(t) + u(t) =

= P%"W)(u(t) - 7(i)(J's(u(t)) + A(t)Pl(u{t)) + a(i)«(0)). f * Í13)

u(0) = щ, u'(0) = щ,

где параметры a(t), ß(t), 7(f), S(t),A(t) зафиксированное зависят от S > 0 из (12), причем при каждом фиксированном уровне погрешности 5,0 < 6 < ¿(0), процесс (13) нужно продолжать до момента t — t(S), определяемого из условия

Щ = sup{i : 6(s) > S, 0 < а < t}. (14)

Обоснованием сформулированного правила останова (14) процесса (13) служит

Теорема 5. Пусть выполнены все условия теоремы 4, кроме условия (10), приближения J's(u),F6(u) градиентов J'(u),P'(u) удовлетворяют условию (12). Пусть u(t),0 < t < t(ê) — траектория процесса (13), где момент t(S) определен согласно правилу (14). Тогда

Hmol!u(i(i)) - и,|| =0.

Из этой теоремы следует, что оператор Re, который каждому набору {J't{v.),P'6(u),6) из (12) ставит в соответствие точку и(6) = u(t(6)) , определяемую методом (13), (14), является регуляризирующим оператором.

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

J(u) inf, и е U = {u е С/о : л(и) < 0, г = 17}, (15)

где иа — заданное выпуклое замкнутое множество из евклидова пространства Еп\ функции J(u),&(u) выпуклы и дифференцируемы на Еп. Непрерывные методы линеаризации первого и второго порядков для задачи (15), соответственно, имеют вид:

«'(*) + u(t) = - 7(î)G-1(u(î))/'(«(<))). t * °> "(0) = «o, (16)

,e(t)G~l{u{t))u"(t) + u'(t) + u(t) =

= ~ l(t)G-\u(t))J'(u(t))), t > 0, (17)

u(0) = u0, v'(0) = «i,

где

S(u) ={zzU0\ gi(u)+ < si(u), z — и >< 0, i — TJ], (18)

щ,и1 заданные точки из E"\ 7(t),/?(t) — параметры методов.

Заметим, что в методах (3), (5) в каждый момент времени, кроме выбора параметров f(t),ft(t) нужно еще проектировать точку на множество U или, иначе говоря, решать задачу минимизации (4), которая для произвольного множества ¡7 не всегда просто решается. Поэтому методами проекции градиента обычно пользуются в тех случаях, когда задача проектирования точки решается просто и в явном виде (например, когда множество U представляет собой параллелепипед, гиперплоскость, полупространство или положительный октант). В отличие от непрерывных методов проекции градиента с переменной метрикой (3), (5) в методах (1б)-(18) в случае, если Uq — многогранное множество, задача проектирования превращается в стандартную задачу квадратичного программирования, которая может быть решена за конечное число шагов. Теорема 6. Пусть

1) Uo — выпуклое замкнутое множество из Е"; выполнены условие (2), условие Слейте ра

3 «с е U0, g¡(uc) < 0, ¿ = 1,...,/;

функции J{n),gi(u),.. .,gi(u) выпуклы, непрерывно дифференцируемы на Е'\ и их градиенты удовлетворяют условию Липшица

IlíS («) - 5i(»)ll < ¿(ll « - «II, «' = I, ■ ■ ■, l, V и, v с Е";

выполнено условие 2) теоремы 1;

2) фупкция 7(t) такова, что

T(Í) б с[0,+оо), О < ъ < 7(<) < 7!, т - 7(í) + É A?f ) > с > 0, í > О,

где AJ,..., А* — седяовые множителя функции Лагранжа задачи (15).

Пусть и — u(t), t > 0 — решение задачи (16). Тогда для любого начального приближения «о б Еп найдется точка uM е U, такая, что

-гоо

J ||и'(<)1|2(Й < +оо,

О

Iim(||u(¿) - ««,11 + ||u'(í)¡{) = 0.

I—*oo

В случае, когда вместо точных значений функций д,(и) и градиентов g[(u),J'(u) нам известны их приближения g¡(u,t),g[(v,,t), J'(u,t),u е Н, зависящие от параметра t > О, для решения задачи (15) можно использовать следующие регуляризоваиные варианты методов (16)-(18):

u'(t) + u(t) = P^Ht) - 7{t)G->(u{t))re(u(t), *)),*> O, (ig)

и(0) = u0,

^(*)G-1(u(t))«"(*) + u'(t) + «(*) =

= - T(t)G-4u(t))Ts(u(t),t)), t > O, (20)

«(0) = щ, u'(0) = «x,

где

S(«,i) = {íe U0\ 9i{u,t)+ < g[(u,t),z - u>< í(í)(H-||u||2), ¿=1,...,/); (21)

щ,щ — заданные точки из Н\ T¡(u,t) = t) -f- a(t)u — приближение градиента функции Тихонова T{u,t) = J(u) -(- |a(í)||u|j2, и e H, зависящей от параметра i > 0; a(í),7(¿),0(t), /?(<), t >0 — параметры методов.

В работе исследовано поведение решений задач Коши (19)- (21) при t -> +00 и показано, что методы (19)- (21) обладают регуляризирующими свойствами, построен регуля-ризирующий оператор.

В третьей главе диссертации предлагаются алгоритмы, основанные на идее проксимальных методов. Проксимальные методы первого и второго порядков с переменной метрикой предназначены для решения задачи (1) с выпуклой, но, возможно недифференци-руемой функцией J (и). Вышеупомянутые методы описываются следующими дифференциальными уравнениями:

u'(t) + tt(t) =argmb{|||!/- иЭДцед+тЮА»)}. f £ О,

и(0) = и0 € Н,

/3(0 G-^u^KW + u'(t) + 40 =

= argmmilllj/ - u(i)||^.W) + 7(*)J(lf)}, t > 0, (23)

u(0) = «о, ti'(0) = uj, щ,и! e H, где 7(i),/3(i) — параметры методов.

В работе исследована сходимость методов (22), (23). Приведем одну из теорем сходимости.

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

1) U — выпуклое замкнутое множество из Е"\ функция J(u) выпукла и полунепрерывна снизу на U; выполнено условие (2);

2) квадратная матрица G(u) п - то порядка определена при каждом « е Еп, симметрична, причем существует такая сильно выпуклая дважды дифференцируемая функция Ф(м), что

Ф"(и) = G(u), m||u||2 << G(v)u,u >< M\\uf, V u,v e E";

3) параметры 7(0,/?(0 метода (23) таковы, что

0 < 7o < 7(0 < 7i;

/3(f) > 0, /3'(0 < 0,/Э"(0 > 0, vt> 0,

Urn/3(0 = Д», ()</?„< те;

4) траектория it = u(0 задачи Коши (23) определена при всех t > 0.

Тогда

Ijm(||u(<) - u,»!! + ||u'(f)H + ||«и(0й) = 0.

-boo

/ (II«"(Oil2 +1!«'(Oil2 +/3"(0Ni) - «coll2)dt < +00,

0

где «оо — некоторая точка из V-*.

Для решения задачи (6) с неточными исходными данными в работе предложены ре-"уляризовашше варианты методов (22), (23), имеющие вид:

U'(i) + M(i) = argmin{||!/- и(011сМ())+7(0Гб(у,0}. * > О,

и(0) = «о е Н,

(24)

/9(i)G-1(u(t))«,,(t) + «'(i) + «(*) =

= argiam{№- «Wllcw«))^ °>

(25)

и(0) = и0) u'(0) = Iii, Щ, Щ 6 Я,

где — J(y,t) + A(t)P(y,t) + ±a(t)\\y\\2 — приближение функции Тихонова Т(у,{) =

= У(г/) + А^)Р(у) + |а(г)||у\\2. Исследована сходимость методов (24), (25), построен регу-пяризирующий оператор.

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

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

3) предложены непрерывные проксимальные методы первого и второго порядков с ¡временной метрикой, исследована их сходимость;

4) проведена регуляризация всех предложенных методов и на их основе построены зегуляризирующне операторы.

Проведены вычислительные эксперименты, показывающие эффективность предложенных методов.

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

1. Амочкина Т.В., Антипин A.C., Васильев Ф.П. Регуляризованный непрерывный метод минимизации с переменной метрикой при неточно заданных исходных данных // Вестн. Моск. ун-та, Сер. 15, Вычисл. матем. и киберн. 1996, N 4, с. 5-11.

2. Амочкина Т.В. Непрерывный метод второго порядка с переменной метрикой // Ж. вычисл. матем. и матем. физ., 1997, N 10, с. 1174-1182.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ ДИССЕРТАЦИИ

3. Амочкияа Т.В. Непрерывный метод линеаризации второго порядка с переменной метрикой // Вестн. Моск. ун-та, Сер. 15, Вычисл. матем. и киберн., N 3, 1997, с. 9-12.

4. Амочкина Т.В., Антипин A.C., Васильев Ф.П. Непрерывный метод линеаризации с переменной метрикой для задач выпуклого программирования // Ж. вычисл. матем. и магем. физ., 1997, N 12, с. 1-8.

5. Амочкина Т.В., Антипин A.C., Васильев Ф.П. Непрерывный регуляризованный проксимальный метод минимизации с переменной метрикой. Обратные задачи естествознания: Сборник под ред. Д.П. Костомарова, В.И. Дмитриева, М.: Изд. Моск. у-та, 1997, с. 39-48.