ИЗВЕСТИЯ РАН. ТЕОРИЯ И СИСТЕМЫ УПРАВЛЕНИЯ, 2014, № 3, с. 86-93
СИСТЕМНЫМ АНАЛИЗ И ИССЛЕДОВАНИЕ ОПЕРАЦИЙ
УДК 517.97
НЕРЕГУЛЯРНЫЕ МОДЕЛИ ОПТИМИЗАЦИИ И УСЛОВИЯ ОПТИМАЛЬНОСТИ ^-ГО ПОРЯДКА ТИПА КУНА-ТАККЕРА*
© 2014 г. A. A. Третьяков1, 2, Э. Щчепаник2
1 Россия, Москва, ВЦ РАН; 2 Польша, Варшава, Польская Академия наук, Systems Research Institute, Сельце, Естественно-Гуманитарный Университет в г. Сельце Поступила в редакцию 20.12.13 г., после доработки 27.01.14 г.
Исследуется задача вариационного исчисления с нерегулярными ограничениями. Получены условия оптимальности для вырожденного случая, позволяющие отсеять фальшивые решения. Рассмотрение ведется для конечномерного случая, хотя основной результат верен и для банаховых пространств.
DOI: 10.7868/S0002338814030147
Введение. Вырождение в оптимизационных задачах возникает в линейном программировании, в транспортных постановках, в блочном программировании, оптимизации на сетях (см., например, [1—5]) и т.д., а также в математическом программировании в бесконечномерных экстремальных задачах, чему и посвящена данная работа. Теория Куна—Таккера является основным математическим аппаратом в задачах оптимизации [6—8] и применяется при теоретическом обосновании алгоритмов [9, 10].
1. Постановка задачи. Рассматривается задача вариационного исчисления с нерегулярными ограничениями вида
t2
J(x) = jF(t,x(t),x'(t)..., x(r\t))dt ^ min (1.1)
при условиях
H(t,x(t),x'(0,.. xW(0) < 0, (1.2)
где H () - вектор-функция размерности m,
x(t) 6 CK 12]
Akx (k)ft) + Bkx {k)(t2) = 0
и Ak, Bk — n x n-матрицы, k = 1, r. К такому типу задач (1.1), (1.2) сводятся многие прикладные модели (задача Чаплыгина, Лагранжа и др.). Например
п
J(x) = j(x2(t) + x22(t) + x32(t))dt ^ min (1.3)
0
при условии
H(t,x(t),x'(t),x''(t)) = x; '(t) + x1(t) + x22(t)x:(t) - x2(t)x1(t) = 0, (1.4)
x;(0) - xi(n) = 0, x'i(0) + x'(n) = 0, i = 1,3. Очевидно, что решение этой задачи x(t) = 0 и в этой точке оператор производной по Фреше H '(x) вырожден. Тогда уравнение Эйлера—Пуассона имеет следующий вид:
Работа выполнена при финансовой поддержке РФФИ (проект № 11-01-00786-а), Программы Президента ведущих научных школ НШ-5264.2012.1 и программы Президиума РАН П-18.
XF + ЩИХ - d((ЩИ*) + ^ (ЩИ*.)) = 0 dt \ dt )
или
2X0xl + X + Xx22 - Xx32 + X'' = 0,
2X 0x2 + 2Xx2x1 = 0,
2X 0x3 + 2Xx3x1 = 0,
X(0) -X(n) = 0, X'(0) + X'(n) = 0,
что дает серию фальшивых решений x1 = a sin t, x2 = 0, x3 = 0.
Ранее были предложены необходимые условия оптимальности для задачи оптимизации с нерегулярными ограничениями-неравенствами для некоторых классов задач. Например, предполагалось вырождение только до второго порядка или наличие нетривиальных р-ядер у операторов высших производных функций ограничений и т.д. [11, 12]. Либо условия оптимальности давались в виде сопряженных конусов, описание которых отсутствовало. В данной работе предлагается описание сопряженного конуса для общего случая вырождения при р-регулярных ограничениях и формируются условия оптимальности в классическом виде — типа Куна—Таккера, но с использованием р-фактор-операторов для общей задачи математического программирования. Рассматривается задача вида
min 9(x), (1.5)
gi(x) < 0, i=im (1.6)
где x e IR", ф, gi : IR" ^ [R1, ф, gi — достаточно гладкие функции, т.е. ф е C2(R"), g¡ е Cp+1([R"), p е N, i = 1,m. Через x* и Xбудем обозначать соответственно решение задачи (1.5), (1.6) и допустимое множество, т.е. X = {x е R"|gi(x) < 0, i = 1,m}. При этом предполагается, что в решении x* активные ограничения g¡(x), i е I(x*) = {i e {1, m} |g,(x*) = 0} = {1, £}, £ < m, вырождены, т.е. {g'(x*)}ieI(x*} линейно зависимы.
Считаем далее, что g = (gb ..., gri, gri+b ..., gr2,..., g +1, ..., g )т, Гр = í, и
g'(x*) = 0, i = Г1 + 1, ..., t,
g''(x*) = 0, i = Г2 + 1, ..., t, (17)
¿Г1\х*) = 0, I = Гр_! + 1, ..., Гр = I. При этом операторы (тензоры) высших производных {о-(к)(х*)}. —г- линейно независимы,
г 1 =Гк-1+1,Гк
к = 1, р, г0 == 0. К виду (1.7) можно привести ограничения при помощи линейных преобразований отображения g(x).
В работах [11, 13—21] были рассмотрены случаи, когда существует вектор к, М = 1, такой, что
¿к\х*)[Н]к = 0, г = Гк-1 + 1, Гк, (1.8)
к = 1, р, и получены необходимые условия экстремума типа
ф'(х*) = £ Х,(И)(Е(р)(х*)[й]р-1)т, Х,(И) < 0, г 6 I(х*). (1.9)
1е1 (х*)
Определение используемых обозначений см. [18, с. 73].
Здесь написано уравнение для абсолютно вырожденного случая до р-го порядка, который является ключевым при исследовании вырожденной ситуации. Однако существует класс задач, для которых не выполнено условие (1.8) и соответственно отсутствуют условия оптимальности вида (1.9). Например, для ограничений
&(х) = (Х2 + х22)Х1 < 0, (1 10)
g2^x) = (X]2 + Х22)Х2 < 0
в точке х* = 0, р = 3 не существует вектора к, ||Л|| = 1, такого, что g"2(0)[k]3 = 0. Аналогичная ситуация имеет место для смешанного случая с ограничениями
gl(x) < 0, g2(x) < 0, (1 11)
gз(x) = (Х2 - Х])(Х] - 2X2) < 0.
Ранее были получены условия оптимальности вида (1.9) только для случая (ф '(х*), к) = 0,
к е Ag(x*) = {k е [n |g(k)(x*) [k]k < 0, i = rk-1 + 1, rk, k = 1, p},
(1.12)
где Ag (x*) — критический конус для задачи (1.5), (1.6) [11], или необходимые условия минимума в виде
(Ф'(x*),к < 0, к е Ag(x*), (1.13)
ф '(x*) е (Ag (x*))*.
В данной работе предлагается соотношение, которое должно выполняться в точке минимума х* в случае нарушения (1.8) или (1.12) и которое имеет такой же вид, как и уравнение Куна— Таккера в регулярном случае.
2. Условия оптимальности решений. Введем необходимые для дальнейшего обозначения и
определения. Для к е Ag (x*) определим множество индексов
_ p
10k(k) = {i 6 {rk-1 + 1,..., rk}|gf)(x*)[k]k0}, k = 1P, 10(k) = U10k(k).
k=1
Обозначим через Ж max конус максималного раствора (замкнутый), такой, что Int Ж max С Ag(x*). Отметим,что конус Ag (x*) — замкнутый. Это следует из условия gi е Cp+1(Rn), i = 1, m.
Определение 1. Пусть Ж — замкнутый конус с непустой внутренностью, т.е. Int Ж ^ 0. Границей ОЖЖ конуса Ж назовем такие лучи к е Ж, что окрестность UE(k) содержит как точки x е Ж, так и точки x £ Ж.
Определение 2. Пусть граница ОЖЖ конуса Ж разбивает пространство [Rn на части G+Ж и в~Ж с общей границей GCTЖ (GCTЖ с GЖ) так, что [n = G+Ж u Ga3( и Ж £ IntG+Ж, Ж с Ga3£, где пе! — множество индексов (конечное). При этом Int G+Ж n Int G^-Ж = 0 при ст' ф ст ", а', а'' еБ. Причем G+Ж п G.-''Ж = {0}. Внешней границей О^Ж конуса Ж называется граница ОаЖ, такая, что конус Ж max С G+Ж.
Введем понятие ^-регулярности ограничений gi(x), i = 1, m.
Определение 3. Будем говорить, что ограничения gi(x), i = 1,m, р-регулярны в точке x* е X, если для любого k е Ag(x*), ||k|| = 1, векторы {g(k)(x*)[k]k-1}. k = 1, p, линейно независимы либо Ag (x*) = {0}.
Векторы g-p)(x*)[k]p-1 называются р-фактор-операторами.
Лемма 1. Пусть g{(x) e Cp+1(Rn), i = 1, m, р-регулярны в точке х*. Тогда любой k е Ag(x*), Ikl ^ 0, такой, что I0(k) Ф 0, принадлежит границе GAg(x*), т.е. k е GAg(x*).
Доказательство. Действительно векторы {g(k)(x*)[k]k-1}. 7^, k = 1,p, линейно независимы и следовательно 3 k такой, что g(k)(x*) [k]k-1k < 0. Далее доказательство с очевидностью следует из свойства р-форм.
Следствие 1. Пусть вектор к е Ля(х*), к * 0, и 10(к) Ф 0. Тогда h порождает непустую внутренность 1пи (х*) Ф0 и граничный элемент к е ОЛя(х*).
Следствие 2. Если ограничения gi(x) е Ср+1(К"), I = 1, т, р-регулярны в точке х* и к е Лё (х*),
= 1, 10(к) Ф 0, то 1п[к Л&(х*) содержат шар D5 одинакового радиуса 5 > 0 равномерно для всех такихh.
Определение 4. Будем говорить, что конус (х*) разложим на элементарные конусы Л^(х*) (а е М — множество индексов), если конус Л&(х*) может быть представлен как объединение конусов Л?(х*), таких, что
Ag (x*) = U Ag(x*)
ае Ы
и каждый Ag(x*) содержит непустую внутренность Int Ag (x*), причем Int Ag (x*) n Int A" (x*) = 0 для любых аа'' е Ы, а' ^ а'' и Ag(x*) не разложим на элементарные конусы для любых а е Ы. В противном случае конус Ag (x*) не разложим на элементарные конусы.
Лемма 2. В условиях леммы 1 конус Ag (x*) разложим в конечную сумму элементарных конусов с непустой внутренностью
Ag (x*) = U Aga(x*),
а=1
т.е. М = {1, ..., — конечное множество.
Доказательство. Следует из непрерывности ограничений и gki (х), к = 1, р, I = 1, т в окрестности точки х*, свойств р-регулярности, следствия 2 леммы 1 и соображений компактности (лемма Бореля). Не может конус в конечномерном пространстве быть объединением бесконечного числа непересекающихся конусов с внутренностью, содержащей шар больше заданого положительного радиуса при ||к|| = 1.
Очевидно, что каждый Лg'(x*) имеет замкнутую внутреннюю границу GEЛg'(x*) и конусы Л^(х*) являются односвязными конусами (иначе были бы разложимыми). Обозначим через Ц- множество индексов ю (возможно, континуальное), такое, что
h 6 GEAJg (x*), U h = GEAJg (x*).
oeQ :
Теорема (необходимое условия оптимальности). Пусть ф е С (К"), g¡ е Ср+ (К"), i = 1, т, и в точке минимума х* ограничения g¡(х) р-регулярны. Тогда для любых у е {1, и векторов к^ е &ЕЛ]& (х*), ю е О.у, ||кщ|| = 1, существуют Хк(к^) < 0, i е /0к(к^), к = 1,р, такие, что
ф'(х*) = X | X ^(к<Мх*)Т + X Хг2(k¿)(g;•(x*)[A¿])т + ...
шеПу [¡Е!0(ку) ¡е!М) (2 1)
+ X ^Р(к<Ш)^(р)(х*) [к<]р-1)т [.
¡е! 0р(ку) ]
Здесь индекс - отвечает за конус Л^(х*), у = 1, ..., ^, а индекс ю — за принадлежность всем элементам множества 0ЕЛ]&(х*).
Замечание. Если ОЛ& (х*) = 0, то 0ЕЛ& (х*) = 0 и ф '(х*) = 0, так как в этом случае ЛДх*) = К". При Л (х*) = {0}, 0ЕЛ (х*) = {0} считаем правую часть (2.1) равной К", т.е. ф'(х*) е К".
5
Доказательство. B силу р-регулярности ограничений можем полагать gi(x) = g'(x*) [x - x*], i = 1,..., r
gi(x) = g^x*) [x - x*]p, i = rp_1 + 1, ..., rp. Рассмотрим два случая.
10. Не существует опорной гиперплоскости для конуса Ag (x*), проходящей через точку 0 так, что Ag (x*) лежал бы в одном из двух полупространств, порожденных этой гиперплоскостью. Другими словами, для любой гиперплоскости п, порожденной ортом Ь(П = x| (Ь, x) = 0)
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.