Обобщенный приведенный метод Ньютона

Панферов, Семен Валерьевич

Обобщенный приведенный метод Ньютона тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

Панферов, Семен Валерьевич АВТОР

кандидата физико-математических наук УЧЕНАЯ СТЕПЕНЬ

Москва МЕСТО ЗАЩИТЫ

2005 ГОД ЗАЩИТЫ

01.01.09 КОД ВАК РФ

Диссертация по математике на тему «Обобщенный приведенный метод Ньютона»

Автореферат диссертации на тему "Обобщенный приведенный метод Ньютона"

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

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

Панфёров Семён Валерьевич ОБОБЩЁННЫЙ ПРИВЕДЁННЫЙ МЕТОД НЬЮТОНА

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

Авт ореферат диссертации на соискание учёной степени кандидата физико-математических наук

Москва - 2005 Н

Работа выполнена на кафедре исследования операций факультета ВМиК МГУ им. М.В.Ломоносова.

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

доктор физико-математических наук, профессор Новикова Наталья Михайловна.

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

доктор физико-математических наук, профессор Васильев Фёдор Павлович,

доктор физико-математических наук Попов Николай Михайлович.

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

Вычислительный центр им. А.А.Дородницына Российской академии наук.

Защита диссертации состоится __

2005 г. в // час. мин. на заседании диссертационного совета Д501.001.44 в Московском государственном университете им. М.В.Ломоносова по адресу: 119992, ГСП-2, Москва, Ленинские горы, МГУ, 2-й учебный корпус, факультет ВМиК, аудитория 685.

С диссертацией можно ознакомиться в библиотеке факультета ВМиК МГУ. ^

Автореферат разослан 2005 г.

Учёный секретарь диссертационного совета,

профессор Н. П. Трифонов

№06-Г

3_10№66

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

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

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

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

Основными задачами работы являются

- обобщение идеи метода приведённого градиента для построения алгоритмов второго порядка в задаче с ограничениями-равенствами;

- исследование дифференциальных свойств приведённой относительно ограничений целевой функции задачи;

- теоретическое обоснование сходимости алгоритма.

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

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

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

В рамках разработанного общего подхода построен метод второго порядка (называемый в работе обобщённым приведённым методом Ньютона). Проведено теоретическое исследование дифференциальных свойств приведённой функции цели. На основе результатов этих исследований получено теоретическое обоснование сходимости приведённого метода Ньютона.

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

Апробация работы. Основные результаты диссертации докладывались на научных семинарах МГУ им. М.В.Ломоносова, ВЦ РАН, на конференции «Ломоносовские чтения», Москва, 2003 г.

Публикации. Основное содержание диссертации отражено в 3 научных работах [1-3].

Структура и объём работы. Основной текст диссертации состоит из введения, 3 глав, заключения, и занимает 109 страниц. Кроме того, в работе имеется список литературы из 61 названия.

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

Рассмотрим задачу

f(x) min,

х G X = {х € Rn: 9i{x) = 0, г = 1,...,т} .

Будем считать, что функции f(x) и gi(x) (i = 1,2,...,m) дважды непрерывно дифференцируемы на множестве X, удовлетворяют условию Липшица и для всех х € X векторы Vgt(x) (г = 1,2,..., т) линейно независимы — условие регулярности.

Целью работы является построение алгоритма, позволяющего применить метод Ньютона решения задачи безусловной оптимизации в решении задачи (1) с ограничениями типа равенства.

Пусть е = (ei,ег, -. ■ ,еп) — ортонормированный базис пространства R". Через I = («ь ¿2> ■.., in-m) обозначим набор индексов ii,i2,... ,in-m таких, что 1 ^ ¿х < гг < ...гга_т ^ п. Через

= {I = {чЛъ, ■ ■ ■ Лп-m)- 1 < Ч < Ч < ■■■in-m <

обозначим множество всех таких наборов.

Введём

Е(1) = 1лп(е»г, ei2,..., ein_m) -

подпространство в Rn, образованное базисными векторами е^, &i2,. ■ ■, е^ ■

Будем считать, что функции f(x) и дг(х) (г = 1,2,...,ш), равно как и их производные, вычисляются как функции аргументов, разложенных по базису е.

Суть алгоритма обобщённого приведённого метода Ньютона состоит в следующем.

Рассмотрим к-ю итерацию алгоритма.

На первом этапе строится касательное подпространство N(хк) размерности n — m. к множеству ограничений и выбирается координатное подпространство Е(1) той же размерности п — т.

Через E(I)1- обозначим ортогональное дополнение к Е(1).

Аналогично алгоритмам с исключением переменных координат, происходит разбиение переменной хк на пару переменных {ук,гк) следующим образом:

хк = ук + гк, укеЕ{1)±, гкеЕ{1),

функция ук = <р(гк) определяется как решение системы нелинейных уравнений

9»(У*,**) = 0 (г = 1,2,... ,т).

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

ад = /(*>(*),*).

Таким образом, задача (1) сводится к задаче безусловной оптимизации

(2)

2 6 К"""*

При переходе от задачи (1) к задаче (2) мы использовали достаточные условия существования дифференцируемой неявной функции у = ч>{г).

На втором этапе происходит сдвиг по методу Ньютона в координатном подпространстве Е(1):

при этом проверяется условие релаксации

< F(гfc).

Далее, решая уравнение ук+г = <р(гк+1), например, модифицированным методом Ньютона, получаем следующую допустимую точку

Хк+1 = ук+1 + гк+1.

Обоснование замены касательной плоскости координатной плоскостью той же размерности приводится в главе I.

В §1.1 вводится определение и устанавливаются представления матрицы оператора ортогонального проектирования.

Рассмотрим пространство Rn, и пусть М С Kn: dimM = т, т < п. Оператор Р^ такой, что для любого х 6 Rn выполнено

1) PifX € М,

2) х- Р±х € М\

называется оператором ортогонального проектирования.

Через 0(т х n) = (Oy) (i = 1,2,...,m,j = 1,2,...,п) обозначим нулевую матрицу размера тп х п. Для единичной матрицы порядка т будем использовать обозначение

— (¿ (;:«:::)

Пусть h = {hi, h2,..., hm, /im+i,..., /in} — ортонормирован-ный базис в Rn. Обозначим через

Я = Н(п х тп) = (Ль..., Л™), Я = Н(п х (n - rn)) = (Лщ+i,..., hn).

матрицы, столбцами которых являются координаты векторов h в базисе е. Отметим некоторые свойства этих матриц.

1) ЯТЯ = I(m х тп),

2) ЯТЯ = 0(mx (п~т)),

3) ЯЯТ + Я ЯТ = f (п х п),

4) = ЯЯТ. Пусть

h- (hi,h2,--.,hm), d= {di,d2,-..,dm),

Я = H(n х m), Z? = D(n x m),

тогда для матрицы Грама пары (h, d)

((hi,di) ... {hi,dm)\ .......................

{hm,di) ... {hm, dm) J

выполнено G(h,d) = HrD.

Пусть МЪМ2 С Rn — линейные подпространства, dim Mi = = dimM2 = m, a d и h — ортонормированные базисы Mi и Мг соответственно. Обозначим через Рщ{М\) оператор ортогонального проектирования с Mi на Мг, тогда

Pii2(M1) = G(h,d} = G(d,h)T.

В §1.2 вводится существенное для работы понятие угла между пространствами одинаковой размерности и исследуются его свойства.

Обозначим через Si единичную сферу в Мп:

5i = {ж € Rn: ||®|| = 1}.

Через 5х(М) обозначим пересечение единичной сферы S\ с подпространством М С Rn.

Определение. Пусть М\ и Mi — подпространства в Rn размерности т, т < п. Углом между Mi и Mi назовём величину

ang(Mi,M2) = arccos min P^2(Mi)x

iGSi(Afi)

Отметим простые свойства угла между подпространствами.

1) Если т = 1, то ang(Mi, Мг) — не тупой угол между пересекающимися прямыми.

2) Если rn = 2, то ang(Mi, Мг) совпадает с определением не тупого линейного угла двугранного угла между плоскостями.

3) Справедливо равенство ang(Mj, М2) = ang(M2,Mi).

4) Справедливо равенство ang(Mx, М2) = ang(M|L,M2L).

В §1.2 получено представление косинуса угла между подпространствами через сингулярные числа матрицы Грама систем базисных векторов подпространств.

cosang(MbM2) = Pmia(G(M)),

где Pmin — минимальное сингулярное число матрицы G(h,d), причём если Mi + М^ = Мп, то

cosang (МЪМ2) = ЦС^Л)"1!!-1.

В §1.3 устанавливается один из основных результатов работы — получение нетривиальной нижней оценки угла между касательной плоскостью N(xk) и координатной Е{1) в случае

dimiV(xfe) = dim £(7).

Ответ на вопрос, каким может оказаться угол в худшем случае расположения N(xk), даётся значением следующего макси-мина

Нам будет удобно искать не значение угла, а значение его косинуса.

Отметим, что оценка величины cos 7* является общей характеристикой евклидова пространства и зависит только отпит.

Теорема 1.3.1. Пусть М С R", dim М = т,(еi, е2,..., еге) — ортонормированный базис пространства Rn. Тогда найдётся координатное пространство

Е{1) = Lin(eil,ei2,...,eiin)

такое, что

cosang (M,E(I)) ^

л/С^'

Применительно к задаче (1) теорема формулируется так: Для касательного подпространства N(xk) размерности п — т найдётся координатное подпространство Е(1) той же размерности п — т такое, что

cosang(N(xk),E(I)) > - JL=.

vCn

В главе II диссертации установлены дифференциальные свойства приведённой целевой функции F(z) = f(<p(z),z) задачи

F(z) —> min г е Rn~m

и получены оценки норм её градиента и гессиана.

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

вГ1(уо) = {у- ИУ-уоИП},

bt2{zq) = {z: ||z - zq\\ < г2} , Щуо,2о) = {(y,z): \\у-уо\\ < т\, \\z — zo||

Пусть функция g(y,z) непрерывно дифференцируема на множестве П(уо, zq)- Пусть выполнены следующие условия: существуют Li,L2,Lz = const > 0, такие что

1) ¡(^(Уо^о))-1 | ^ L\,

2) Уz е Br2(zo) | фо, z) - д'у(уо, г0)|| < Ь2{\\у - и>|| + 11* - *ь||),

3) Vz е Вфо) | g(yo,z)\\ ^ и \\z - z01|. Тогда Vz е Br(zo), где

. ( 4£i ¿2 \

существует единственное решение у = ip(z) уравнения g(y,z)= 0, уеЩуо),

где

7Г=т1п(Г1'21к(гт&)/)'

дифференцируемое в точке го-1

Для получения решения у = <р(г) уравнения д(у, г) — 0 применим метод Ньютона:

Ч>п+\&) = <рп(г) - ^(уо^оУ^^п^г),

<рЛг) = Уо € Вг(уо)-Введём функцию Лагранжа задачи (1): £(х,А) = /(х) + А тд(х),

обозначим через

УД®, А ) = У/(х) + АтУр(х)

У2Ь(х, А) = У2/(х) + АтУ2<?(х) её градиент и гессиан соответственно. Обозначим

Р(х,(Я,Я)) = ЯТ -ЯТУ5(х)т((Уд(х)Я)-1)ТЯт.

В §2.1 получены формулы для вычисления градиента и гессиана функции /(г):

Пусть функции /(х) и дг(х) дважды непрерывно дифференцируемы на X, У/(х) удовлетворяет условию Липшица, векторы У<7((х) (г = 1,2,... ,т) линейно независимы. Тогда для любого г 6 ВГ2(хо)

Уад = Р(х,(Я,Я))У/(х), У2^) = Р(х,(Я,Я))У2Ь(х,А)Р(х,(Я,Я))Т,

где х = у + г, у = <р(г).

1см. В. А. Треногин, «Функциональный анализ» — М.: Физматлит, 2002

В §2.2 исследованы дифференциальные свойства приведённой целевой функции.

Точку хо € X будем называть (¿-отделённой по разбиению М1М2, Мг + М2 = Кп, если

^(хоЩ <

Пусть точка хо € X ш-отделена по разбиению К" = Мх + М2,

хо = Уо + 20, уо € Мь 20 € М2,

тогда 31^1 и К2 > 0: У г, г', г" 6 ВГ2(го) выполнено 1)

2) ЦУ^(г') - У^ОН < #2 -

На основании результатов параграфов §2.1 и §2.2, в параграфе §2.3 получены равномерные по углу между касательным и координатным пространствами оценки норм градиента и гессиана приведённой целевой функции.

При выполнении перечисленных выше ограничений на функции /(х) и дг(х) (г = 1,2,..., т) справедливы неравенства

11 " с0827* рпп^цх^)

где ртах и рт1П — наибольшее и наименьшее сингулярные числа матрицы вторых производных функции Лагранжа задачи (1).

В главе III диссертации описан алгоритм и доказана сходимость обобщённого приведённого метода Ньютона. В §3.1 описан алгоритм обобщённого приведённого метода Ньютона.

1) Пусть на &-й итерации метода получена точка

хкеХ: ||У0(х*)|| ^ 6.

2) Проверяем регулярность точки хк. При отсутствии регулярности — остановка работы метода в точке хк.

3) 3.1. Строим касательное подпространство N(xk) к множеству ограничений.

3.2. Выбираем координатное подпространство Е{1) таким, что 0 < ang (N(xk), E(I)) < f.

4) Вычисляем VF(zfc), (V2F(zk))~l ддя xk=yk+zk, z € E{I).

5) Вычисляем hk = (S72F{zk))~1VF(zk).

6) zk+1 — zk+hk~ шаг метода Ньютона в подпространстве E(J).

7) Проверяем F(zk+l) < F(zk).

8) Решая систему д(у, zk+l) = 0, находим ук+1.

9) Получаем следующую точку хк+1 = yk+l 4- zk+1.

В §3.2 исследуется сходимость обобщённого приведённого метода Ньютона.

Точка х* 6 X задачи (1) называется Морс-регулярной, если

1) точка х* регулярна и ЗА*: VL(x*, А*) = О,

2) существуют п — тп линейно независимых векторов si,s2,... ..., «n-m таких, что

VF(x*)si = 0 (г = 1,2,...,n-m) и (VL(x*, X*)si, Si) ф 0.

Условие Морс-регулярности эквивалентно условию невырожденности спроектированной матрицы Гессе функции Лагранжа. Таким образом, условие Морс-регулярности стационарной точки является обобщением условия невырожденности экстремума задачи (1).

Теорема 3.2.1. Если последовательность определяется алгоритмом обобщённого приведённого метода Ньютона, и каждая стационарная точка функции Лагранжа Морс-регулярна, то найдётся А* 6 R такое, что последовательность {xfc} сходится к точке х*, в которой

VL(x*, А) = 0

и найдётся q G (0,1) такое, что

f(xk+1)-f(x*)^q(f(xk)-f(x*)).

Доказательство теоремы 3.2.1 опирается на результат теоремы 1.3.1 о строгой отделённости от | угла между N(xk) и Е{1).

Сравнивая предложенный метод, например, с методом множителей Лагранжа, сводящим решение задачи (1) к решению системы нелинейных уравнений

dL -п gt(x) - 0.

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

F(z) —* min, z € Rn_m

меньшей размерности.

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

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

В заключении сформулированы основные результаты работы.

1. Разработан унифицированный подход к конструированию численных методов решения задач условной оптимизации, предполагающий последовательное исключение групп переменных в исходной задаче и применения в решении получающейся задачи безусловной оптимизации с «приведённой» функцией цели методов безусловной оптимизации.

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

3. Построен и обоснован новый метод решения задач условной оптимизации — обобщённый приведённый метод Ньютона.

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

1. С.В.Панфёров, «Гарантированная оценка угла между касательной и координатной плоскостью» — Сборник «Прикладная математика и информатика», №8, с. 154-158.

2. С.В.Панфёров, «Алгоритм обобщённого приведённого метода Ньютона» — Электронный журнал «Исследовано в России», N«8, 2004, с. 22-27.

3. С.В.Панфёров, «Дифференциальные свойства приведённой целевой функции» — Электронный журнал «Исследовано в России», №4, 2005, с. 22-27.

»2053*

РНБ Русский фонд

2006-4 20604

Напечатано с готового оригинал-макета

Издательство ООО "МАКС Пресс" Лицензия ИДИ 00510 от 01.12.99 г. Подписано к печати 23.09.2005 г. Формат 60x90 1/16. Уел печл. 1,0. Тираж 100 экз. Заказ 565. Теп. 939-3890. Тел./факс 939-3891. 119992, ГСП-2, Москва, Ленинские горы, МГУ им. М.В. Ломоносова, 2-й учебный корпус, 627 к.

Содержание диссертации автор исследовательской работы: кандидата физико-математических наук, Панферов, Семен Валерьевич

1 Угол между подпространствами одинаковой размерности

§1.1 Операторы проектирования.

§1.2 Свойства угла между подпространствами одинаковой размерности.

§1.3 Оценка угла между подпространствами одинаковой размерности.

2 Приведенная целевая функция задачи с ограничениями типа равенства

§2.1 Дифференциальные свойства приведенной целевой функции.

§2.2 Вычисление градиента и гессиана приведенной целевой функции.

§2.3 Оценки норм градиента и гессиана приведенной целевой функции.

3 Обобщенный приведенный метод Ньютона

§3.1 Алгоритм обобщенного приведенного метода Ньютона.

§3.2 Доказательство сходимости алгоритма.

§3.3 Оценки скорости сходимости приведенных алгоритмов.

Основные обозначения

• Жп — арифметическое пространство векторов х = (хх,., хп) € Еп.

• (х, у) = х\у\ + . + хпуп — скалярное произведение векторов х = {хъ .,хп),у = (уи ., уп) е Мп.

• е = (ех,., еп) — ортонормированный базис в К.п: еп 67/ — Оц — <

1^1, 1 ^ г = ^ п.

• 1лп(/г1,., Нт) — линейная оболочка, порождённая векторами /11,., /гт €

• ||г|| = (х\ + . + Хп)1^2 — евклидова норма вектора х = (хи.,хп)еШп.

• А = (а,ц) — прямоугольная матрица.

• А(тх п) — матрица, состоящая из га строк и п столбцов.

• Ртт{А), Ртах(А) — наименьшее и наибольшее сингулярные числа матрицы А.

• ||А|| — спектральная норма матрицы А.

• АТ — матрица, транспонированная к матрице А.

• \7.Р(а;) или Ь'х(х, А) — градиент функции -Р(х) или Ь(х, Л) по переменным х.

• или Ь"х(х, Л) — гессиан функции -Р(х) или Ь(х, А) по переменным х.

Введение диссертация по математике, на тему "Обобщенный приведенный метод Ньютона"

При применении в различных областях техники и экономики математических методов исследования операций зачастую возникает необходимость численного решения задач условной оптимизации. В настоящее время имеется и активно используется большое количество численных релаксационных методов локального поиска, позволяющих эффективно отыскивать локальный экстремум для широкого круга задач (см. работы Д. И. Батищева, Ф. П. Васильева, И. М. Гельфанда, Ю. Г. Данилина, Ю. Г. Евтушенко, А. А. Жиглявского, С. К. Завриева, В. Г. Карманова, Б. Т. Поляка, Б. Н. Пшеничного, Р. Г. Стронгина, А. Г. Сухарева, В. В. Фёдорова, Д.Б.Юдина, и их учеников; [9], [10], [19], [21], [23], [24], [28], [39], [41], [43], [44]).

Основными задачами работы являются

- исследование дифференциальных свойств приведённой относительно ограничений целевой функции задачи;

- теоретическое обоснование сходимости алгоритма.

Рассмотрим задачу fix) —► min,

1) х € X = {х € Rn: д{ (х) = О, г = 1,., га} .

Будем считать, что функции /(х) и gi(x) (« = 1,2, .,га) дважды непрерывно дифференцируемы на множестве X, удовлетворяют условию Липшица и для всех х € X векторы Vgi(x) (г = 1,2,. ,га) линейно независимы — условие регулярности.

Пусть е = (ei, в2,. ■ •, еп) — ортонормированный базис пространства Rn. Через I = (¿i,«2,. ,in-m) обозначим набор индексов ii, i2,., in-m таких, что 1 < ¿1 < ¿2 < . in-m ^ п. Через

1п~Ш = U = (и» «2» . . . , in-m) : 1 ^ ¿1 < ¿2 < . . . in-m ^ п} обозначим множество всех таких наборов.

Введём

E(I) = Lm(eilt eia,., einJ подпространство в Rn, образованное базисными векторами е^,

Будем считать, что функции f(x) и gi(x) (г = 1,2,., га), равно как и их производные, вычисляются как функции аргументов, разложенных по базису е.

Суть алгоритма обобщённого приведённого метода Ньютона состоит в следующем.

Рассмотрим к-ю итерацию алгоритма.

На первом этапе строится касательное подпространство N(xk) размерности п — т к множеству ограничений и выбирается координатное подпространство Е{1) той же размерности п — т.

Через E(I)L обозначим ортогональное дополнение к Е{1).

Аналогично алгоритмам с исключением переменных координат, происходит разбиение переменной хк на пару переменных (yk,zk) следующим образом: xk = yk + zk^ ук ^ E(I)1, zkeE(I), функция ук = <p(zk) определяется как решение системы нелинейных уравнений

9i(yk,zk) = 0 (г = 1,2,. ,т).

В условиях теоремы о неявных функциях, в окрестности точки zk определена приведённая целевая функция

F{z) = f(y{z),z).

Таким образом, задача (1) сводится к задаче безусловной оптимизации

F(z) —> min z <Е Rn~m 5

При переходе от задачи (1) к задаче (2) мы использовали достаточные условия существования дифференцируемой неявной функции у = <p(z).

На втором этапе происходит сдвиг по методу Ньютона в координатном подпространстве Е{1): zk+1 = zk при этом проверяется условие релаксации

F(zk+1) < F(zk).

Далее, решая уравнение yk+1 = ip(zkJrl), например, модифицированным методом Ньютона, получаем следующую допустимую точку xk+l = yk+1 + zk+1.

Обоснование замены касательной плоскости координатной плоскостью той же размерности приводится в главе I.

Рассмотрим пространство Rn, и пусть М С R": dimМ = т, т < п. Оператор Р^ такой, что для любого жбК" выполнено

1) Pbx € М,

2) х- Р^х е м\ называется оператором ортогонального проектирования.

Через 0{тхп) — (Oij) (i = 1,2,., га, j = 1,2,.,n) обозначим нулевую матрицу размера тхп. Для единичной матрицы порядка га будем использовать обозначение га х га) = О о 1 (<У i = l,2,.,m, j = 1,2,., га.

Пусть /г, = {/¿1, /¿2» • • • 5 Ь>т+1,., кп} — ортонормированный базис в Мп. Обозначим через

Я = Я(п х га) = (/г-х,., кт)1 Н = Я(п х (гг - га)) = {Кт+Ъ., /гп). матрицы, столбцами которых являются координаты векторов К в базисе е. Отметим некоторые свойства этих матриц.

1) ЯТЯ = /(га х га),

2) НтН = 0(т х (тг-га)),

3) ННТ + ННТ = 1(п х п),

4) = ЯЯТ. Пусть г = (/¿1, /¿2, . , ^ш), Л = (¿1, £¿2, ., с?т), Я = Я(п х га), /) = /?(п х га), тогда для матрицы Грама пары (Л,, с?)

G(h,d) =

K(h выполнено G(h, d) = Ят/).

Пусть МЬМ2 С — линейные подпространства, dim Mi = = dim Л/2 = га, a d и h — ортонормированные базисы Mi и М2 соответственно. Обозначим через Р^2{М\) оператор ортогонального проектирования с М\ на Мг, тогда

Pjh2(M1) = G(h,d) = G(d}h)T.

Обозначим через Si единичную сферу в Rn:

Si = {x£Rn: И = 1}.

Через Si(M) обозначим пересечение единичной сферы Si с подпространством М С W1.

Пусть М\ и М2 — подпространства в Rn размерности т, т ^ п. Углом между Mi и М2 назовём величину ang(Mi, М2) = arccos min^ ^ •

Отметим простые свойства угла между подпространствами.

1) Если т = 1, то ang(Mi, М2) — не тупой угол между пересекающимися прямыми.

2) Если т = 2, то ang(Mi, М2) совпадает с определением не тупого линейного угла двугранного угла между плоскостями.

3) Справедливо равенство ang(Mi, М2) = ang(M2, Mi).

4) Справедливо равенство ang(Mi,M2) = ang(Mi", М¡jr).

В §1.2 получено представление косинуса угла между подпространствами через сингулярные числа матрицы Грама систем базисных векторов подпространств. cos ang(Mi, М2) = Pmin {G{h, d)), 8 где рщщ — минимальное сингулярное число матрицы С(/1, (Г), причём если Мх + М2Х = Мп, то cos ang(Mb М2) = \\G(d, h)

-Hl-1

В §1.3 устанавливается один из основных результатов работы — получение нетривиальной нижней оценки угла между касательной плоскостью N(xk) и координатной Е(1) в случае dim N(xk) = dim E(I).

Ответ на вопрос, каким может оказаться угол в худшем случае расположения N(xk), даётся значением следующего максимина

7* = max min ang(N(xk), E(I)). xkex iein~m

Нам будет удобно искать не значение угла, а значение его косинуса.

Теорема 1.3.1. Пусть М С Mn, dimМ = т, (ei, ег,., еп) — ортонормированный базис пространства Rn. Тогда найдётся координатное пространство

Е{1) = Lm(eil,ei2,.,eim) такое, что cos ang{M,E(I)) > у/С. т п

Применительно к задаче (1) теорема формулируется так: Для касательного подпространства М(хк) размерности п — т найдётся координатное подпространство Е(1) той же размерности п — га такое, что

В главе II диссертации установлены дифференциальные свойства приведённой целевой функции F(z) = f(jp(z),z) задачи

F(z) —> min и получены оценки норм её градиента и гессиана.

ВгЛуо) = {У- \\У-УО\\ ВГ2Ы = ||<г-20|| < г2}, П(Уо,2о) = {(y*z): \\y-yoW < Г1,||г-2ь|| < г2} .

Пусть функция g(y, z) непрерывно дифференцируема на множестве Г2(т/о, zq). Пусть выполнены следующие условия: существуют Li, L2, Lz = const > 0, такие что

1) ИКЫ^о))-1!!^^,

2) VzeBr2(z0) \\g'y{yo,z)-g'y(yo,z0)\\ < L2(\\y - 2/0II + \\z - гь||),

3) VzeBr2(z0) \\g{y0,z)\\ ^ Lz \\z — 20Ц. Тогда Vz e Bt{zq), где cos an; zeM! n—m существует единственное решение у = <p(z) уравнения g(y,z) = 0, уеВг(у0), Ю где

Г = Ш1П I Г1,

1 ( ии дифференцируемое в точке го (см. [45]).

Для получения решения у = ср(г) уравнения д(у, г) = О применим метод Ньютона: рп+1(2) = <Рп{2) - (р'уЫ, г),

1(2) = Уо € В¥{уо). Введём функцию Лагранжа задачи (1):

Ь(х,\) = /(х) + \тд(х), обозначим через

В §2.1 получены формулы для вычисления градиента и гессиана функции /(2):

Пусть функции f(x) ид^х) дважды непрерывно дифференцируемы на X, удовлетворяет условию Липшица, векторы Vд{(х) (г = 1,2,., т) линейно независимы. Тогда для любого г е ВГ2(го)

ЪЬ(х,\) = Ч/{х) + \ТУд{х) Ъ2Цх, А) = Ч2/(х) + \тЪ2д(х) её градиент и гессиан соответственно. Обозначим

Р(х, (Я, Я)) = ЯТ - НТ^д(х)т(^д(х)Ну1)ТНт.

УРМ = Р(:г,(Я,Я))У/(:г), V 2Р(г) = Р(х,(Н,Н))Ч2Ь(х,\)Р(х,{Н,Н))Т, т где х = у + г, у = <р(г).

В §2.2 исследованы дифференциальные свойства приведённой целевой функции.

Точку Хо £ X будем называть ¿^-отделённой по разбиению М1М2, Мх + М2 = Еп, если

V<;(:ro)

-11 и

Пусть точка € X и>-отделена по разбиению Мп = + Хо = Уо + ¿о, Уо € Мь г0 е М2> тогда и К2 > 0: € Д^Сзо) выполнено

1) иу^ЛК^Ь

2) ЦУ^(г') - ^ К2

При выполнении перечисленных выше ограничений на функции /(х) и <7г(я) = 1,2,. ,т) справедливы неравенства

П'ПНт^-тт, сое 7* 1 РтахЧ2Цх,\) где Ртах и pmin — наибольшее и наименьшее сингулярные числа матрицы вторых производных функции Лагранжа задачи (1).

В главе III диссертации описан алгоритм и доказана сходимость обобщённого приведённого метода Ньютона.

В §3.1 описан алгоритм обобщённого приведённого метода Ньютона.

1) Пусть на k-Pi итерации метода получена точка

2) Проверяем регулярность точки хк. При отсутствии регулярности — остановка работы метода в точке хк.

3) 3.1. Строим касательное подпространство N(xk) к множеству ограничений.

3.2. Выбираем координатное подпространство Е(1) таким, что О < a,ng(N(xk), Е(1)) <

4) Вычисляем VF(zk), (V2F(^))-1 для хк = ук + г*, z е Е{1).

5) Вычисляем hk = (V2F(^))-1VF(^).

6) zk+1 = zk + hk — шаг метода Ньютона в подпространстве Е{1).

7) Проверяем F(zk+1) < F(zk).

8) Решая систему д(у, zk+1) = 0, находим ук+1.

9) Получаем следующую точку хк+1 = ук+1 + zk+1.

В §3.2 исследуется сходимость обобщённого приведённого метода Ньютона.

Точка х* Е X задачи (1) называется Морс-регулярной, если

1) точка х* регулярна и 3 Л*: VL(x*, Л*) = О,

2) существуют п — т линейно независимых векторов Si, $2,., sn-m таких, что

VF{x*)si = 0 (г = 1,2,.,п-т) и

VL{x\X*)si,Si)^ 0. Условие Морс-регулярности эквивалентно условию невырожденности спроектированной матрицы Гессе функции Лагранжа. Таким образом, условие Морс-регулярности стационарной точки является обобщением условия невырожденности экстремума задачи (1).

Теорема 3.2.1. Если последовательность {я^} определяется алгоритмом обобщённого приведённого метода Ньютона, и каждая стационарная точка функции Лагранжа Морс-регулярна, то найдётся А* £ R такое, что последовательность {х*;} сходится к точке х*, в которой

VL(x*, А) = 0 и найдётся q £ (0,1) такое, что f(xk+1)-f(x*)^q(f(xk)-f(x*)).

Доказательство теоремы 3.2.1 опирается на результат теоремы 1.3.1 о строгой отделённости от | угла между N(xk) и Е(1).

Сравнивая предложенный метод, например, с методом множителей Лагранжа, сводящим решение задачи (1) к решению системы нелинейных уравнений dxi и>

Ф) = 0. видим, что эта система включает в себя п 4- т уравнений относительно п + т переменных. В нашем методе предлагается перейти к задаче

F(z) —► min, 2 6 Rn-m меньшей размерности.

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

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

В заключении сформулированы основные результаты работы.

Список источников диссертации и автореферата по математике, кандидата физико-математических наук, Панферов, Семен Валерьевич, Москва

1. Гроссман К., Каплан A.A. Нелинейное программирование на основе безусловной оптимизации. — Новосибирск, Наука, 1981.

2. Деннис Дж., Шнабель Р. Численные методы безусловной оптимизации и решения нелинейных уравнений. М.: Мир, 1988.

3. Добров Б.В. О сходимости одного класса итерационных процессовСистемное программирование и вопросы оптимизации /Ред. Королев JT.H., Краснощеков П.С. М.: Изд-во Моск. ун-та, 1987.

4. Евтушенко Ю.Г. Методы решения экстремальных задач и ихприменение в системах оптимизации. М.: Наука, 1982.

5. Есенков A.C., Ишмухаметов А.З., Карюкина Ю.Г. Регуляризованные методы проекции и условного градиента в выпуклых конечномерных задачах оптимизации. Вопросы моделированияи анализа в задачах принятия решений. М., ВЦ РАН 2004.

6. Жиглявский A.A., Жилинскас А.Г. Методы поиска глобальногоэкстремума. М.: Наука, 1991.

7. Зангвилл У.И. Нелинейное программирование. М.: Сов. радио,1973.

8. Измаилов А.Ф., Третьяков A.A. Факторанализ нелинейныхотображений. М.: Наука, 1994.

9. Измаилов А.Ф., Третьяков A.A. 2-регулярные решения нелинейных задач. Теория и численные методы. М.: Физматлит, 1999.

10. Ильин В.А., Садовничий В.А., Сендов Бл.Х. Математическийанализ. М.: Наука, 1979.

11. Карманов В.Г. Математическое программирование. М.: Физматлит, 2000.

12. Кларк Ф. Оптимизация и негладкий анализ. М.: Наука, 1988.

13. Левитин Е.С. Теория возмущений в математическом программировании и ее приложения. М.: Наука, 1992.

14. Мину M. Математическое программирование. Теория и алгоритмы. М.: Наука, 1990.

15. Михалевич B.C., Гупал A.M., Норкин В.И. Методы невыпуклойоптимизации. М.: Наука, 1987.

16. Моисеев H.H., Иванилов Ю.П., Столярова Е.М. Методы оптимизации. М.: Наука, 1978.

17. Нурминский Е.А. Численные методы выпуклой оптимизации.М.: Наука, 1991.

18. Ортега Дж., Рейнболдт В. Итерационные методы решения нелинейных систем уравнений со многими неизвестными. М.: Мир, 1975.

19. Панфёров С. В. Гарантированная оценка угла между касательной и координатной плоскостью. — Сборник «Прикладная математика и информатика», №8.

20. Панфёров C.B. Алгоритм обобщённого приведённого методаНьютона — Электронный журнал «Исследовано в России», №8, 2004.

21. Панфёров С. В. Дифференциальные свойства приведённой целевой функции — Электронный журнал «Исследовано в России», №4, 2005.

22. Полак Э. Численные методы оптимизации. Единый подход. -М.: Мир, 1974.

23. Поляк Б.Т. Введение в оптимизацию. М.: Наука, 1983.

24. Пшеничный Б.Н., Данилин Ю.М. Численные методы в экстремальных задачах. М.: Наука, 1975.

25. Рокафеллар Р. Выпуклый анализ. М.: Мир, 1973.

26. Стронгин Р.Г. Численные методы в многоэкстремальных задачах. М.: Наука, 1978.

27. Сухарев А.Г., Тимохов A.B., Федоров В.В. Курс методов оптимизации. М.: Наука, 1986.

28. Треногин В. А. Функциональный анализ — М.: Физматлит, 2002

29. Фиакко А., Мак-Кормик Г. Нелинейное программирование. Методыпоследовательной безусловной минимизации. М.: Мир, 1972.

30. Химмельблау Д. Прикладное нелинейное программирование.М.: Мир, 1975.

31. Alldower E.L., Georg K. Numerical continuation methods. Anintroduction. Berlin, Heidelberg: Springer-Verlag, 1990.

32. Bertsekas D.P. Nonlinear programming. Second Edition.Belmont: Athena, 1999.

33. Bonnars J.F., Gilbert J.Ch., Lemarechal C., Sagastizabal C.Numerical optimization. Theoretical and practical aspects. Berlin:Springer-Verlag, 2003.

34. Borgwardt K.H. The simplex methods. A probabilistic analysis.Berlin, Heidelberg: Springer-Verlag, 1987.

35. Conn A.R., Gould N.I.M., Toint Ph.L. Trust-region methods.Philadelphia: SIAM,2000.

36. Fletcher R. Practical methods of optimization. V.l. Unconstrainedoptimization. Chichester, NewYork, Brisbane, Toronto: John Wiley, 1980.

37. Fletcher R. Practical methods of optimization. V.2. Constrained optimization. Chichester, NewYork, Brisbane, Toronto: John Wiley, 1981.

38. Mangasarian O.L. Nonlinear Programming. Philadelphia: SIAM,1994.

39. More J.J., Wright S.J. Optimization software guide. Philadelphia: SIAM,1993.

40. Nocedal J., Wright S.J. Numerical optimization. New York, Berlin,Heidelberg: Springer-Verlag, 2000.

41. Treccani G. On the critical points of continuosly differentiablefunctions// Towards global optimization.

42. Wolfe P. Methods for nonlinear constraints// Nonlinear programming/Ed. Abadie J. Amsterdam: north-Holland, 1967.

43. Yamashita H. A continuous path method of optimization andits application to global optimization // Survey of Mathematical Programming (Proc. 9th International Math. Progr. Symp.Budapest, 1976). V.l. Amsterdam: north-Holland, 1979.

44. Zwart P.B. Nonlinear programming: counter-examples to two globaloptimization algorithms// Oper. Res. 1973. - V.21, N.6.