Аппроксимационные и регуляризирующие свойства штрафных функций и функций Лагранжа в математическом программировании тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

004614455

На правах рукописи

СКАРИН ВЛАДИМИР ДМИТРИЕВИЧ

АППРОКСИМАЦИОННЫЕ И РЕГУЛЯРИЗИРУЮЩИЕ СВОЙСТВА ШТРАФНЫХ ФУНКЦИЙ И ФУНКЦИЙ^АГРАНЖА В МАТЕМАТИЧЕСКОМ ПРОГРАММИРОВАНИИ

01.01.09 - дискретная математика и математическая кибернетика

Автореферат диссертации на соискание ученой степени доктора физико-математических наук

Екатеринбург - 2010

2 5 НОЯ

т

004614455

Работа выполнена в Учреждении Российской академии наук Институте математики и механики Уральского отделения РАН

Научный консультант: академик РАН

Еремин Иван Иванович

Официальные оппоненты: доктор физико -математических наук

член-корреспондент РАН Васин Владимир Васильевич, доктор физико-математических наук профессор

Заботин Ярослав Иванович,

доктор физико -математических наук

профессор

Колоколов Александр Александрович.

Ведущая организация: Учреждение Российской академии наук

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

Защита состоится " 3 " й/Ша^'СА 2010 г. в 4 { часов на заседании диссертационного совета Д 004.006.04 в Институте математики и механики УрО РАН по адресу: 620990, г. Екатеринбург, ул. С.Ковалевской, 16. 4

С диссертацией можно ознакомиться в библиотеке Института математики и механики УрО РАН.

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

Ученый секретарь диссертационного совета доктор физико-математических наук Л.Д. Попов

Общая характеристика работы

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

Актуальность темы. Метод штрафных функций является универсальным средством решения экстремальных задач различной природы. Метод порождает целое семейство вычислительных процедур, а также служит эффективным инструментом теоретического анализа задач оптимизации.

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

Важное значение при этом имеет метод точных штрафных функций, предложенный в 1966 году И.И.Ереминым. Данный метод позволяет в принципе свести решение исходной условноэкстремальной задачи к однократной минимизации без ограничений некоторой вспомогательной функции. Проблема построения таких функций и нахождения условий точности для различных классов задач МП занимает заметное место в специальной литературе и продолжает оставаться актуальной.

Хорошо известны вычислительные трудности при численной реализации метода штрафных функций, связанные с асимптотическим характером сходимости. Один из возможных путей преодоления этих трудностей предлагают методы модифицированной функции Лагранжа (методы множителей, штрафных оценок). Эти методы, с одной стороны, расширяют возможности стандартной функции Лагранжа, играющей центральную роль в теории МП, с другой — являются определенным обобщением метода штрафных функций. Исследования в этой области,

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

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

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

Несобственные задачи (НЗ) МП характеризуются тем, что для них не выполняются соотношения двойственности. Свойство несобственности тесно связано с совместностью систем ограничений исходной задачи и двойственной к ней. Поэтому о несобственных задачах говорят в более узком смысле как о задачах МП с противоречивыми ограничениями. Интерес к противоречивым моделям обусловлен как потребностями математической теории (анализ систем уравнений и неравенств, некорректные задачи, задачи идентификации, распознавания образов и др.), так и необходимостью анализа прикладных задач с противоречивыми условиями, прежде всего экономических, где появление несовместных моделей — обычное явление. Распространенность и актуальность несобственных задач порождает острую потребность в разработке теории и методов их численной аппроксимации.

Определение НЗ МП и систематическое исследование таких задач было инициировано в начале 80-х годов прошлого века работами уральской школы по МП, возглавляемой академиком И.И.Ереминым. Впоследствии эта тема получила широкое отражение в специальной

литературе (работы Н.Н.Астафьева, В.А.Булавского, А.А.Ватолина, В.А.Горелика, И.И.Еремина, В.И.Ерохина, А.В.Зыкиной, М.М.Ковалева,

B.Д.Мазурова, Л.Д.Попова, Н.В.Третьякова, М.Ю.Хачая и др.). Многие важные в прикладном отношении задачи планирования, проектирования и управления являются некорректно поставленными. Решения таких задач не зависят непрерывно от входной информации. Поэтому нельзя быть уверенным, что приближенное решение задачи будет близким к точному и, следовательно, требуются специальные методы регуляризации, которые обеспечивали бы сходимость генерируемой итерационной последовательности к искомому множеству решений.

Начало исследований теории и методов некорректных задач связано с именами А.Н.Тихонова, В.К.Иванова, М.М.Лаврентьева. Дальнейшее развитие данная проблематика получила в работах А.Л.Агеева,

A.С.Антипина, А.Б.Бакушинского, Ф.П.Васильева, В.В.Васина, Д.В.Денисова, В.Г.Карманова, В.А.Морозова, В.П.Тананы, А.Г.Яголы и др. К этому направлению также тесно примыкают исследования по устойчивости задач МП (работы Н.Н.Астафьева, А.Ауслендера,

C.А.Ашманова, Ю.Гудцата, И.И.Еремина, С.Злобека, Е.С.Левитина,

B.В.Федорова, А.Фиакко — для непрерывных задач МП, В.А.Емеличева, А.А.Колоколова, И.В.Сергиенко — для дискретного случая).

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

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

1. Построение различных модификаций метода штрафных функций (точных, асимптотически сходящихся, барьерных, расширенных) и их применение для оптимальной коррекции НЗ МП и регуляризации некорректных задач МП.

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

3. Разработка новых конструктивных алгоритмов, основанных на применении штрафных функций и модифицированных функций Лагранжа для численного анализа НЗ МП и регуляризации некорректных задач оптимизации.

4. Развитие оценочного подхода при обосновании сходимости предлагаемых методов.

Научная новизна. Основные результаты диссертации являются новыми.

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

Получены оценки уклонений компонент седловой точки регуляризованной по прямым и двойственным переменным функции Лагранжа Ьа(х, А) от решений исходной и двойственной задач ВП, в том числе, и для несобственных постановок. При этом исследованы различные по степени общности виды стабилизирующих добавок. Предложены и обоснованы два универсальных по отношению к типам несобственности подхода к оптимальной коррекции задач ВП, основанных на применении функции Ьа{х,А).

Найдены условия управления параметрами регуляризации сг = [а,/3] функции Ь„{х, Л) в случае симметрической аппроксимации несобственных задач линейного и квадратичного программирования для нахождения нормальных решений соответствующей пары двойственных задач.

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

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

Теоретическая и практическая значимость. Работа носит, в основном, теоретический характер, но имеет в то же время и выраженную практическую направленность. Полученные в ней оценки уклонений решений задач минимизации штрафных функций и модифицированных функций Лагранжа от решений исходной задачи (или ее естественных аппроксимаций) показывают возможный наилучший порядок сходимости соответствующих итерационных схем, возникающих при численной реализации данных подходов. В работе на примере метода барьерных функций показано, как полученные теоретические оценки могут быть применены для решения вопроса об управлении штрафным параметром с целью обеспечения сходимости метода со скоростью геометрической прогрессии как по функции, так и по аргументу. Также в работе предложен ряд конкретных конструктивно реализуемых вычислительных алгоритмов для оптимальной коррекции НЗ МП и для регуляризации некорректных задач оптимизации.

Апробация работы. Результаты диссертационной работы докладывались на следующих конференциях:

- 12-13-я Международные конференции "Математическая оптимизация" (Университет Гумбольдта, Берлин, 1980, 1981);

- 3-6-я Всесоюзные конференции "Методы математического програм-

мирования и их программное обеспечение" (Свердловск, 1981, 1984, 1987, 1989);

- У1-я, Х-Х1У-Я Байкальские школы-семинары "Методы оптимизации и их приложения" (Иркутск, 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 наименований.

Основное содержание работы.

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

В главе 1 с единых позиций исследуются вопросы теории метода штрафных функций, в частности, условия точности и асимптотической сходимости ряда модификаций данного метода, а также их применимость для аппроксимации НЗ ВП.

В качестве исходной рассматривается задача ВП

шш{/о(х) : х е X}, (1)

где X = {х : /(х) < 0} , /(:г) = [/^х),..., /т(х)], /Дх) — выпуклые функции, определенные на Мп (г = 0,1,..., т).

Данной постановке соответствует задача нахождения

М{Р(х, г) = /0(х) + Ф(х, г)} (= (2)

х

где Ф(х, г) — функция штрафа за нарушение ограничений, определяющих множество X , г — скалярный или векторный штрафной коэффициент (г > 0).

В § 1.1 исследуются некоторые теоретические вопросы метода штрафных функций для задачи (1). В частности, здесь формулируются общие условия на конструкцию штрафной функции, при которых она является точной. Пусть функция Лагранжа Ь(х, А) = /о(х) + (Л, /(х)), поставленная в соответствие задаче (1), имеет непустое множество X* х Л* седловых точек в области К" х Е™. Положим в (2) Ф(х, г) = <р(г(х, г)), ф,г) = [21(х,г),...,2т(х,г)] , ¿¿(х,г) = Г;/^(х) (г = 1,...,т), г = [гь..., гт] > 0, где (р = <р(г) — выпуклая функция, определенная на Ж"1, удовлетворяет условиям

дг

д^) — производная от <р(г) в точке г = 0 по направлению г, 5 = {г <Е К? : ||*|| = 1}.

Теорема 1.1.1. В сформулированных выше условиях Р(х, г) является точной штрафной функцией для задачи (1) с множеством оптимальных параметров Ё = {г € К+ : г > ■^Р^А*} ( т.е. — /* = /о(х*)

при г£Ё, х*ЕХ*), где А* € Л*. Если г > ^А*, то X* = Х*(г), где Х*(г) — множество точек минимума в задаче (2).

Данная теорема справедлива для общей задачи математического программирования (т.е. без предположения выпуклости функций /¡(ж), г = 0,1,..., т). Она обобщает известные факты для классических видов точных штрафных функций таких, как функция Еремина-Зангвилла

m i=l

В следующем утверждении (теорема 1.1.2) приводятся достаточно общие условия для штрафной функции, обеспечивающие асимптотическую

сходимость метода. Этим условиям удовлетворяет, например, функция m

F(x, г) = /о(г) + J2 п/+Р(х), р > 1, которая становится далее объектом i=i

более подробного рассмотрения. В теореме 1.1.3 устанавливаются оценки скорости сходимости метода, основанного на применении этой функции, обобщающие классические результаты для квадратичной штрафной функции (р = 2). Анализ полученных оценок показывает, что имеет

смысл согласованно изменять параметры Го — min г,- и р. В итераци-

i

онном процессе метода штрафных функций рационально выбирать параметры р и го, например, так: рк = 1 + £к > (ro)k = ej.1, £k > 0, lim £к = 0. Если функции /,(х), i = 0,1,..., ш, в задаче (1) диффе-

к—>оо

ренцируемы, то F(x, (г0)д.) будет приближать в пределе точную штрафную функцию, оставаясь при этом дифференцируемой для любого к.

Следующий раздел (§1.2) посвящен применению метода штрафных функций для оптимальной коррекции НЗ ВП. При этом используется идея ранжирования ограничений. Возможно несовместная система ограничений задачи (1) разбивается на две части и определяет два множества Xi = {х : fi{x) <0, г = 1,...,т}, Х% — {ж : fi(x) < 0, г = т + 1,..., т + £} , одно из которых (Х2) заведомо непусто. Строится штрафная функция F(x, г), которая агрегирует целевую функцию /о (х) с функциями-ограничениями из Х\, и далее она минимизируется на множестве Х^ . Для задачи (1) строится следующая аппроксимаци-онная постановка

тт{/о(ж): <р(х) <ф, (3)

где ф — inf{</>(x) : х £ X?}, <р(х) — функция штрафа за нарушение ограничений, определяющих множество Xi. При этом <р(х) = u(z(x)),

z(x) = [zi(x),...,zm(x)}, Zi(x) = aif{~(x), щ > 0, i = l,...,m; ixj(z) — выпуклая неубывающая функция, определенная на M™, Ц0) =

m

0, u(z) = u(zu...,zm) > ß'Es?, ß > о, Pi > 1, i = l,...,m. Для

i=i

задачи (1) вводится условие 7 -ограниченности: существуют q индексов из т + I таких, что множество S^ — {х : fi3{x) < 7, s = 1, ...,g} непусто и ограничено, 7 € R1.

Теорема 1.2.1. Пусть для задачи (1) выполнено условие 7 -ограниченности и fo{x) > / > —00 (Va; € Х2) ■ Тогда

1. X* ^ 0 , где X* — множество решений задачи (3).

2. Для любого г > 0 задача

inf{F(x,r) = f0(x) + rtp(x) : х G Х2}, г > О,

разрешима в некоторой точке х*(г).

3. При г —* оо выполняются соотношения

МЛг)) S Г, ф*(г)) \ ф, р(**(г),Л") - 0,

где /* — оптимальное значение задачи (3).

Далее аналогичный факт доказывается при замене условия 7 -ограниченности на условие существования седловой точки у функции Лагран-жа для аппроксимирующей задачи (теорема 1.2.3). Обе теоремы уточняются на случай, когда задача min F(x, г) решается приближенно (теоремы 1.2.2 и 1.2.4). Для обеспечения свойств регулярности аппроксимирующей задачи применяется идея s -расширения1 ее ограничений (теорема 1.2.5). Наконец, в теореме 1.2.6 определяются условия сходимости метода, когда штрафная функция включает все ограничения исходной задачи.

В § 1.3 показывается, что проблема коррекции НЗ ВП из § 1.2 может быть интерпретирована как трехэтапная задача лексикографической минимизации или, в другой терминологии, как задача последовательного программирования. Формулируется теорема 1.3.1, в которой конкретизируются функции векторного критерия, условия на исходную задачу и

1 Еремин И.И. О задачах выпуклого программирования с противоречивыми ограничениями // Кибернетика, 1971. 4. -С. 124-129.

требования на согласование параметров скаляризации, которые обосновывают данный подход.

В § 1.4 речь идет о расширенной штрафной функции

т т

F(x, А, г) = /„(*) + Шх) +г £ /+'(*), А = [Аь..., Ат] > 0, г > 0. t=l i=l

В свое время она была введена автором2 в целях улучшения свойств сходимости метода квадратичной штрафной функции при г —* оо. Теперь же исследуются возможности функции F(x, А, г) для оптимальной коррекции НЗ ВП 1-го рода (случай, когда X — 0, Л Ф 0, где Л = {А е R+ : inf L(x, А) > —оо}. Исходная несобственная постановка ВП аппроксимируется следующей задачей

тт{/0(сс) : х 6 (4)

где Х( = {х : /(яг) < £}, £ = argmin{||£|| : £ <е К?, Х( ф 0} . В предположении существования седловой точки [ж, А] функции Лагран-жа для задачи (4) в теореме 1.4.1 установлены оценки, связывающие решение х\ задачи

miaF(x,\,r) (5)

X

с векторами i,A и f. Из этих оценок следует, что сходимость метода будет иметь место не только при г —► оо , но и при А —► А.

Следующий § 1.5 посвящен рассмотрению близкой к F(x,X,r) функции

F&, А, г) = Мх) + (А, f+(x)) + г ||/+(х)||2, А € К+, г > 0.

Функция Fi(x, А, г) является, очевидно, определенной модификацией штрафной функции, а именно, она представляет собой комбинацию классических точной и квадратичной штрафных функций. Теорема 1.5.1 показывает, что в случае разрешимой задачи ВП метод, построенный на основе F\(x, А, г), будет комбинировать и свойства сходимости соответствующих методов штрафных функций.

2Скарин В.Д. Об одной модификации метода штрафных функций в выпуклом программировании // Нелинейная оптимизация и приложения в планировании. -Свердловск: УНЦ АН СССР, 1973. -С. 51-62.

Сформулируем задачу

minFiCn.A.r) (=FlT). (6)

X

Теорема 1.5.1. Пусть в задаче (1) X* х Л* ф 0 , х* € X*, Л* € Л*, fo{x*) = /*. Справедливы соотношения

(1) Г-||ЛТ4~Л||2^-^л,г<Г (VA > 0, г > 0);

(2) = /* (VA > А*, г > 0);

(3) Х(Л,г) = X* (VA > А*, г > 0), г<?е Х(Х,r) = ArgminFi(x, А,г).

X

Если Х(А,г) ^ 0 и £л,г € -У (А, г) , то

(4) ||/+(ха,г)||<^^ (VA > 0, г > 0);

(5) 0 < /* - /0(5д,г) < ||А* || (VA > 0, г > 0).

Соотношения (1)-(5) теоремы 1.5.1 показывают, что для малых А основной вклад в сходимость метода дает квадратичная составляющая г ||/+(х) ||2, а при больших — F\(x, А, г) ведет себя как точная штрафная функция. С другой стороны, если функция L(x, А) для исходной задачи ВП имеет непустое множество X* х А* седловых точек в области К" х М™ , то согласно теореме 1.5.2 функция Fi(x, X, г) при любом фиксированном г > 0 будет обладать непустым множеством X* х (Л*+R+) седловых точек в этой же области. Таким образом, F\(x, А, г) является и модифицированной функцией Лагранжа. Соответственно, Fi(x,\,r) может использоваться для построения эффективных итерационных алгоритмов. В § 1.5 приводится и обосновывается (теорема 1.5.5) вариант метода множителей3, построенный на основе применения функции Fi(x, А, г). Наконец, по аналогии с F(x, А, г) из § 1.4 функция F\(x, А, г) может использоваться для оптимальной коррекции НЗ ВП.

Пусть (1) — НЗ ВП 1-го рода, для которой построена аппроксимирующая задача (4), [ж, А] — седловая точка функции Lf(x, А) = /о(х) + (А, }{х) - О в области ГхМ™.

3Beri3tkas D.P. Multiplier methods: a survey // Automatica, 1976. -Vol. 12, до. 2. -P. 133-145.

Теорема 1.5.4. Пусть задача (6) разрешима в точке x\¡r. Справедливы оценки

||/+(*А,г) - < ^Д |/о(5л,г) - Ш)\ < С(A) MzM,

где С(А) = тах{||Л||, ||Л||} .

§ 1.6 посвящен применению оценочного подхода в методе барьерных функций (методе внутренних штрафных функций). Очевидное преимущество таких функций перед классическими функциями (внешнего) штрафа состоит в высокой степени гладкости вспомогательной функции (в случае дифференцируемое™ /¿(я), г = 1,... ,т), что позволяет использовать при численной реализации итеративные методы минимизации высокого порядка. В качестве вспомогательной функции рассматривается следующее обобщение обратной барьерной функции:

т

где £ = [£i,...,£m] >0, Pi> 1, i =T7m.

Теорема 1.6.1. Пусть в задаче (1) X* х Л* ф 0, Xo ± 0, где Xo = {ж : f{x) < 0} . Тогда существуют константы С\, а и вектор ё € Мт такие, что для любых {)<£<£ выполняются неравенства

0 <B¡-f*< Сх тах ef,

где f* и В* — оптимальные значения задач (1) и inf^ В(х, г) соответственно, 0 < а < min i i-.

' i 1 +Pi

Теорема 1.6.4. Если в (1) /о (ж) — сильно выпуклая функция, то

С4тш(—< ||х(е) - х*|| < С3юахе"/2, i \тах ef J %

где х* и х(е) — решения задачи (1) и задачи inf^ В(х, е) соответственно, Сз, С i — положительные константы.

14

Здесь же выводятся оценки для приближений двойственных переменных (теоремы 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. Пусть Xq — произвольная точка из R", {ё^}, {4} — последовательности положительных чисел такие, что ёк+1 < £fc , Hm Eh = lim 6k = 0 . Положим

к—юо к—too

= ||/+(яо)||оо, £"0 = £о, Но 6 (о, 1), Уо = {s : fi{x) < сго+е0, i = Т~ш}.

Опишем (к + 1) -ю итерацию алгоритма, считая известными точку Xk € К" , параметры (Тк > 0, £к > 0, 6к > 0, рк > 0 и множество Y® = {х : fi(x) < ст/с + i = 1, m} . Построим функцию

m

Хк+1 = arg min {5fc(x) : x € Y°}. 15

Положим crjfc+i = ||/+(zfc+i)||oo • Выберем число £k+i по правилу

О < Ek+i < min {ак - <Тк+1 + £ь ёк+i}-

Теорема 1.7.1. Пусть задача (1) — НЗ ВП 1 -го рода и Цк — о(бк). Тогда

lim Вк(хк+1) = lim fo(xk+i) = f,

к—>oo к—юс

где / — оптимальное значение аппроксимирующей задачи (4), в которой f = [ff,..., ff], ä = min И/ЧаОИоо.

X

Объектом исследований в главе 2 являются аппроксимационные и регуляризирующие свойства модифицированной функции Лагранжа

L^x, А) = Х(х, А) + аш(х) - /Зг(А),

где L(x,X) — стандартная функция Лагранжа для задачи (1), а = \a,ß] > 0, и/(х),т(\) — выпуклые неотрицательные функции, определенные на 3R" и Rm соответственно. Предполагается, что лебеговы множества М(С) = {гбГ: ш[х) < С} , N(C) = {А € Мт : т( А) < С} функций ш(х) и т(А) ограничены для любых С > 0. Типичными примерами функций и(х),т(Х) служат: ш(х) = ||х||2, т(А) = ||А||2. В терминах методов регуляризации некорректных экстремальных задач функция и)(х) называется стабилизатором для исходной задачи ВП (1), а функция г(А) — стабилизатором для задачи, двойственной к (1). Поэтому функцию L,7(х, А) можно называть стабилизированной или регуля-ризованной по прямым и двойственным переменным функцией Лагранжа.

В §2.1 исследуется случай разрешимой задачи ВП. Вначале в п. 2.1.1 рассматривается общая конструкция стабилизирующих функций и>{х) и г(А). При этом показано, что при условии существования седловой точки [ж*, А*] функции L{x, А) таковым же свойством обладает и La(x, А) для любого ff > 0 (теорема 2.1.1). Связь между седловыми значениями функций L(x, А) и La(x, А) устанавливается в теореме 2.1.2.

Теорема 2.1.2. Пусть для задачи (1) существует [ж*, А*] — седловая точка функции Ь(х, А) в области Rn х R+. Тогда для любого а > О справедливы оценки

г — ßr(X*) < La{x°, У) < Г + аш(х*),

где [ха, Аст] — седловая точка функции La{x, А) в области R" х R+ , /* = L(x*,X*) = f0(x*).

Далее в п. 2.1.2 в целях конкретизации характера сходимости предлагаемого метода регуляризованной функции Лагранжа полагается и(х) = ||х||2 , т(А) = ||А||2 . Если теперь на основе La(x, А) определить прямую и двойственную функции

<ра(х) = sup La{x, А), фа{Х) = inf La(x, А), л>о 1

то ipa(x) будет сильно выпуклой на R", а гра(Х) — сильно вогнутой на R™, и поэтому для любого сг > 0 будет существовать единственная седловая точка функции La(x, А) в области R" х К"'. Несложными выкладками можно показать, что

Мх) = Мх) + jß 11/+(ж)112 + » INI2-

Таким образом, оказывается, что регуляризация функции Лагранжа по двойственным переменным с помощью добавки —ß ||А||2 эквивалентна применению для исходной задачи функции квадратичного штрафа. Это позволяет при выводе оценок для [х",Ха] использовать методику, которая применялась при обосновании метода штрафов. В теореме 2.1.4 такие оценки показывают характер приближения точки х" к решению задачи (1) по функциям-ограничениям и по целевой функции.

Теорема 2.1.4. Пусть выполнены условия теоремы 2.1.2 и ш{х) = ||a;||2, т(А) = ||А||2. Справедливы оценки

\\f+(x°)\\<2vfßCl(*),

ШО-r \<С2Н,

где С\(а) = (а ||ж*||2 + /?||А*||2)1''2, ОД = 2а И|2 + 3/?||А*!|2.

Следствие 2.1.3. Пусть множество X* решений задачи (1) ограничено. Тогда

р(ха,Х*)-+0 (<г > 0), где p(x,S) = inî ||a: - у||.

Следствие 2.1.4. Пусть а —> 0 , 0 = о (а) . Тогда ха —» х*0, где Жд — нормальное решение задачи (1) : = arg min{||:r|| : х £ X*} .

Теорема 2.1.5. Пусть функции fi(x) в задаче (1) дифференцируемы на М" (г = 0,1,..., т). Для произвольного а > О справедливы оценки

|| v*£(zff,ACT)||<2 VeC^tr),

О < А?fi(xa) < 2 С?(<т), i =

где \а = [А^,..., А^], С\{а) — из теоремы 2.1.4.

Следствие 2.1.5. Пусть задача (1) имеет единственное решение х* и а —>• 0, а = о{0). Тогда X" —» Aq , где Х*0 — минимальный по норме вектор множителей Лагранжа, соответствующий решению х*.

В следующем п. 2.1.3 несколько усложняется структура стабилизирующих добавок. А именно, рассмотрен случай, когда

п т

uj(x) = ^ajr(A) = $>A?; j=1 i=1

aj > 0, jel^n; h > 0, t£l,m; + q= 1 + v, ii,v> 0.

Показано, что в зависимости от вида т(А) меняется структура функции <ра{х) — вместо квадратичного штрафа появляется сумма слагаемых f*(x) в степени ^ , т.е. возникает, если не учитывать стабилизатор и{х), асимптотическая штрафная функция, подобная той, которая рассматривалась в §1.1. Оценки, приводимые в теореме 2.1.6, показывают, как характер сходимости метода зависит от изменения стабилизирующих добавок ш(х) и т(А) и как можно распорядиться параметрами метода для улучшения этой сходимости.

§2.2 посвящен исследованию метода регуляризованной функции Лагранжа применительно к несобственным задачам ВП. Согласно классификации4 НЗ ВП в зависимости от пустоты или непустоты допустимых множеств X в задаче (1) и Л = {А (Е R+ : inf А) > —оо} в

X

двойственной к (1) задаче различают три рода НЗ ВП: 1-го рода, если

1Еремин H.H., Мазуров В.Д., Астафьев H.H. Несобственные задачи лилейного и выпуклого программирования. -М.: Наука, 1983. -336 с.

X = 0, Л ф 0; 2-го рода, если X Ф 0 , Л = 0; 3-го рода, когда X — 0 , Л = 0.

Вначале рассматривается случай несобственности 1-го рода. Задаче ВП (1) ставится в соответствие проблема нахождения седловых точек [х*, А*] функции La{x, А) с w(z) = ||х||2, т(А) = ||А||2. Как отмечалось выше, такая функция при любом и > 0 имеет единственную седловую точку в области М" х К™. Причем этот факт справедлив независимо от того, является задача (1) собственной или нет. В этом L„{x, А) существенно отличается от стандартной функции L(x, А), которая заведомо не имеет седловых точек, если X = 0 .

В теореме 2.2.1 устанавливается, что для НЗ ВП 1-го рода характер сходимости {ха} к решению аппроксимирующей задачи (4) аналогичен сходимости {ж"7} к решению задачи (1) в случае разрешимости последней.

Теорема 2.2.1. Пусть для задачи (4) выполнены условия Куна-Таккера: существуют векторы х € Х^, А £ М™, для которых V*L(i, А) = 0, (A, f(x) -0 = 0. Тогда

1КДО - < Л9ВД, I - /1 < ВД,

где А» - 2[v^||A|| + №||2+/?||A||2)2], К2(а) = max{ap||2, у/РК^7)||А||}, /=/О(х).

Отсюда следует, что lim f+(xa) = £.

Далее найдены условия, при которых последовательность {х°} сходится к нормальному решению задачи (4) (теорема 2.2.2). В теореме 2.2.3 оценивается скорость этой сходимости. Показано, что она имеет порядок 0(^/(3/а). Оценки из теоремы 2.2.4 устанавливают степень выполнения для [ха, Аа] условий Куна-Таккера для задачи (4). В силу этой теоремы и теоремы 2.2.1 lira L(x", X") = lim La(x°, Xе) = +oo . Этот факт

<7—>0 (7—»0

может служить индикатором несовместности системы ограничений задачи (1), поскольку при | = 0 La(xa,Xa) —> /* (а -> 0). И, наконец, заключительная теорема 2.2.5 характеризует сходимость двойственной составляющей Ха.

В п. 2.2.2 рассматривается общий случай несобственности задачи ВП. Здесь обосновывается универсальный подход к оптимальной коррекции

НЗ ВП независимо от рода несобственности, основанный на применении функции Ьа(х, А). Суть подхода заключается во введении дополнительного звена, помимо задачи (4), в цепь, связывающую исходную задачу (1) и задачу отыскания седловой точки функции La(x, А). Это звено представлено задачей, близкой к (1):

min{F,(i) = fo(x) + 7 INI2 : х 6 X}, (7)

где 7 > 0. Если X ^ 0 , то задача (7) разрешима в единственной точке х*, если же X = 0, то легко видеть, что задача (7) может быть несобственной только 1-го рода независимо от характера несобственности исходной задачи (1). Данное обстоятельство позволяет обосновать предлагаемый метод с помощью результатов п. 2.2.1.

Вначале решается вопрос о близости задачи (1) и задачи

min{/o(ar) + 7^(2:): х G X},

где 7 > 0, fi(x) — некоторый стабилизатор. Результаты представлены в леммах 2.2.2 и 2.2.3.

Если теперь для задачи (7) составить функцию Ьа(х, А), то в ней появится слагаемое (а + 7) ||х||2, т.е. возникнет дополнительный управляющий параметр 7.

Теорема 2.2.6. Пусть задача (1) разрешима и регулярна. Тогда

\\х° - ®;ц2 < ^ ijzSH2 + £ ца;ц2,

где 0<7<а, 0:1=0-7, = argmin{||a;|| : х € Л""} , X* —множество решений задачи (1), А* — вектор множителей Лагранжа в задаче (7), соответствующий решению х* .

Следствие 2.2.6. Образуем последовательности положительных чисел 7& , а* , ßk так, чтобы

lim 7£ = lim — = lim — = 0.

k~>00 k—>00 7fc k—>00

Тогда xak —> Xq (k —> 00).

Аналогичным образом можно доказать и сходимость к решению задачи, двойственной к (1) (теорема 2.2.7 и следствие 2.2.7).

Если (1) — НЗ ВП, то введем аналог аппроксимации (4) для задачи

(7):

min{F7(:r) : х € Л^},

где £ имеет тот же смысл, что и в (4). Сходимость результирующего метода выражает следующий факт.

Следствие 2.2.8. lim lim FJx°) = /,

7-0

0-Ю

где f — оптимальное значение задачи (4).

Это утверждение справедливо для задач ВП произвольного рода несобственности (т.е. включая случай / = —оо ).

В § 2.3 метод регуляризованной функции Лагранжа применяется для несобственных задач линейного программирования (ЛП). Для пары взаимно двойственных задач ЛП

min{(c, х) : Ах <Ь, х> 0}, (8)

тах{(Ь, и) : АТи < с, и < 0} (9)

строится их симметрическая аппроксимация5

min{(c + fj,x) : Ах <b + Ç, х > 0}, (10)

max{(6 + f,u) : ATu<c + f), u < 0}, (И)

где £ G R™ , rj G R™ выбраны так, чтобы допустимые множества задач (10) и (11) были непусты (этого достаточно для разрешимости этих задач и совпадения их оптимальных значений), а также, чтобы они были минимальны по норме среди всех £ и г], обладающих этими свойствами. В отличие от общей задачи ВП для задачи ЛП можно определить

явным образом не только функцию ipa(x) = sup La{x, Л), но и =

А>0

Ы Ux, А) : = -{Ъ, А) - £ ||(АГ(-А) - с)+||2 - ß ||А||2.

5Еремин И.И., Мазуров В.Д., Астафьев H.H. Несобственные задачи линейного и выпуклого программирования. -М.: Наука, 1983. -336 с.

Это позволяет получать оценки сходимости, симметричные для х" и для А° .

Теорема 2.3.1. Для любого а > 0 компоненты седловой точки [ха, Аст] функции La{x, А) удовлетворяют неравенствам

II(Ах° - Ь -1)+|| < /?1/2 h2(a), ||(ЛГ(-Л") - с - ff)+\\ < a1'2 h(a),

max{|(c + 7?,x*) - /% |(Ь + £,-Л") - /*|} < h0h4(а),

где Xq — argmin{||a;|| : х € X*} , Uq = argтт{||гг|( : и € U*} ,

йо = тах{Ы, IKII}> ^li0") = (а llxoll2+ß lluoll2)1/'2 > /* = {c+v, atf) = (b + I u*o), h2(a) = 1|«5|| + , A3W = «1/2 11*511 + M*),

hi(a) = maxla1/2 Цж^Ц hs(a), ß1!2 ||iiß|| Л2(сг)} , X*, U* — множества решений задач (10) и (11) соответственно.

Если и —> 0, то отсюда следуют сходимости р{ха, X*) —> 0, р{—Ха, U*) —> 0. Из этой же теоремы следует практический способ определения характера несобственности задачи ЛП (8). Если при а —> 0 будет (с, х") —> /*, (b, —А") —► /*, то это случай разрешимой задачи (8); если (с,ха) /*, (Ь,-\а) ->• +оо, то (8) - НЗ ЛП 1-го рода; (с, ха) —> —оо, (2>, -А*7) —► /* — НЗ ЛП 2-го рода; если (с, х") —► —оо , (6, - А17) +оо , то (8) - НЗ ЛП 3-го рода.

Последующие теоремы 2.3.2 и 2.3.3 уточняют характер сходимости последовательностей х" и X" . Так, для ха имеет место следующее утверждение.

Теорема 2.3.2. Существует число «о > 0 такое, что при а € (0, с*о] и произвольном ß > 0 справедливо

\\xa-xa\\<(ß/a)V2\\u*0l где xQ = Pxx,(v/(2a)). (12)

Соответственно, сходимость X" характеризует

Теорема 2.3.3. Существует число ßo > 0 такое, что при ß € (О, Д)1 и произвольном а > 0 справедливо

IIA' + MI^W/^llzSII, где U/9 = Рг„.(-£/(2/?)).

Развитый выше подход является универсальным в том смысле, что применим ко всем задачам ЛП, независимо от рода их несобственности.

В частности, если задача (8) разрешима (£ = О, Г) — 0), то в (12) ха = Хд = Ргх, О, и эта оценка характеризует сходимость ха к нормальному решению задачи (8).

Идея симметрической аппроксимации задачи ЛП в § 2.4 переносится на случай задачи квадратичного программирования:

тт|^(<5х,а;) + (сг,а:) : Ах < , (13)

где С} — симметрическая неотрицательно определенная матрица порядка п.

Аналогом задач (10) и (11) здесь будут

тт {(¡х,х) + (<2 - г}, х) : Ах < Ь +1|, (14)

тах|~(дх,г)-(6 + |,А) :С}хЛ-Ат\ + <1 = т), А>о|, (15)

где I € Е"1, т) € К" — минимальные по норме векторы, обеспечивающие непустоту допустимых множеств задач (14) и (15). По аналогии с §2.3 устанавливаются оценки, характеризующие близость компонент седловой точки [х", А"] к решениям задач (14) и (15) по функциям-ограничениям и целевым функциям (теорема 2.4.1) и затем уточняется характер сходимости переменных ха (теорема 2.4.2) и А"' (теорема 2.4.3). В отличие от ЛП оценки сходимости для ха и в задаче квадратичного программирования теряют свою симметрию. Так, утверждение для \а выглядит следующим образом.

Теорема 2.4.3. Существует число /?о такое, что для (3 £ (0,/?о] и произвольного а > 0 справедливо неравенство

где Ауз = Ргл, ^ , х* £ X*, С — неотрицательная константа, X* — оптимальное множество задачи (14), Л* — соответствующее множество множителей Лагранжа.

Следствие 2.4.2. Пусть задача (14) имеет единственное решение х* и с* —> 0, /3 -> О, а = о(Р). Тогда р{Х", Л*) —> О.

В §2.5 рассматривается несколько более общая по сравнению с (13) задача полноквадратичного программирования

где /¿(х) = I (С}1х,х)+(с11,х)+е1, с,^ € К" , е* е М1, Qi —симметрические неотрицательно определенные матрицы порядка п (г ~ 1,т). Если предположить, что среди Q¿ имеется хотя бы одна положительно определенная матрица, то (16) может быть несобственной задачей ВП только 1-го рода. Поэтому для этой задачи можно воспользоваться результатами §2.2. Уточнения касаются разве что двойственной сходимости, поскольку двойственная задача для (16) может быть выписана явным образом. Особо рассматривается случай, когда не достигается супремум двойственной функции. Если среди матриц нет положительно определенных, то к ограничениям задачи (16) можно добавить дополнительное неравенство ||х||2 < г, где г > 0. Такой прием фактически порождает новый способ коррекции НЗ ВП, исследованию которого посвящен § 2.6.

Новый подход заключается в построении особой аппроксимирующей задачи для НЗ ВП вида (1). Для этого определяется множество 5Г = {х : ||ж||2 < г} и вектор £г = : Х?П5Г ф 0} , где г > 0, £€Кт,

= {х : /(х) < £} . Затем для (1) строится аппроксимирующая задача

Далее исследуется связь между задачей (17) и проблемой нахождения седловых точек [х£, А£] функции Ьа(х, А) в области 5Г х!^. При этом рассматриваются два случая: 1) £г ф О (V г); 2) X ф 0. В первом случае мы имеем дело с НЗ ВП 1-го рода и поэтому с незначительными изменениями можем применить общие результаты п. 2.2.1. Так что основное внимание уделяется случаю 2), когда Ы: /о(х) = / не достигается. Примером полученных результатов может служить Теорема 2.6.2. Если в задаче (1) X Ф 0 и точка \х*г, А*] удовлетво-

тт{(с,х): /¿(х) < 0, г = 1 , т},

(16)

тт{/0(х) : х € П 5Г}.

(17)

ряет условиям Куна-Таккера для задачи (17) при £г = 0 , то

fo{x*r) ~ 0 HA;!!2 < La{x°, Х°) < fo(x*T) + аг для всех а = [а, /?] > О и достаточно больших г > О.

Если при этом параметры метода согласовать следующим образом: а —> 0, г —» +оо, аг —► 0, /Зг —> 0, то La{х°, X") —> / (теорема 2.6.4).

В заключение § 2.6 обсуждается вопрос о связи обсуждаемого здесь подхода к оптимальной коррекции НЗ ВП и общим подходом из п. 2.2.2.

Глава 3 посвящена детальному исследованию регуляризирующих свойств рассмотренных ранее методов: штрафных и барьерных функций, расширенных штрафных функций и регуляризованной функции Лагранжа. Сразу заметим, что ряд доказанных в предыдущих главах результатов уже имел отношение к регуляризации некорректных задач ВП и ЛП. Особенно это касается применения функции La(x, А) из глаг вы 2. Фактически те утверждения, где речь шла об условиях сходимости последовательностей /иА'к нормальным решениям исходной задачи и двойственной к ней, представляют собой теоремы о сходимости метода регуляризации, построенного на использовании функции La (х, А), для, в том числе, и некорректных задач оптимизации в случае точного задания функций цели и ограничений.

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

P(x,r,j) = F{x,r)+jn(x),

где F{x,r) — штрафная функция из §1.1, П(х) — некоторый стабилизатор, 7 > 0. Конструкция F(x,r) выбирается аналогично п. 1.1.1 (точная штрафная функция) и п. 1.1.2 (асимптотический случай). Соответствующие результаты о сходимости этих вариантов метода регуляризации приведены в теоремах 3.1.1 и 3.1.3.

Далее рассматривается случай, связанный с регуляризацией задач на множествах, заданных приближенно6. Предположим, что в (1) вместо

6Васильев Ф.П. Методы решения экстремальных задач. -М.: Наука, 1981. -400 с.

fi(x) известны непрерывные функции ff (х), определенные на R" , такие, что

\fi(x) — fi(x)\ < е, е > 0 (VigR", г = 0,1,...,т). (18) Поставим в соответствие задаче (1) проблему нахождения

min .F(:r,r,7), (19)

X

где Р£(х, г, 7) = Ш + £ П [ff+(x)Y + 7 П(х), г = [п,..., rm] > 0, р> 1, 7 > 0, решение которой хста будем находить с точностью £ > 0:

Ps«7>r,7)<infPe(®,r>7) + i.

'' х

В теореме 3.1.4 установлены оценки уклонения точки от решения задачи (1). Из этих оценок выводятся условия согласования управляющих параметров 7, £, г, £, обеспечивающих сходимость х^. к -множеству Ü -нормальных решений задачи (1).

Следствие 3.1.3. Пусть в задаче (19) г* = го (г = 1,..., т). Если Iki £fc, £fc, — положительные числовые последовательности такие, что

lim 7k = lim Ск = lim & = lim — =

к—>оо fc-»oo fc—»00 fc—>00 Гок

= lim — = lim — = lim = lim---= 0,

k-*oo^k *->oo7/fc *-*oo Tfc i-+oo 7^ fy/TÖ^

mo lim p(a;/fc, Xg) = 0 и любая предельная точка последовательности fc—>00

Xk = x%<rk будет fi -нормальным решением задачи (1).

По аналогии со штрафными функциями для регуляризации некорректных задач ВП могут использоваться и барьерные функции. Соответствующие теоретические предпосылки для этого были приведены в § 1.6. Заметим, что вопрос применения барьерных функций вместо штрафных в методе Тихонова в литературе исследован достаточно слабо. В §3.2 исходной проблеме (1) ставится в соответствие задача

m

mjo{ß7(x,s) = Ш + £ ^ + 7 INI2} (= в;,),

где е > 0, р > 1, 7>0, Х° = {х : /(х) < 0} . Доказываются утверждения (теоремы 3.2.1 и 3.2.2) о сходимости 2(7, е) = arg min ß7(x, е) и

23* е к нормальному решению Хд и оптимальному значению /* задачи (1) соответственно.

В следующем § 3.3 для построения метода регуляризации используется функция La(x, А) из главы 2. В отличие от известных схем метода регуляризации данный подход позволяет оценить приближения не только к решению исходной задачи, но и к соответствующим множителям Лагранжа. Кроме того, метод применим и для анализа несобственных задач ВП. Содержание §3.3 разбивается на две части: вначале в п. 3.3.1 исследуется случай разрешимой задачи ВП и в п. 3.3.2 рассматривается несобственная задача ВП. При этом предполагается, что информация о функциях fi(x) (1 = 0,1,...,тп) в задаче (1) носит приближенный характер, т.е. вместо /¿(г) известны непрерывные функции ff (х), удовлетворяющие неравенствам (18). Для приближенной задачи

min{/0e(x): /f(x) < 0, г =

строится регуляризированная по прямым и двойственным переменным функция Лагранжа Lea(x, А), получающаяся из La(x, А) заменой /¿(х) на //(х) (г = 1, ттг). Сильная вогнутость функции Uc{x, А) по А позволяет явным образом выписать функцию у£(х) = maxl£(x, А).

Показано (теорема 3.3.1), что множество Argminy£(x) непусто для

X

любых сг > 0, £ > 0. Далее оценивается степень близости точек х", = arg min <рЕа(х) и решений задачи (1) (теорема 3.3.2). Найдены усло-

X

вия на параметры сие, обеспечивающие сходимость точек х° к множеству X* решений задачи (1) (теорема 3.3.3) и к нормальному решению этой задачи (следствие 3.3.3). Условия сходимости двойственных переменных Ag функции Ьеа(х, А) к минимальному по норме множителю Лагранжа для задачи (1) устанавливаются теоремой 3.3.5 и следствием 3.3.5.

В п. 3.3.2 описанный выше подход к регуляризации задачи (1) на основе функции Ua{x, А) распространяется на несобственную задачу ВП 1-го рода. Аналогично доказывается существование в этом случае точки х° = arg min <£>ст(х) (теорема 3.3.6), устанавливаются оценки уклонения

от решения задачи (4) — аппроксимации для (1) (теорема 3.3.7) и находятся условия сходимости х° к нормальному решению (4) (теорема 3.3.8).

Теорема 3.3.8. Пусть для задачи (4) выполнены условия Куна-Таккера, е—> 0, а—>0, /3—>0, /? = о{а), е = o{aß). Тогда х^ —> Xq > где Xq — нормальное решение задачи (4):

х0 = arg min ||х||, X = Arg min /0(ж).

ZE.X хСЛ^

Методы регуляризации задач ВП могут быть построены и на базе расширенных штрафных функций F(x,\,r) из §1.4 и Fi(x, Л, г) из §1.5. Этому вопросу посвящен § 3.4. Здесь исследуются связи между задачами inf{F(a;, Л,г) + 7 ||х||2} и inf{Fi(x,A,r)-f7||a;||2} и исходной зада-

X X

чей (1), в том числе, несобственной. Используя аппарат доказательства, аналогичный тому, который применялся в §§ 1.4-1.5, находим условия сходимости точек минимума регуляризованных расширенных штрафных функций к нормальному решению задачи (1) (теорема 3.4.1) или ее аппроксимации (4) (теоремы 3.4.2 и 3.4.3).

Теорема 3.4.3. Пусть в точке [i, Л] для задачи (4) выполнены условия Куна-Таккера, q&Q = {q = [Л,г,7] € R™xRi.xM]¡_: г > 0, 7 > 0} , xq = argтт{Ф1(х, q) = F\{x, А, г) + 7 ||а;||2} . Для любого q £ Q выполняются неравенства

ll/+(í,)-íll < 4 0(?), 1Л(г,)-Л(г)I < т ||гр+тах{]|Л||, ||л||} W?),

Следствие 3.4.3. Пусть 7 —> 0, —> 0. Тогда xq —» xq , где

xq — нормальное решение задачи (4).

На основе применения регуляризованных расширенных штрафных функций из предыдущего раздела можно строить конкретные итерационные процедуры для регуляризации задач МП. В §3.5 предлагаются две конструктивно реализуемые алгоритмические схемы для задачи линейной оптимизации с использованием Fy(x, А, г) = F(x, А, г) + 7 ||ж||2.

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

Пусть (1) — НЗ ЛП 1-го рода, fQ(x) = (с,х), f(x) = Ах - Ъ, А = (öij)mxn , be Rm , dij G К1. Обозначим через X множество

решений задачи (4), xq = argmin{||a;|| : х е X] . Пусть хо £ тШ, где ft = {х : х < х < х) , х,х — фиксированные векторы из R" .

Алгоритм 3.5.2. Пусть заданы i°eil, Л° = 0, Го > 1, 7о = 1. Опишем к +1 -й шаг, считая известными хк £ ft, Afc > 0, гк > 0, 7i > 0. Обозначим хк = хк0 . Вычислим

- , р ut _ KVxflfr*), 1кз) 1 _ 0 г -

Fk(x) = Flk(x, Хк, rk), lk° = yks - xk\ yks = [j/f,.. -, укЛ

- (x■ - X ) sen t dFk^\ \x senx - J X> X >

sk = min{4,4}, 4 = min{s : (vxFk(xk% 1кз) = 0} , s2k = {V ] +1, v>l. Положим

xk+1 = xksk, a**1 = [Afc + ßk (Azfc+1 - b)]+, ßk > 0, 1 tk+i = (ft + 1)~T, rM = (ft + l)u, t > 0, w > 0, v>t + w. J

00 00

Теорема 3.5.2. Пусть в алгоритме 3.5.2 Y1 у/R = оо , ßk < °° •

*=o k=о

Тогда lim (Ахк - b)+ = f, lim xk = хо.

к—»00 к—>oo

Методы регуляризации, рассмотренные в §§3.1-3.4, являются теоретическими в том смысле, что в них, как правило, предполагается умение точно определять точку минимума заданной функции. Однако для этой цели может потребоваться бесконечное число итераций некоторого

вспомогательного метода минимизации функций. В § 3.5 были построены алгоритмы, на каждой итерации которых для нахождения приближенного минимума регуляризованной расширенной штрафной функции использовалось конечное число §к шагов метода условного градиента. Недостатками алгоритмов можно считать увеличение ёк с ростом числа итераций к.

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

В § 3.6 предлагается ряд реализаций принципа итеративной регуляризации для задач линейного и выпуклого программирования, основанных на применении регуляризованной функции Лагранжа Ьа(х, X). Вначале строятся алгоритмы для задачи ЛП и двойственной к ней в условиях точного задания информации о функциях задач (алгоритмы 3.6.1 и 3.6.2). Далее предлагается метод регуляризации для НЗ ЛП с приближенными данными (алгоритм 3.6.3), и в заключение обсуждается возможность применения подобных алгоритмов для противоречивых задач ВП (алгоритм 3.6.4).

Рассмотрим, как и в §3.5, НЗ ЛП 1-го рода

Предположим, что в этой задаче вместо А, Ь, с известны их приближения As, bs, с* с погрешностью тах{||Л'5 - А\\, - Ъ\\, ЦС5 - с||} < 5, где 8 > 0, норма матрицы ||Л|| согласована с ||а;||.

Алгоритм 3.6.3. Выберем произвольно х1 е R" . Определим

= [(1 - 2акрк)хк - цк(2ßk)~\Askf(Aökxk - ***)+ -¿ = 1,2,..., ak > 0, ßk>0, 6k> 0, Mfc>0,

где последовательности чисел ak, ßk, fik удовлетворяют условиям:

min{(c,a:) : Ах <b, x > 0}.

k~> oo

lim ak =

= 0, (VA;),

оо со 2 00 Л 00

¿Гакрк = 00, < оо, < 00, ^(аА)Ьк < ОО.

к= 1 к=1 Рк к=1 Рк к=1

Теорема 3.6.3. Последовательность {я*} , определяемая согласно алгоритму 3.6.3, сходится к нормальному решению задачи

тт{(с,х): Ах <Ь + £, х > 0},

где £ определяется как в (4).

В этом методе в качестве регуляризирующей выступила функция

<£(х) = шах{Ь1(х, А) = (с5, х) + (А, А'х -Ъ*) + а \\х\\2 - 01|А||2},

в качестве вспомогательного алгоритма — метод проекции градиента. При доказательстве сходимости здесь существенно использовались полученные в главе 2 оценки уклонений компонент седловых точек функции Ьа(х, А) от решений соответствующих задач МП.

Основные результаты.

1. Построены общие конструкции штрафных функций и сформулированы условия точности и асимптотической сходимости метода штрафных функций как для решения задачи ВП, так и для ее оптимальной коррекции в несобственном случае;

введены новые перспективные расширения штрафных функций, обладающие характерными свойствами модифицированных функций Лагранжа;

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

2. Получены оценки уклонений компонент седловой точки регуляризо-ванной по прямым и двойственным переменным функции Лагранжа Ьа(х, А) от решений исходной и двойственной задач ВП, в том числе, и для несобственных постановок;

исследованы различные по степени общности виды стабилизирующих добавок;

предложены и обоснованы два универсальных по отношению к типам несобственности подхода к оптимальной коррекции задач ВП, основанных на применении функции Ьа(х, Л).

3. Найдены условия управления параметрами регуляризации <т = [а,/?] функции Ьа(х,А) в случае симметрической аппроксимации несобственных задач линейного и квадратичного программирования для нахождения минимальных по норме решений соответствующей пары двойственных задач.

4. Исследованы регуляризирующие свойства ряда модификаций штрафных функций и функции Ьа(х,Х) в условиях неточно заданной информации об исходной задаче ВП как для разрешимого, так и для несобственного случаев;

предложены новые варианты конструктивно реализуемого метода регуляризации для задач линейного и выпуклого программирования, использующие расширенные штрафные функции и функцию Ьа(х, А) и основанные, в частности, на идее итеративной регуляризации.

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

Публикации по теме диссертации

[1] Окарин В.Д. К регуляризации минимаксных задач, возникающих в выпуклом программировании // Ж. вычисл. матсм. и матем. физики, 1977. -Т. 17, № б. -С. 1408-1420 (перечень ВАК).

[2] Скарин В.Д. Об алгоритмах линейного программирования, использующих модификации функции Лагранжа. -В кн. "Методы для нестационарных задач математического программирования". -Свердловск: УНЦ АН СССР, 1979. -С. 74-83.

[3] Скарин В.Д. Об одном итерационном методе нахождения нормального решения задачи линейного программирования. -В кн. "Методы математического программирования и приложения". -Свердловск: УНЦ АН СССР, 1979. -С. 20-25.

[4] Скарин В.Д. О некоторых методах анализа несобственных задач выпуклого и линейного программирования. -В кн. "Несобственные модели математического программирования". -ВИНИТИ, 1980. -№2823-80 Деп. -С. 187-234.

[5] Скарин В.Д. О скорости сходимости метода барьерных функций. -В кн. "Методы оптимизации и распознавания образов в задачах планирования". -Свердловск: УНЦ АН СССР, 1980. -С. 27-36.

[6] Скарип В.Д. К анализу несобственных задач выпуклого программирования с позиций последовательной оптимизации. -В кн. "Несобственные задачи оптимизации". -Свердловск: УНЦ АН СССР, 1982. -С. 30-36.

[7] Скарин В.Д. Методы коррекции несобственных задач выпуклого программирования 1-го рода, основанные на последовательном программировании. -В кн. "Несобственные задачи лилейного и выпуклого программирования" (И.И.Еремин, В.Д.Мазуров, Н.Н.Астафьев}. -М.: Наука, 1083. -С. 262-272.

[8] Скарин В.Д. О применении метода регуляризации для коррекции несобственных задач линейного программирования 1-го рода. -В кн. "Методы аппроксимации несобственных задач математического программирования". -Свердловск: УНЦ АН СССР, 1984. -С. 55-66.

[9| Скарин В.Д. Об одном алгоритме численного анализа несобственных задач линейного программирования. -В кн. "Параметрическая оптимизация и методы аппроксимации несобственных задач математического программирования". -Свердловск: УНЦ АН СССР, 1985. -С. 63-69.

[10] Скарин В.Д. Об одном подходе к анализу несобственных задач линейного программирования // Ж. вычисл. матем. и матем. физики, 1986. -Т. 26, № 3. -С. 439-448 (перечень ВАК).

[11] Скарин В.Д. Об одном методе численного анализа противоречивых задач выпуклого программирования. -В кн. "Противоречивые модели оптимизации". -Свердловск: УНЦ АН СССР, 1987. -С. 56-63.

[12] Скарин В.Д. Об одном регуляризирующем алгоритме коррекции противоречивых задач выпуклого программирования с линейными ограничениями. -В кн. "Исследования по несобственным задачам оптимизации". -Свердловск: УрО АН СССР, 1988. -С. 4856.

[13] Скарин В.Д. Регуляризирующий алгоритм для несобственных полноквадратичных задач выпуклого программирования. -В кн. "Нерегулярная двойственность в математическом программировании". -Свердловск: УрО АН СССР, 1990. -С. 58-67.

[14] Скарин В.Д. О методе регуляризации для противоречивых задач выпуклого программирования К Изв. ВУЗов. Математика, 1995. -У' 12. -С. 81-88 (перечень ВАК).

15] Скарин В.Д. Об одном универсальном подходе к оптимальной коррекции несобственных задач выпуклого программирования. -В кн. "Методы оптимизации и их приложения" (Тр. Х1-й междунар. Байкальской шк.-сем.). -Иркутск: СЭИ СО РАН, 1998. -Т. 1. -С. 56-59.

16] Скарин В.Д. О применении барьерных функций для коррекции несобственных задач выпуклого программирования. -В кн. "Методы оптимизации и их приложения" (Тр. ХИ-й Байкальской междунар. конф.). -Иркутск: ИСЭМ СО РАН, 2001. -Т. 1. -С. 50-54.

[17] Скарин В.Д. Оценочный подход в методах линейного и выпуклого программировал ния // Информ. бюллетень АМП (Приоритетные результаты в области математического программирования. Ч. 1). -Екатеринбург: УрО РАН, 2001. -№ 9. -С. 123-127.

[18] Скарин В.Д. О применении функции Лагранжа для регуляризации задач выпуклого программирования. -В кн. "Современные методы оптимизации и их приложения к моделям энергетики". -Новосибирск: Наука, 2003. -С. 189-209.

[19] Скарин В.Д. О некоторых регуляризирующих и аппроксимирующих свойствах метода штрафных функций в выпуклом программировании // Оптимизация, управление, интеллект, 2005. -№ 1(9). -С. 107-128.

[20] Скарин В.Д. О применении штрафных функций для коррекции несобственных за-дач выпуклого программирования. -В кн. "Методы оптимизации и их приложения" (Тр. XIII-й Байкальской междунар. шк.-сем.). -Иркутск: ИСЭМ СО РАН, 2005. -Т. 1. -С. 175-180.

[21] Скарин В.Д. О методе барьерных функций и алгоритмах коррекции несобственных задач выпуклого программирования // Тр. Ин-та матем. и мех. УрО РАН. -Екатеринбург: ИММ УрО РАН, 2008. -Т. 14, № 2. -С. 115-128 (перечень ВАК).

[22] Скарин В.Д. Расширенная штрафная функция и оптимальная коррекция несобственных задач выпуклого программирования. -В кн. "Методы оптимизации и их приложения" (Тр. XIY-й Байкальской междунар. шк.-сем.). -Иркутск: ИСЭМ СО РАН, 2008. -Т. 1. -С. 203-209.

[23] Скарин В.Д. Аппроксимационные и регуляризирукяцие свойства расширенной штрафной функции в выпуклом программировании // Тр. Ин-та матем. и мех. УрО РАН. -Екатеринбург: ИММ УрО РАН, 2009. -Т. 15, № 4. -С. 234-250 (перечень ВАК).

[24] Скарин В.Д. Об одном общем подходе к оптимальной коррекции несобственных задач выпуклого программирования // Тр. Ин-та математики и механики УрО РАН, 2010. -Т. 16, П'- 3. -С. 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 // Semmaiberichte. -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 (перечень ВАК).

Подписано в печать 25.10.2010 Формат 60 х 84 1/16 Объем 2 п.л.

Офсетная печать Тираж 100 Заказ К'

Ризография НИЧ УрФУ

620002, г.Екатеринбург, ул.Мира, 19

Введение

Глава 1. Метод штрафных функций и несобственная задача выпуклого программирования

§ 1.1. Метод штрафных функций для задач выпуклого программирования.

1.1.1. Метод точных штрафных функций.

1.1.2. Асимптотический случай.

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

§ 1.3. Метод штрафных функций в лексикографической оптимизации

§ 1.4. Расширенная штрафная функция в анализе несобственных задач выпуклого программирования.

§ 1.5. Комбинирование точной и квадратичной штрафных функций

§ 1.6. Метод барьерных функций.

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

Глава 2. Методы регуляризированной функции Лагранжа

§ 2.1. Разрешимая задача выпуклого программирования.

2.1.1. Общий вид стабилизирующих функций.

2.1.2. Стабилизирующие функции на базе евклидовой нормы

2.1.3. Применение нормы Гельдера.

§ 2.2. Несобственная задача выпуклого программирования

2.2.1. Несобственная задача выпуклого программирования

1-го рода.

2.2.2. Общий случай несобственности задачи выпуклого программирования.

§2.3. Несобственная задача линейного программирования.

§ 2.4. Несобственная задача квадратичного программирования

§ 2.5. Задача полноквадратичного программирования.

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

2.6.1. Задача выпуклого программирования с противоречивыми ограничениями

2.6.2. Задача выпуклого программирования с совместной системой ограничений.

Глава 3. Методы регуляризации задач выпуклого программирования

§3.1. Метод штрафных функций и регуляризация задачи выпуклого программирования

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

§ З.З.Регуляризирующие свойства модифицированной функции

Лагранжа La{pc, Л) для задач, заданных приближенно

3.3.1. Регуляризация разрешимых задач выпуклого программирования.

3.3.2. Несобственная задача выпуклого программирования

§3.4. Методы регуляризации на основе расширенных штрафных функций.

§ 3.5. Метод расширенной штрафной функции и регуляризация задачи линейного программирования

§3.6. Методы итеративной регуляризации для несобственных задач линейного и выпуклого программирования.

3.6.1. Метод итеративной регуляризации для разрешимой задачи линейного программирования

3.6.2. Итеративная регуляризация несобственной задачи линейного программирования.

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

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

Рассмотрим задачу МП где X = {х еЖп : Цх) < 0}, /(ж) = [Л(х),., /т(х)] , /¿(ж) непрерывные функции, определенные на 1п (г = 0,1,., т).

Метод штрафных функций лежит в основе универсального подхода к решению экстремальных задач различной природы. Применительно к МП данный метод ставит в соответствие проблеме (1) последовательность задач где = /о(ж) + Ф(ж,г), Ф(ж, г) — заданная некоторым образом функция "штрафа" за нарушение ограничений, определяющих множество X , 7* = [7*1, . , Гт] ~ вектор штрафных коэффициентов, Г{ > 0 , 1 < г < т, Хо — множество более простой природы, чем- X (чаще всего Хо = Мп). Функция Ф(х,г) строится таким образом,, чтобы последовательность решений задачи (2) сходилась (в том или ином смысле при определенном изменении параметра г) к решению исходной задачи (1).

Метод штрафных функций порождает не только целое семейство вычислительных процедур, но и служит эффективным инструментом теоретического анализа задач оптимизации. Методу посвящено большое количество работ (их обзоры содержатся, например, в [12, 20, 47, 55, 83, 112, 167, 184, тш{Мх):хеХ} (=/*),

1)

2>

185]). При этом важное значение имеет метод точных штрафных функций, предложенный в 1966 г. И.И.Ереминым [61, 62, 242]. Данный метод позволяет в принципе свести решение исходной задачи на условный экстремум к однократной минимизации без ограничений подходящим образом выбранной вспомогательной функции. Проблема построения таких функций и нахождение условий точности для различных классов задач МП занимает заметное место в специальной литературе и продолжает оставаться актуальной [48, 52, 56, 57, 68, 185, 192, 197, 206, 211, 243].

Вместе с тем точные штрафные функции не всегда отвечают необходимым условиям гладкости для применения эффективных процедур численной минимизации к решению задачи (2). С другой стороны, выбор конструкций штрафных функций достаточно обширен, что позволяет в общем случае обеспечить требуемые свойства выпуклости и гладкости функции г) при фиксированном г , но при этом сходимость метода достигается в пределе при ттгг —> +оо . С ростом же г увеличивается овражность функции Ф(ж,г) (ухудшается обусловленность (см., например, [123, 217]) задачи (2)), что влечет за собой значительные вычислительные трудности при практическом поиске минимума F(x, г).

Один из возможных путей преодоления трудностей, возникающих вследствие ухудшения обусловленности задачи (2), предлагает метод модифицированной функции Лагранжа. Наиболее прозрачно идея этого метода выглядит для задачи (1) с ограничениями-равенствами fi(x) = 0 , г = 1, m . В этом случае задаче (1) ставится в соответствие задача mî M (х, А, г), (3) X m где М(х, А, г) = /оН + ЕШ + Ф^г), А = [Ai,.,Am] > 0, i

Ф(ж,г) = г > 0. С одной стороны, данный метод можно рассматривать как некоторое расширение метода штрафных функций (за счет введения в штрафную функцию дополнительного слагаемого т

X) )> с Другой — замечаем, что М(х, Л, г) = Ь(х, А) + Ф(ж, г) , где 1

Ь(х, Л) = /о(^) + X Лг/г(ж)) — стандартная функция Лагранжа для задачи (1). Поэтому М(х,Х,г) можно интерпретировать и как определенную модификацию функции Лагранжа для задачи (1).

Хорошо известна тесная связь между решением задачи (1) и нахождением седловых точек [х, А] функции Ь(х, А). Эта связь, выраженная в классической теореме Куна-Таккера [171], играет центральную роль в теории МП. Множители Лагранжа А важны при анализе оптимальности и устойчивости в задаче МП [39, 73, 108], имеют наглядную и полезную интерпретацию, связанную с содержательной постановкой задач, прежде всего, экономических [72, 86, 104]. Идея поиска седловых точек функции Ь(х, А) широко используется для построения численных алгоритмов МП. Типичным представителем таких алгоритмов является градиентный метод Эрроу-Гурвица [171]. Однако данный метод сходится при достаточно жестких ограничениях на задачу (1) [40, 87, 123, 171]. Причина плохой сходимости кроется в неоднородности свойств выпуклости и вогнутости функции Ь(х, А) по х и по А соответственно.

Для улучшения сходимости метода Эрроу-Гурвица и была первоначально использована [171] функция М(х, А, г) из (3). Таким образом, целесообразность рассмотрения модификаций функции Лагранжа обусловлена как трудностями численной реализации алгоритмов, основанных на штрафных функциях, так и алгоритмов поиска седловых точек функции Ь(х, А).

С конца 60-х годов прошлого столетия был предложен достаточно широкий спектр модификаций функции Лагранжа и численных алгоритмов, основанных на их применении, для различных классов задач МП [4, 35, 42, 55, 79, 84, 123, 124, 183, 184, 191, 196, 208, 227, 229, 244]. Как правило, новые функции строились таким образом, чтобы имело место совпадение множеств седловых точек модифицированной функции Лагранжа и функции L(x, А) или оно достигалось в пределе при изменении соответствующих параметров.

Современные тенденции в развитии методов штрафных функций и модифицированных функций Лагранжа состоят как в нахождении новых перспективных конструкций вспомогательных функций (например, сочетающих свойства функции Лагранжа и барьерных функций [127, 128, 176, 179, 195, 226]), так и в максимальном расширении сферы применения этих функций. В первую очередь это касается построения новых алгоритмов для анализа таких классов задач МП, как невыпуклые [48, 58, 84, 95, 178, 186, 187, 191, 202, 210], негладкие [25, 51, 175, 238], нестационарные [32, 55, 75], бесконечномерные [1, 9, 52, 189, 190, 193, 198, 232], многокритериальные [82, 90, 121, 166], полуопределенные [194, 212, 225, 237], билинейные [6, 241], несобственные [29, 76, 126,140,150,155] и некорректные [3,18,19, 22,152], а также задач большой размерности [180]. В настоящей работе основное внимание уделяется применению указанных выше функций к несобственным и некорректным задачам линейного и выпуклого программирования.

Одним из важнейших в теории МП является понятие двойственности. Задача, двойственная к (1), может быть сформулирована как где ф(А) = іпїЦх, А), А = {А Є 1? : ф(А) > -оо} . Из теории двойх ственности для различных классов задач МП известны условия (см., например, [12, 39, 73,129,131,170]), при которых для задач (1) и (4) выполняются соотношения двойственности где X* и А* — множества решений задач (1) и (4) соответственно. max{V>(A) : А Є А}, (= ф*)

4)

X* ^ 0, А* ^ 0, /* =

Если соотношения двойственности (5) не выполняются, то задача (1) становится несобственной [76]. Свойство несобственности тесно связано с тем, совместны или нет множества X и Л. Поэтому о несобственных задачах говорят в более узком смысле как о "противоречивых" моделях МП или как о задачах МП с противоречивыми ограничениями.

Интерес к противоречивым моделям обусловлен как потребностями математической теории (анализ систем уравнений и неравенств, задачи теории приближения функций, некорректные задачи, задачи идентификации, распознавания образов и др.), так и необходимостью анализа прикладных задач с противоречивыми условиями, прежде всего экономических. При этом практика показывает, что появление несовместных моделей в сфере управления производственной деятельностью — это обычное явление. Причинами его могут быть, с одной стороны, погрешности моделирования сложной экономической системы (ошибки в выборе и оценке структурных связей, плохое качество исходной информации, трудности формализации и т.п.), с другой, — объективные противоречия, характеризующие моделируемую систему. Так, для систем управления производственно-экономической деятельностью противоречивость может возникнуть вследствие дефицита сырьевых, финансовых и других ресурсов, необоснованности требований к состоянию технико-экономических показателей, несогласованности целей производства и охраны окружающей среды, стремления к оптимизации по нескольким критериям и т.д.

Распространенность и актуальность несобственных задач порождает острую необходимость разработки теории и методов их численной аппроксимации. Отдельные публикации, связанные с анализом противоречивых задач, появились достаточно давно [60, 63, 103,110, 115, 116]. Систематическое же исследование несобственных задач МП было инициировано работами уральской школы по МП, возглавляемой академиком И.И.Ереминым

65, 67, 74, 76]. Впоследствии эта тема получила достаточно широкое отражение в специальной литературе [17, 26, 28, 29, 44, 46, 78, 89, 102, 111, 114, 125, 169, 172, 188, 216, 231]. В области теории несобственных задач основное внимание уделялось формированию двойственных задач и выводу соотношений двойственности [8, 66, 71, 72, 74, 113], в области численных методов — созданию методов оптимальной коррекции несобственных задач [2, 27, 91, 126, 142, 150]. Построение методов оптимальной коррекции как объективных процедур "развязки" противоречивых ограничений может базироваться на разных идеях. Это может быть идея погружения рассматриваемой противоречивой модели в параметрическое семейство разрешимых задач с нахождением при этом оптимального значения параметра. Далее, существует идея ранжирования ограничений, когда условия задачи разбиваются на две части. Одна часть ограничений определяет непустое множество M , а вторая агрегируется с помощью вспомогательной штрафной функции с последующей ее минимизацией на M . Наконец, это может быть подход с позиций дискретной оптимизации, связанной с решением оптимизационной задачи на совместных покрытиях системы ограничений исходной модели.

Большое значение при численном решении задачи (1) имеет корректность ее постановки. Решение корректно поставленной задачи должно непрерывно зависеть от информации о функциях fi(x). Так как в реальных практических задачах эти функции задаются, как правило, с определенной степенью погрешности, то решение этой приближенной задачи в случае ее корректности и малой величины погрешности будет близким к решению точно заданной задачи. С другой стороны, многие важные в прикладном отношении задачи планирования, проектирования и управления не обладают [163] свойством корректности, т.е. задачи являются некорректно поставленными. Более строго: задача (1) некорректно поставлена [18], если /* > — ОО , X* 0 , существует последовательность точек Xf~ Е X таких, что lim fo{xk) = /* , но lim p(xk, X*) ф 0 . В таких задачах в качеоо к—>оо стве приближенного решения, вообще говоря, нельзя брать элемент минимизирующей последовательности с произвольно большим номером к . Для этой цели требуется строить специальные методы, которые бы обеспечивали сходимость итерационной последовательности точек к множеству решений задачи (1). Такие методы называются методами регуляризации.

Начало исследований теории и методов некорректных задач связано с именами А.Н.Тихонова [161, 162], В.К.Иванова [92, 93], М.М.Лаврентьева [105]. К настоящему времени по данной проблематике опубликовано значительное количество работ, среди которых отметим [15, 18, 21, 24, 69, 94, 101, 106, 117, 163, 164]. К этому направлению также тесно примыкают исследования по устойчивости задач МП (работы [7, 10, 16, 70, 108, 166, 174, 177, 199, 204, 245] — для непрерывных задач МП, [49, 50, 59, 132] — для дискретного случая).

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

Настоящая работа состоит из введения, трех глав и списка литературы.

Основные результаты диссертационной работы, выносимые на защиту, состоят в следующем.

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

2. Получены оценки уклонений компонент седловой точки регуляризо-ванной по прямым и двойственным переменным функции Лагранжа Ьа(х, А) от решений исходной и двойственной задач ВП, в том числе, и для несобственных постановок; исследованы различные по степени общности виды стабилизирующих добавок; предложены и обоснованы два универсальных по отношению к типам несобственности подхода к оптимальной коррекции задач ВП, основанных на применении функции Ьа(х, А) .

3. Найдены условия управления параметрами регуляризации а = [а, ¡3] функции Ьа(х, А) в случае симметрической аппроксимации несобственных задач линейного и квадратичного программирования для нахождения минимальных по норме решений соответствующей пары двойственных задач.

4. Исследованы регуляризирующие свойства ряда модификаций штрафных функций и функции La(x, А) в условиях неточно заданной информации об исходной задаче ВП как для разрешимого, так и для несобственного случаев; предложены новые варианты конструктивно реализуемого метода регуляризации для задач линейного и выпуклого программирования, использующие расширенные штрафные функции и функцию La(x, А) и основанные, в частности, на идее итеративной регуляризации.

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

Результаты, составляющие основное содержание диссертации, опубликованы в следующих работах автора:

§ 1.1 - [151, 153], § 1.2 - [140, 141, 153, 154], § 1.3 - [140, 141, 234],

§ 1.4 - [156, 157], § 1.5 - [139, 155], § 1.6 - [139, 155], § 1.7- [150, 155],

§ 2.1 - [135, 235], § 2.2 - [142, 148, 149, 235], § 2.3 - [144],

§ 2.4 - [235], § 2.5 - [147], § 2.6 - [158],

§ 3.1 - [153], § 3.2 - [155], § 3.3 - [152],

§ 3.4 - [157], § 3.5 - [136, 137, 157], § 3.6 - [138, 143, 145].

Обозначения и сокращения

Мп — вещественное п -мерное евклидово пространство; (•, ■) — скалярное произведение в М71; х = [жі,.,жп] — вектор х Є Мп с координатами Xj (при матричной записи х — матрица размера (n х 1)) ; х > 0 — Xj > 0 для всех j = 1,., п ; х > 0 — Xj > 0 для всех j — 1,., п ; {х <е W1 : х > 0} ; ж : £} — множество всех точек х , удовлетворяющих условию С ; — равно по определению;

V х Є М — для всех точек х из множества М ;

3 х Є М — существует точка х множества М ; п

Wx\\i = \хз\ ~~ октаэдрическая норма вектора х ; г=1

Оп^ \ 1/2

Г xf J — евклидова норма вектора х Є Мп ; / п \і/Р

МІр = ( \xj\P) ~ норма Гельдера вектора х (1 < р < оо) ;

ЦхЦоо = max \xj\ — чебышевская норма вектора х ; 1 <j<n

Ат — матрица, транспонированная к матрице А ;

Е — единичная матрица; А\\ — норма матрицы А ; intX — внутренность множества X ; diamX = sup ||ж — у\\ — диаметр множества X ;

Х,уех sup — точная верхняя грань; inf — точная нижняя грань; /+(*) = max {0,/(я)}; а [аь ., ап]+ = [а+,., а+] ег- = ef = [0,., 1,., 0] — г -й единичный вектор пространства Rn ; i df(x) — субдифференциал выпуклой функции f(x) в точке х ; V/M = , • • •, dj^ — градиент функции f(x) в точке ж ; df(x) f(x + al)—f(x) l ' = lim -^-J v ' — производная функции / в точке х по направлению I £ Жп ; Ргм (х) — проекция точки х на множество М С Rn ; р(х, М) = inf IIж — у\\ — расстояние от точки х до множества М ; уеМ

Arg min f{x) — множество точек глобального минимума функции f{x) на хеХ множестве X; arg min f(x) — точка из множества Arg min/(ж); х£Х ХЕХ

1) найти /* = inf f(x),

2) если inf достигается, найти х* = arg min/(ж); xGX

Arg(Р) — множество решений задачи Р ; arg(P) — элемент множества Arg(P) ; opt(P) — оптимальное значение задачи Р ; N — множество натуральных чисел; к,р= {к,к +1,., р}, к,р £ N; 7 ] — целая часть числа 7 ;

ЛП — линейное программирование; КП — квадратичное программирование;

ВП — выпуклое программирование; МП — математическое программирование; НЗ — несобственная задача.

Заключение

1. Абанъкин А.Е.О точных штрафных функциях // Вестник С.-Петерб. ун-та. Сер. 1, 1995. 3(13). -С. 3-8.

2. Абрамов А.П. Несобственные задачи оптимального выбора плановых пропорций. -В кн. "Исследование операций (модели, системы, решения)". -М.: ВЦ РАН, 1994. -С. 3-14.

3. Антипин A.C. Метод регуляризации в задачах выпуклого программирования // Экономика и матем. методы, 1975. -Т. 11, № 2. -С. 336-342.

4. Антипин A.C. Методы нелинейного программирования, основанные на прямой и двойственной модификации функции Лагранжа. -М.: Изд-во ВНИИСИ, 1979. -74 с.

5. Антипин A.C. О сходимости и оценках скорости сходимости проксимальных методов к неподвижным точкам экстремальных отображений // Ж. вычисл. матем. и матем. физики, 1995. -Т. 35, № 5. -С. 688-704.

6. Антипин A.C. Методы множителей в билинейном равновесном программировании с приложением к играм с ненулевой суммой // Тр. Ин-та матем. и мех. УрО РАН. -Екатеринбург: ИММ УрО РАН, 2002. -Т. 8, № 1. -С. 3-30.

7. Астафьев H.H. Устойчивость и маргинальные значения задачи выпуклого программирования // Сиб. мат. ж., 1978. -Т. 19, № 3. -С. 491-503.

8. Астафьев H.H. Бесконечномерные задачи линейного программирования с разрывом в двойственности // ДАН СССР, 1984. -Т. 275, № 5. -С. 1033-1036.

9. Астафьев H.H. Бесконечные системы линейных неравенств в математическом программировании. -М.: Наука, 1991. -136 с.229

10. Ашманов С.А. Линейное программирование. -М.: Наука, 1981. -340 с.

11. Ащепков Л.Т., Белов Б.И., Булатов В.П. Численные методы в математическом программировании и оптимальном управлении. -Новосибирск: Наука, 1984. -233 с.

12. Базара М., Шетти К. Нелинейное программирование. Теория и алгоритмы. -М.: Мир, 1982. -583 с.

13. Бакушинский А.Б. Методы решения монотонных вариационных неравенств, основанные на принципе итеративной регуляризации // Ж. вычисл. матем. и матем. физики, 1977. -Т. 17, № 6. -С. 1350-1362.

14. Бакушинский А.Б. К принципу итеративной регуляризации // Ж. вычисл. матем. и матем. физики, 1979. -Т. 19, № 4. -С. 1040-1043.

15. Бакушинский А.Б., Гончарский A.B. Итеративные методы решения некорректных задач. -М.: Наука, 1989. -128 с.

16. Белоусов Е.Г. Разрешимость и устойчивость задач математического программирования. -В кн. "Методы оптимизации и их приложения" (Тр. ХШ-й Байкальской междунар. шк.-сем.). -Иркутск: ИСЭМ СО РАН, 2005. -Т. 1. -С. 203-208.

17. Булавский В.А. Обобщенные решения и регуляризация систем неравенств // Вычисл. методы линейной алгебры. -Новосибирск: ИМ СО АН СССР, 1985. -Т. 6. -С. 161-174.

18. Васильев Ф.П. Численные методы решения экстремальных задач. -М.: Наука, 1988. -552 с.

19. Васильев Ф.П., Иваницкий А.Ю. Линейное программирование. -М.: Факториал, 1998. -176 с.

20. Васильев Ф.П., Ковач М. О регуляризации некорректных экстремальных задач с использованием штрафных и барьерных функций / / Вестник Моск. ун-та. Сер. вычисл. матем. и киберн., 1980. 2. -С. 29-35.

21. Васильев Ф.П., Ячимович М.Д. Об итеративной регуляризации метода условного градиента и метода Ньютона при неточно заданных исходных данных // ДАН СССР, 1980. -Т. 250, № 2. -С. 265-269.

22. Васин В.В., Агеев A.J1. Некорректные задачи с априорной информацией. -Екатеринбург: УИФ Наука, 1993. -262 с.

23. Васин В.В., Еремин И. И. Операторы и итерационные процессы фейе-ровского типа. Теория и приложения. -Екатеринбург: УрО РАН, 2005. -212 с.

24. Ватолин A.A. Об аппроксимации несобственных задач выпуклого программирования // Мат. заметки, 1983. -Т. 33, вып. 4. -С. 627-636.

25. Ватолин A.A. Аппроксимация несобственных задач линейного программирования по критерию евклидовой нормы // Ж. вычисл. матем. и матем. физики, 1984. -Т. 24, № 2. -С. 1907-1908.

26. Вересков А.И., Гольштейн Е.Г. О задаче линейного программирования в размытой постановке // Экономика и матем. методы, 1986. -Т. 22, № 6. -С. 1078-1093.

27. Вересков А.И., Третьяков И.В. Об использовании модифицированных функций Лагранжа для корректировки несовместных задач выпуклого программирования // Изв. АН СССР. Техн. кибернетика, 1988. 1. -С. 70-81.

28. Вилков В. Б. Некоторые свойства функции Лагранжа в задачах математического программирования // Кибернетика, 1986. -№ 1. -С. 65-69.

29. Владимиров A.A., Нестеров Ю.Е., Чеканов Ю.Н. О равномерно выпуклых функционалах // Вестник Моск. ун-та. Сер. вычисл. матем. и киберн., 1978. 1. -С. 12-23.

30. By Г., Намм Р.В., Сачков С.А. Итерационный метод поиска седло-вой точки для полукоэрцитивной задачи Синьорини, основанный на модифицированном функционале Лагранжа // Ж. вычисл. матем. и матем. физики, 2006. -Т. 46, № 1. -С. 25-36.

31. Гермейер Ю.Б. К задаче отыскания максимина с ограничениями // Ж. вычисл. матем. и матем. физики, 1970. -Т. 10, № 1. -С. 39-54.

32. Галл Ф., Мюррей У., Райт М. Практическая оптимизация. -М.: Мир, 1985. -509 с.

33. Голиков А.И. Модифицированные функции Лагранжа в нелинейном программировании. -М.: ВЦ АН СССР, 1988. -56 с.

34. Голиков А.И., Евтушенко Ю.Г. Отыскание нормальных решений в задачах линейного программирования // Ж. вычисл. матем. и матем. физики, 2000. -Т. 40, № 12. -С. 1766-1786.

35. Голиков А.И., Евтушенко Ю.Г. Новый метод решения систем линейных равенств и неравенств // Докл. РАН, 2001. -Т. 381, № 4. -С. 444-447.

36. Голиков А.И., Евтушенко Ю.Г. Нахождение проекции заданной точки на множество решений задач линейного программирования //Тр. Ин-та матем. и мех. УрО РАН. -Екатеринбург: ИММ УрО РАН, 2008. -Т. 14, № 2. -С. 33-47.

37. Гольштейн Е.Г. Теория двойственности в математическом программировании и ее приложения. -М.: Наука, 1971. -352 с.

38. Голъштейн Е.Г. Обобщенный градиентный метод отыскания седло-вых точек // Экономика и матем. методы, 1972. -Т. 8, № 4. -С. 569-579.

39. Голъштейн Е.Г., Третьяков Н.В. Модифицированные функции Лаг-ранжа // Экономика и матем. методы, 1974. -Т. 10, № 3. -С. 568-591.

40. Голъштейн Е.Г., Третьяков Н.В. Модифицированные функции Лаг-ранжа. Теория и методы оптимизации. -М.: Наука, 1989. -400 с.

41. Горбунов В.К. О регуляризации экстремальных задач // Ж. вычисл. матем. и матем. физики, 1991. -Т. 31, № 2. -С. 235-248.

42. Горелик В.А. Матричная коррекция задачи линейного программирования с несовместной системой ограничений // Ж. вычисл. матем. и матем. физики, 2001. -Т. 41, № 11. -С. 1697-1705.

43. Горелик В.А., Ерохин В.И. Оптимальная матричная коррекция несовместных систем линейных алгебраических уравнений по минимуму евклидовой нормы. -М.: ВЦ РАН, 2004. -192 с.

44. Горелик В.А., Кондратьева В.А. Параметрическое программирование и несобственные задачи линейной оптимизации. В кн. "Моделирование, декомпозиция и оптимизация сложных динамических процессов". -М.: ВЦ РАН, 1999. -С. 56-82.

45. Гроссман К., Каплан A.A. Нелинейное программирование на основе безусловной минимизации. -Новосибирск: Наука, 1981. -184 с.

46. Данилин Ю.М., Ковнир В.Н. Об одной точной штрафной функции для задачи нелинейного программирования // Кибернетика, 1986.5. -С. 43-46.

47. Девятерикова М.В., Колоколов A.A. Анализ устойчивости некоторых алгоритмов дискретной оптимизации / / Автоматика и телемеханика, 2004. 3. -С. 48-54.

48. Девятерикова М.В., Колоколов А.А., Колосов А.П. К решению дискретной задачи планирования производства с интервальными данными // Тр. Ин-та матем. и мех. УрО РАН. -Екатеринбург: ИММ УрО РАН, 2008. -Т. 14, № 2. -С. 48-57.

49. Демьянов В.Ф. Точные штрафные функции в задачах негладкой оптимизации // Вестник СПб ун-та. Сер. 1, 1994. 4(12). -С. 21-27.

50. Демьянов В. Ф. Условия экстремума и вариационное исчисление. -М.: Высш. шк., 2005. -335 с.• 53. Денисов Д. В. Метод итеративной регуляризации в задачах условной минимизации // Ж. вычисл. матем. и матем. физики, 1978. -Т. 18, № 6. -С. 1405-1415.

51. Дикин И.И., Зоркальцев В.И. Итеративное решение задач математического программирования (алгоритмы метода внутренних точек). -Новосибирск: Наука, 1980. -144 с.

52. Евтушенко Ю.Г. Методы решения экстремальных задач и их применение в системах оптимизации. -М.: Наука, 1982. -432 с.

53. Евтушенко Ю.Г. Оценки точности в методах штрафных функций. -В кн. "Проблемы прикладной математики и информатики". -М.: Наука, 1987. -С. 199-208.

54. Евтушенко Ю.Г., Жадан В. Г. Точные вспомогательные функции в задачах оптимизации // Ж. вычисл. матем. и матем. физики, 1990. -Т. 30, № 1. -С. 43-57.

55. Евтушенко Ю.Г., Жадан В. Г. Барьерно-проективные и барьерно-ньютоновские методы решения задач нелинейного программирования // Ж. вычисл. матем. и матем. физики, 1994. -Т. 34, № 5. -С. 669-684.

56. Емеличев В.А., Подкопаев Д.П. Устойчивость и регуляризация векторных задач целочисленного линейного программирования // Дискретный анализ и исслед. операций. Сер. 2, 2001. Т. 8. -С. 47-69.

57. Еремин И. И. О несовместных системах линейных неравенств // ДАН СССР, 1961. -Т. 138, № 6. -С. 1280-1283.

58. Еремин И. И. О методе штрафов в выпуклом программировании // Тез. междунар. матем. конгр. Секц. 14. -М., 1966.

59. Еремин И. И. Метод "штрафов" в выпуклом программировании // ДАН СССР, 1967. -Т. 173, № 4. -С. 748-751.

60. Еремин И. И. О задачах выпуклого программирования с противоречивыми ограничениями // Кибернетика, 1971. 4. -С. 124-129.

61. Еремин И. И. О задачах последовательного программирования // Сиб. мат. ж., 1973. Т. 14, №. 1. -С. 53-63.

62. Еремин И. И. Двойственность для несобственных задач линейного и выпуклого программирования // ДАН СССР, 1981. -Т. 256, № 2. -С. 272-276.

63. Еремин И. И. Двойственность и аппроксимация для несобственных задач математического программирования // Изв. АН СССР. Техн. кибернетика, 1987. 1. -С. 70-81.

64. Еремин И.И. Противоречивые модели оптимального планирования. -М.: Наука, 1988. -160 с.

65. Еремин И. И. К методу штрафов в математическом программировании // Докл. РАН, 1996. -Т. 346, № 4. -С. 459-461.

66. Еремин И.И. Теория линейной оптимизации. -Екатеринбург: УрО РАН, 1999. -312 с.

67. Еремин И. И. Общая теория устойчивости в линейном программировании // Изв. ВУЗов. Математика, 1999. -№ 12. -С. 43-52.

68. Еремин И. И. Двойственность в линейной оптимизации. -Екатеринбург: УрО РАН, 2001. -180 с.

69. Еремин И. И. Теория двойственности в линейной оптимизации. -Челябинск: "Библиотека А.Миллера", 2005. -196 с.

70. Еремин И.И., Астафьев H.H. Введение в теорию линейного и выпуклого программирования. -М.: Наука, 1976. -192 с.

71. Еремин И.И., Мазуров В.Д., Астафьев H.H. Несобственные задачи линейного и выпуклого программирования. -М.: Наука, 1983. -336 с.

72. Еремин И.И., Мазуров В.Д., Опарин В.Д., Хачай М.Ю. Математические методы в экономике. -Екатеринбург: Изд-во "Y-Фактория", 2000. -280 с.

73. Ерохин В. И. Матричная коррекция двойственной пары несобственных задач линейного программирования // Ж. вычисл. матем. и матом. физики, 2007. -Т. 47, № 4. -С. 587-601.

74. Жадан В. Г. Модифицированные функции Лагранжа в нелинейном программировании // Ж. вычисл. матем. и матем. физики, 1982. -Т. 22, № 2. -С. 296-308.

75. Жадан В. Г. Об одном классе итеративных методов решения задач выпуклого программирования // Ж. вычисл. матем. и матем. физики, 1984. -Т. 24, № 5. -С. 665-676.

76. Жадан В. Г. О некоторых оценках коэффициента штрафа в методах штрафных функций // Ж. вычисл. матем. и матем. физики, 1984. -Т. 24, № 8. -С. 1164-1171.

77. Жадан В. Г. Точные штрафные функции в невыпуклой многокритериальной оптимизации. -В кн. "Методы оптимизации и их приложения" (Тр. XII-й Байкальской междунар. конф.). -Иркутск: ИСЭМ СО РАН, 2001. -Т. 1. -С. 317-323.

78. Жадан В. Г. Численные методы линейного и нелинейного программирования. Вспомогательные функции в условной оптимизации. -М.: ВЦ РАН, 2002. -160 с.

79. Заботин Я.И., Фукин И. А. Об одной модификации метода сдвига штрафов для задач нелинейного программирования // Изв. ВУЗов. Математика, 2000. 12. -С. 49-54.

80. Зангвилл У.И. Нелинейное программирование. -М.: Сов. радио, 1973. -312 с.

81. Зоркалъцев В.И. Обоснование алгоритма внутренних точек // Ж. вы-числ. матем. и матем. физики, 1999. -Т. 39, № 2. -С. 208-221.

82. Зыкина A.B. Параметризация в несобственных задачах линейного программирования. -В кн. "Дискретная оптимизация и анализ сложных систем". -Новосибирск: ВЦ СО АН СССР, 1989. -С. 56-61.

83. Зыкина A.B. Параметрическое обобщенное решение в линейной векторной оптимизации // Кибернетика и сист. анализ, 2001. 1. -С. 177-181.

84. Зыкина A.B. Обобщенное решение для интерактивной процедуры // Кибернетика и сист. анализ, 2004. -JY® 2. -С. 10-16.

85. Иванов B.K. О линейных некорректных задачах // ДАН СССР, 1962. -Т. 145, № 2. -С. 270-272.

86. Иванов В.К. О некорректно поставленных задачах // Матем. сборник, 1963. -Т. 61, № 2. -С. 211-223.

87. Иванов В.К., Васин В.В., Танана В.П. Теория линейных некорректных задач и ее приложения. -М.: Наука, 1978. -208 с.

88. Ижуткин B.C., Петропавловский М.В. Методы приведенных направлений на основе модифицированной функции Лагранжа для задачи нелинейного программирования // Изв. ВУЗов. Математика, 1995. 12. -С. 33-42.

89. Ижуткин B.C., Петропавловский М.В., Блинов A.B. Методы центров и барьерных функций с использованием приведенных направлений для задачи нелинейного программирования // Изв. ВУЗов. Математика, 1996. 12. -С. 30-41.

90. Ишмухаметов А.З. Двойственный метод решения одного класса выпуклых задач минимизации // Ж. вычисл. матем. и матем. физики, 2000. -Т. 40, № 7. -С. 1045-1060.

91. Ишмухаметов А.З. Регуляризованные приближенные методы проекции и условного градиента с конечношаговыми внутренними алгоритмами // Ж. вычисл. матем. и матем. физики, 2003. -Т. 43, № 12. -С. 1896-1909.

92. Калинин И.Н., Стерлин A.M. Об одном варианте модифицированной функции Лагранжа // ДАН СССР, 1982. -Т. 267, № 4. -С. 787-789.

93. Каплан A.A. Алгоритмы выпуклого программирования, использующие сглаживание точных функций штрафа // Сиб. матем. ж., 1982. -Т. 23, № 4. -С. 53-64.

94. Карманов В.Г. Математическое программирование. -М.: Наука, 1980. -256 с.

95. Ковалев М.М., Топчишвили А.Л. Несобственные задачи выпуклой дискретной оптимизации // Вестник БГУ. Сер. 1, 1991. 1. -С. 39-41.

96. Коробкин А.Д., Михайленко Ю.М. К анализу несовместных систем ограничений в задачах оптимизации. -В кн. "Применение ЭВМ в оптимальном планировании и управлении". -Новосибирск: ИМ СО РАН, 1980. 4. -С. 3-25.

97. Крушевский A.B., Швецов К.И. Математическое программирование и моделирование в экономике. -Киев: Вища школа, 1979. -456 с.

98. Лаврентьев М.М. О некоторых некорректных задачах математической физики. -Новосибирск: СО АН СССР, 1962. -92 с.

99. Лаврентьев М.М., Романов В.Г., Шишатский С.П. Некорректные задачи математической физики и анализа. -М.: Наука, 1980. -286 с.

100. Левитин Е. С. О корректности ограничений и устойчивости в экстремальных задачах // Вестник Моск. ун-та. Сер. матем., мех., 1968.1. -С. 24-34.

101. Левитин Е.С. Теория возмущений в математическом программиро- „ вании и ее приложения. -М.: Наука, 1992. -360 с.

102. Любич Ю.И., Майстровский Г.Д. Общая теория релаксационных процессов для выпуклых функционалов // Усп. матем. наук, 1970. -Т.25, № 1(151). -С. 57-112.

103. Мазуров Вл.Д. О построении комитета системы выпуклых неравенств // Кибернетика, 1967. -№ 2. -С. 56-59.

104. Мазуров Вл.Д. Метод комитетов в задачах оптимизации и классификации. -М.: Наука, 1990. -248 с.

105. Мину М. Математическое программирование. Теория и алгоритмы. -М. : Наука, 1990. -488 с.

106. Мирзоахмедов Ф., Мошеев Л. И. Двойственность для одного класса несобственных задач линейного программирования и их приложения // Кибернетика, 1990. 6. -С. 30-34.

107. Могилевская Р.Л., Шварцман П. А. О корректировке свободных членов несовместной системы линейных неравенств // Экономика и ма-тем. методы, 1988. -Т. 24, № 1. -С. 147-154.

108. Молчанов H.H., Яковлев М.Ф. Итерационные процессы решения одного класса несовместных систем алгебраических уравнений //Ж. вычисл. матем. и матем. физики, 1975. -Т. 15, № 3. -С. 547-558.

109. Морозов В.А. О псевдорешениях // Ж. вычисл. матем. и матем. физики, 1969. -Т. 9, № 6. -С. 1387-1391.

110. Морозов В.А. Регулярные методы решения некорректно поставленных задач. -М.: Наука, 1987. -239 с.

111. Нестеров Ю.Е. Эффективные методы выпуклой оптимизации. -М.: Радио и связь, 1989. -301 с.

112. Нурминский Е.А. Численные методы выпуклой оптимизации. -М.: Наука, 1991. -167 с.

113. Панин В.М. Методы конечных штрафов с линейной аппроксимацией ограничений // Кибернетика, 1984. -Ч. 1, № 2. -С. 44-50. -Ч. 2, № 4. -С. 73-81.

114. Подиновский В.В., Гаврилов В.М. Оптимизация по последовательно применяемым критериям. -М.: Сов. радио, 1987. -192 с.

115. Полак Э. Численные методы оптимизации. Единый подход. -М.: Мир, 1974. -376 с.

116. Поляк Б. Т. Введение в оптимизацию. -М.: Наука, 1983. -384 с.

117. Поляк Б. Т., Третьяков Н.В. Метод штрафных оценок для задач на условный экстремум // Ж. вычисл. матем. и матем. физики, 1973. -Т. 13, № 1. -С. 34-46.

118. Попов Л.Д. Линейная коррекция несобственных выпукло-вогнутых минимаксных задач по максиминному критерию //Ж. вычисл. ма-тем. и матем. физики, 1986. -Т. 26, № 9. -С. 1325-1338.

119. Попов Л.Д. Применение модифицированного ргох-метода для оптимальной коррекции несобственных задач выпуклого программирования // Тр. Ин-та матем. и мех. УрО РАН. -Екатеринбург: ИММ УрО РАН, 1995. -Т. 3. -С. 261-266.

120. Попов Л. Д. Об одной модификации метода логарифмических барьерных функций в линейном и выпуклом программировании // Тр. Инта матем. и мех. УрО РАН. -Екатеринбург: ИММ УрО РАН, 2008. -Т. 14, № 2. -С. 103-114.

121. Попов Л.Д. Схемы включения двойственных переменных в обратные барьерные функции задач линейного и выпуклого программирования // Тр. Ин-та матем. и мех. УрО РАН. -Екатеринбург: ИММ УрО РАН, 2009. -Т. 15, № 1. -С. 195-207.

122. Пшеничный Б.Н. Выпуклый анализ и экстремальные задачи. -М.: Наука, 1980. -320 с.

123. Пшеничный Б.Н., Данилин Ю.М. Численные методы в экстремальных задачах. -М.: Наука, 1975. -320 с.

124. Рокафеллар Р. Выпуклый анализ. -М.: Мир, 1973. -472 с.

125. Сергиенко И.В., Козерацкая Л.Н., Лебедева Т.Т. Исследование устойчивости и параметрический анализ дискретных оптимизационных задач. -Киев: Наукова думка, 1995. -168 с.

126. Скарин В.Д. О методе штрафных функций для задач нелинейного программирования // ДАН СССР, 1973. -Т. 209, № 6. -С. 1292-1295.

127. Скарин В.Д. Об одной модификации метода штрафных функций в выпуклом программировании // Нелинейная оптимизация и приложения в планировании. -Свердловск: УНЦ АН СССР, 1973. -С. 51-62.

128. Скарин В.Д. К регуляризации минимаксных задач, возникающих в выпуклом программировании //Ж. вычисл. матем. и матем. физики, 1977. -Т. 17, № 6. -С. 1408-1420.

129. Скарин В Д. Об алгоритмах линейного программирования, использующих модификации функции Лагранжа. -В кн. "Методы для нестационарных задач математического программирования". -Свердловск: УНЦ АН СССР, 1979. -С. 74-83.

130. Скарин В Д. Об одном итерационном методе нахождения нормального решения задачи линейного программирования. -В кн. "Методы математического программирования и приложения". -Свердловск: УНЦ АН СССР, 1979. -С. 20-25.

131. Скарин В.Д. О некоторых методах анализа несобственных задач выпуклого и линейного программирования. -В кн. "Несобственные модели математического программирования". -ВИНИТИ, 1980. -№2823-80 Деп. -С. 187-234.

132. Скарин В.Д. О скорости сходимости метода барьерных функций. -В кн. "Методы оптимизации и распознавания образов в задачах планирования". -Свердловск: УНЦ АН СССР, 1980. -С. 27-36.

133. Скарин В.Д. К анализу несобственных задач выпуклого программирования с позиций последовательной оптимизации. -В кн. "Несобственные задачи оптимизации". -Свердловск: УНЦ АН СССР, 1982. -С. 30-36.

134. Скарин В.Д. О применении метода регуляризации для коррекции несобственных задач линейного программирования 1-го рода. -В кн. "Методы аппроксимации несобственных задач математического программирования". -Свердловск: УНЦ АН СССР, 1984. -С. 55-66.

135. Скарин В.Д. Об одном подходе к анализу несобственных задач линейного программирования // Ж. вычисл. матем. и матем. физики, 1986. -Т. 26, № 3. -С. 439-448.

136. Скарин В.Д. Об одном методе численного анализа противоречивых задач выпуклого программирования. -В кн. "Противоречивые модели оптимизации". -Свердловск: УНЦ АН СССР, 1987. -С. 56-63.

137. Скарин В.Д. Об одном регуляризирующем алгоритме коррекции противоречивых задач выпуклого программирования с линейными ограничениями. -В кн. "Исследования по несобственным задачам оптимизации". -Свердловск: УрО АН СССР, 1988. -С. 48-56.

138. Скарин В.Д. Регуляризирующий алгоритм для несобственных полноквадратичных задач выпуклого программирования. -В кн. "Нерегулярная двойственность в математическом программировании". -Свердловск: УрО АН СССР, 1990. -С. 58-67.

139. Скарин В.Д. О методе регуляризации для противоречивых задач выпуклого программирования // Изв. ВУЗов. Математика, 1995. 12. -С. 81-88.

140. Скарин В.Д. Об одном универсальном подходе к оптимальной коррекции несобственных задач выпуклого программирования. -В кн.

141. Методы оптимизации и их приложения" (Тр. XI-й междунар. Байкальской шк.-сем.)- -Иркутск: СЭИ СО РАН, 1998. -Т. 1. -С. 56-59.

142. Скарин В.Д. О применении барьерных функций для коррекции несобственных задач выпуклого программирования. -В кн. "Методы оптимизации и их приложения" (Тр. XII-й Байкальской междунар. конф.). -Иркутск: ИСЭМ СО РАН, 2001. -Т. 1. -С. 50-54.

143. Скарин В.Д. Оценочный подход в методах линейного и выпуклого программирования // Информ. бюллетень АМП (Приоритетные результаты в области математического программирования. Ч. 1). -Екатеринбург: УрО РАН, 2001. 9. -С. 123-127.

144. Скарин В.Д. О применении функции Лагранжа для регуляризации задач выпуклого программирования. -В кн. "Современные методы оптимизации и их приложения к моделям энергетики". -Новосибирск: Наука, 2003. -С. 189-209.

145. Скарин В.Д. О некоторых регуляризирующих и аппроксимирующих свойствах метода штрафных функций в выпуклом программировании // Оптимизация, управление, интеллект, 2005. 1(9). -С. 107-128.

146. Скарин В.Д. О применении штрафных функций для коррекции несобственных задач выпуклого программирования. -В кн. "Методы оптимизации и их приложения" (Тр. ХШ-й Байкальской междунар. шк.-сем.). -Иркутск: ИСЭМ СО РАН, 2005. -Т. 1. -С. 175-180.

147. Скарин В.Д. О методе барьерных функций и алгоритмах коррекции несобственных задач выпуклого программирования // Тр. Ин-та ма-тем. и мех. УрО РАН. -Екатеринбург: ИММ УрО РАН, 2008. -Т. 14, № 2. -С. 115-128.

148. Скарин В.Д. Расширенная штрафная функция и оптимальная коррекция несобственных задач выпуклого программирования. -В кн.

149. Методы оптимизации и их приложения" (Тр. XIY-й Байкальской междунар. шк.-сем.). -Иркутск: ИСЭМ СО РАН, 2008. -Т. 1. -С. 203-209.

150. Скарин В.Д. Аппроксимационные и регуляризирующие свойства расширенной штрафной функции в выпуклом программировании // Тр. Ин-та матем. и мех. УрО РАН. -Екатеринбург: ИММ УрО РАН, 2009. -Т. 15, № 4. -С. 234-250.

151. Скарин В.Д. Об одном общем подходе к оптимальной коррекции несобственных задач выпуклого программирования // Тр. Ин-та матем. и мех. УрО РАН. -Екатеринбург: ИММ УрО РАН, 2010. -Т. 16, № 3. -С. 265-275.

152. Стрекаловский A.C. Элементы невыпуклой оптимизации. -Новосибирск: Наука, 2003. -356 с.

153. Сухарев А.Г., Тимохов A.B., Федоров В.В. Курс методов оптимизации. -М.: Наука, 1986. -328 с.

154. Тихонов А.Н. О решении некорректно поставленных задач // ДАН СССР, 1963. -Т. 151, № 3. -С. 501-504.

155. Тихонов А.Н. О некорректных задачах оптимального планирования и устойчивых методах их решения // ДАН СССР, 1965. -Т. 164, № 3. -С. 507-510.

156. Тихонов А.Н., Арсенин В.Я. Методы решения некорректных задач. -М.: Наука, 1979. -288 с.

157. Тихонов А.Н., Леонов A.C., Ягола А.Г. Нелинейные некорректные задачи. -М.: Наука, 1995. -312 с.

158. Третьяков Н.В. Метод штрафных оценок для задач выпуклого программирования // Экономика и матем. методы, 1973. -Т. 9, № 3. -С. 526-540.

159. Федоров В.В. Численные методы максимина. -М.: Наука, 1979. -280 с.

160. Фиакко А., Мак-Кормик Г. Нелинейное программирование. Методы последовательной безусловной минимизации. -М.: Мир, 1972. -240 с.

161. Численные методы условной оптимизации (ред. Гилл Ф., Мюррей У.). -М.: Мир, 1977. -292 с.

162. Шамрай Н.Б. Вариационный подход к решению несобственных задач линейного программирования. -В кн. "Методы оптимизации и их приложения" (Тр. ХШ-й Байкальской междунар. шк.-сем.). -Иркутск: ИСЭМ СО РАН, 2005. -Т. 1. -С. 155-160.

163. Элъстер К.-Х., Рейнгардт Р., Шойбле М., Донат Г. Введение в нелинейное программирование. -М.: Наука, 1985. -264 с.

164. Эрроу К.Дж., Гурвиц Л., Удзава X. Исследования по линейному и нелинейному программированию. -М.: ИЛ, 1962. -336 с.

165. Amaral РBarahona P. Connections between the total least squares and the correction of an infeasible system of linear inequalities // Linear Algebra and its Appl., 2005. 395. -P. 191-210.

166. Auslender A. Penalty methods for computing points that satisfy second-order necessary conditions // Math. Progr., 1979. -V. 17, № 2. -P. 229-238.

167. Auslender A. Stability in mathematical programming with nondifferen-tiable data // SIAM J. Control Optim., 1984. -V. 22, № 2. -P. 239-254.

168. Auslender A. Numerical methods for nondifferentiable convex optimization // Math. Progr. Study, 1987. -V. 30. -P. 102-126.

169. Auslender A., Cominetti R., Haddou M. Asymptotic analysis of penalty and barrier methods in convex and linear programming // Math. Oper. Res., 1997. -V. 22, № 1. -P. 1-18.

170. Bank В., Guddat J., Klatte В., Rummer В., Tammer K. Non-linear parametric optimization // Berlin: Akademic-Verlag, 1982.

171. Bazaraa M.S., Goode J.J. Sufficient conditions for a globally exact penalty function without convexity // Math. Progr. Study, 1982. -V. 19. -P. 1-15.

172. Benchakroun A., Dussault J.P., Mansouri A. A two parameter mixed interior-exterior penalty algorithm // Math. Methods of Oper. Res., 1995. -V. 41. -P. 25-55.

173. Ben-Tal A., Roth G. A trancated log barrier algorithm for large-scale convex programming and minimax problems: implementation and computational results // Optim. Methods and Software, 1996. -V. 6, № 4. -P. 283-312.

174. Ben-Tal A., Zibulevsky M. Penalty / barrier multiplier methods for convex programming problems // SIAM J. Optim., 1997. -V. 7, № 2. -P. 347-366.

175. Bertsekas D. Combined primal-dual and penalty methods for constrained minimization // SIAM J. Control, 1975. -V. 13, № 3. -P. 521-544.

176. Bertsekas D.P. Multiplier methods: a survey // Automatica, 1976. -Vol. 12, № 2. -P. 133-145.

177. Bourkary D., Fiacco A. V. Survey of penalty, exact-penalty and multiplier methods from 1968 to 1993 // Optimization, 1995. -V. 32, № 4. -P. 301-334.

178. Burke J. V. An exact penalization viewpoint of constrained optimization // SIAM J. Contr. Optim., 1991. -V. 29, № 4. -P. 968-998.

179. Charalambous C. On conditions for optimality of the nonlinear l\ -problem // Math. Progr., 1979. -V. 17, № 2. -P. 123-135.

180. Conn A.R., Gould N.I.M., Toint P.L. A globally convergent augmented Lagrangian algorithm for optimization with general constraints and simple bounds // SIAM J. Numer. Anal., 1991. -V. 28, № 2. -P. 545-572.

181. Dax A. The smallest correction of an inconsistent system of linear inequalities // Optimization and Engineering, 2001. 2. -P. 349-359.

182. Demyanov V.F., Di Pillo G., Facchinei F. Exact penalization via Dini and Hadamars conditional derivatives // Optim. Methods and Software, 1998. -V. 9. -P. 19-36.

183. Demyanov V.F., Giannessi F., Karelin V. V. Optimal control problems via exact penalty functions // J. of Global Optim., 1998. -V. 12, № 3. -P. 215-223.

184. Di Pillo G., Grippo L. Exact penalty functions in constrained optimization // SIAM J. Contr. Optim., 1989. -V. 27. -P. 1333-1360.

185. Dolecky S., Rolewich S. Exact penalties for local minima // SIAM J. Contr. Optim., 1979. -V. 17, № 5. -P. 596-606.

186. Doljansky M., Teboulle M. An interior proximal algorithm and the exponential multiplier method for semidefinite programming // SIAM J. Optim., 1998. -V. 9, № 1. -P. 1-13.

187. Dussault J.-P. Numerical stability and efficiency of penalty algorithms // SIAM J. Numer. Anal., 1995. -V. 32, № 1. -P. 296-317.

188. Dussault J.-P. Augmented non-quadratic penalty algorithms // Math. Progr., Ser. A, 2004. -V. 99. -P. 467-486.

189. Evans J.P., Gould F.J., Tolle J. W. Exact penalty functions in nonlinear programming // Math. Progr., 1973. -V. 4, № 1. -P. 72-97.

190. Evtushenko Y.G., Rubinov A.M., Zhadan V.G. General Lagrange-type functions in constrained global optimization // Optim. Methods and Software, 2001. -V. 16. -P. 193-256.

191. Fiacco A. V. Introduction to sensitivity and stability analysis in nonlinear programming. -New York: Academic Press, 1983.

192. Frank M., Wolfe P. An algorithm for quadratic programming // Naval Res. Logist. Quart., 1956. -V. 3. -P. 95-110.

193. Gill P.E., Murray W., Saunders M.A., Tomlin J.A., Wright M.H. On projected Newton barrier methods for linear programming and an equivalence to Karmarkar's projected methods // Math. Progr., 1986. -V. 36. -P. 183-209.

194. Gould N.I.M., Tomt Ph.L. A note on the corvergence of barrier algorithms to second-order necessary points // Math. Progr., 1999. -V. 85, № 2. -P. 433-438.

195. Grodzevich 0., Wolkowicz H. Reqularization using a parametrized trust region subproblem // Math. Progr., Ser. B, 2009. -V. 116, №1-2. -P. 193-220.

196. Guddat J. Stability in convex quadratic parametric programming // Math. Operationsforsch, 1976. -V. 7. -P. 223-245.

197. Haarhoff P., Buyes J. A new method for the optimization of a nonlinear function subject to nonlinear constraints // Comp. J., 1970. -V. 13, № 2. -P. 171-177.

198. Han S.-P., Mangasarian O.L. Exact penalty functions in nonlinear programming // Math. Progr., 1979. -V. 17, № 3. -P. 251-269.

199. Hartung J. A stable interior penalty method for convex extremal problems // Numer. Math., 1978. -V. 29, № 2. -P. 149-158.

200. Hestenes M. Multiplier and gradient methods //J. Opt. Theory and Appl., 1969. -V. 4, № 5. -P. 303-320.

201. Hu X.M., Ralph D. Convergence of a penalty method for mathematical programming with complementarity constraints //J. Opt. Theory and Appl., 2004. -V. 123, № 2. -P. 365-390.

202. Huang X.X., Yang X.Q. Convergence analysis of a class of nonlinear penalization methods for constrained optimization via first-order necessary optimality conditions // J. Opt. Theory and Appl., 2003. -V. 116, № 2. -P. 311-332.

203. Huang X.X., Yang X.Q. A unified augmented Lagrangian approach to duality and exact penalization // Math. Oper. Res., 2003. -V. 28. -P. 533-552.

204. Huang X.X., Yang X.Q., Teo K.L. Lower-order penalization approach to nonlinear semidefinite programming //J. Opt. Theory and Appl., 2007. -V. 132, № 1. -P. 1-20.

205. Jongmans F. Enquete socio-geometrique sur les vertus de l'ignorance // Bull. Soc. roy. sci. Ligraveege, 1983. -V. 52, no. 4. -P. 5-10.

206. Kanzow C., Qi N., Qi L. On the minimum norm solution of linear programs 11 J. Opt. Theory and Appl., 2003. -V. 116, № 2. -P. 333-345.

207. Karmarkar N. A new polynomial-time algorithm for linear programming // Combinatorica, 1984. -V. 4. -P. 373-395.

208. Khachay M.Yu. On approximate algorithm of a minimal committee of a linear inequalities system // Pattern Recogn. and Image Anal., 2003. -V. 13, № 3. -P 459-464.

209. Lootsma F.A. Boundary properties of penalty functions for constrained minimization // Philips Res. Repts. Suppl, 1970. -V. 25, №. 3. -P. 201-308.

210. Mangasarian O.L. Least-norm linear programming solution as an unconstrained minimization problem //J. Math. Anal, and Appl., 1983. -V. 92, № 1. -P. 240-251.

211. Mangasarian O.L. Normal solution of linear programs // Math. Progr. Study, 1984. -V. 22. -P. 206-216.

212. Mangasarian O.L., De Leone R. Error bounds for strongly convex programs and (super) linearly convergent iterative schemes for the least2.norm solution of linear programs // Appl. Math, and Optim., 1988.17. -P. 1-14.

213. Mangasarian O.L., Meyer R.R. Nonlinear perturbation of linear programs // SIAM J. Contr. Optim., 1979. -V. 17, № 6. -P. 745-752.

214. Miele A., Cragg E.E., Iver R.R., Levy A. V. Use of the augmented penalty function in mathematical programming problems //J- Opt. Theory and Appl., 1971. -V. 8, № 2. -P. 115-153.

215. Miele A., Moseley P.E., Levy A.V., Cog gins G.M. On the method of multipliers for mathematical programming problems // J. Opt. Theory and Appl., 1972. -V. 10, № 1. -P. 1-33.

216. Mifflin R. On the convergence of the logarithmic barrier function method. In "Numerical methods for unconstrained optimization" (F.A. Lootsma, ed.) -London & New York: Acad. Press, 1972. -P. 367-369.

217. Mosheyev L., Zibulevsky M. Penalty / barrier multiplier algorithm for semidefinite programming // Optim. Methods and Software, 2000. -V. 13, № 4. -P. 235-261.

218. Polyak R. Modified barrier functions (theory and methods) // Math. Progr., 1992. -V. 54, № 2. -P. 177-222.

219. Powell M.J.D. A method for nonlinear constraints in minimization problems. In "Optimization" (R. Fletcher, ed.) -London: Acad. Press, 1969. -P. 283-298.

220. Rockafellar R.T. A dual approach to solving nonlinear programming problems by unconstrained optimization // Math. Progr., 1973. -V. 5, № 3. -P. 354-373.

221. Rockafellar R.T. Augmented Lagrange multiplier functions and duality in nonconvex programming // SIAM J. Contr., 1974. -V. 12, № 2. -P. 268-285.

222. Rockafellar R.T. Lagrange multipliers and optimality // SIAM Rev., 1993. -V. 35, № 2. -P. 183-238.

223. Rosen J.B., Park H., Glick J. Total least norm formulation and solution for structured problems // SIAM J. on Matrix Anal. Appl., 1996. -V. 17, № 1. -P. 110-128.

224. Rubinov A.M., Glover B.M., Yang X.Q. Modified Lagrange and penalty functions in continuous optimization // Optimization, 1999. -V. 46. -P. 327-351.

225. Rubinov A.M., Glover B.M., Yang X.Q. Decreasing functions with application to penalization // SIAM J. Optim., 2000. -V. 10. -P. 289-313.

226. 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., 1986. 81. -P. 130-144.

227. 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.

228. Tripathi S.S., Narendra K.S. Constrained optimization problems using multiplier methods //J. Opt. Theory and Appl., 1972. -V. 9, № 1. -P. 59-70.

229. Vanderberge L., Boyd S. Semi-definite programming // SIAM Rev., 1996. -V. 38. -P. 49-95.

230. Ward D.E. Exact penalties and sufficient conditions for optimality in nonsmooth optimization //J. Opt. Theory and Appl., 1988. -V. 57, № 3. -P. 485-499.

231. Watson G.A. Data fitting problems with bounded uncertainties in the data 11 SIAM J. Matrix Anal. Appl., 2001. -V. 22, № 4. -P. 1274-1293.

232. Wierzbicki A. P. A penalty function shifting method in constrained static optimization and its convergence properties // Arch. Automat. Telemech., 1971. -V. 16, № 4. -P. 395-416.

233. Ye J.J., Zhu D.L., Zhu Q.J. Exact penalization and necessary optimality conditions for generalized bileved programming problems / / SI AM J. Optim., 1997. -V. 7. -P. 481-507.

234. Zangwill W.I. Nonlinear programming via penalty functions // Manag. Sci., 1967. -V. 13, № 5. -P. 344-358.

235. Zhou Y.Y., Yang X.Q. Some results about duality and exact penalization // J. Glob. Optim., 2004. -V. 29. -P. 497-509.

236. Zhou Y.Y., Yang X.Q. Duality and penalization in optimization via an augmented Lagrangian functions with applications //J. Optim. Theory and Appl., 2009. -V. 140, № 1. -P. 171-188.

237. Zlobec S. Stable parametric programming. -Dordrecht ets.: Kluwer Academic Publishers, 2001.