Введение к работе
Диссертационная работа посвящена построению и исследованию свойств методов численного анализа задач математического программирования (МП), основанных на применении различных модификаций штрафных функций и функций Лагранжа. Основное внимание при этом уделяется задачам оптимизации с особенностями, прежде всего, несобственным и некорректно поставленным.
Актуальность темы. Метод штрафных функций является универсальным средством решения экстремальных задач различной природы. Метод порождает целое семейство вычислительных процедур, а также служит эффективным инструментом теоретического анализа задач оптимизации.
Активные исследования в области метода штрафных функций ведутся с начала 60-х годов прошлого столетия. Методу посвящено большое количество работ, как отечественных авторов (Ф.П.Васильев, В.Ф.Демьянов, Ю.Г.Евтушенко, И.И.Еремин, В.Г.Жадан, Я.И.Заботин, Б.Т.Поляк, В.В.Федоров и др.), так и зарубежных (ААуслендер, М.Базара, У.Зангвилл, Ф.Лутсма, Г.Маккормик, О.Мангасариан, А.Фиакко, Р.Хьюард и др.).
Важное значение при этом имеет метод точных штрафных функций, предложенный в 1966 году И.И.Ереминым. Данный метод позволяет в принципе свести решение исходной условноэкстремальнои задачи к однократной минимизации без ограничений некоторой вспомогательной функции. Проблема построения таких функций и нахождения условий точности для различных классов задач МП занимает заметное место в специальной литературе и продолжает оставаться актуальной.
Хорошо известны вычислительные трудности при численной реализации метода штрафных функций, связанные с асимптотическим характером сходимости. Один из возможных путей преодоления этих трудностей предлагают методы модифицированной функции Лагранжа (методы множителей, штрафных оценок). Эти методы, с одной стороны, расширяют возможности стандартной функции Лагранжа, играющей центральную роль в теории МП, с другой — являются определенным обобщением метода штрафных функций. Исследования в этой области,
начатые в 1969 году М.Хестенсом и М.Пауэллом, были развиты многими авторами (А.С.Антипин, Д.Бертсекас, А.И.Голиков, Е.Г.Голынтейн, Ю.Г.Евтушенко, В.Г.Жадан, Б.Т.Поляк, Г.Гокафеллар, Н.В.Третьяков и др). Был предложен достаточно широкий спектр модификаций функции Лагранжа и численных алгоритмов, основанных на ее применении.
Современные тенденции в развитии методов штрафных функций и модифицированных функций Лагранжа состоят как в нахождении новых перспективных конструкций вспомогательных функций (например, сочетающих свойства функции Лагранжа и барьерных функций), так и в максимальном расширении сферы применения этих функций. В первую очередь, это касается построения новых алгоритмов для анализа таких классов задач МП, как невыпуклые, негладкие, нестационарные, бесконечномерные, многокритериальные, полуопределенные, билинейные, несобственные, некорректные и задачи большой размерности.
В настоящей работе основное внимание уделяется анализу методов штрафных функций и модифицированных функций Лагранжа применительно к несобственным и некорректным задачам линейного и выпуклого программирования.
Несобственные задачи (НЗ) МП характеризуются тем, что для них не выполняются соотношения двойственности. Свойство несобственности тесно связано с совместностью систем ограничений исходной задачи и двойственной к ней. Поэтому о несобственных задачах говорят в более узком смысле как о задачах МП с противоречивыми ограничениями. Интерес к противоречивым моделям обусловлен как потребностями математической теории (анализ систем уравнений и неравенств, некорректные задачи, задачи идентификации, распознавания образов и др.), так и необходимостью анализа прикладных задач с противоречивыми условиями, прежде всего экономических, где появление несовместных моделей — обычное явление. Гаспространенность и актуальность несобственных задач порождает острую потребность в разработке теории и методов их численной аппроксимации.
Определение НЗ МП и систематическое исследование таких задач было инициировано в начале 80-х годов прошлого века работами уральской школы по МП, возглавляемой академиком И.И.Ереминым. Впоследствии эта тема получила широкое отражение в специальной
литературе (работы Н.Н.Астафьева, В.А.Булавского, А.А.Ватолина, В.А.Горелика, И.И.Еремина, В.И.Ерохина, А.В.Зыкиной, М.М.Ковалева, В.Д.Мазурова, Л.Д.Попова, Н.В.Третьякова, М.Ю.Хачая и др.).
Многие важные в прикладном отношении задачи планирования, проектирования и управления являются некорректно поставленными. Решения таких задач не зависят непрерывно от входной информации. Поэтому нельзя быть уверенным, что приближенное решение задачи будет близким к точному и, следовательно, требуются специальные методы регуляризации, которые обеспечивали бы сходимость генерируемой итерационной последовательности к искомому множеству решений.
Начало исследований теории и методов некорректных задач связано с именами А.Н.Тихонова, В.К.Иванова, М.М.Лаврентьева. Дальнейшее развитие данная проблематика получила в работах А.Л.Агеева, А.С.Антипина, А.Б.Бакушинского, Ф.П.Васильева, В.В.Васина, Д.В.Денисова, В.Г.Карманова, В.А.Морозова, В.П.Тананы, А.Г.Яголы и др. К этому направлению также тесно примыкают исследования по устойчивости задач МП (работы Н.Н.Астафьева, А.Ауслендера, С.А.Ашманова, И.И.Еремина, Ю.Гуддата, С.Злобека, Е.С.Левитина, В.В.Федорова, А.Фиакко — для непрерывных задач МП, В.А.Емеличева, А.А.Колоколова, И.В.Сергиенко — для дискретного случая).
Таким образом, диссертационная работа, посвященная развитию теории метода штрафных функций, построению новых модификаций функции Лагранжа и соответствующих алгоритмов с целью их применения для коррекции несобственных задач и регуляризации некорректных задач МП, лежит в русле актуальных современных исследований в области математической оптимизации.
Цель работы состоит в построении и исследовании свойств штрафных функций и модифицированных функций Лагранжа в математическом программировании. При этом решаются следующие задачи.
1. Построение различных модификаций метода штрафных функций (точных, асимптотически сходящихся, барьерных, расширенных) и их применение для оптимальной коррекции НЗ МП и регуляризации некорректных задач МП.
-
Исследование аппроксимационных и регуляризирующих свойств функции Лагранжа, регуляризованной по прямым и двойственным переменным, для различных классов задач МП.
-
Разработка новых конструктивных алгоритмов, основанных на применении штрафных функций и модифицированных функций Лагранжа для численного анализа НЗ МП и регуляризации некорректных задач оптимизации.
-
Развитие оценочного подхода при обосновании сходимости предлагаемых методов.
Научная новизна. Основные результаты диссертации являются новыми.
Построены новые общие конструкции штрафных функционалов и сформулированы условия точности и асимптотической сходимости метода штрафных функций как для разрешимой задачи выпуклого программирования (ВП), так и обеспечивающие оптимальную коррекцию задачи в случае ее несобственности. Введены новые перспективные расширения штрафных функций, обладающие характерными свойствами модифицированных функций Лагранжа. На основе предложенных вариантов штрафных и барьерных функций построен ряд итерационных алгоритмов, сходящихся к решению задачи, аппроксимирующей исходную несобственную постановку.
Получены оценки уклонений компонент седловой точки регуляризованной по прямым и двойственным переменным функции Лагранжа La(x,X) от решений исходной и двойственной задач ВП, в том числе, и для несобственных постановок. При этом исследованы различные по степени общности виды стабилизирующих добавок. Предложены и обоснованы два универсальных по отношению к типам несобственности подхода к оптимальной коррекции задач ВП, основанных на применении функции La(x,X) .
Найдены условия управления параметрами регуляризации а = [сх,(3] функции La(x,X) в случае симметрической аппроксимации несобственных задач линейного и квадратичного программирования для нахождения нормальных решений соответствующей пары взаимно двойственных
задач.
Исследованы регуляризирующие свойства ряда модификаций штрафных функций и функции La(x, А) в условиях неточно заданной информации об исходной задаче выпуклого программирования как для разрешимого, так и для несобственного случаев. Предложены новые варианты конструктивно реализуемого метода регуляризации для задач линейного и выпуклого программирования, использующие расширенные штрафные функции и функцию La(x,\) .
Методы исследования. В работе используется математический аппарат выпуклого анализа, теории линейного, квадратичного и выпуклого программирования, теории несобственных и некорректных задач оптимизации. При обосновании предлагаемых методов широко применяется оценочный подход, опирающийся на теорию двойственности в МП.
Теоретическая и практическая значимость. Работа носит, в основном, теоретический характер, но имеет в то же время и выраженную практическую направленность. Полученные в ней оценки уклонений решений задач минимизации штрафных функций и модифицированных функций Лагранжа от решений исходной задачи (или ее естественных аппроксимаций) показывают возможный наилучший порядок сходимости соответствующих итерационных схем, возникающих при численной реализации данных подходов. В работе на примере метода барьерных функций показано, как полученные теоретические оценки могут быть применены для решения вопроса об управлении штрафным параметром с целью обеспечения сходимости метода со скоростью геометрической прогрессии как по функции, так и по аргументу. Также в работе предложен ряд конкретных конструктивно реализуемых вычислительных алгоритмов для оптимальной коррекции НЗ МП и для регуляризации некорректных задач оптимизации.
Апробация работы. Результаты диссертационной работы докладывались на следующих конференциях:
12-13-я Международные конференции "Математическая оптимизация" (Университет Гумбольдта, Берлин, 1980, 1981);
3-6-я Всесоюзные конференции "Методы математического програм-
мирования и их программное обеспечение" (Свердловск, 1981, 1984, 1987, 1989);
VI-я, X-XIV-я Байкальские школы-семинары "Методы оптимизации и их приложения" (Иркутск, 1983, 1995, 1998, 2001, 2005, 2008);
7-13-я Всероссийские конференции "Математическое программирование и приложения" (Екатеринбург, 1991, 1993, 1995, 1997, 1999, 2003, 2007);
1-4-я Всероссийские конференции "Проблемы оптимизации и экономические приложения" (Омск, 1997, 2003, 2006, 2009);
Международная конференция "Распределенные системы: оптимизация и приложения в экономике и науках об окружающей среде" (Екатеринбург, 2000);
Всероссийские конференции "Алгоритмический анализ неустойчивых задач" (Екатеринбург, 2001, 2004, 2008);
Российские конференции "Дискретная оптимизация и исследование операций" (Новосибирск, 2002, Владивосток, 2007, Алтай, 2010).
Результаты неоднократно обсуждались на научных семинарах Института математики и механики УрО РАН и отдела математического программирования ИММ.
Публикации. По теме диссертации автором опубликовано 26 научных работ, среди них 7 в журналах из списка ВАК.
Структура и объем работы. Диссертация состоит из введения, трех глав, списка обозначений и сокращений, заключения и списка литературы. Главы разбиты на 19 параграфов, некоторые из которых разделены на пункты. Нумерация утверждений и формул тройная и однозначно указывает на главу, параграф в главе и номер утверждения (формулы). Общий объем работы — 253 страницы. Библиография содержит 245 наименований.
