Введение к работе
Актуальность темы. Разработка методов решения экстремальных задач является одним из интенсивно развивающихся направлений вычислительной математики. Важным классом методов минимизации является класс непрерывных методов, в которых процесс минимизации описывается дифференциальными уравнениями. Интерес к непрерывным методам стимулируется, с одной стороны тем, что при исследовании сходимости траекторий непрерывных процессов к точке равповесия можно широко использовать развитый в теории дифференциальных уравпений аппарат, с другой стороны тем, что эти методы оставляют свободу при выборе методов численного интегрирования получающихся дифференциальных уравнений и определяют таким образом целый класс дискретных методов, которые не так просто обнаружить, оставаясь в рамках привычных представлений, павязанных итеративной оптимизацией. До сих пор в литературе много внимания уделялось непрерывным методам первого порядка, изучались также непрерывные методы проекции градиента второго, третьего и четвертого порядков. Здесь можно упомянуть работы В.И. Венеда, М.В. Рыбашова, Ю.Г. Евтушенко, В.Г. Жадана, Б.Т. Поляка, Н.А.Бобылева, С.К. Коровина, А.С. Антипина, М. Ковач, А. Недич и других.
Ряд хорошо известных непрерывных и итерационных методов минимизации основан на замечательном свойстве антиградиента: направление наибыстрейшего убывания целевой функции в точке совпадает с направлением аптиградиента в этой точке. Хорошо известны непрерывный градиентный метод первого порядка, метод "тяжелого шарика", описываемый дифференциальным уравнением второго порядка, непрерывный аналог метода Ньютона. А.С. Антипиным были впервые предложены непрерывные методы минимизации, содержащие оператор проектирования. Идеи построения непрерывных алгоритмов минимизации с оператором проектирования нашли свое продолжение и обобщение в трудах А. Недич: были разработаны непрерывные алгоритмы второго, третьего и четвертого порядков.
Однако, теоретические исследования и численные эксперименты подтверждают, что различные варианты градиентного метода медленно сходятся в тех случаях, когда поверхности уровня целевой функции сильно вытянуты, и функция имеет так называемый "овражный" характер. Один из способов ускорения сходимости градиентного метода заключается в выборе подходящей замены переменных с тем, чтобы в пространстве новых переменных поверхности уровня целевой функции были близки к сферам. Таким образом, появляется новый параметр метода — симметричная положительно определенная матрица, или, если замена переменных делается в текущие моменты времени — семейство таких матриц. С помощью симметричной положительно определенной матрицы в
пространстве можно задать новое скалярное произведение и соответствующую ему метрику. Поэтому методы такого типа в литературе называются методами с переменной метрикой или методами с "растяжением пространства". То, что на этом пути можно добиться существенного ускорения сходимости, подтверждается, например, хорошо известным методом Ньютона, где в качестве матрицы — параметра метода — берется матрица вторых производных целевой функции. Однако, метод Ньютона обычно применяют в тех случаях, когда вычисление матрицы вторых производных не представляет трудностей. Для решения задач минимизации существует также целый ряд квазиныотоповских методов, в которых матрица — параметр метода — выбирается близкой к матрице вторых производных. Сюда можно отнести, например, метод Девидона-Флетчера-Пауэлла, метод Стеффенсена и другие.
Проблема построения устойчивых методов минимизации, которые обладали бы достаточно высокой скоростью сходимости, были приспособлены для минимизации сильно овражных функции и для своей реализации не требовали вычисления матрицы вторых производных и ее трудоемких аппроксимаций представляется актуальной.
Цель работы: разработка непрерывных методов проекции градиента, линеаризации и проксимальных методов с переменной метрикой для задач минимизации, исследование их сходимости, конструирование регуляризованных вариантов предложенных методов и построение регуляризирующего оператора.
Методы исследований. В работе используются теория и методы выпуклого программирования, дифференциальных уравнений, методы функционального анализа, теория некорректных задач.
Научная новизна работы. В диссертации предлагаются новые непрерывные методы проекции градиента, линеаризации и проксимальные методы с переменной метрикой, исследуется их сходимость. Исследованы регуляризованные методы минимизации, основанные на предложенных непрерывных методах.
Практическая значимость. Методы, предложенные в работе, могут быть использованы при решении задач минимизации овражных, многоэкстремальных функций, неустойчивых к погрешностям задания исходных данных оптимизационных задач.
Апробация работы. Результаты диссертации докладывались и обсуждались на:
научном семинаре кафедры оптимального управления факультета ВМиК МГУ под руководством проф. Васильева Ф.П.;
научно-исследовательском семинаре кафедры математической физики факультета ВМиК МГУ под руководством проф. Денисова A.M.;
IY Международной научной конференции "Многокритериальные и игровые задачи при неопределенности" в Орехово-Зуево (8-14 сентября 1996 г.)
Публикации. Основные результаты диссертации опубликованы в работах [1]-[5], перечисленных в конце автореферата.
Структура и объем работы. Диссертация состоит из введения, трех глав, двух приложений и списка литературы, включающего 82 наименования. Объем работы составляет 151 страницу машинописного текста.
