ЖУРНАЛ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ И МАТЕМАТИЧЕСКОЙ ФИЗИКИ, 2007, том 47, < 4, с. 555-577
УДК 519.626.2
ЧУВСТВИТЕЛЬНОСТЬ РЕШЕНИЙ СИСТЕМ УСЛОВИЙ ОПТИМАЛЬНОСТИ ПРИ НАРУШЕНИИ УСЛОВИЙ
РЕГУЛЯРНОСТИ ОГРАНИЧЕНИЙ1)
© 2007 г. А. Ф. Измаилов
(119992 Москва, Ленинские горы, МГУ, ВМиК) e-mail: izmaf@ccas.ru Поступила в редакцию 25.10.2006 г.
Излагаются результаты о чувствительности решений систем условий оптимальности по отношению к параметрическим возмущениям, как известные, так и новые. Результаты такого рода играют центральную роль в тонком анализе сходимости и скорости сходимости различных алгоритмов условной оптимизации. Рассматриваются общие системы условий оптимальности для задач с абстрактными ограничениями, системы Каруша-Куна-Таккера для задач математического программирования, а также системы Лагранжа для задач с ограничениями-равенствами. Особое внимание уделено случаям нарушения традиционных условий регулярности ограничений. Библ. 30.
Ключевые слова: условия оптимальности, система Каруша-Куна-Таккера, система Лагранжа, устойчивость, чувствительность, регулярность ограничений.
1. ВВЕДЕНИЕ. СИСТЕМА УСЛОВИЙ ОПТИМАЛЬНОСТИ
Пусть Z = Us, X = U", Y = U f: Z x X —- U - гладкая функция, F : Z x X —- Y - гладкое отображение, Q с Y - выпуклое замкнутое множество. Для задачи оптимизации вида
f(o, x) —» min, x e D(o), (1.1)
D(o) = {x e X| F(o, x) e Q}, (1.2)
отвечающей значению параметра o e Z, введем функцию Лагранжа
L(o, x, Ä) = f (o, x) + <Ä, F(o, x)>,
где x e X, Ä e Y. Будем рассматривать параметрическую прямодвойственную систему условий первого порядка оптимальности
I- (o, x,Ä) = 0, Äe Nq( F(o, x)), (1.3)
характеризующую стационарные точки задачи (1.1), (1.2) и отвечающие им множители Лагранжа (см., например, [1, определение 1.3.2]). Здесь и далее через NS(y) обозначается нормальный конус к множеству S в точке у.
Пусть o e Z - базовое значение параметра, (x, Ä) e Xx Y- некоторое решение системы (1.3) при o = o. В данной работе речь идет о чувствительности (количественной устойчивости) этого решения по отношению к малым возмущениям параметра o.
Подчеркнем, что здесь рассматривается вопрос о чувствительности именно прямодвойствен-
ных решений (x, Ä). Можно также рассматривать вопрос о чувствительности только стационарных точек, не заботясь о поведении множителей [2] (на самом деле известные результаты такого рода обычно неявно используют количественную устойчивость множества множителей; см. лемму 1 ниже). Однако вопрос о поведении множителей и, скажем, устойчивости или неустойчивости конкретного множителя Ä (при его неединственности) весьма важен и интересен.
^ Работа выполнена при финансовой поддержке РФФИ (код проекта 04-01-00341) и грантов президента РФ для государственной поддержки ведущих научных школ (код проекта НШ-9344.2006.1) и молодых российских ученых -докторов наук (код проекта МД-2723.2005.1).
Заметим также, что можно было бы существенно упростить изложение, если (с какого-то момента) предполагать, что x - локальное решение невозмущенной задачи оптимизации. Вместе с тем, желательно без необходимости этого не делать: полезно знать, какие свойства устойчивости/чувствительности связаны с локальной оптимальностью, а какие - только со стационарностью.
Особую роль в анализе чувствительности прямодвойственных решений играют так называемые канонические возмущения задачи (1.1), (1.2), т.е. произвольные линейные возмущения целевой функции и произвольные возмущения правых частей ограничений (см. задачу (2.28), (2.29) в лемме 2 ниже). Любая параметризация, допускающая канонические возмущения, настолько богата, что анализ свойств чувствительности для всех малых возмущений в рамках данной параметризации может считаться анализом "в худшем возможном случае". В частности, как будет неоднократно отмечаться ниже, достаточные условия для количественной устойчивости того или иного типа в случае наличия канонических возмущений часто оказываются и необходимыми. Вместе с тем, учет специфики конкретной имеющейся параметризации иногда позволяет получить более тонкие достаточные условия.
Наиболее сильный известный результат о чувствительности для системы (1.3) основан на введенном в [3] понятии сильной регулярности для обобщенных уравнений. А именно, система (1.3) равносильна обобщенному уравнению
Ф(с,(хД)) + N(А,)э 0, (1.4)
где для а е X и (х, X) е X х Y положено
Ф(с, (х, X)) = (а, х, X), -F(а, х)), (1.5)
N(X) = { 0 } х Ng1 (X), (1.6)
Ng1 (X) = {y е Y | Xe NQ(y)}. (1.7)
Важно, что множество N(-) в (1.6) не зависит от параметра а.
Несложно убедиться, что если Q - конус, то для всякого X е Y справедливо равенство
nQ (X) = Nq°(x) .
Здесь через K° обозначается полярный конус к конусу K.
Говорят, что решение (х, X) системы (1.3) при а = а является сильно регулярным, если (х, X) является сильно регулярным решением обобщенного уравнения (1.4), в котором Ф(-) и N(-) введены согласно (1.5) и (1.6) соответственно. Последнее же означает, что для любой пары (r, р) е е X х Y, достаточно близкой к (0, 0), возмущенное линеаризованное обобщенное уравнение
Ф(а, (х, X)) + (а, (х, X))(t П) + N(X + п) э (r, р) (1.8)
имеет вблизи точки (0, 0) единственное решение (^(r, р), п(г, р)), причем соответствующее отображение (^(0, п(0) непрерывно по Липшицу вблизи (0, 0). Согласно (1.5) и (1.6), возмущенное линеаризованное обобщенное уравнение (1.8) можно записать в виде системы
Э2^- _ , . OF,_ _
—(а, х, ^ + ^х)) п = -, - х) - |Х(5, х)£, + ^ (^ + П) э р,
причем, согласно (1.7), последнее соотношение можно переписать в виде
Э
X + п е Ng( F(а, х) + ^(а, х)£ + р).
Подчеркнем, что сильная регулярность полностью является свойством невозмущенного обобщенного уравнения (невозмущенной системы условий оптимальности): значение а = а зафиксировано, и зависимость Ф (/и К) от параметра а не играет в этом определении никакой роли.
Несложно проверить, что если (х, X) - сильно регулярное решение системы (1.3) при а = а, то для ограничений, задающих множество Б(а) в (1.2), в точке х, выполнено условие регулярности Робинсона
0 е Цк(а, х) + х) - б). (1.9)
При выполнении этого условия, если х является локальным решением задачи (1.1), (1.2), то х является стационарной точкой этой задачи, т.е. удовлетворяет (1.3) с некоторым множителем
Лагранжа X е У. Более того, если х - стационарная точка задачи (1.1), (1.2), то условие Робинсона является необходимым и достаточным для ограниченности множества множителей Лагранжа, отвечающих точке х. Для задачи математического программирования (см. разд. 2 ниже) этот результат был получен в [4].
Сильная регулярность позволяет применить к (1.4) полученную в [3] (см. также [1, теорема 1.2.4]) теорему о неявной функции для обобщенных уравнений. Отметим, что из приводимой ниже теоремы 1, которая в такой форме была доказана в [5] (см. также [1, теорема 3.1.2]), в частности следует, что если (х, X) - сильно регулярное решение системы (1.3), то X - единственный множитель Лагранжа, отвечающий стационарной точке х задачи (1.1), (1.2).
Теорема 1. Пусть функция/: Ъ XX —► К и отображение К : Ъ XX —► У дважды непрерывно дифференцируемы в некоторой окрестности точки (а, х) е Ъ XX. Пусть х - стационарная
точка задачи (1.1), (1.2) при а = а, а X е У - отвечающий х множитель Лагранжа.
Тогда если (х, X) является сильно регулярным решением системы (1.3) при а = а, то для любого а е Ъ, достаточно близкого к а, имеет место следующее:
а) система (1.3) имеет вблизи (х, X) единственное решение (х(а), X(а)), причем отображение
(х(-), X(•)) непрерывно по Липшицу вблизи а, и х(а) = х + ^(а) + о(||а - а ||), X(а) = X + п(а) + о(||а - а ||), где (^(а), П(а)) - единственное вблизи (0, 0) решение системы
_ ^ „ , ГЭК _ Л * д2Ь _ ^
-2 (с, х, Х)£, + (с, х )j Л = (ä, х,ХХс - с), (1.10)
X + ne F(ä, х) + |£(с, х + |ä(ö, х )(с - с)), (1.11)
которое по необходимости непрерывно по Липшицу вблизи (0, 0);
б) если х - локальное решение задачи (1.1), (1.2) при с = с, то х(с) является единственным вблизи х локальным решением задачи (1.1), (1.2), а Х(с) - единственным отвечающим х(с) множителем Лагранжа.
Отметим следующее обстоятельство. Если рассматривать двойственную переменную в виде
X + n, то для каждого с e Z система (1.10), (1.11), определяющая "главные члены" ^(с) и п(с) разложения х(с) и Х(с) соответственно, является прямодвойственной системой условий первого порядка оптимальности для задачи
(с, х), Й + (с, х, X)[с - с, S] + (с, х, Х)& £] — min, S e ö1(ö, х; с), (1.12)
удх ' / дсдх ' 2дх2'
Д(0, х; с) = Ue X
F(Ö, х) + d-F(ö, х + -^(0, х )(с - с) e qI (1.13)
Легко видеть, что сильная регулярность решения (x, X) системы (1.3) при g = G эквивалентна сильной регулярности решения (0, 0) линеаризованной системы
р(g, X, X)£, + (JF(G, X))= 0, (1.14)
X + ne ^g^F(g, X) + |X(G, X, (1.15)
которая, в свою очередь, является прямодвойственной системой условий первого порядка оптимальности для задачи
(I(G, XЦ + (g, X, X)[^]—► min, ^ e D,(g, X), (1.16)
A (G, X) = j^ e X I F(G, X) + |X(G, X)£, e g j. (1.17)
Систему (1.10), (1.11) (задачу (1.12), (1.13)) можно рассматривать как параметрическое возмущение системы (1.14), (1.15) (задачи (1.16), (1.17)), поэтому утверждения теоремы 1 справедливы и для задачи (1.12), (1.13) (вместо (1.1), (1.2)) и системы (1.10), (1.11) (вместо (1.3)). В частности, для G e X, близких к G, можно искать "главный член" ^(g) разложения x(g) с помощью локальных
алгоритмов решения задачи (1.12), (1.13), стартуя из точки X (или (X, X) для прямодвойственных алгоритмов; см. [6]). Кроме того, если (1.1), (1.2) является задачей математического программирования (см. разд. 2), то (1.12), (1.13) есть задача квадратичного программирования, для которой существуют эффективные специальные численные методы [6, § 7.3], [7, гл. 6, § 4].
Заметим также, что сильная регулярность решения (0, 0) линеаризованной системы (1.14), (1.15), равносильна выполнению утверждения а) теоремы 1 для этого решения данной системы в случае параметризации, порождаемой каноническими возмущениями задачи (1.1), (1.2), т.е., произвольными линейными возм
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.