ЖУРНАЛ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ И МАТЕМАТИЧЕСКОЙ ФИЗИКИ, 2015, том 55, № 9, с. 1486-1492
УДК 519.642.8
ОБ ОЦЕНКАХ РЕШЕНИЙ СИСТЕМ ВЫПУКЛЫХ НЕРАВЕНСТВ1)
© 2015 г. А. В. Арутюнов, С. Е. Жуковский
(117198 Москва, ул. Миклухо-Маклая, 6, РУДН) e-mail: arutun@orc.ru; s-e-zhuk@yandex.ru Поступила в редакцию 12.11.2014 г.
Получены оценки расстояния от заданной точки до множества решений системы строгих и нестрогих неравенств, описываемых выпуклыми функциями. В качестве следствий получены оценки расстояния от заданной точки до множества Лебега выпуклой функции, а также достаточные условия накрываемости выпуклозначных многозначных отображений. Библ. 13.
Ключевые слова: выпуклые функции, системы выпуклых неравенств, оценки расстояний до множества.
DOI: 10.7868/S0044466915070030
Пусть ^ — рефлексивное банахово пространство с нормой || • ||. Заданы выпуклое замкнутое множество Xс выпуклые функции gj : ^ —>- R и {+да}, j = 1, k (натуральное k задано), точки У = (У1, •••, Ук) е Rk и Хо е X.
Рассмотрим систему неравенств
gj(Х)< yj, j = 1, 5, gj(х)< yj, j = s + 1, k, (1)
х е X,
относительно неизвестного x (целое неотрицательное s < к задано).
Обозначим через Yс [к множество тех векторов y е Rk, для которых система (1) имеет решение. Для каждого y е Yобозначим через D(y) с ^ множество решений системы (1). Цель настоящей заметки заключается в получении оценки расстояния от точки x0 до множества D(y) решений системы (1).
Классическим результатом об оценке расстояния от произвольной точки до множества решений системы линейных равенств и неравенств является лемма Хоффмана (см. [1], [2]). Это утверждение имеет многочисленные приложения в линейном программировании (см., например, [1, глава 2, § 10]) и общей теории экстремальных задач (см., например, [2, § 3.3]). Что касается изложенной выше проблемы, то интерес к ней обусловлен, прежде всего, вопросами построения и обоснования численных методов решения выпуклых задач условной оптимизации. Так, например, оценки расстояний от заданной точки до множества D(y) используются при определении скорости сходимости метода штрафных функций для задачи
f(x) —" min, x е D(y),
где f: Rn —► R — некоторая функция. Этот вопрос подробно изучен, например, в [3, § 4.7.3]. Эти оценки используются также при идентификации активных индексов систем неравенств вида (1) (см., в частности, [3, § 4.6.1], [4], [5]). Отметим также, что исследование систем вида (1) имеет приложения в теории оптимального управления, например при исследовании линейных задач с фазовыми ограничениями, определенными выпуклыми неравенствами. Такие задачи изучались в [6].
Работа выполнена в рамках реализации государственного задания министерства образования и науки РФ в сфере научной деятельности (код проекта 1.333.2014/К), при поддержке РФФИ (коды проектов 14-01-31185, 13-01-12446 офи_м), РНФ (код проекта 15-11-10021).
Еще одним вопросом, связанным с оценками решений системы (1), является задача о накры-ваемости многозначных отображений некоторого специального вида. Напомним определение накрываемости (см., например, [7]).
Пусть задано положительное число а и многозначное отображение G : Y, ставящее в со-
ответствие каждой точке х е X непустое замкнутое подмножество G(x) с Y. Это многозначное отображение G называется а-накрывающим, если
Ух0 е X, Уу0 е в(х0), Уу е У Зх е X : у е в(х) и \\х - х0|| < .
а
Понятие накрывающего отображения используется для получения условий разрешимости уравнений и включений (см., например, [7]) и при построении численных методов решений уравнений и включений (см. [8]). В связи со сказанным представляет интерес вывод условий накрываемости многозначных отображений следующего вида.
Рассмотрим многозначное отображение G : X=t Y, определенное по формуле
в(х) = g(x) + Ух е X, (2)
где g(x) = ^(х), ..., qk(x)), а — множество всех векторов из [к с неотрицательными компонентами. Очевидно, что если ■х) < для любого x е X,] = 1, к, то многозначное отображение G сюръективно. При этом, как будет показано ниже, если выполняются некоторые оценки расстояния от произвольной точки х0 до множеств Б(у), то отображение G будет накрывающим.
1. ПРЕДВАРИТЕЛЬНЫЕ СВЕДЕНИЯ
Введем необходимые обозначения. Обозначим через Ш* пространство, топологически сопряженное к Ш. Норму в Ш* будем обозначать так же, как и норму в Ш, т.е. через || • ||. Значение функционала х* е Ш* на векторе х е Ш будем обозначать через (х*, х). Пусть также 0(х, Я) = {и е Ш : : ||и — х|| < Я} — это Я-окрестность точки х е Ш. Единичную сферу в Ш обозначим через S. Расстояние от точки х до множества и с Ш определим соотношением
х, и) = тДНх - и|| : и е и}.
Через с1( и) обозначим замыкание множества и, а через ш1( и) — его внутренность. Наряду с бесконечномерным нормированным пространством Ш будем рассматривать евклидово пространство [к с евклидовой нормой | • |.
Напомним некоторые понятия и факты из выпуклого анализа. Пусть /: Ш —»- [ и{+да} — выпуклая функция. Эффективным множеством функции/называется множество
ёош(/) = {х е Ш :/(х)< + да}.
Субдифференциалом функции / в точке х е Ш называется множество д/(х) всех линейных непрерывных функционалов х* е Ш* таких, что
/(и) >/(х) + (х *, и - х) У и е Ш.
Касательным конусом к множеству Xв точке и е Xназывается множество
Тх(и) = с1 {Х(х - и) : х е X, X > 0}.
Нормальным конусом к множеству Xв точке и е Xназывается множество
и) = {х* е Ш* : (х*, х- и) < 0 Ух е X}.
Определенные таким образом множества Т^и) и ^(и) являются замкнутыми выпуклыми конусами. Очевидно, для них имеет место неравенство
(х*, К) < 0 Ух* е и), УН е Т^и).
2. основной результат и некоторые следствия
Всюду далее мы будем полагать, что
(i) Xс int(dom(gj)) для любого j = 1, k;
(ii) на множестве 1 int(dom(gj)) каждая из функций g, j = 1, k, непрерывна.
Приведем оценку расстояния от точки x0 до множества D(y) решений системы (1). Доказательства всех утверждений приводятся в следующем разделе.
Теорема 1. Предположим, что выполняется следующее условие регулярности: существуют числа R > 0, а > 0 такие, что
Vx е X\O(x0, R) Бе = e(x) е (-TX(x)) n S : <x*, е) > а Vx* е dgt(x), Vj = Тд. (3)
Тогда имеет место неравенство
dist(x0, D(y)) < maxjR, 1 ]Г max{ 0, gj(x0) -y-} j Vy е Y. (4)
L j = 1 J
Замечание 1. Если в системе (1) заменить нестрогие неравенства на строгие, то множество D(y) решений системы (1) уменьшится. Однако, как показывает теорема 1, оценка (4) при этом не изменится. Более того, далее, в лемме 1, будет показано, что и само расстояние dist(x0, D(y)) при этом не изменится.
Замечание 2. Условие регулярности (3) в теореме 1 существенно. Если оно нарушается, то утверждение теоремы 1 может не выполняться ни при каких R > 0, а > 0. Приведем соответствующий пример.
Пример. Пусть к = 1, ^ = X = R, g(x) = ex, x0 = 0. Тогда утверждение теоремы 1 нарушается, поскольку для любых R > 0, > 0, для достаточно малого положительного y справедливо неравенство
dist (x0, D(y)) = |lny| > max j R, ^ J = maxj R,g (Х ^ - y
Здесь дело в том, что условие регулярности (3) нарушается, поскольку dg(x) = e —- 0 при x —» —да.
Приведем теперь следствия теоремы 1. Начнем с утверждения об оценке расстояния от заданной точки до множества решений выпуклого неравенства.
Теорема 2. Пусть функция f : ^ —»- R и {+да} выпукла, существует точка Х е X, для которой f (Х) < 0. Предположим, что существуют числа R > 0, а > 0 такие, что
Vx е X\O(x0, R) Бе = е(x) е (-TX(x)) n S : <x*, е) > а Vx* е df(x). (5)
Тогда имеет место неравенство
dist(x0, {x е X : f(x) < 0}) < maxjR,f(xL)^. (6)
Задача об оценке расстояния до множеств Лебега выпуклой функции изучалась также в [9], [10]. В этих работах были получены аналогичные оценки при условиях регулярности, отличных от (5).
Приведем теперь достаточные условия накрываемости многозначных отображений. Зададим многозначное отображение G : X=e Yro формуле (2).
Предложение 1. Предположим, что условие (3) выполнено при некотором а > 0 и R = 0, т.е.
Vx е X Бе = в (x) е (-TX(x)) n S : < x*, е) > а Vx * е dgj (x), Vj = IJc. (7)
Тогда многозначное отображение Gявляется (а/ Jk)-накрывающим.
3. ДОКАЗАТЕЛЬСТВА Доказательству теоремы 1 предпошлем вспомогательное утверждение. Лемма 1. Для любого y е Yимеет место равенство
{х е X : gj(х) < y, j = ~k} = cl(D(y)).
Доказательство. Положим
D (y) = {x е X : gj (x )< yp j = }.
В силу непрерывности функций g-(-) на множестве Xсправедливо включение D(y) ^ cl(D(y)). Поэтому для доказательства леммы достаточно показать, что
D(y)с cl(D(y)). (8)
Возьмем произвольные точки х е D(y), х е D(y). В силу выпуклости функций g-(-), j = 1, k, при любом б е (0, 1] имеем
gj(х + б(х - х)) = gj(sx + (1 - б)х) < вgj(х) + (1 - s)gj(х).
Следовательно, при любом в е (0, 1] справедливы неравенства
gj(х + в(х -х))< 0, j = 1, s, gj-x + s(x-x)< 0, j = s + 1, k.
Поэтому x + s(x - x) е D(y) для любого s е (0, 1] и, следовательно, х е cl(D(y)). Включение (8) доказано.
Доказательство теоремы 1. Рассмотрим два случая. Если существует точка х е D(y) такая, что ||х0 — х|| < R, то неравенство (4) выполняется автоматически.
Пусть теперь ||х0 — х|| > R для любого х е D(y). В силу леммы 1 имеем dist(xo, D(y)) = dist(хо, {х е X: gj(х) <y, j = 1, k}).
В свою очередь имеем
dist (хо, {x е X : gj(x) < y, j = 1, k}) = ||xo - x||,
где x — решение задачи
||x0 - x|| —min, gj (x )< yj, j = ~k, (9)
x е X.
Отметим, что решение в этой задаче существует. Действительно, множество допустимых точек D(y) является выпуклым замкнутым подмножестовом банахова пространства и, значит, это множество слабо замкнуто. Кроме того, минимизирующая последовательность допустимых точек {хи} (т.е. такая, что ||х0 — хи|| —► inf{ ||х0 — х|| : х е D(y)}) ограничена и, значит, поскольку банахово пространство ^ рефлексивно, она содержит подпоследовательность, которая слабо сходится к некоторой точке х. В силу слабой секвенциальной полунепрерывности снизу нормы точка х является решением задачи (9) (подробнее см. [11, глава 8, § 1]).
Применим к задаче (9) теорему Куна—Таккера (см., например, [12, глава 1, § 1.1]). Определим функци
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.