ЖУРНАЛ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ И МАТЕМАТИЧЕСКОЙ ФИЗИКИ, 2007, том 47, < 10, с. 1657-1671
УДК 519.626
ОБ УСТОЙЧИВОСТИ РЕШЕНИЯ ЗАДАЧ О ВНЕШНЕЙ И ВНУТРЕННЕЙ ОЦЕНКЕ ВЫПУКЛОГО КОМПАКТА ШАРОМ1
© 2007 г. С. И. Дудов, А. С. Дудова
(410012 Саратов, ул. Астраханская, 83, Саратовский гос. ун-т) e-mail: dudovsi@info.sgu.ru Поступила в редакцию 03.05.2007 г.
Рассматриваются конечномерные задачи о внешней и внутренней оценке выпуклого компакта шаром некоторой нормы (задачи об описанном и вписанном шаре). Дается общая характеристика устойчивости решения относительно погрешности задания оцениваемого компакта. Получен новый критерий решения задачи о внешней оценке в форме, связывающей ее с задачей о внутренней оценке нижнего лебегова множества функции расстояния до самой дальней точки оцениваемого компакта. При дополнительном предположении о сильной выпуклости компакта дается количественная оценка устойчивости центра вписанного шара. В предположении сильной квазивыпуклости используемой нормы получена количественная оценка устойчивости центра описанного шара. Библ. 24.
Ключевые слова: оценка выпуклого компакта шаром, устойчивость решения, внешняя и внутренняя оценки, сильная выпуклость.
1. ВВЕДЕНИЕ
Интерес математиков к оценке и аппроксимации достаточно сложных множеств множествами простой геометрической структуры возник очень давно (см., например, [1], [2] и библиографии в них) и возобновлялся по мере появления в математике новых средств исследования, позволяющих рассматривать как новые задачи, так и старые задачи, но на более высоком уровне. Ныне это направление поддерживается в рамках негладкого анализа и недифференцируемой оптимизации, которые дают эффективные инструменты для исследования таких задач.
Задачи по оценке множеств, а также многозначных отображений находят обширные приложения в естествознании, в том числе и в самой математике. Известны многочисленные работы, связанные с внешними и внутренними эллипсоидальными оценками множеств и многозначных отображений (см., например, [3], [4]). Для техники особое значение имеют внешние и внутренние оценки множеств ориентированными параллелепипедами (см., например, [5], [6]). Рассматривались аппроксимации выпуклого компакта линейными комбинациями заданного набора выпуклых компактов простого вида (см., например, [7]), а также внутренние и внешние аппроксимации выпуклого компакта многогранниками (см., например, [8], [9]) и другие задачи.
Наряду с эллипсоидом и многогранником, к числу наиболее простых множеств относится шар любой нормы. В данной статье на предмет устойчивости решения рассматриваются две известные задачи по оценке множества шаром некоторой нормы.
Первая из них - задача об описанном шаре или чебышёвском центре множества. Если D -оцениваемый компакт из конечномерного пространства IFS^, а функция n(x) - используемая норма на f^, то задачу можно записать в виде
R (x, D )= maxn (x - y)—- min. (1.1)
У e D „P
7 x e R
Эту задачу будем также называть задачей о внешней оценке компакта D шаром нормы n(). Она требует построения шара наименьшего радиуса, содержащего оцениваемый компакт D. Поскольку замена компакта D в задаче (1.1) на его выпуклую оболочку не меняет ее решения, то без потери общности будем далее считать компакт D выпуклым.
^Работа выполнена при финансовой поддержке РФФИ (код проекта 06-01-00003).
1657
Вторая задача - задача о вписанном шаре или задача о внутренней оценке выпуклого компакта В шаром нормы «(•). Ее можно записать в виде
р(х, О) = ттп(х - у)—► тах. (1.2)
у ей хе В
Здесь Q = Rp\D, а функция р(х, Q) выражает расстояние от точки х до множества Q в норме n(-). Задача (1.2) требует построения шара нормы n(-) с максимальным радиусом, который содержится в D.
О некоторых свойствах целевых функций задач (1.1) и (1.2), а также самих решений как для случая евклидовой нормы, так и для произвольной см., например, [1], [10]—[14].
В этой работе исследуем задачи (1.1) и (1.2) на устойчивость решения относительно погрешности задания оцениваемого выпуклого компакта D. Уточним постановку вопроса.
В практических ситуациях информация о компакте D может носить приближенный характер, т.е. вместо D нам может быть известен другой выпуклый компакт De такой, что h(D, De) < е. Здесь е > 0 - известная погрешность задания компакта D, а
h(A, B) = max{ sup inf|\a - b\\, sup inf|\a - b|| } (1.3)
aeAbeB beBaeA
есть расстояние Хаусдорфа между множествами A и B в евклидовой норме ||-1|. Таким образом, о решениях (1.1) и (1.2) мы можем судить по решению приближенных задач
R (х, De)= max n (х - y)—» min, (1.4)
Уe De „p
* е х e R
p(x,Qe) = minn(х -y)—- max, (1.5)
y eQe х e De
где О£ = КР \ В£. Требуется охарактеризовать устойчивость решений задач в целом и по возможности дать количественную оценку устойчивости через £ оптимальных значений целевых функций и самих множеств решений, т.е. радиусов и центров описанных и вписанных шаров.
Отметим, что исследование устойчивости решения задачи выпуклого программирования, как известно (см., например, [15]), может опираться на сильную выпуклость (см. [16, с. 181]) целевой
функции, если она имеется. Однако функция Я(х, В), являясь выпуклой по х на И^, ни при каких условиях на В и п(-) не является сильно выпуклой на каком-либо телесном выпуклом множестве. А функция р(х, О) является вогнутой по х на выпуклом компакте В, но на любом его выпуклом телесном подмножестве не является сильно вогнутой. Уточняющие комментарии по этому поводу имеются в разд. 2.
Содержание работы таково. В разд. 2 приводятся используемые вспомогательные понятия и факты. Главными из них являются сведения из сильно выпуклого анализа (см. [9]), лежащие в основе получения количественной оценки устойчивости центров описанного и вписанного шаров. В разд. 3 дана общая характеристика устойчивости решения задач (1.1) и (1.2), т.е. не требующая каких-либо дополнительных условий на В и п(-). В разд. 4 получен новый критерий решения задачи (1.1) о внешней оценке в форме, связывающей ее с задачей о внутренней оценке нижнего лебегова множества функции Я(х, В). Именно он оказался удобным для оценки устойчивости центра вписанного шара. В разд. 5 при дополнительном предположении о сильной выпуклости компакта В получена количественная оценка устойчивости центра вписанного шара, а в предположении сильной квазивыпуклости используемой нормы п() дана оценка устойчивости центра описанного шара.
Авторам неизвестны работы, где бы ранее ставился вопрос об устойчивости центра вписанного или описанного шара. Дело, по-видимому, в том, что, как показывает один из приведенных в разд. 5 примеров, без какой-либо количественной характеристики выпуклости оцениваемого компакта получить количественную оценку устойчивости центра вписанного шара нельзя. Понятие сильно выпуклого множества как раз дает пример количественной характеристики выпуклости множества.
2. ВСПОМОГАТЕЛЬНЫЕ ФАКТЫ
Для общей характеризации и оценки устойчивости решения задач (1.1) и (1.2) нам будут нужны некоторые сведения о свойствах функций Я(х, В) и р(х, О), а также понятия и факты из сильно выпуклого анализа (см. [8], [9]). Кроме уже введенных будем использовать следующие обозна-
чения: А , тЫ, соА - соответственно, замыкание, внутренность, выпуклая оболочка множества А; А - В = {с : с + В с А} - разность Понтрягина множеств А и В;
Вп(х, г) = {у е КР : п(х - у )< г }, 8п(х, г) = {у е КР : п (х - у) = г }
суть шар и сфера нормы п() с центром в точке х и радиусом г; В(х, г), £(х, г) - шар и сфера евклидовой нормы с центром в точке х и радиусом г;
х, В) = {у е В : Я (х, В) = п (х - у)}
есть множество точек касания компакта В и сферы 8п(х, Я(х)); 0р(х, П) = {у е П : р(х, П) = п(х - у)} -
проекция точки х на множество П; (х, у) - скалярное произведение элементов х и у е Кр; К(А) =
= {V е Кр : За > 0, а е А, V = аа}, К+ = {^ е Кр : (V, м>) > 0, VV е К}; К(х, А) - конус возможных направлений множества А в точке х (см. [12, с. 31]);
n *(w) = max ( v, w)
v:n(v) < 1
есть полярная норма к n(-);
GR(X) = {x e Up : R(x, D)<^}, = Rp\GR(X),
D(x) = {у e Up : p(y, Q) > p(x, Q)}, Q(x) = {y e Up : p(y, Q) < p(x, Q)};
diamЛ = sup ||x - y||
x, y e A
есть диаметр множества A в евклидовой норме, 0p = (0, ..., 0) e U^.
2.1. Известно, что все нормы на конечномерном пространстве Up являются эквивалентными и, следовательно, для конкретно выбранной нормы n() найдутся положительные константы Q и C2 такие, что
Cjx|| < n (x)< C2\\x\\ Vx e Up. (2.1)
Далее по тексту, не оговаривая каждый раз специально, будем считать, что константы C1 и C2 соответствуют неравенствам (2.1). Кроме того, любая норма является конечной и выпуклой на Up функцией. Субдифференциал нормы можно записать в виде (см. [11, с. 161])
dn(0 p) = { v e Up : n * (v) < 1},
p (2.2)
д n (x) = { v e Up : n * (v) = 1, n (x) = ( v, x)}, x Ф 0 p.
Теперь напомним некоторые общие свойства функций R(x, D) и p(x, Q).
Теорема 1 (см. [11, с. 163]). Функция R(x, D) является выпуклой по x на Up, а ее субдифференциал может быть выражен формулой
dR(x, D) = co{dn(x-z) : z e QR(x, D)}. (2.3)
Теорема 2 (см. [17]). Функция p(x, Q) является вогнутой по x на выпуклом множестве D, а ее супердифференциал в точках x e intD может быть выражен формулой
др( x, Q) = co{d n (x - z)n K+ (z, D) : z e Qp( x,Q)}. (2.4)
В [18] доказана
Лемма 1. Если точки x иy таковы, что p(y, Q) > p(x, Q), то
р(y, Q) = p(y,Q(x)) + p(x, Q).
Из (2.1) легко следует
Лемма 2. Если радиус максимального шара нормы n(-), вложенного в множество D, равен 5, то радиус максимального евклидова шара, вложенного в то же множество D, не более чем 5/Cx.
2.2. Далее будем использовать некоторые понятия и факты из сильно выпуклого анализа (см. [8], [9]).
Определение 1. Множество A с [ называется r-сильно выпуклым, если оно представимо в виде пересечения замкнутых евклидовых шаров радиуса r.
Определение 2. Пусть A - ограниченное множество из а числа r > р > 0 такие, что B(0p, р) -
- A Ф 0. Сильно выпуклой оболочкой радиуса r множества A называется множество, получаемое при пересечении всех замкнутых евклидовы
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.