Обобщенный приведенный метод Ньютона тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат физико-математических наук Панферов, Семен Валерьевич

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

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

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,. ,га) линейно независимы — условие регулярности.

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

Пусть е = (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.

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

Рассмотрим пространство 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.

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

Обозначим через 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

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

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

Теорема 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

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

При выполнении перечисленных выше ограничений на функции /(х) и <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. Разработан унифицированный подход к конструированию численных методов решения задач условной оптимизации, предполагающий последовательное исключение групп переменных в исходной задаче и применения в решении получающейся задачи безусловной оптимизации с «приведённой» функцией цели методов безусловной оптимизации.

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

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

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

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.