Авторефераты по всем темам >>
Авторефераты по разное
На правах рукописи
скарин владимир дмитриевич
АППРОКСИМАЦИОННЫЕ И РЕГУЛЯРИЗИРУЮЩИЕ СВОЙСТВА ШТРАФНЫХ ФУНКЦИЙ И ФУНКЦИЙ ЛАГРАНЖА В МАТЕМАТИЧЕСКОМ ПРОГРАММИРОВАНИИ
01.01.09 - дискретная математика и математическая кибернетика
Автореферат диссертации на соискание ученой степени доктора физико-математических наук
Екатеринбург - 2010
Работа выполнена в Учреждении Российской академии наук Институте математики и механики Уральского отделения РАН
Научный консультант: академик РАН Еремин Иван Иванович
Официальные оппоненты: доктор физико -математических наук член-корреспондент РАН Васин Владимир Васильевич, доктор физико -математических наук профессор Заботин Ярослав Иванович, доктор физико -математических наук профессор Колоколов Александр Александрович.
Ведущая организация: Вычислительный центр РАН.
Защита состоится У 15 Ф декабря 2010 г. в 15 часов на заседании диссертационного совета Д 004.006.04 в Институте математики и механики УрО РАН по адресу: 620219, г. Екатеринбург, ул.
С.Ковалевской, 16.
С диссертацией можно ознакомиться в библиотеке Института математики и механики УрО РАН.
Автореферат разослан У Ф 2010 г.
Ученый секретарь диссертационного совета доктор физико-математических наук Л.Д. Попов
Общая характеристика работы
Диссертационная работа посвящена построению и исследованию свойств методов численного анализа задач математического программирования (МП), основанных на применении различных модификаций штрафных функций и функций Лагранжа. Основное внимание при этом уделяется задачам оптимизации с особенностями, прежде всего, несобственным и некорректно поставленным.
Актуальность темы. Метод штрафных функций является универсальным средством решения экстремальных задач различной природы.
Метод порождает целое семейство вычислительных процедур, а также служит эффективным инструментом теоретического анализа задач оптимизации.
Активные исследования в области метода штрафных функций ведутся с начала 60-х годов прошлого столетия. Методу посвящено большое количество работ, как отечественных авторов (Ф.П.Васильев, В.Ф.Демьянов, Ю.Г.Евтушенко, И.И.Еремин, В.Г.Жадан, Я.И.Заботин, Б.Т.Поляк, В.В.Федоров и др.), так и зарубежных (А.Ауслендер, М.Базара, У.Зангвилл, Ф.Лутсма, Г.Маккормик, О.Мангасариан, А.Фиакко, Р.Хьюард и др.).
Важное значение при этом имеет метод точных штрафных функций, предложенный в 1966 году И.И.Ереминым. Данный метод позволяет в принципе свести решение исходной условноэкстремальной задачи к однократной минимизации без ограничений некоторой вспомогательной функции. Проблема построения таких функций и нахождения условий точности для различных классов задач МП занимает заметное место в специальной литературе и продолжает оставаться актуальной.
Хорошо известны вычислительные трудности при численной реализации метода штрафных функций, связанные с асимптотическим характером сходимости. Один из возможных путей преодоления этих трудностей предлагают методы модифицированной функции Лагранжа (методы множителей, штрафных оценок). Эти методы, с одной стороны, расширяют возможности стандартной функции Лагранжа, играющей центральную роль в теории МП, с другой являются определенным обобщением метода штрафных функций. Исследования в этой области, начатые в 1969 году М.Хестенсом и М.Пауэллом, были развиты многими авторами (А.С.Антипин, Д.Бертсекас, А.И.Голиков, Е.Г.Гольштейн, Ю.Г.Евтушенко, В.Г.Жадан, Б.Т.Поляк, Р.Рокафеллар, Н.В.Третьяков и др). Был предложен достаточно широкий спектр модификаций функции Лагранжа и численных алгоритмов, основанных на ее применении.
Современные тенденции в развитии методов штрафных функций и модифицированных функций Лагранжа состоят как в нахождении новых перспективных конструкций вспомогательных функций (например, сочетающих свойства функции Лагранжа и барьерных функций), так и в максимальном расширении сферы применения этих функций. В первую очередь, это касается построения новых алгоритмов для анализа таких классов задач МП, как невыпуклые, негладкие, нестационарные, бесконечномерные, многокритериальные, полуопределенные, билинейные, несобственные, некорректные и задачи большой размерности.
В настоящей работе основное внимание уделяется анализу методов штрафных функций и модифицированных функций Лагранжа применительно к несобственным и некорректным задачам линейного и выпуклого программирования.
Несобственные задачи (НЗ) МП характеризуются тем, что для них не выполняются соотношения двойственности. Свойство несобственности тесно связано с совместностью систем ограничений исходной задачи и двойственной к ней. Поэтому о несобственных задачах говорят в более узком смысле как о задачах МП с противоречивыми ограничениями. Интерес к противоречивым моделям обусловлен как потребностями математической теории (анализ систем уравнений и неравенств, некорректные задачи, задачи идентификации, распознавания образов и др.), так и необходимостью анализа прикладных задач с противоречивыми условиями, прежде всего экономических, где появление несовместных моделей обычное явление. Распространенность и актуальность несобственных задач порождает острую потребность в разработке теории и методов их численной аппроксимации.
Определение НЗ МП и систематическое исследование таких задач было инициировано в начале 80-х годов прошлого века работами уральской школы по МП, возглавляемой академиком И.И.Ереминым.
Впоследствии эта тема получила широкое отражение в специальной литературе (работы Н.Н.Астафьева, В.А.Булавского, А.А.Ватолина, В.А.Горелика, И.И.Еремина, В.И.Ерохина, А.В.Зыкиной, М.М.Ковалева, В.Д.Мазурова, Л.Д.Попова, Н.В.Третьякова, М.Ю.Хачая и др.).
Многие важные в прикладном отношении задачи планирования, проектирования и управления являются некорректно поставленными. Решения таких задач не зависят непрерывно от входной информации. Поэтому нельзя быть уверенным, что приближенное решение задачи будет близким к точному и, следовательно, требуются специальные методы регуляризации, которые обеспечивали бы сходимость генерируемой итерационной последовательности к искомому множеству решений.
Начало исследований теории и методов некорректных задач связано с именами А.Н.Тихонова, В.К.Иванова, М.М.Лаврентьева. Дальнейшее развитие данная проблематика получила в работах А.Л.Агеева, А.С.Антипина, А.Б.Бакушинского, Ф.П.Васильева, В.В.Васина, Д.В.Денисова, В.Г.Карманова, В.А.Морозова, В.П.Тананы, А.Г.Яголы и др. К этому направлению также тесно примыкают исследования по устойчивости задач МП (работы Н.Н.Астафьева, А.Ауслендера, С.А.Ашманова, И.И.Еремина, Ю.Гуддата, С.Злобека, Е.С.Левитина, В.В.Федорова, А.Фиакко для непрерывных задач МП, В.А.Емеличева, А.А.Колоколова, И.В.Сергиенко для дискретного случая).
Таким образом, диссертационная работа, посвященная развитию теории метода штрафных функций, построению новых модификаций функции Лагранжа и соответствующих алгоритмов с целью их применения для коррекции несобственных задач и регуляризации некорректных задач МП, лежит в русле актуальных современных исследований в области математической оптимизации.
Цель работы состоит в построении и исследовании свойств штрафных функций и модифицированных функций Лагранжа в математическом программировании. При этом решаются следующие задачи.
1. Построение различных модификаций метода штрафных функций (точных, асимптотически сходящихся, барьерных, расширенных) и их применение для оптимальной коррекции НЗ МП и регуляризации некорректных задач МП.
2. Исследование аппроксимационных и регуляризирующих свойств функции Лагранжа, регуляризованной по прямым и двойственным переменным, для различных классов задач МП.
3. Разработка новых конструктивных алгоритмов, основанных на применении штрафных функций и модифицированных функций Лагранжа для численного анализа НЗ МП и регуляризации некорректных задач оптимизации.
4. Развитие оценочного подхода при обосновании сходимости предлагаемых методов.
Научная новизна. Основные результаты диссертации являются новыми.
Построены новые общие конструкции штрафных функционалов и сформулированы условия точности и асимптотической сходимости метода штрафных функций как для разрешимой задачи выпуклого программирования (ВП), так и обеспечивающие оптимальную коррекцию задачи в случае ее несобственности. Введены новые перспективные расширения штрафных функций, обладающие характерными свойствами модифицированных функций Лагранжа. На основе предложенных вариантов штрафных и барьерных функций построен ряд итерационных алгоритмов, сходящихся к решению задачи, аппроксимирующей исходную несобственную постановку.
Получены оценки уклонений компонент седловой точки регуляризованной по прямым и двойственным переменным функции Лагранжа L(x, ) от решений исходной и двойственной задач ВП, в том числе, и для несобственных постановок. При этом исследованы различные по степени общности виды стабилизирующих добавок. Предложены и обоснованы два универсальных по отношению к типам несобственности подхода к оптимальной коррекции задач ВП, основанных на применении функции L(x, ).
Найдены условия управления параметрами регуляризации = [, ] функции L(x, ) в случае симметрической аппроксимации несобственных задач линейного и квадратичного программирования для нахождения нормальных решений соответствующей пары взаимно двойственных задач.
Исследованы регуляризирующие свойства ряда модификаций штрафных функций и функции L(x, ) в условиях неточно заданной информации об исходной задаче выпуклого программирования как для разрешимого, так и для несобственного случаев. Предложены новые варианты конструктивно реализуемого метода регуляризации для задач линейного и выпуклого программирования, использующие расширенные штрафные функции и функцию L(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 параграфов, некоторые из которых разделены на пункты. Нумерация утверждений и формул тройная и однозначно указывает на главу, паpагpаф в главе и номеp утверждения (фоpмулы). Общий объем работы 253 страницы. Библиография содержит 245 наименований.
Основное содержание работы
.
Во введении обосновывается актуальность темы диссертации, формулируются цели проводимых в ней исследований и научная новизна полученных результатов, кратко излагается содержание работы.
В главе 1 с единых позиций исследуются вопросы теории метода штрафных функций, в частности, условия точности и асимптотической сходимости ряда модификаций данного метода, а также их применимость для аппроксимации НЗ ВП.
В качестве исходной рассматривается задача ВП min{f0(x) : x X}, (1) где X = {x : f(x) 0}, f(x) = [f1(x),..., fm(x)], fi(x) выпуклые функции, определенные на Rn (i = 0, 1,..., m).
Данной постановке соответствует задача нахождения inf{F (x, r) = f0(x) + (x, r)} (= Fr ), (2) x где (x, r) функция штрафа за нарушение ограничений, определяющих множество X, r скалярный или векторный штрафной коэффициент ( r > 0 ).
В з 1.1 исследуются некоторые теоретические вопросы метода штрафных функций для задачи (1). В частности, здесь формулируются максимально общие условия на конструкцию штрафной функции, при которых она является точной. Пусть функция Лагранжа L(x, ) = f0(x) + (, f(x)), поставленная в соответствие задаче (1), имеет непустое множество X седловых точек в области Rn Rm. Положим в (2) + (x, r) = (z(x, r)), z(x, r) = [z1(x, r),..., zm(x, r)], zi(x, r) = rifi+(x) (i = 1,..., m), r = [r1,..., rm] > 0, где = (z) выпуклая функция, определенная на Rm, удовлетворяет условиям + (0) (0) = 0, inf = > 0, zS z (0) производная от (z) в точке z = 0 по направлению z, S = z {z Rm : z = 1}.
+ Теорема 1.1.1. В сформулированных выше условиях F (x, r) является точной штрафной функцией для задачи (1) с множеством оптималь m} ( ных параметров R = {r Rm : r + т.е. Fr = f = f0(x) m то X = X(r), при r R, x X), где . Если r >, где X(r) множество точек минимума в задаче (2).
Данная теорема справедлива для общей задачи математического программирования (т.е. без предположения выпуклости функций fi(x), i = 0, 1,..., m ). Она обобщает известные факты для классических видов точных штрафных функций таких, как функция ЕреминаЦЗангвилла m F (x, r) = f0(x) + rifi+(x).
i=В следующем утверждении (теорема 1.1.2) приводятся достаточно общие условия для штрафной функции, обеспечивающие асимптотическую сходимость метода. Этим условиям удовлетворяет, например, функция m p F (x, r) = f0(x)+ rifi+ (x), p > 1, которая становится далее объектом i=более подробного рассмотрения. В теореме 1.1.3 устанавливаются оценки скорости сходимости метода, основанного на применении этой функции, обобщающие классические результаты для квадратичной штрафной функции (p = 2). Анализ полученных оценок показывает, что имеет смысл согласованно изменять параметры r0 = min ri и p. В итерациi онном процессе метода штрафных функций рационально выбирать параметры p и r0, например, так: pk = 1 + k, (r0)k = -1, k > 0, k lim k = 0. Если функции fi(x), i = 0, 1,..., m, в задаче (1) диффеk ренцируемы, то F (x, (r0)k) будет приближать в пределе точную штрафную функцию, оставаясь при этом дифференцируемой для любого k.
Следующий раздел (з 1.2) посвящен применению метода штрафных функций для оптимальной коррекции НЗ ВП. При этом используется идея ранжирования ограничений. Возможно несовместная система ограничений задачи (1) разбивается на две части и определяет два множества X1 = {x : fi(x) 0, i = 1,..., m}, X2 = {x : fi(x) 0, i = m + 1,..., m + l}, одно из которых ( X2 ) заведомо непусто. Строится штрафная функция F (x, r), которая агрегирует целевую функцию f0(x) с функциями-ограничениями из X1, и далее она минимизируется на множестве X2. Для задачи (1) строится следующая аппроксимационная постановка min{f0(x) : (x) , x X2}, (3) где = inf{(x) : x X2}, (x) функция штрафа за нарушение ограничений, определяющих множество X1. При этом (x) = (z(x)), z(x) = [z1(x),..., zm(x)], zi(x) = ifi+(x), i > 0, i = 1,..., m ;
(z) выпуклая неубывающая функция, определенная на Rm, (0) = + m pi 0, (z) = (z1,..., zm) zi, > 0, pi 1, i = 1,..., m. Для i=задачи (1) вводится условие -ограниченности: существуют q индексов из m + l таких, что множество S = {x : fis(x) , s = 1,..., q} непусто и ограничено, R1.
Теорема 1.2.1. Пусть для задачи (1) выполнено условие -ограни ченности и f0(x) f > - ( x X2). Тогда 1. X = , где X множество решений задачи (3).
2. Для любого r > 0 задача inf{F (x, r) = f0(x) + r(x) : x X2}, r > 0, разрешима в некоторой точке x(r).
3. При r выполняются соотношения f0(x(r)) f, (x(r)) , (x(r), X) 0, где f оптимальное значение задачи (3).
Далее аналогичный факт доказывается при замене условия -ограни ченности на условие существования седловой точки у функции Лагранжа для аппроксимирующей задачи (теорема 1.2.3). Обе теоремы уточняются на случай, когда задача min F (x, r) решается приближенно (теоxXремы 1.2.2 и 1.2.4). Для обеспечения свойств регулярности аппроксимирующей задачи применяется идея -расширения1 ее ограничений (теорема 1.2.5). Наконец, в теореме 1.2.6 определяются условия сходимости метода, когда штрафная функция включает все ограничения исходной задачи.
В з 1.3 показывается, что проблема коррекции НЗ ВП из з 1.2 может быть интерпретирована как трехэтапная задача лексикографической минимизации или, в другой терминологии, как задача последовательного программирования. Формулируется теорема 1.3.1, в которой конкретизируются функции векторного критерия, условия на исходную задачу и Еремин И.И. О задачах выпуклого программирования с противоречивыми ограничениями // Кибернетика, 1971. Ц№ 4. ЦC. 124Ц129.
требования на согласование параметров скаляризации, которые обосновывают данный подход.
В з 1.4 речь идет о расширенной штрафной функции m m F (x, , r) = f0(x)+ ifi(x)+r fi+ (x), = [1,..., m] 0, r > 0.
i=1 i=В свое время она была введена автором2 в целях улучшения свойств сходимости метода квадратичной штрафной функции при r . Теперь же исследуются возможности функции F (x, , r) для оптимальной коррекции НЗ ВП 1-го рода (случай, когда X = , = , где = { Rm : inf L(x, ) > -}. Исходная несобственная постановка + x ВП аппроксимируется следующей задачей min{f0(x) : x X}, (4) где X {x : f(x) }, = arg min{ : Rm, X = }. В + предположении существования седловой точки [x, ] функции Лагран жа для задачи (4) в теореме 1.4.1 установлены оценки, связывающие решение x задачи ,r min F (x, , r) (5) x .
с векторами x, и Из этих оценок следует, что сходимость метода будет иметь место не только при r , но и при .
Следующий з 1.5 посвящен рассмотрению близкой к F (x, , r) функции F1(x, , r) = f0(x) + (, f+(x)) + r f+(x), Rm, r > 0.
+ Функция F1(x, , r) является, очевидно, определенной модификацией штрафной функции, а именно, она представляет собой комбинацию классических точной и квадратичной штрафных функций. Теорема 1.5.1 показывает, что F1(x, , r) комбинирует и свойства сходимости этих функций в случае разрешимой задачи ВП.
Скарин В.Д. Об одной модификации метода штрафных функций в выпуклом программировании // Нелинейная оптимизация и приложения в планировании. ЦСвердловск: УН - АН СССР, 1973. ЦС. 51Ц62.
Сформулируем задачу min F1(x, , r) (= F,r). (6) x Теорема 1.5.1. Пусть в задаче (1) X = , x X, , f0(x) = f. Справедливы соотношения - 2 F,r f ( 0, r > 0);
(1) f 4 r (2) F,r = f ( , r > 0);
(3) X(, r) = X ( > , r > 0), где X(, r) = Arg min F1(x, , r).
x Если X(, r) = и x,r X(, r), то - (4) f+(x,r) ( 0, r > 0);
r - (5) 0 f - f0(x,r) ( 0, r > 0).
r Соотношения (1)Ц(5) теоремы 1.5.1 показывают, что для малых основной вклад в сходимость метода дает квадратичная составляющая r f+(x), а при больших F1(x, , r) ведет себя как точная штрафная функция. С другой стороны, если функция L(x, ) для исходной задачи ВП имеет непустое множество X седловых точек в области Rn Rm, то согласно теореме 1.5.2 функция F1(x, , r) при любом фик+ сированном r > 0 будет обладать непустым множеством X ( +Rm) + седловых точек в этой же области. Таким образом, F1(x, , r) является и модифицированной функцией Лагранжа. Соответственно, F1(x, , r) может использоваться для построения эффективных итерационных алгоритмов. В з 1.5 приводится и обосновывается (теорема 1.5.5) вариант метода множителей3, построенный на основе применения функции F1(x, , r). Наконец, по аналогии с F (x, , r) из з 1.4 функция F1(x, , r) может использоваться для оптимальной коррекции НЗ ВП.
Пусть (1) НЗ ВП 1-го рода, для которой построена аппрокси мирующая задача (4), [x, ] седловая точка функции L(x, ) = f0(x) + (, f(x) - ) в области Rn Rm.
+ Bertsekas D.P. Multiplier methods: a survey // Automatica, 1976. ЦVol. 12, no. 2. ЦP. 133Ц145.
Теорема 1.5.4. Пусть задача (6) разрешима в точке x,r. Справед ливы оценки - - f+(x,r) - , |f0(x,r) - f0(x)| C(), r r где C() = max{ , }.
з 1.6 посвящен применению оценочного подхода в методе барьерных функций (методе внутренних штрафных функций). Очевидное преимущество таких функций перед классическими функциями (внешнего) штрафа состоит в высокой степени гладкости вспомогательной функции (в случае дифференцируемости fi(x), i = 1,..., m ), что позволяет использовать при численной реализации итеративные методы минимизации высокого порядка. В качестве вспомогательной функции рассматривается следующее обобщение обратной барьерной функции:
m i B(x, ) = f0(x) +, |fi(x)|pi i=где = [1,..., m] > 0, pi 1, i = 1, m.
Теорема 1.6.1. Пусть в задаче (1) X = , X0 = , где X0 = {x : f(x) < 0}. Тогда существуют константы C1, и вектор Rm такие, что для любых 0 < выполняются неравенства 0 B - f < C1 max , i i где f и B оптимальные значения задач (1) и inf B(x, ) соотxXветственно, 0 < min 1 + pi.
i Теорема 1.6.4. Если в (1) f0(x) сильно выпуклая функция, то i 1/pi C4 min < x() - x < C3 max /2, i i i max i i где x и x() решения задачи (1) и задачи inf B(x, ) соответxXственно, C3, C4 положительные константы.
Здесь же выводятся оценки для приближений двойственных переменных (теоремы 1.6.2 и 1.6.5). Полученные оценки применяются для решения вопроса об управлении штрафным коэффициентом с целью обеспечения сходимости метода барьерных функций к решению исходной задачи со скоростью геометрической прогрессии, как по функции (теорема 1.6.6), так и по аргументу (теорема 1.6.7).
В з 1.7 показано, что, как и в случае метода штрафов, барьерные функции могут применяться для оптимальной коррекции несобственных задач МП. Предлагаются два итерационных алгоритма численного анализа НЗ ВП, основанных на использовании обратной барьерной функции. Идея алгоритмов состоит в построении на каждой итерации некоторого расширения аппроксимационной задачи вида (4) и учета ее ограничений с помощью барьерной функции. Алгоритмы различаются, прежде всего, различными способами управления изменяющимися параметрами: штрафным коэффициентом и параметрами, определяющими степень расширения допустимого множества задачи (4). Соответствующие утверждения о сходимости алгоритмов представлены в теоремах 1.7.1 и 1.7.2.
Алгоритм 1.7.1. Пусть x0 произвольная точка из Rn, {k}, {k} последовательности положительных чисел такие, что k+1 < k, lim k = lim k = 0. Положим k k 0 = f+(x0), 0 = 0, 0 (0, 1), Y0 = {x : fi(x) 0 + o, i = 1, m}.
Опишем (k + 1) -ю итерацию алгоритма, считая известными точку xk Rn, параметры k > 0, k > 0, k > 0, k > 0 и множество Yk0 = {x : fi(x) < k + k, i = 1, m}. Построим функцию m k Bk(x) = f0(x) +.
k + k - fi(x) i=Определим точку xk+1 Yk0 согласно условию Bk(xk+1) - Bk(xk+1) < k, где xk+1 = arg min {Bk(x) : x Yk0}.
Положим k+1 = f+(xk+1). Выберем число k+1 по правилу 0 < k+1 < min {k - k+1 + k, k+1}.
Теорема 1.7.1. Пусть задача (1) НЗ ВП 1 -го рода и k = o(k).
Тогда lim Bk(xk+1) = lim f0(xk+1) = f, k k где f оптимальное значение аппроксимирующей задачи (4), в ко торой = [,..., ], = min f+(x).
x Объектом исследований в главе 2 являются аппроксимационные и регуляризирующие свойства модифицированной функции Лагранжа L(x, ) = L(x, ) + (x) - (), где L(x, ) стандартная функция Лагранжа для задачи (1), = [, ] > 0, (x), () выпуклые неотрицательные функции, определенные на Rn и Rm соответственно. Предполагается, что лебеговы множества M(C) = {x Rn : (x) C}, N(C) = { Rm : () C} функций (x) и () ограничены для любых C 0. Типичными при2 мерами функций (x), () служат: (x) = x, () = . В терминах методов регуляризации некорректных экстремальных задач функция (x) называется стабилизатором для исходной задачи ВП (1), а функция () стабилизатором для задачи, двойственной к (1). Поэтому функцию L(x, ) можно называть стабилизированной или регуляризованной по прямым и двойственным переменным функцией Лагранжа.
В з 2.1 исследуется случай разрешимой задачи ВП. Вначале в п. 2.1.рассматривается общая конструкция стабилизирующих функций (x) и (). При этом показано, что при условии существования седловой точки [x, ] функции L(x, ) таковым же свойством обладает и L(x, ) для любого > 0 (теорема 2.1.1). Связь между седловыми значениями функций L(x, ) и L(x, ) устанавливается в теореме 2.1.2.
Теорема 2.1.2. Пусть для задачи (1) существует [x, ] седловая точка функции L(x, ) в области Rn Rm. Тогда для любого > + справедливы оценки f - () L(x, ) f + (x), где [x, ] седловая точка функции L(x, ) в области Rn Rm, + f = L(x, ) = f0(x).
Далее в п. 2.1.2 в целях конкретизации характера сходимости предлагаемого метода регуляризованной функции Лагранжа полагается (x) = 2 x, () = . Если теперь на основе L(x, ) определить прямую и двойственную функции (x) = sup L(x, ), () = inf L(x, ), x то (x) будет сильно выпуклой на Rn, а () сильно вогнутой на Rm, и поэтому для любого > 0 будет существовать единственная + седловая точка функции L(x, ) в области Rn Rm. Несложными + выкладками можно показать, что 2 (x) = f0(x) + f+(x) + x.
4 Таким образом, оказывается, что регуляризация функции Лагранжа по двойственным переменным с помощью добавки - эквивалентна применению для исходной задачи функции квадратичного штрафа.
Это позволяет при выводе оценок для [x, ] использовать методику, которая применялась при обосновании метода штрафов. В теореме 2.1.такие оценки показывают характер приближения точки x к решению задачи (1) по функциям-ограничениям и по целевой функции.
Теорема 2.1.4. Пусть выполнены условия теоремы 2.1.2 и (x) = 2 x, () = . Справедливы оценки f+(x) 2 C1(), | f0(x) - f | C2(), 2 2 2 где C1() = ( x + )1 / 2, C2() = 2 x + 3 .
Следствие 2.1.3. Пусть множество X решений задачи (1) ограничено. Тогда (x, X) 0 ( 0), где (x, S) = inf x - y.
yS Следствие 2.1.4. Пусть 0, = o (). Тогда x x, где x 0 нормальное решение задачи (1) : x = arg min { x : x X}.
Теорема 2.1.5. Пусть функции fi(x) в задаче (1) дифференцируемы на Rn (i = 0, 1,..., m). Для произвольного > 0 справедливы оценки L(x, ) 2 C1(), x 0 fi(x) 2 C12(), i = 1, m, i где = [,..., ], C1() из теоремы 2.1.4.
1 m Следствие 2.1.5. Пусть задача (1) имеет единственное решение x и 0, = o (). Тогда , где минимальный по норме 0 вектор множителей Лагранжа, соответствующий решению x.
В следующем п. 2.1.3 несколько усложняется структура стабилизирующих добавок. А именно, рассмотрен случай, когда n m (x) = aj|xj|p, () = biq;
i j=1 i=aj > 0, j 1, n; bi > 0, i 1, m; p = 1 + , q = 1 + , , > 0.
Показано, что в зависимости от вида () меняется структура функции (x) вместо квадратичного штрафа появляется сумма слагаеq мых fi+(x) в степени, т.е. возникает, если не учитывать стабилизатор (x), асимптотическая штрафная функция, подобная той, которая рассматривалась в з 1.1. Оценки, приводимые в теореме 2.1.6, показывают, как характер сходимости метода зависит от изменения стабилизирующих добавок (x) и () и как можно распорядиться параметрами метода для улучшения этой сходимости.
з 2.2 посвящен исследованию метода регуляризованной функции Лагранжа применительно к несобственным задачам ВП. Согласно классификации4 НЗ ВП в зависимости от пустоты или непустоты допустимых множеств X в задаче (1) и = { Rm : inf L(x, ) > -} в + x двойственной к (1) задаче различают три рода НЗ ВП: 1-го рода, если Еремин И.И., Мазуров В.Д., Астафьев Н.Н. Несобственные задачи линейного и выпуклого программирования. ЦМ.: Наука, 1983. Ц336 с.
X = , = ; 2-го рода, если X = , = ; 3-го рода, когда X = , = .
Вначале рассматривается случай несобственности 1-го рода. Задаче ВП (1) ставится в соответствие проблема нахождения седловых точек 2 [x, ] функции L(x, ) с (x) = x, () = . Как отмечалось выше, такая функция при любом > 0 имеет единственную седловую точку в области Rn Rm. Причем этот факт справедлив независимо от + того, является задача (1) собственной или нет. В этом L(x, ) существенно отличается от стандартной функции L(x, ), которая заведомо не имеет седловых точек, если X = .
В теореме 2.2.1 устанавливается, что для НЗ ВП 1-го рода характер сходимости {x} к решению аппроксимирующей задачи (4) аналогичен сходимости {x} к решению задачи (1) в случае разрешимости последней.
Теорема 2.2.1. Пусть для задачи (4) выполнены условия Куна - Таккера : существуют векторы x X, Rm, для которых + L(x, ) = 0, (, f(x) - ) = 0. Тогда x )+ | (f(x) - K1(), | f0(x) - f K2(), 2 2 где K1() = 2 [ + ( x + ) ], K2() = max { x, K1() }, f = f0(x).
.
Отсюда следует, что lim f+(x) = Далее найдены условия, при которых последовательность {x} сходится к нормальному решению задачи (4) (теорема 2.2.2). В теореме 2.2.оценивается скорость этой сходимости. Показано, что она имеет порядок O( /). Оценки из теоремы 2.2.4 устанавливают степень выполнения для [x, ] условий КунаЦТаккера для задачи (4). В силу этой теоремы и теоремы 2.2.1 lim L(x, ) = lim L(x, ) = +. Этот факт мо0 жет служить индикатором несовместности системы ограничений задачи (1), поскольку при = 0 L(x, ) f. И, наконец, заключительная теорема 2.2.5 характеризует сходимость двойственной составляющей .
В п. 2.2.2 рассматривается общий случай несобственности задачи ВП.
Здесь обосновывается универсальный подход к оптимальной коррекции НЗ ВП независимо от рода несобственности, основанный на применении функции L(x, ). Суть подхода заключается во введении дополнительного звена, помимо задачи (4), в цепь, связывающую исходную задачу (1) и задачу отыскания седловой точки функции L(x, ). Это звено представлено задачей, близкой к (1):
min{F(x) = f0(x) + x : x X}, (7) где > 0. Если X = , то задача (7) разрешима в единственной точ ке x, если же X = , то легко видеть, что задача (7) может быть несобственной только 1-го рода независимо от характера несобственности исходной задачи (1). Данное обстоятельство позволяет обосновать предлагаемый метод с помощью результатов п. 2.2.1.
Вначале решается вопрос о близости задачи (1) и задачи min{f0(x) + (x) : x X}, где > 0, (x) некоторый стабилизатор. Результаты представлены в леммах 2.2.2 и 2.2.3.
Если теперь для задачи (7) составить функцию L(x, ), то в ней появится слагаемое ( + ) x, т.е. возникнет дополнительный управляющий параметр .
Теорема 2.2.6. Пусть задача (1) разрешима и регулярна. Тогда 1 2 2 x - x x + , 0 где 0 < , 1 = -, x = arg min{ x : x X}, X множество решений задачи (1), вектор множителей Лагранжа в задаче (7), соответствующий решению x.
Следствие 2.2.6. Образуем последовательности положительных чиk сел k, 1, k так, чтобы k 1 k lim k = lim = lim = 0.
k k k k k Тогда xk x (k ).
Аналогичным образом можно доказать и сходимость к решению задачи, двойственной к (1) (теорема 2.2.7 и следствие 2.2.7).
Если (1) НЗ ВП, то введем аналог аппроксимации (4) для задачи (7):
min{F(x) : x X}, где имеет тот же смысл, что и в (4). Сходимость результирующего метода выражает следующий факт.
Следствие 2.2.8. lim lim F(x) = f, 1 где f оптимальное значение задачи (4).
Это утверждение справедливо для задач ВП произвольного рода несоб ственности (т.е. включая случай f = - ).
В з 2.3 метод регуляризованной функции Лагранжа применяется для несобственных задач линейного программирования (ЛП). Для пары взаимно двойственных задач ЛП min{(c, x) : Ax b, x 0}, (8) max{(b, u) : AT u c, u 0} (9) строится их симметрическая аппроксимация min{(c + , x) : Ax b + , x 0}, (10) max{(b + , u) : AT u c + , u 0}, (11) где Rm, Rn выбраны так, чтобы допустимые множества задач + + (10) и (11) были непусты (этого достаточно для разрешимости этих задач и совпадения их оптимальных значений), а также, чтобы они были минимальны по норме среди всех и , обладающих этими свойствами.
В отличие от общей задачи ВП для задачи ЛП можно определить явным образом не только функцию (x) = sup L(x, ), но и () = 1 2 inf L(x, ) : () = -(b, ) - (AT (-) - c)+ - .
4 xЕремин И.И., Мазуров В.Д., Астафьев Н.Н. Несобственные задачи линейного и выпуклого программирования. ЦМ.: Наука, 1983. Ц336 с.
Это позволяет получать оценки сходимости, симметричные для x и для .
Теорема 2.3.1. Для любого > 0 компоненты седловой точки [x, ] функции L(x, ) удовлетворяют неравенствам (Ax - b - )+ 1/2 h2(), [AT (-) - c - ]+ 1/2 h3(), max{|(c + , x) - f|, |(b + , -) - f|} h0 h4(), где x = arg min{ x : x X}, u = arg min{ u : u U}, 0 2 h0 = max{ x, u }, h1() = ( x + u )1/2, f = (c+, x) = 0 0 0 0 (b + , u), h2() = 1/2 u + h1(), h3() = 1/2 x + h1(), 0 0 h4() = max{1/2 x h3(), 1/2 u h2()}, X, U множества ре0 шений задач (10) и (11) соответственно.
Если 0, то отсюда следуют сходимости (x, X) 0, (-, U) 0. Из этой же теоремы следует практический способ определения характера несобственности задачи ЛП (8). Если при будет (c, x) f, (b, -) f, то это случай разрешимой задачи (8); если (c, x) f, (b, -) +, то (8) НЗ ЛП 1-го рода;
(c, x) -, (b, -) f НЗ ЛП 2-го рода; если (c, x) -, (b, -) +, то (8) НЗ ЛП 3-го рода.
Последующие теоремы 2.3.2 и 2.3.3 уточняют характер сходимости последовательностей x и . Так, для x имеет место следующее утверждение.
Теорема 2.3.2. Существует число 0 > 0 такое, что при (0, 0] и произвольном > 0 справедливо x - x (/)1/2 u, где x = Pr (/(2)). (12) 0 X Соответственно, сходимость характеризует Теорема 2.3.3. Существует число 0 > 0 такое, что при (0, 0] и произвольном > 0 справедливо + u (/)1/2 x, где u = Pr (-/(2)).
0 U Развитый выше подход является универсальным в том смысле, что применим ко всем задачам ЛП, независимо от рода их несобственности.
В частности, если задача (8) разрешима ( = 0, = 0 ), то в (12) x = x = Pr 0, и эта оценка характеризует сходимость x к нормальному 0 X решению задачи (8).
Идея симметрической аппроксимации задачи ЛП в з 2.4 переносится на случай задачи квадратичного программирования:
min (Qx, x) + (d, x) : Ax b, (13) где Q симметрическая неотрицательно определенная матрица порядка n.
Аналогом задач (10) и (11) здесь будут min (Qx, x) + (d - , x) : Ax b + , (14) max - (Qx, x) - (b + , ) : Qx + AT + d = , 0, (15) где Rm, Rn минимальные по норме векторы, обеспечива + ющие непустоту допустимых множеств задач (14) и (15). По аналогии с з 2.3 устанавливаются оценки, характеризующие близость компонент седловой точки [x, ] к решениям задач (14) и (15) по функциям-ограничениям и целевым функциям (теорема 2.4.1) и затем уточняется характер сходимости переменных x (теорема 2.4.2) и (теорема 2.4.3).
В отличие от ЛП оценки сходимости для x и в задаче квадратичного программирования теряют свою симметрию. Так, утверждение для выглядит следующим образом.
Теорема 2.4.3. Существует число 0 такое, что для (0, 0] и произвольного > 0 справедливо неравенство 2 - x + C x - x, где = Pr, x X, C неотрицательная константа, X 2 оптимальное множество задачи (14), соответствующее множество множителей Лагранжа.
Следствие 2.4.2. Пусть задача (14) имеет единственное решение x и 0, 0, = o (). Тогда (, ) 0.
В з 2.5 рассматривается несколько более общая по сравнению с (13) задача полноквадратичного программирования min{(c, x) : fi(x) 0, i = 1, m}, (16) где fi(x) = (Qix, x)+(di, x)+ei, c, di Rn, ei R1, Qi симметрические неотрицательно определенные матрицы порядка n ( i = 1, m ).
Если предположить, что среди Qi имеется хотя бы одна положительно определенная матрица, то (16) может быть несобственной задачей ВП только 1-го рода. Поэтому для этой задачи можно воспользоваться результатами з 2.2. Уточнения касаются разве что двойственной сходимости, поскольку двойственная задача для (16) может быть выписана явным образом. Особо рассматривается случай, когда не достигается супремум двойственной функции. Если среди матриц Qi нет положительно определенных, то к ограничениям задачи (16) можно добавить дополнительное неравенство x r, где r > 0. Такой прием фактически порождает новый способ коррекции НЗ ВП, исследованию которого посвящен з 2.6.
Новый подход заключается в построении особой аппроксимирующей задачи для НЗ ВП вида (1). Для этого определяется множество Sr = {x :
x r} и вектор r = arg min{ : XSr = }, где r > 0, Rm, X = {x : f(x) }. Затем для (1) строится аппроксимирующая задача min{f0(x) : x Xr Sr}. (17) Далее исследуется связь между задачей (17) и проблемой нахождения седловых точек [x, ] функции L(x, ) в области Sr Rm. При r r + этом рассматриваются два случая: 1) r = 0 ( r) ; 2) X = . В первом случае мы имеем дело с НЗ ВП 1-го рода и поэтому с незначительными изменениями можем применить общие результаты п. 2.2.1.
Так что основное внимание уделяется случаю 2), когда inf f0(x) = f не xX достигается. Примером полученных результатов может служить Теорема 2.6.2. Если в задаче (1) X = и точка [x, ] удовлетво r r ряет условиям КунаЦТаккера для задачи (17) при r = 0, то f0(x) - L(x, ) f0(x) + r r r r r r для всех = [, ] > 0 и достаточно больших r > 0.
Если при этом параметры метода согласовать следующим образом:
0, r +, r 0, r 0, то L(x, ) f (теорема r r 2.6.4).
В заключение з 2.6 обсуждается вопрос о связи обсуждаемого здесь подхода к оптимальной коррекции НЗ ВП и общим подходом из п. 2.2.2.
Глава 3 посвящена детальному исследованию регуляризирующих свойств рассмотренных ранее методов: штрафных и барьерных функций, расширенных штрафных функций и регуляризованной функции Лагранжа. Сразу заметим, что ряд доказанных в предыдущих главах результатов уже имел отношение к регуляризации некорректных задач ВП и ЛП. Особенно это касается применения функции L(x, ) из главы 2. Фактически те утверждения, где речь шла об условиях сходимости последовательностей x и к нормальным решениям исходной задачи и двойственной к ней, представляют собой теоремы о сходимости метода регуляризации, построенного на использовании функции L(x, ), для, в том числе, и некорректных задач оптимизации в случае точного задания функций цели и ограничений.
В з 3.1 исследуется метод штрафных функций применительно к регуляризации задач ВП. При этом для задачи (1) строится стабилизирующая функция Тихонова P (x, r, ) = F (x, r) + (x), где F (x, r) штрафная функция из з 1.1, (x) некоторый стабилизатор, > 0. Конструкция F (x, r) выбирается аналогично п. 1.1.(точная штрафная функция) и п. 1.1.2 (асимптотический случай). Соответствующие результаты о сходимости этих вариантов метода регуляризации приведены в теоремах 3.1.1 и 3.1.3.
Далее рассматривается случай, связанный с регуляризацией задач на множествах, заданных приближенно6. Предположим, что в (1) вместо Васильев Ф.П. Методы решения экстремальных задач. ЦM.: Наука, 1981. Ц400 c.
fi(x) известны непрерывные функции fi(x), определенные на Rn, такие, что |fi(x) - fi(x)| < , > 0 ( x Rn, i = 0, 1,..., m). (18) Поставим в соответствие задаче (1) проблему нахождения min P (x, r, ), (19) x + где P (x, r, ) = f0(x) + ri [fi (x)]p + (x), r = [r1,..., rm] > 0, p > 1, > 0, решение которой x будем находить с точностью 0 :
r, P (x, r, ) inf P (x, r, ) + .
r, x В теореме 3.1.4 установлены оценки уклонения точки x от решения r, задачи (1). Из этих оценок выводятся условия согласования управля ющих параметров , , r, , обеспечивающих сходимость x к Xr, множеству -нормальных решений задачи (1).
Следствие 3.1.3. Пусть в задаче (19) ri = r0 (i = 1,..., m). Если k, k, k, r0k положительные числовые последовательности такие, что lim k = lim k = lim k = lim = k k k k r0k p r0k k k k = lim = lim = lim = lim = 0, p k k k k k k k k r0k то lim (xk, X0) = 0 и любая предельная точка последовательности k xk = xk будет -нормальным решением задачи (1).
k,rk По аналогии со штрафными функциями для регуляризации некорректных задач ВП могут использоваться и барьерные функции. Соответствующие теоретические предпосылки для этого были приведены в з 1.6.
Заметим, что вопрос применения барьерных функций вместо штрафных в методе Тихонова в литературе исследован достаточно слабо. В з 3.исходной проблеме (1) ставится в соответствие задача m inf B(x, ) = f0(x) + + x 2 (= B,), xX0 |fi(x)|p i=где > 0, p 1, > 0, X0 = {x : f(x) < 0}. Доказываются утверждения (теоремы 3.2.1 и 3.2.2) о сходимости x(, ) = arg min B(x, ) и xX B, к нормальному решению x и оптимальному значению f задачи (1) соответственно.
В следующем з 3.3 для построения метода регуляризации используется функция L(x, ) из главы 2. В отличие от известных схем метода регуляризации данный подход позволяет оценить приближения не только к решению исходной задачи, но и к соответствующим множителям Лагранжа. Кроме того, метод применим и для анализа несобственных задач ВП. Содержание з 3.3 разбивается на две части: вначале в п. 3.3.исследуется случай разрешимой задачи ВП и в п. 3.3.2 рассматривается несобственная задача ВП. При этом предполагается, что информация о функциях fi(x) ( i = 0, 1,..., m ) в задаче (1) носит приближенный характер, т.е. вместо fi(x) известны непрерывные функции fi(x), удовлетворяющие неравенствам (18). Для приближенной задачи min{f0(x) : fi(x) 0, i = 1, m} строится регуляризированная по прямым и двойственным переменным функция Лагранжа L (x, ), получающаяся из L(x, ) заменой fi(x) на fi(x) (i = 1, m). Сильная вогнутость функции L (x, ) по позволяет явным образом выписать функцию (x) = max L (x, ).
Показано (теорема 3.3.1), что множество Arg min (x) непусто для x любых > 0, > 0. Далее оценивается степень близости точек x = arg min (x) и решений задачи (1) (теорема 3.3.2). Найдены усло x вия на параметры и , обеспечивающие сходимость точек x к мно жеству X решений задачи (1) (теорема 3.3.3) и к нормальному решению этой задачи (следствие 3.3.3). Условия сходимости двойственных переменных функции L (x, ) к минимальному по норме множителю Лагранжа для задачи (1) устанавливаются теоремой 3.3.5 и следствием 3.3.5.
В п. 3.3.2 описанный выше подход к регуляризации задачи (1) на основе функции L (x, ) распространяется на несобственную задачу ВП 1-го рода. Аналогично доказывается существование в этом случае точки x = arg min (x) (теорема 3.3.6), устанавливаются оценки уклонения x x от решения задачи (4) аппроксимации для (1) (теорема 3.3.7) и находятся условия сходимости x к нормальному решению (4) (теорема 3.3.8).
Теорема 3.3.8. Пусть для задачи (4) выполнены условия Куна - Таккера, 0, 0, 0, = o(), = o(). Тогда x x0, где x0 нормальное решение задачи (4) :
x0 = arg min x, X = Arg min f0(x).
xX xX Методы регуляризации задач ВП могут быть построены и на базе расширенных штрафных функций F (x, , r) из з 1.4 и F1(x, , r) из з 1.5.
Этому вопросу посвящен з 3.4. Здесь исследуются связи между задача2 ми inf{F (x, , r) + x } и inf{F1(x, , r) + x } и исходной задаx x чей (1), в том числе, несобственной. Используя аппарат доказательства, аналогичный тому, который применялся в зз 1.4Ц1.5, находим условия сходимости точек минимума регуляризованных расширенных штрафных функций к нормальному решению задачи (1) (теорема 3.4.1) или ее аппроксимации (4) (теоремы 3.4.2 и 3.4.3).
Теорема 3.4.3. Пусть в точке [x, ] для задачи (4) выполнены усло вия КунаЦТаккера, q Q = {q = [, r, ] RmR1 R1 : r > 0. > 0}, + + + xq = arg min{1(x, q) = F1(x, , r) + x }. Для любого q Q выпол x няются неравенства f+(xq)- D(q), |f0(xq)-f0(x)| x +max{ , } D(q), r + x 2 + -r.
где D(q) = 2 r Следствие 3.4.3. Пусть 0, 0. Тогда xq x0, где r x0 нормальное решение задачи (4).
На основе применения регуляризованных расширенных штрафных функций из предыдущего раздела можно строить конкретные итерационные процедуры для регуляризации задач МП. В з 3.5 предлагаются две конструктивно реализуемые алгоритмические схемы для задачи линейной оптимизации с использованием F(x, , r) = F (x, , r) + x.
Предлагаемые алгоритмы реализуют идею метода множителей, в котором для приближенного поиска минимума рассматриваемой функции производится конечное число шагов метода условного градиента. Первый алгоритм сходится (теорема 3.5.1) к нормальному решению исходной задачи ЛП и к некоторому решению двойственной задачи. Второй алгоритм применяется для численного анализа несобственной задачи ЛП.
Пусть (1) НЗ ЛП 1-го рода, f0(x) = (c, x), f(x) = Ax - b, A = (aij)mn, c, x Rn, b Rm, aij R1. Обозначим через X множество решений задачи (4), x0 = arg min{ x : x X}. Пусть x0 int, где = {x : x x x}, x, x фиксированные векторы из Rn.
Алгоритм 3.5.2. Пусть заданы x0 , 0 = 0, r0 > 1, 0 = 1.
Опишем k + 1 -й шаг, считая известными xk , k 0, rk > 0, k > 0. Обозначим xk = xk0. Вычислим |( Fk(xks), lks)| x xk(s+1) = xks + kslks, ks =, s = 0, 1,..., sk;
2 2 (r0 Alks + k lks ) ks ks Fk(x) = Fk(x, k, rk), lks = yks - xks, yks = [y1,..., yn ], + Fk(xks) 1, x > 0, ks yi = (xi - xi) sgn - + xi, sgn x = xi 0, x 0, sk = min{s1, s2}, s1 = min{s : ( Fk(xks), lks) = 0}, s2 = [ k ] +1, x k k k k > 1.
Положим xk+1 = xksk, k+1 = [k + k (Axk+1 - b)]+, k > 0, k+1 = (k + 1)-, rk+1 = (k + 1), > 0, > 0, > + .
Теорема 3.5.2. Пусть в алгоритме 3.5.2 k = , k < .
k=0 k=, Тогда lim (Axk - b)+ = lim xk = x0.
k k Методы регуляризации, рассмотренные в зз 3.1Ц3.4, являются теоретическими в том смысле, что в них, как правило, предполагается умение точно определять точку минимума заданной функции. Однако для этой цели может потребоваться бесконечное число итераций некоторого вспомогательного метода минимизации функций. В з 3.5 были построены алгоритмы, на каждой итерации которых для нахождения приближенного минимума регуляризованной расширенной штрафной функции использовалось конечное число sk шагов метода условного градиента.
Недостатками алгоритмов можно считать увеличение sk с ростом числа итераций k.
От этого недостатка свободны методы итеративной регуляризации, в которых для минимизации регуляризирующего функционала на каждой итерации обычно используют один шаг некоторого алгоритма безусловной оптимизации. При определенном согласовании параметров регуляризации и параметров вспомогательного алгоритма может быть обеспечена требуемая сходимость результирующего алгоритма.
В з 3.6 предлагается ряд реализаций принципа итеративной регуляризации для задач линейного и выпуклого программирования, основанных на применении регуляризованной функции Лагранжа L(x, ). Вначале строятся алгоритмы для задачи ЛП и двойственной к ней в условиях точного задания информации о функциях задач (алгоритмы 3.6.1 и 3.6.2).
Далее предлагается метод регуляризации для НЗ ЛП с приближенными данными (алгоритм 3.6.3), и в заключение обсуждается возможность применения подобных алгоритмов для противоречивых задач ВП (алгоритм 3.6.4).
Рассмотрим, как и в з 3.5, НЗ ЛП 1-го рода min{(c, x) : Ax b, x 0}.
Предположим, что в этой задаче вместо A, b, c известны их приближения A, b, c с погрешностью max{ A - A, b - b, c - c } , где 0, норма матрицы A согласована с x.
Алгоритм 3.6.3. Выберем произвольно x1 Rn. Определим + xk+1 = [(1 - 2kk)xk - k(2k)-1(Ak)T (Akxk - bk)+ - kck]+, k = 1, 2,..., k > 0, k > 0, k > 0, k > 0, где последовательности чисел k, k, k, k удовлетворяют условиям:
k k k+1 k lim k = lim = lim = 0, ( k), k k kk k kk k+1 k 2 kk k kk = , < , < , (kk) k < .
k k k=1 k=1 k=1 k=Теорема 3.6.3. Последовательность {xk}, определяемая согласно алгоритму 3.6.3, сходится к нормальному решению задачи min{(c, x) : Ax b + , x 0}.
где определяется как в (4).
В этом методе в качестве регуляризирующего функционала выступила функция 2 (x) = max{L (x, ) = (c, x) + (, Ax - b) + x - }, в качестве вспомогательного алгоритма метод проекции градиента.
При доказательстве сходимости здесь существенно использовались полученные в главе 2 оценки уклонений компонент седловых точек функции L(x, ) от решений соответствующих задач МП.
Основные результаты.
1. Построены общие конструкции штрафных функционалов и сформулированы условия точности и асимптотической сходимости метода штрафных функций как для разрешимой задачи ВП, так и обеспечивающие оптимальную коррекцию задачи в случае ее несобственности;
введены новые перспективные расширения штрафных функций, обладающие характерными свойствами модифицированных функций Лагранжа;
построен на основе предложенных вариантов штрафных и барьерных функций ряд итерационных алгоритмов, сходящихся к решению задачи, аппроксимирующей исходную несобственную постановку.
2. Получены оценки уклонений компонент седловой точки регуляризованной по прямым и двойственным переменным функции Лагранжа L(x, ) от решений исходной и двойственной задач ВП, в том числе, и для несобственных постановок;
исследованы различные по степени общности виды стабилизирующих добавок;
предложены и обоснованы два универсальных по отношению к типам несобственности подхода к оптимальной коррекции задач ВП, основанных на применении функции L(x, ).
3. Найдены условия управления параметрами регуляризации = [, ] функции L(x, ) в случае симметрической аппроксимации несобственных задач линейного и квадратичного программирования для нахождения минимальных по норме решений соответствующей пары взаимно двойственных задач.
4. Исследованы регуляризирующие свойства ряда модификаций штрафных функций и функции L(x, ) в условиях неточно заданной информации об исходной задаче ВП как для разрешимого, так и для несобственного случаев;
предложены новые варианты конструктивно реализуемого метода регуляризации для задач линейного и выпуклого программирования, использующие расширенные штрафные функции и функцию L(x, ) и основанные, в частности, на идее итеративной регуляризации.
5. При доказательстве аппроксимационных и регуляризирующих свойств различных модификаций штрафных функций и функции Лагранжа получил систематическое развитие оценочный подход, опирающийся, в первую очередь, на теорию двойственности для соответствующих классов задач оптимизации.
Публикации по теме диссертации [1] Скарин В.Д. К регуляризации минимаксных задач, возникающих в выпуклом программировании // Ж. вычисл. матем. и матем. физики, 1977. ЦT. 17, № 6. ЦC. 1408Ц14(перечень ВАК).
[2] Скарин В.Д. Об алгоритмах линейного программирования, использующих модификации функции Лагранжа. ЦВ кн. УМетоды для нестационарных задач математического программированияФ. ЦСвердловск: УН - АН СССР, 1979. ЦC. 74Ц83.
[3] Скарин В.Д. Об одном итерационном методе нахождения нормального решения задачи линейного программирования. ЦВ кн. УМетоды математического программирования и приложенияФ. ЦСвердловск: УН - АН СССР, 1979. ЦC. 20Ц25.
[4] Скарин В.Д. О некоторых методах анализа несобственных задач выпуклого и линейного программирования. ЦВ кн. УНесобственные модели математического программированияФ. ЦВИНИТИ, 1980. Ц№2823-80 Деп. ЦC. 187Ц234.
[5] Скарин В.Д. О скорости сходимости метода барьерных функций. ЦВ кн. УМетоды оптимизации и распознавания образов в задачах планированияФ. ЦСвердловск: УН - АН СССР, 1980. ЦC. 27Ц36.
[6] Скарин В.Д. К анализу несобственных задач выпуклого программирования с позиций последовательной оптимизации. ЦВ кн. УНесобственные задачи оптимизацииФ.
ЦСвердловск: УН - АН СССР, 1982. ЦC. 30Ц36.
[7] Скарин В.Д. Методы коррекции несобственных задач выпуклого программирования 1-го рода, основанные на последовательном программировании. ЦВ кн. УНесобственные задачи линейного и выпуклого программированияФ (И.И.Еремин, В.Д.Мазуров, Н.Н.Астафьев). ЦМ.: Наука, 1983. ЦC. 262Ц272.
[8] Скарин В.Д. О применении метода регуляризации для коррекции несобственных задач линейного программирования 1-го рода. ЦВ кн. УМетоды аппроксимации несобственных задач математического программированияФ. ЦСвердловск: УН - АН СССР, 1984.
ЦC. 55Ц66.
[9] Скарин В.Д. Об одном алгоритме численного анализа несобственных задач линейного программирования. ЦВ кн. УПараметрическая оптимизация и методы аппроксимации несобственных задач математического программированияФ. ЦСвердловск: УН - АН СССР, 1985. ЦC. 63Ц69.
[10] Скарин В.Д. Об одном подходе к анализу несобственных задач линейного программирования // Ж. вычисл. матем. и матем. физики, 1986. ЦT. 26, № 3. ЦC. 439Ц4(перечень ВАК).
[11] Скарин В.Д. Об одном методе численного анализа противоречивых задач выпуклого программирования. ЦВ кн. УПротиворечивые модели оптимизацииФ. ЦСвердловск: УН - АН СССР, 1987. ЦC. 56Ц63.
[12] Скарин В.Д. Об одном регуляризирующем алгоритме коррекции противоречивых задач выпуклого программирования с линейными ограничениями. ЦВ кн. УИсследования по несобственным задачам оптимизацииФ. ЦСвердловск: УрО АН СССР, 1988. ЦC. 48 - 56.
[13] Скарин В.Д. Регуляризирующий алгоритм для несобственных полноквадратичных задач выпуклого программирования. ЦВ кн. УНерегулярная двойственность в математическом программированииФ. ЦСвердловск: УрО АН СССР, 1990. ЦC. 58Ц67.
[14] Скарин В.Д. О методе регуляризации для противоречивых задач выпуклого программирования // Изв. ВУЗов. Математика, 1995. Ц№ 12. ЦC. 81Ц88 (перечень ВАК).
[15] Скарин В.Д. Об одном универсальном подходе к оптимальной коррекции несобственных задач выпуклого программирования. ЦВ кн. УМетоды оптимизации и их приложенияФ (Тр. XI-й междунар. Байкальской шк.-сем.). ЦИркутск: СЭИ СО РАН, 1998. ЦТ. 1.
ЦC. 56Ц59.
[16] Скарин В.Д. О применении барьерных функций для коррекции несобственных задач выпуклого программирования. ЦВ кн. УМетоды оптимизации и их приложенияФ (Тр. XII-й Байкальской междунар. конф.). ЦИркутск: ИСЭМ СО РАН, 2001. ЦТ. 1.
ЦC. 50Ц54.
[17] Скарин В.Д. Оценочный подход в методах линейного и выпуклого программирования // Информ. бюллетень АМП (Приоритетные результаты в области математического программирования. Ч. 1). ЦЕкатеринбург: УрО РАН, 2001. Ц№ 9. ЦС. 123Ц127.
[18] Скарин В.Д. О применении функции Лагранжа для регуляризации задач выпуклого программирования. ЦВ кн. УСовременные методы оптимизации и их приложения к моделям энергетикиФ. ЦНовосибирск: Наука, 2003. ЦC. 189Ц209.
[19] Скарин В.Д. О некоторых регуляризирующих и аппроксимирующих свойствах метода штрафных функций в выпуклом программировании // Оптимизация, управление, интеллект, 2005. Ц№ 1(9). ЦС. 107Ц128.
[20] Скарин В.Д. О применении штрафных функций для коррекции несобственных задач выпуклого программирования. ЦВ кн. УМетоды оптимизации и их приложенияФ (Тр. XIII-й Байкальской междунар. шк.-сем.). ЦИркутск: ИСЭМ СО РАН, 2005. ЦТ. 1.
ЦC. 175Ц180.
[21] Скарин В.Д. О методе барьерных функций и алгоритмах коррекции несобственных задач выпуклого программирования // Тр. Ин-та матем. и мех. УрО РАН.
ЦЕкатеринбург: ИММ УрО РАН, 2008. ЦT. 14, № 2. ЦC. 115Ц128 (перечень ВАК).
[22] Скарин В.Д. Расширенная штрафная функция и оптимальная коррекция несобственных задач выпуклого программирования. ЦВ кн. УМетоды оптимизации и их приложенияФ (Тр. XIY-й Байкальской междунар. шк.-сем.). ЦИркутск: ИСЭМ СО РАН, 2008.
ЦТ. 1. ЦC. 203Ц209.
[23] Скарин В.Д. Аппроксимационные и регуляризирующие свойства расширенной штрафной функции в выпуклом программировании // Тр. Ин-та матем. и мех. УрО РАН.
ЦЕкатеринбург: ИММ УрО РАН, 2009. ЦT. 15, № 4. ЦC. 234Ц250 (перечень ВАК).
[24] Скарин В.Д. Об одном общем подходе к оптимальной коррекции несобственных задач выпуклого программирования // Тр. Ин-та математики и механики УрО РАН, 2010.
ЦT. 16, № 3. ЦC. 265Ц275 (перечень ВАК).
[25] Skarin V.D. Methods for the correction of ill-posed problems of linear and convex programming by using a sequential programming approach // Seminarberichte. ЦBerlin:
HumboldtЦUniv., Sekt. Math., № 81, 1986. ЦP. 130Ц144.
[26] Skarin V.D. Regularized Lagrange function and correction methods for improper convex programming problems // Proc. of the Steklov Institute of Mathematics. Suppl. 1, 2002.
ЦP. S116ЦS144 (перечень ВАК).
Подписано в печать.. 2010.
Формат 60x84/16. Объем 2 п.л.
Тираж 100 экз. Заказ № Размножение с готового оригинал-макета в типографии УрО РАН 620219, г. Екатеринбург, ул. С. Ковалевской, 18.