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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Будем считать, что функции 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 ^ ¿х < гг < . гга_т ^ п. Через

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

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

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

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

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

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

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

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

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