Обобщенный приведенный метод Ньютона Панферов Семен Валерьевич

Содержание к диссертации

Введение

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

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

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

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

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

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

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

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

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

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

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

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

Литература

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

Введение к работе

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

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

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

Основными задачами работы являются обобщение идеи метода приведённого градиента для построения алгоритмов второго порядка в задаче с ограничениями-равенствами; исследование дифференциальных свойств приведённой относительно ограничений целевой функции задачи; - теоретическое обоснование сходимости алгоритма. Рассмотрим задачу f(x) — min,

, (і) х Є X = {х Є Rⁿ: 9і{х) = 0, * = 1,..., m} .

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

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

Пусть є = (еі, Є2,. - -, е„) — ортонормированный базис пространства Ж^п. Через / = {іі,І2,...,і_п-т) обозначим набор индексов «і,«2» )in-m таких, что 1 < ii < г₂ < ...і_п-_т К п. Через jn-m ₌ {j ₌ (г_ьг₂,...,г„__т): 1 < гі <г₂ < ...*_n-m ^ п) обозначим множество всех таких наборов. Введем

Е{1) = Linfe,, в(_а,..., e_in__m) — подпространство в Rⁿ, образованное базисными векторами е^,

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

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

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

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

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

Аналогично алгоритмам с исключением переменных координат, происходит разбиение переменной х^к на пару переменных (y^ft, z^h) следующим образом: x^k = y^k + z^k, у^кЄЕ(І)^±, z^keE{I), функция у^к = k) определяется как решение системы нелинейных уравнений _9i(y^k,z^k) = Q (г = 1,2,...,т).

В условиях теоремы о неявных функциях, в окрестности точки Z определена приведённая целевая функция F(z) = f(tz).

Таким образом, задача (1) сводится к задаче безусловной оптимизации F{z) — rnin z Є Ж^п~^т

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

На втором этапе происходит сдвиг по методу Ньютона в координатном подпространстве Е(1): ^+¹ = _г* _ (F"{z^k)y^lF'(z^k), при этом проверяется условие релаксации F(z^k+l)k).

Далее, решая уравнение y^k+1 = ip(z^k+l)_t например, модифицированным методом Ньютона, получаем следующую допустимую точку rf+i _{= у}к+1 ₊ ^+1_

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

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

Рассмотрим пространство К, и пусть М С Ж⁷¹: dimM = m, т ^п. Оператор Р^ такой, что для любого х Є Rⁿ выполнено 1) Р^х є М, 2)х-Р^хЄМ¹, называется оператором ортогонального проектирования.

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

1(т х т) = _о j = 1,2,..., m.

Пусть /г. = {/її, /і2,..., /г_т, /i_m+i,..., /г_п} — ортонормированный базис в М^п. Обозначим через

Н = Я (те х га) = (Л-і,..., /ь_т),

Я = Я (те х (п - т)) = (Лт+і,..., Л„). матрицы, столбцами которых являются координаты векторов Л в базисе е. Отметим некоторые свойства этих матриц. 1) Н^ГН = 1(т х т), 2)Н^ТН = 0(тх {п-т))> 3)ЯЯ^т + ЯЯ^Т = /(пхп), 4) / = НН^Т. Пусть

Л= (hi,h2,.. . ,/i_m), ^ = (с?1, C?2t -ч^т)»

Я = Я(пхт), D = D(nxm), тогда для матрицы Грама пары (Л,, d) {hudi) ... (h_ud_m) G(h,d) = выполнено G(h,d) — H^TD.

Пусть Mi, Мз С E" — линейные подпространства, dim Mi = = dimM₂ = m, a rf и h — ортонормированные базисы Mi и M₂ соответственно. Обозначим через Pj^ (Mi) оператор ортогонального проектирования с М\ на Мг, тогда Pk₂{M₁) = G{h,d) = G{d,hY.

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

Обозначим через S\ единичную сферу в R": Si = {x<=Rⁿ: ||i|| =1}.

Через S\{M) обозначим пересечение единичной сферы S\ с подпространством М С Е^п.

Пусть Mi и M2) = arccos min |[Р^ (Mi)xlj.

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

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

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

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

Справедливо равенство ang(Mi, Мг) = angCMj¹, М₂^Х).

В 1.2 получено представление косинуса угла между подпространствами через сингулярные числа матрицы Грама систем базисных векторов подпространств. cosang(M_b М₂) = p_mm(G{h, d)), 8 ^гДе Pmin — минимальное сингулярное число матрицы G{h, d), причём если Mi + М₂^Х = R", то cosang(M_bM₂) = ||G(d,A)' -in-¹

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

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

7* = max min ang(tf(x*)₍Е{1)).

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

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

Теорема 1.3.1. Пусть М С Ш^п, dimM = т, (еі,Є2, ...,е„) — ортонормированный базис пространства W¹. Тогда найдётся координатное пространство E(I) = Lin(e_ilte_i3,...,e_im) такое, что cosang(M,(/)) >—?==

Применительно к задаче (1) теорема формулируется так:

Для касательного подпространства N(x^k) размерности п — т найдётся координатное подпространство Е(1) той же размерности п — т такое, что cosang(iV(x^fc),;(/))^-^_

В главе II диссертации установлены дифференциальные свойства приведённой целевой функции F{z) = f(tp(z)_tz) задачи F{z) — min z Є Ш^п~^т и получены оценки норм её градиента и гессиана.

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

В_Г1(уо) = {у: \\у-Уо\\ <п},

Д-₂(²о) = {z: \\z - z₀\\ < r₂} , tt(yo,zo) = {(y,^): ||V — Ї/0ІІ О, такие что l)\H(y<»Z0))-^l\\<;L_U VzeB^izo) ||<(ї/о^)-РІ(ї/о^о)|| ^Ь2(||з/-2А)|| + ||>г;-гь||), Vz B_r2(z_Q) \\g(y_0> z)\\ ^ L_z \\z - z₀||. Тогда "і z Є B_r(zo), где . ( AL1L2 \ ^{r = m,}4^r2'bnsJ' существует единственное решение у = (p(z) уравнения g(y,z) = 0, у<=Вг(уо), ^г=тіа(^г"2їк(їт^Г)' - дифференцируемое в точке Zq (см. [45]).

Для получения решения у — ip(z) уравнения д(у, z) = 0 применим метод Ньютона: Vn+i{z) = n{z)~ip'_y{y_Q,z₀)-¹(p(ip_n(z),z),

Введём функцию Лагранжа задачи (1): L(x_tX) = f(x) + \^Tg(x)_t обозначим через VL(x_t\) = Vf(x) + \^TVg(x) V²I(x, Л) = V²/(x) + X^TV²g(x) ее градиент и гессиан соответственно.

Обозначим

Р(х,(Н,Щ = Я^Т -'H^T^x)^T({Vg(x)H)-¹)^TH^T.

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

Пусть функции f(x) и gi{x) дважды непрерывно дифференцируемы на X, V/(x) удовлетворяет условию Липшица, векторы Vgi{x) (i= 1,2,... ,m) линейно независимы. Тогда для любого z Є B_T2{zq) VF(z) = P{x,(H,H))Vf(x)₇ W²F(z) = Р(х,{Н,ЩЧ²Ь(х,\)Р(х,{Н,Щ^Т₁ где x = t/ + z, у —

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

Точку Xq Є X будем называть ^-отделённой по разбиению М\Мі^ Mi + M₂ = R", если ||v_ff0ron|^.

Пусть точка Хо Є X w-отделена по разбиению W¹ = Mi -f М2, ^0 = ї/о + (b Уо Є Aft, z₀ Є М₂₎ тогда ЗКі и і^2 > 0: Ч z_yz\z" Є ^() выполнено

1)||VF(₂)|K^

2) ||VF(z') - VF(*")|| * ^2 ||V - г"||.

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

При выполнении перечисленных выше ограничений на функции f(x) и Qi{x) (г = 1, 2,..., т) справедливы неравенства UVF(**)||<^-|V/(*)|, ^{11 v} "I ^COS²7* PminV²L(^,A) где ртах и р_т;_п — наибольшее и наименьшее сингулярные числа матрицы вторых производных функции Лагранжа задачи (1).

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

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

1) Пусть на k-ft итерации метода получена точка х^кєХ: ||V₅0r^fc)||<*.

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

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

3.2. Выбираем координатное подпространство Е{1) таким, что 0<&ng(N(x^k),E{I)) <.

Вычисляем VF{z^k), (V²F(z^k))~^l для х^к = у* + z^k, z Є Е{1).

Вычисляем h^k = (V²F{z^k))~^lVF{z^k), z^k+l = z^k + h^k — шаг метода Ньютона в подпространстве Е(І),

Проверяем F(z^k+1) < F(z^k).

Решая систему g(y, z^k+1) = 0, находим y^k+l.

Получаем следующую точку x^k+l = y^k+l + z^k+1.

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

Точка х* Є X задачи (1) называется Морс-регулярной, если точка х* регулярна и 3 A*: VL(x*_t А*) = О, существуют п — т линейно независимых векторов Si, S2, -.. , S_n-m таких, что VF(x*)$i = 0 (г = 1,2,..., п-т) и {VL(x*_}\*)s_uSi)^0. Условие Морс-регулярности эквивалентно условию невырожденности спроектированной матрицы Гессе функции Лагранжа. Таким образом, условие Морс-регулярности стационарной точки является обобщением условия невырожденности экстремума задачи (1).

Теорема 3.2.1. Если последовательность {х } определяется алгоритмом обобщённого приведённого метода Ньютона, и каждая стационарная точка функции Лагранжа Морс-регулярна, то найдётся А* Є Ж такое, что последовательность {#&} сходится к точке х*, в которой VL(x\X) = 0 и найдётся q Є (О,1) такое, что f(x^k+1)-f(x*)^q(f(x^k)-f{x*)).

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

Сравнивая предложенный метод, например, с методом множителей Лагранжа, сводящим решение задачи (1) к решению системы нелинейных уравнений gi{x) = 0. видим, что эта система включает в себя п + т уравнений относительно п + т переменных. В нашем методе предлагается перейти к задаче F(z) —» min, z Є Uⁿ'^m меньшей размерности.

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

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

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

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

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

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

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