Содержание к диссертации
Введение
Глава 1. Задача о внешней оценке компакта шаром произвольной нормы 18
1. Постановка задачи о внешней оценке, вспомогательные сведения 18
2. Свойства строго и сильно квазивыпуклых норм 23
3. Свойства целевой функции R(x) 38
4. Свойства функции расстояния до строго и сильно выпуклого множества 43
5. Критерии решения задачи о внешней оценке 60
6. Характеризация устойчивости решения задачи о внешней оценке 67
Глава 2. Задача о равномерной оценке выпуклого компакта евклидовым шаром
7. Постановка задачи о равномерной оценке, вспомогательные сведения 76
8. Свойства вспомогательной функции RQ(X) 80
9. Оценки для производной по направлениям функции расстояния 82
10. Свойства целевой функции Ф(х) 88
11. Характеризация устойчивости решения задачи о равномерной оценке 96
Список литературы 103
Список используемых обозначений
- Свойства строго и сильно квазивыпуклых норм
- Критерии решения задачи о внешней оценке
- Свойства вспомогательной функции RQ(X)
- Свойства целевой функции Ф(х)
Введение к работе
1. Интерес математиков к оценке и аппроксимации достаточно сложных множеств множествами простой геометрической структуры во шик очень давно (см., например, монографии Т.Боннезена, В.Фенхеля [2], Л.Ф.Тота [21] и библиографии в них). Ныне это направление активно поддерживается в рамках негладкого анализа и недифференцируе-мой оптимизации, основы которых заложены в трудах Р.Т.Рокафеллара, Б.Н.Пшеничного, В.Ф.Демьянова, A.M.Рубикона, Ф.Кларка, Ж.-П.Обена, И.Экланда, Н.З.Шора, Б.Т.Поляка, М.С.Никольского, Е.С.Половиикина ([20], [17]-[18], [5]-[7], [9], [13]-[14], [24], [19], [12], [15]-[16]) и других ма-тематнков. Именно негладкий анализ даог эффективные необходимые математические инструменты для успешного исследования таких задач.
Задачи по оценке множеств находят обширные приложения в естествознании, в том числе и в самой математике. Известны многочисленные работы, связанные с внешними и внутренними эллипсоидальными оценками множеств и многозначных отображений (напр., работы Н.З. Шора [24], Ф.Л. Черноусько [23], А.Б. Куржанского и др.). Можно также указать на работы по внешним и внутренним оценкам заданных множеств ориентированными параллелепипедами и их приложениями (см., напр., [1]). Е.С, Половинкиным в [15] рассматривались внутренние и внешние многогранные аппроксимации выпуклых множеств.
Наряду с эллипсоидом и многогранником к числу наиболее простых множеств, как в геометрическом смысле, так и по числу задающих параметров, относится шар любой нормы.
Задача о внешней оценке компакта шаром произвольной нормы, которая заключается в построении шара используемой нормы с наименьшим радиусом, содержащего оцениваемый компакт, рассматривались Б.Н. Пшеничным в [17].
Задача о наилучшем приближении (равномерной оценке) в метрике Хаусдорфа выпуклого компакта евклидовым шаром была поставлена и изучалась в работе М.С. Никольского и Д.Б. Силина [12].
Основная цель диссертации- исследование устойчивости решения этих
двух задач относительно погрешности задания оцениваемого (приближаемого) компакта.
2. Приведем математическую формализацию задачи о внешней оценке, которую также называют задачей об описанном шаре или задачей о чебышсвском центре множества.
Пусть D заданный компакт из конечномерного действительною пространства W, а функция п(х) удовлетворяет на W аксиомам нормы. Тогда задачу о внешней оценке компакта D шаром нормы п(-) можно записать в виде
R(x) = maxnfa; — у) -> min. (0.1)
Значение функции R(x) выражает радиус наименьшего шара с центром в точке х, содержащего в себе компакт D. Точка %*, доставляющая минимальное значение функции R{x), является центром искомого описанного шара, аЛ* = R(x*) - его радиус.
Известно([2]), что для случая, когда п(х) — \\х\\ - евклидова норма, решение задачи (0.1) единственно. При этом центр описанного шара принадлежит выпуклой оболочке точек, одновременно принадлежащих границе компакта D и поверхности описанного шара (то есть его граничной сферы). Верно и обратное, а именно, шар, содержащий компакт и обладающий указанными выше точками множества D на его границе, есть описанный шар. Следовательно центр описанного шара всегда принадлежит выпуклой оболочке компакта D.
Диаметр компакта D
d* — max Ця; — у\]
x,yD
и радиус описанного евклидова шара R* связаны неравенством, полученным Г. Юнгом (см. [11, с.73]).
-\J2{p+l) Как показывают примеры, если п(х) не является евклидовой нормой,
то задача (0.1) может иметь неединственное решение, а центр описанного шара может не принадлежать выпуклой оболочке компакта D.
В практических ситуациях информация об оцениваемом компакте D может носить приближенный характер, то есть вместо компакта D нам может быть известен некоторый компакт D такой, что
h(D,D)
Здесь є > 0 - известная погрешность задания компакта D, а
k(A, В) = max{sup inf п(а — Ь), sup inf п(а — Ь)}
- расстояние Хаусдорфа между множествами А и В в норме п(-).
И, таким образом, о решении задачи (0.1) мы можем судить по решению приближенной задачи
RJx) = maxn(x — у) —l? min. (0.2)
Получение условия устойчивости и оценка характера устойчивости задачи (0.1) ошосительио оптимального значения целевой функции Щх) и центра описанного шара - один из вопросов, решаемых в диссертации.
Любая норма, как следует из ее аксиом, является выпуклой функцией на всем пространстве. Поэтому, легко видегь, и функция R(x), являющаяся результатом операции максимума от выпуклых функций, также выпукла на W. Следовательно задача (0.1) является задачей выпуклого программирования. Известно (см. [10, с.42]), что вопрос о характериза-ции устойчивости задачи выпуклого программирования легко решается, если целевая функция является сильно выпуклой ([3, с.181]). Однако ни при каких условиях на компакт D и используемую норму п(-) функция R(x) не является сильно выпуклой не только на IRP, но и любом выпуклом множестве с непустой внутренностью. Именно это обстоятельство затрудняет исследование устойчивости задачи (0.1).
3. Приведем математическую формализацию второй задачи, исследуемой на устойчивость решения.
Пусть D непустой выпуклый компакт из W, h(A,B)- расстояние Ха-усдорфа между множествами Аи В в евклидовой норме,
В(х,г) = {у<=№:\\х-у\\<г}
- евклидов шар с центром в точке х и радиусом г.
Тогда задачу о наилучшем приближении о і ого выпуклого компакта D евклидовыми шарами в метрике Хаусдорфа можно записать в виде
h(D,B(x,r))-> min . (0.3)
Задача (0.3) впервые была поставлена и рассматривалась в работе М.С.Никольского и Д.В.Силина [12]. В пси доказаны существование и единственность решения, получено необходимое условие решения. Отметим, что задача (0.3) рассматривалась авторами [12] в рамках более общей задачи о наилучшем приближении элемента пространства непустых выпуклых компактов с метрикой Хаусдорфа элементами его подпространства, которое представляет собой всевозможные линейные комбинации фиксированного набора элементов данного пространства. Очень важным обстоятельством, установленным в [12], оказалось то, что центр шара наилучшего приближения х0 для компакта D в задаче (0.3) является одновременно единственным решением задачи
R{x) - рп(х) -ь min. (0.4)
Здесь
Мх) = max \\х ~ у||, ра(х) = min Цат - у\\, Q = Rp\D.
При этом радиус шара наилучшего приближения есть
ЯЫ + РпЫ
ro = J '
а кроме того
mm h(D.D[x,r)) = ———-—;—-.
Поэтому задачи (0.3) и (0.4) являются эквивалентными. Значение R(x) выражает радиус наименьшего шара с центром в точке х, содержащего
компакт D. Значение функции рп(х) дли х Є D выражает радиус наибольшего шара с центром в точке ж, содержащегося в выпуклом компакте D. Таким образом, величина R(x) — рп(х) есть толщина минимального шарового слоя с центром в точке х D, содержащего границу компакта D.
Задача (0.4) о построении шарового слоя наименьшей толщины, содержащего границу выпуклого компакта D известна давно. Впервые близкая но постановке задача рассматривалась М.Оканем в [25], где был предложен способ построения кругового кольца наименьшей ширины, содержащего заданное конечное семейство точек. А.Лебегом в [26] рассматривалась задача о построении кольца "наименьшей толщины содержащего границу 2-мерного выпуклого множества. Позднее Т. Боннезен в [27] для задачи на плоскости и Н. Критикос в [31J для задачи в трехмерном пространстве получили необходимое и досіаточное условие решения и доказали единственность решения.
Свойства минимального по ширине кольца, содержащего границу двумерного выпуклого компакта изучались в связи с другими экстремальными задачами по оценке того же компакта (см. [29[-[32]). Так в работе I.Vincze ([30]) оценивается соотношение минимального радиуса круга, содержащего выпуклый компакт D С Ш? и внешнего радиуса кольца "наименьшей толщины содержащего границу компакта D, а также соотношение максимального радиуса круга, содержащегося в D, и внутреннего радиуса кольца "наименьшей толщины". Получены следующие оценки
тіп{Д(а): х g D} уД
R{xQ) - 2 '
тгх{рц(х) :хЄР] <2
Ы#о) Для задачи (0.4) в пространстве произвольной размерности р необходимое и достаточное условие было получено ужо в 1988 в работе I.Barany ([32]). Заметим, что в этой работе существенным образом были задействованы средства выпуклого анализа. Дело в том, что функция R(x) является выпуклой на всем пространстве W\ а функция рц(х) - вогнутой
на выпуклом компакте/}. Поэтому целевая функция Ф{х) = R(x) —рц(х)
задачи (0.4) является выпуклой на D.
В работе [32] также доказано, что при р > 3 имеет место точная
оценка:
min{R(x) : х Є D] ^ 1. , ч 1 ,
р/ х ->-(соз'а0 + соза0-1 + ),
/цяо) 2 cosqo
где ао Є [0,7г/2] и является решением уравнения
sin2 а — 2 cos3 а = 0,
а величина
тах{рп(ж) : а; X?}
РаЫ может быть сколь угодно большой.
Ввиду эквивалентности задач (0.3) и (0.4) на них всегда интересно
смотреть в сравнении с задачей о внешней оценке
R(x) -> min
и с задачей о внутренней оценке
Pq (х) -> max
выпуклого компакта D евклидовым шаром. В связи с этим задачи (0.3) и (0.4) можно назвать задачами о равномерной оценке выпуклого компакта D евклидовым шаром.
Как и для задачи (0.1), ставится цель получить характеристику устойчивости задачи (0.3) относительно погрешности приближаемого компакта.
4. Диссертация состоит из двух глав, содержащих 11 параграфов. Нумерация параграфов сквозная. При изложении, кроме уже введенных, используются следующие обозначения:
A, intA, соА - соответственно замыкание, внутренность, выпуклая оболочка множества А,
Л + В = {а + 6 : а Є Л,6 Є В}, А- В = {а-Ъ: а Є Л, 6 Є В}
- алгебраическая сумма и разность множеств А и В,
А-В = {с:с + ВсА]
- разность Минковского ([7)) или Л.С. Помтригина множеств А и В,
[хихъ] = со{хі,х2]
- ОТреЗОК, СОеДИНЯЮЩИЙ ТОЧКИ Х\ И Х2,
и = d>w)2)I/2
1=1
евклидова норма элемента х Є W,
р <х,у>= ^Vz)yw 1=1
- скалярное произведение элементов х,у Є Жр,
Вп(х, г) = {у Є Rp : п(х -у)< г}, Sn{x, г) = {у Є W : п{х - у) = т)
- ша]) и сфера нормы п(*) с центром в точке а; и радиусом г,
Q'foD) - {у Є Л : ^() = п(х - у)}
- проекция точки х на множество D в норме п(-),
QV, D) = {yeD: R{x) = n(z - у)}
- множество точек касания множества D и шара B(x,R(x)),
К{А) = {v Є W :3а > 0,а Є A,v = аа}
- конус, натянутый на множество А,
K+ = {w W :< v,w >> 0, Vu Є К]
- конус, сопряженный к конусу К,
К(х,А) - конус возможных направлений множества А в точке же Л, то есть К(х, А) = 7(2, Л), где
ф,А) = {д GRP :3ад <0 : х + ад Є А,а Є (0,()}.
W(x, Л) = sup < x, a >
- опорная функция множества Л,
>л/М = inf{a > 0 : x Є аМ}
- функция Минковского множества Л,
5/W - субдифференциал выпуклой функции /() в точке X,
!\х,д) = \\та-"[!{х + ад)-!{х]\
- производная функции /() в точке х по направлению д.
Первая глава диссертации содержит 1-G, ее главная цель - харакіе-ризация устойчивости решения задачи (0.1) о внешней оценке.
В 1, кроме постановки задачи о внешней оценке, даются сведения из истории ее исследования, некоторые из которых используются далее.
В 2 приводятся некоторые вспомогательные факты, главные из которых касаются свойств строго и сильно квазивыпуклых норм. Эги свойства использовались далее при исследовании свойств целевой функции R(x) в задаче (0.1) и функции рассюяния, также играющей важную роль. Если понятие строго квазивыпуклой нормы и ее свойства использовались в выпуклом анализе ранее (см. напр. [34]), то понятие г-силыю квазивыпуклой нормы, как нормы, обладающей г-силыю выпуклым ([15)) единичным шаром, вводится впервые.
Следующий факт позволяет сравнивать поведение таких норм на отрезках с поведением сильно выпуклых функций.
Лемма 2.8. Еслип{-) является г-сильно квазивыпуклой нормой, то для любых точек х\ и х% отличных от 0р, и а Є [0,1] выполняется неравенство
п{ах\ + (1 — а)х<ь1 < ап{х\) -і- (1 — а)п(х2)— Cia(l — a)n(xi)n(x2)
Х\ Х2
2r(an(x\) + (1 — а)п(х2))
п(х\) п(х2)
где константа Сі - положительная константа, для которой
Ci\\x\\
Для сильно к и ази выпукл ой нормы, единичный шар ко юрой имеег представление
Вп(%,1) = (~)В(а,г), (0.6)
где Л - симметричный относительно 0;, компакт, получена конкретна;! формула, ее выражающая.
Лемма 2.9. Если единичный шар нормы п(-) имеет вид (0.6) при условии Л С intB(Qp,r), то саму норму modicuo выразить следующей формулой
|< а,х>\ + >/<а,а:>2+|И|г(г2-||а||2)
п{х) = max'
аел г2 - ||а||2
В 3 исследуются свойства функции Я(х), являющейся целевой в экстремальной задаче (0.1). Очень важным для характеризации устойчивости решения является следующий факт
Теорема 3.1. Если п(-) является г-сильно квазивыпуклой нормой, то для любых х\ и х2 из W, а Є (0,1) найдется точка
Уа Є Sn{xhR{xi))f\Sn{x2lR(x2))
такая, что выполняется неравенство
R{axi + (1- а)х2) < аН{хг) + (1 - a)R{x2)~
2=1 -Уа $2~ Уа
Cla(l-a)R{xl)R{x2)
R{xi) R{x2)
2r{aR(xl) + {l-a)R{x2)) где Сі - полооїсительпая константа, для которой выполняется (0.5)
При исследовании задач (0.1) и (0.2) важную вспомогательную роль играет функция расстояния. В 4 изучаются свойства функции расстояния до строго и сильно выпуклых множеств, а также до множеств, которые являются их дополнениями. Нетрудно видеть, что функция расстояния
рл(х) = ттп(х -у) уел
не может быть строго, и тем более сильно выпуклой или вогнутой на любом выпуклом множестве с непустой внутренностью при любом мно-
жестве Л и любой используемой норме. Однако строгая (сильная) выпуклость множества Л или его дополнения и етізогая (сильная) квазивыпуклость нормы п{-) дают возможность сравниваль поведение функции расстояния на некоторых отрезках с поведением строго (сильно) выпуклой или строго (сильно) вогнутой функции, а в некоторых случаях говорить о ее строгой квазивыпуклости или строгой квазивогнутости. Для случая, когда D - строго выпуклое множество доказана Теорема 4.1. Если D является строго выпуклым мнооїсеством и точки х\ и х2 из D таковы, что
Р<л{х\) < РпЫ < pn(ari) + п(х\ - х2), то для любого а (0,1) выполняется строгое неравенство pn(axi + (1- 0:)2:2) > apn(zi) + (1- а)ра{х2).
Описание поведения функции рц(х) сразу на веем множестве D даег Теорема 4.2. Если D является строго выпуклым мнооїсеством, то функция рп(х) является строго квазивогнутой на D. Нижние лебеговы множества функции ро{х)
G{\,D) = {xRp:pD{x)<\]
характеризует
Теорема 4.3. Если D является строго выпуклым мнооїсеством, а п(-) - строго квазивыпуклой нормой, то для любого А > 0 мнооїсество G(\t D) является строго выпуклым.
По аналогии с теоремой 4.1, получены также условия, при которых функция рд(ж) ведет себя на некоторых отрезках как строго выпуклая функция.
Теорема 4.5. Пусть D - строго выпуклое мнооїсество, а п(-) - строго квазивыпуклая норма. Если точки х\ и х2 из W удовлетворяют неравенству
Pd(%\) < Pd(x2) < Pd{xi) + п(х\ - х2), причем х2 D, то для любых а Є (0,1) выполняется
Рв{<ухі + (1- а)х2) < apD(xi) + (1- a)pD(x2).
Нижеследующие два факта говорят о том, насколько усиливаются соответствующие свойства функции рв{х), зафиксированные в теоремах 4.3 и 4.5, если D - сильно выпуклое множество, а п{-) - сильно квазивы-нуклая норма.
Теорема 4.6. Если D является г\-силъно выпуклым множеством, а п(*) — г2-сильпо квазивыпуклой нормой, то для любого А > 0 мпооїсество G(X, D) является (п + Хг2)-сильно выпуклым.
Теорема4.7. Пусть D является г\-сгіль)іо выпуклым миооїсестволі, а п(-) - Г2-сильпо квазивыпуклой нормой, и точки х\ и х2 таковы, что
[xhx2]f)D = <&.
Тогда для любых точек yi Qp(x\,D), у2 Є Qp(x2}D) и любого а Є [0,1] справедливо неравенство:
pD{ax\ + (1- а)х2) < apD(xx) + (1- a)pD{x2) - уа(1 - а)*
Х\ - Т/1 х2 - у2
+
Pd(x\) Pofa)
П r2[apD(xi) + (1- a)pD(x2)\
В некоторых относительно простых ситуациях, а именно, на отрезках, концы которых равноудалены от множества D или U, функция расстояния может вести себя как сильно выпуклая или сильно вогнутая функция.
Теорема 4.9. Пусть D - г\-сильио выпуклое мпооїсество, п(-) - г2-сильио квазивыпуклая норма, а точки х\ и х2 таковы, что
Pd{x\) - роЫ) - р > 0, [хих2] f]D = 0.
Тогда для всех значений а [0,1] справедливо неравенство
/ /> \ л ^ CW1 — а)„ )|2
pD(ax: + (1- а)х2) <р- , ді - х2| ,
4Г1 -г рг2)
где Сі - положительная константа, удовлетворяющая (0.5)
Теорема 4.10. Пусть D является г-сильно выпуклым множеством.
Тогда для любых точек Х{ и х2 из D таких, что
и любых значений а Є [0,1] выполняется неравенство
pn{axi + (1- а)х2) >р + — -pi - х2\\ .
Следует отметить, что важную роль и исследовании свойств функции R(x) и функции расстояния, касающихся случаев с сильно выпуклым множеством D или сильно квазивыпуклой нормой, сыграли факты из сильно выпуклого анализа (см. [15]-[16]).
Свойства функции R(x) и функции рассюянин использованы далее в 5, где сформулирован и доказан критерий решения задачи (0.1) в форме, связывающий ее с задачей о внутренней оценке нижнего лебегова множества функции R(x) шаром используемой нормы.
Теорема 5.1. Точка х* является решением задачи (0.1) тогда и только тогда, когда для любого X > R* она является центром вло-оісеиного в мнооїсество GR(X) = {х Є W : R(x) < А} шара наибольшего радиуса, то есть решением задачи
Рп(\)(%) — min п(х — у)-> max ,
где Г2(А) = RP\Gfi(A). При этом радиус вложенного шара есть
Pm{x*) = \-R*.
Эта теорема является самым трудным по доказательству результатом первой главы.
Основным в первой главе является 6, где собраны и доказаны факты, касающиеся устойчивости решения задачи (0.1).
Выяснилось, что устойчивость задачи (0.1) относительно оптимального значения целевой функции R(x) имеет место всегда, причем справедлива
Теорема 6.1. Справедливо неравенство
\R* - Щ\ < С2е,
R' = min Rtx), R: = min RAxY
а Сі - полооїсительная константа, для которой
п{х) < С2\\х\\, VxeW. (0.7)
Каждому выпуклому компакту D, как элементу пространства всех выпуклых компактов Kv(Rp), можно сопоставить X(D) - множество рр-шений задачи (0.1), то есть множество цен і ров описанных шаров. Поэтому можно рассматривать многозначное оюбражение
Х{-) : Kv{Rp) -* 2"Р.
Его характеризует
Теорема 6.2. Многозначное отобраоїсение Х(-) является полунепрерывным сверху всюду на Kv(W).
Приведенный пример 6.1 говорит о том, ч*ю в некоторых ситуациях многозначное отображение Х(-) может не обладать свойством полунепрерывное снизу.
Основным результатом главы является
Теорема 6.3. Пусть п(-) является т-сильно квазивыпуклой нормой. Если точка х" является решением задачи (0.1), а точка х - решением задачи (0.2), то справедливо неравенство
V -xe\\
где полоэ/сителъиые константы С\ и С2 удовлетворяют неравенствам (0.5) и (0.7) соответственно.
5. Вторая глава диссертации содержит 7-11, ее цель - исследование устойчивости задачи (0.3). В 7 дается постановка этой задачи и формулировки результатов из работы М.С.Никольского и Д.Б.Силина [12], которые в значительной мере далее используются.
В 8 приводятся некоторые свойства вспомогательной функции
Rq(x) = тахЦх ~ у\\,
VUD0
D0 = B{xhR{xl))f]B{x2,R(x2))
ДЛЯ НеКОТОрЫХ фиксированных ТОЧек Х\ ф Х%
В 9 получены верхние и нижние оценки производной по направлениям функции расстояния при некоторых дополнительных условиях на выбор направления.
В 10 рассматриваются некоторые свойства целевой функции
Ф(х) = R{x)-pa{x)
в экстремальной задаче (0.4).
Во первых, получена оценка снизу для ее производной по направлению через значение производной по этому направлению функции R(x).
Теорема 10.1. Если intD ф 0; точка х Є intD, а единичное направление g MP таково, что
то
&(xtg)>8(l-
^МЛ _ /(1 _ ^2) Л _ /^(^1
R(x)J у J\ R2{x)J'
Во вторых, дается характеристика устойчивости оптимального значения целевой функции задачи (0.4).
Теорема 10.2. Пусть D - выпуклый компакт такой, что
h{D, D) < є,
где є > 0. Если точка xq - решение задачи (0.3), а х - решение приближенной задачи
h{De,B(x,r))^ miii (0.8)
то справедливо неравенство
\Ф(х0)~Ф(х)\<4є.
Вспомогательные результаты 8-10, а также работы [12] и первой главы диссертации применяются в 11 для получения основных результатов - характеризации устойчивости задачи (0.3).
Наиболее принципиальной и трудной но доказательству во всей диссертации является
Теорема 11.1. Пусть xq - центр шара наилучшего приближения в задаче (0.3), а х - в приблиоісепной задаче (0.8). Тогда справедливо асимптотическое неравенство
. п^лгн \ і 2е 1 + 0 (1))
\х0 - х\\ < 4R{x0)J-B7^- yt-
у R(xQ) - р(я0)
где о(1) -> 0 при є 4-0.
Ее следствием, по сути, является получаемая далее оценка устойчивости радиуса шара наилучшего приближения
Теорема 11.2. Если го - радиус гиара наилучшего приближения в задаче (0.3), агє - в приблиоісепниой задаче (0.8), то справедливо асимптотическое неравенство
У ЩЩ - Мяо) где о(1) -4 0 при є 4-0.
Основные результаты диссертации опубликованы в [35]-[40].
Автор выражает глубокую признательность своему научному руководителю профессору А.П.Хромову за помощь и внимание к работе.
Свойства строго и сильно квазивыпуклых норм
Свойства решения задачи (1.1), в іом числе и характер ее устойчивости к погрешности задания компакта Д во многом зависят от свойств используемой нормы п(-). Любая норма п(х), как выпуклая и конечная на ШР функция является всюду непрерывной и дифференцируемой по любому направлению, а ее субдифференциал дп[-) : ШР — 2ИР, как многозначное отображение, является полунепрерывным сверху всюду на ШР (см. [6, гл.1]), причем для производной по направлениям справедлива формула п (х1д) = \їта і[п(х-\-ад]"п(х)]= max v,g . Q0 vdn[x) Известна формула субдифференциала нормы (см. [17,с.161]) dn{Op) = {veW: n {v) 1}, dn(x) = [v Ер : п» = 1, п(х) = v,x }, х ф 0Р. (2.1) Здесь п (-) = max v. Ф) 1 - полярная норма, 0Р = (0,0, ...0) Є ЕР. В соответствии с хорошо известным понятием строго квазивыпуклой функции можно дать определение строго к вази выпуклой нормы. Определение 2.1. Будем говорить, что норма п(-) является строго квазивыпуклой, если для любых а (0,1) и точек х\ ф х2 выполняется строгое неравенство п{ах\ + (1 — ос)х2) max{n(x\), nfa)}.
Замечание 2.1. Легко показать (как, например, в (6,c.51j), что норма является строго квазивыпуклой тогда и только тогда, когда шар отой нормы является строго выпуклым мноо/сеством. Ясно, что любое строго выпуклое тело, симметричное относительно начала координат Ор, порооїсдает своей функцией Минковского строго квазивыпуклую норму. Следует также отметить, что, в силу своей второй аксиомы, любая норма не может быть строго выпуклой функцией. Примером строю квазивыпуклой нормы является евклидова норма. Чебышевская норма п(х) = тюс х , х = {х{1\х{2\...х ), является примером нормы, не являющейся строго квазивыпуклой. Отметим два свойства строго квазивыпуклых норм, которые могут не иметь места для произвольно выбраной нормы. Лемма 2.1.([34]) Если п(-) - строго квазивыпуклая норма, то для любых точек хіфОр и Х2Ф 0р таких, что X2 ф \%і, при любом А О, выполняется строгое неравенство n{axi + (1- а)х2) an{xi) + (1- а)п{х2) V а Є (0,1). (2.2) Лемма 2.2.((34]) Если п(-) - строго квазивыпуклая норма, то равенство n(x2) = n(xi) + п(х\ - х2) выполняется для х\ ф 0Р тогда и только тогда, когда существует А 1 такое, что х2 = Хх\. Докажем еще несколько лемм, необходимых нам в дальнейшем. Лемма 2.3. Если А - строго выпуклое замкнутое множество, х-[,х2 - его граничные точки и К(х\,А) С К(х2,А), то х\ = х2. Доказательство. Обозначим через At = Xi + K(xltA)} і- 1,2. Очевидно, что, в силу выпуклости множества А, выполняется включение А С хг + К(х17 Л), г = 1,2. (2.3) Предположим, что #і #2- В силу строгой выпуклости множества А, имеем XQ = (хі + хг) гп(Л. Следовательно, учитывая (2.3), для і 2, имеем XQ Є іп Лг Поэтому точки луча X2 + G(XQ — X2),а О являются внутренними для Л2. А значит, в частности при о- = 2, получаем Отсюда, используя условие леммы, имеем xi + К(хиА) С int{x2 + K{x2,A)) + /фь Л) С С in (2 + К(х2, A)) + /Ґ(я2, Л) = int(x2 + іф2, Л)) или Л) С ЫЛ2. Следовательно, точка а » являясь граничной для множества Л2, не содержится в Лі и тем более, в силу (2.3) при і 1, множеству Л, что является противоречием. О Лемма 2.4. Пусть h(x) - выпуклая конечная на W функция, для точки XQ выполняется h(xo) = 0 и ОрЗА(х0). (2.4) Тогда для множества А = {х Є W : h(x) 0} имеет место формула K(x0iA) = K+{dh{xQ)). (2-5) Доказательство. Обозначим через 7лЫ = {9 Rp : ft fa.s) 0}, 7иЫ = {5Г: /t (x0,s) 0}. 1) Если д Є %{хо) т0 есть h (x0i9) 0J 10 из асимптотической фор мулы А(жо + од) = h(x0) + ah (xQ, д) + о(а, (/), где о(а,д)/а - 0 при a J. 0 и, по условию леммы, /і(жо) = 0, следует, что найдется ад 0 такое, что A(x0 + s) 0, VoE (Q,ag) и, следовательно яо + одЄ Д Va(0,%). (2.6) В соответствии с определением конуса допустимых наиранлений множества в точке, последнее означает, что д Є "((XQ,A). Тем самым мы доказали включение 1пЫсфо,Л). (2.7) 2) С другой стороны, если д Є (XQ,A), то найдется ад 0, для которого выполняется (2.6) или h{x0 + ag) 0, Vo(0,as). Учитывая, что /і(яо) = 0) отсюда вьпекаег h (x0,g) Нта-1(Л(аг0 + д) - h(x0)) 0. Тем самым мы показали, что фо,А)сЪ,пЫ- (2-8) 3) Покажем, что ТА W = 7І,ЛМ- (2-9) Ввиду очевидного включения 7л( о) С 71,/1(3)) нам достаточно показать, что произвольно выбранный вектор до, для которого A (:EQ,5O) = 0, является предельным для множества "{h{x{yj. Для этого обозначим череч 9k = 0-- Хк)9о - акЩ где ак 0 при к - со, ш = arg min М. vOh(xQ) - ближайшая к началу координат точка из dh(xo) - субдифференциала функции h(x) в точке XQ. Поскольку dh{x0) - выпуклый компакт, то, по теореме о проекции, эта точка существует и единственна. Используя формулу производной по направлению выпуклой функции через ее субдифференциал (см. [6,с.55]) имеем /фо,0ь)= max vtgk = max Vj (1 - ак)д0 - akv0 vCOh(X(j) vGoh{xn) (1 — Qffc) max v,go — ak min V,VQ . (2.10) vdh{x0) vCQh(x0) Отметим, что, в соответствии с выбором направления да, h {xQ,g0)= max v,g0 =0, (2.11) а, кроме того, (см. [5,с.309]) min v,vQ = v0,v0 - \\v0\\2. (2.12) vedhfao) Подставляя (2.11)-(2.12) в (2.10), получаем hr{xQ,gk) -ak\\v0\\2 0, (2.13) поскольку VQ ф Op, как это следует из (2.4). Выполнение неравенства (2.13) означает, что дк Є 7ft(#()) А так как да является пределом последовательности { &}, =1,2,., то мы тем самым доказали (2.9). 4) Из включений (2.7) и (2.8), равенства (2.9), учитывая К(хо, А) = 7(#{ъ А), получаем K(x0iA) = ihh{xo) Теперь осталось получить формулу (2.5): %Ы,А) = {д Є Rp : h (x0,g) 0} = {д Є Rp : max v,g 0} = vedh[zo) = {д Є Rp : v,g 0,V«e -Щя0)} = = {g eRp: v,g 0, V w Є -асЩ о), a 0} = = {г/ЄЙр: и,з 0,УиЄ -/((Щі0))} = D Следствие 2.1 Ьш тг(ж — XQ) = г, то K(x,Bn{xQ,r)) = -К+{дп{х - х0)). (2.14) Доказательство. Следует непосредственно из леммы 2.4, если взять в качестве h(xo) = п(х XQ) — г, Л = Вп(хц,г) и учесть, что, в силу формулы (2.1), 0р $. дп(х — XQ), так как х =f= XQ. П Следствие 2.2 Если п(х) г О, R 0, то К(х, Вп(0р, Г)) = K(-R, Вп{0Р) Я)). (2.15) Доказательство. Равенство (2.15) следует из (2.14) и равенства дп(ах) dn(x)j V а 0, которое следует из (2.1). П Лемма 2.5. Пусть п(-) - строго квазивыпуклая норма. Если для Яі 0, Я2 0 n(xi-x ) = Ru п(х2 - х ) = R2i (2.16) и для некоторого 8 0 справедливо включение Bn(xi,Ri)f)B(x ,5) С Bn{x2,R2), (2.17) то Х\ — Х2 R2 = R\ + п(жі - жг), г = жі + ЯГ П(Я;І - х2) Доказательство. В силу условий теоремы (2.16) и (2.17) выполняется К(х\ Вп{хи Пі)) С К(х\ Bn{x2t R2)). Это эквивалентно тому, что К{х - xh Вп(Ор, Яі)) С К(х - х2, Bn{0Pi R2)). Отсюда, используя следствие 2.2, получаем K{ p-R2, Вп{Ор, R2)) С К{х - х% Вп{Ор, Д2)). Теперь по лемме 2.3, поскольку Bn(0p,R2) - строго выпуклое множество, а (х — x\)R2JR\ и х — х2 его граничные точки, имеем —-—Я2 = х х2. Щ Выражая отсюда х , получаем х = х\ Н , 1 R2-Ri откуда, в силу (2.16), п(х\ хо) — Яг Ri-Следовательно, Х\ Х2 R2 Rl+Mxx-X2), X =Xi+Ry .. n[xi - х2) D Нам также будет необходима Лемма 2.6. Если п(-) - строго квазивыпуклая норма, то сферы Sn(x\,Ri) и Sn(x2, Ri + n(xi — 3)) имеют единственную общую точку У0 = Жі+Іі-;; г. п(жі - Х2) Доказательство. Если Ї/ Є Sn(x\, R{) f] Sn(x2, R\ + n(x\ — 372)), то п(яі-у) = Яі, п(х2 у) = Лі +n(a?i -2:2), (2.18) то есть, п{х2 — у) = п{х\ — у) + п(а;і — х2). По лемме 2,2, это означает, что х2 — у = А( і - у), где А 1. Выражая отсюда у и подставляя в (2.18), мы получаем выражение для единственной общей точки через точки а;!, и радиус Лі. 2. Определение 2.2((15]). Множество А С № называется г-сильно выпуклым, если оно представимо в виде пересечения евклидовых шаров радиуса г. Определение 2.3. Будем говорить, что норма п(-) является г-сильио квазивыпуклой, если ее единичный шар Вп(Ор, 1) = [х є W : п(х) 1} является r-сильно выпуклым множеством.
Замечание 2.2. Легко видно, что любое сильно выпуклое множество является и строго выпуклым. Примеры показывают, что обратное верно не всегда. Следовательно сильно квазивыпуклая норма всегда является строго квазивыпуклой, но не всегда строго квазивыпуклая норма будет одновременно и сильно квазивыпуклой. Соответствующий пример будет приведен в конце параграфа. Далее нам понадобится понятие сильно выпуклой оболочки множества и некоторые из ее свойств. Напомним их {[15]). Определение 2.4((15].) Пусть дано ограниченное множество А ш W, числа р 0 и г О такие, что В(0р, р) — Аф и г р. Сильно выпуклой оболочкой радиуса г (или, короче, г-сильно выпуклой оболочкой) мнооїсества А называется множество, получаемое при пересечении всех замкнутых евклидовых шаров радиуса г, которые содержат данное множество. Будем обозначать г-силыю выпуклую оболочку мнооїсества А через strrA.
Критерии решения задачи о внешней оценке
Функция R{x), как зафиксировано и 3, является выпуклой и конечной на W. Поэтому, как известно из выпуклого анализа (см., напр., [17, с.142]) для того, чтобы точка х являлась решением задачи (1.1), необходимо и достаточно, чтобы выполнялось соотношение ОрЄШж ). (5.1) Формула (2.1) субдифференциала нормы п(-) и формула (3.2) субдифференциала функции R(x), полученные Б.Н. Пшеничным, позволяют интерпретировать соотношение (5.1) и следующем виде Теорема БП2 (Б.Н. Пшеничный [17, с.163]). Для того, чтобы точка х била решением задачи (1.1) необходимо и достаточно, чтобы нашлись числа Xt 0, точки zt QR(% , D), точки уг Кр, г = 1,р-г 1 такие, что р+1 p-rl Ьм =0P1 ]Г)Л, = 1, i=i i=i х - zt1 v, - п(хщ - 2г), n (vt) = 1, г = 1,р + 1. При этом радиус минимального шара, содероісащего множество DQ = =Т п+ї совпадает с R(x )} а точка х является центром такого шара. Приведем еще один критерий решения, связывающий задачу (1.1) о внешней оценке с задачей о внутренней оценке нижнего лебегова множества функции R(x) шаром нормы п(-). Именно он будет использован далее в 6 для характеризации устойчивости задачи (1.1). Считаем далее R = min R(x). Теорема 5.1. Точка х является решением задачи (1.1) тогда и только тогда, когда для любого А R она является центром вло-оісенпого в множество GR(X) {х Є W : R(x) А} шара наибольшего радиуса, то есть решением задачи рц(\){х) = ттп{х - у) -J- max. (5.2) уєП(Л) xGR(\) где Q(X) = MP\GR(X), При этом радиус влооїсеииого шара есть Аі(А)0О = А-Я . Доказательство. Необходимость докажем в четыре этапа. Итак, пусть точка ее является решением задачи (1.1). 1) Покажем, что справедливо включение Bn{x ,X-R )cGR(X). (5.3) Действительно, для любого у Є D, очевидно, выполняется х 6 Вп(у, R ) Отсюда вытекает Вп(х\ А - Я ) С Вп{у, А), V у Є D. (5.4) А поскольку, как легко видно, GR(X) = {хєГ: тахф - у) А} = yeD = {я Є Кр : п(а; - у) А, V у Є D} = f Brcfe, А), (5.5) то из (5.4) следует (5.3). 2) Возьмем произвольную точку z Є Q V, ) = {у Є D : R = п{х - у)} (5.() и сопоставим ей точку X — R zx = x + -J- r(i - z). (5.7) n(z - z) Покажем, что zx Є № ,П(А)) = {у fi(A): /»п(Л)(ж ) = n( - ff)}, (5-8) то есть точка z\ принадлежит проекции ючки х на множество П(, в норме п(-). В самом деле, с одной стороны, из (5.6)-(5.7) имеем n(zx-z) = n{x -z) + X R =X, ( )) то есть точка z\ лежит на сфере Sn(z} А); zx Є Sn(z, А) = {у Є Шр : ф - у) = А}. (с j )) В то же время из (5.7) вытекает n(zx-x ) = X-W (5.11) и значит, в силу (5.3), ЛєСй(А). (5.12) Поскольку точка z, взятая из QR(x fD), содержится в D, то шар 5n(z, А), для которого сфера 5п(г, А) является граничной, в соответствии с (5.5), содержит GR(X). Поэтому из (5.10) и (5.12) следует, что z\ является граничной точкой множества GR(X)1 а следовательно и множества 12(A). Итак, шар Вп(х\Х — R) содержится к GR(X) (см.(5.3)) и касается своей граничной точкой (см. (5.11)) z\ множества П(А). Эго и означает справедливость (5.8). 3) Покажем, что справедливо включение K+{zx,GR(X)) э К(дп{х - zx))t (5.13) где точка z\ соответствует точке z t QR(x\ D) по формуле (5.7). Так как точка z Є D, то, в соответствии с (5.5), имеем включение GR(X)cBn{z,X). (5.10 А поскольку из (5.10) и (5.12) следует zA6G (A)pSn(z,A), то из (5.14) получаем K(zhGR(X))cK(zx,Bn(z,X)). Тогда для сопряженных конусов выполняется обратное включение K+(zx,Bn(z,\)) С K+(zx,GR(\)). (5.15) Учитывая (5.9), из следствия 2.1 вытекает K{zx,Bn(z,\)) = K+{dn{z-zx)). (5.16) Из (5.7) имеем Z\-Z = (l + —г- г){Х -Z), Z\ X =-Г- АХ -Z), п[хч - z) п[х - Z) то есть X — Z\ = /5(2 - Z\), где _ А — Н ,, А — К . _i к n(:r -2)v n(a: -z) Поэтому из формулы субдифференциала нормы (2.1) получаем дп{х - z\) dn(z — z\). (5-17/ Следует также отметить, что Oj, $ dn[z — гд) и значит (см., напр., [П с.314-316]) ii:++(an(z - zx)) = іфф - А)). (s.is) Теперь из (5.15)-(5.18) следует (5.13). 4) Напомним, что поскольку точку х считаем решением задачи (1.Г то, в соответствии с (5.1) и формулой (3.2), выполняется соотношение Ор Є со{дп{х -z):ze QR{x\ D)}. (5.191 Как нижнее лебегово множество выпуклой функции /?(), МН0ЖЄСТ1ІО (?Л(А) является выпуклым. Тогда, по теореме Д2, функция рщ){х) является вогнутой на GR(X). Поэтому в соответствии с известным фактом выпуклого анализа (см.[6]) критерием того, что некоторая ючк %Q intGR(X) является решением задачи (5.2), является соотношение 0;,е п«{А)Ы- (5-20) Следовательно, для того, чтобы доказать, что точка х является решением задачи (5.2) нам, учитывая формулу супердифференциала функции расстояния (4.3), надо показать справедливость соотношения 0Р Є со{дп(х - у) f] К+(у, GR(X)) (у Є Qp(x\ ЩХ)). (5.21) В самом деле, из (5.13) получаем dn{x -zx)f)K+(zx,Gn(X))D D дп{х - zx) f] К{дп{х - zx)) = дп(х - zx). (5.22) В соответствии с (5.7), х — z\ = у(х — z)} где Я -А п[х - Z) Поэтому из формулы субдифференциала нормы (2.1) вытекает дп{х -zx) = -dn{x -z). (5.23) Учитывая (5.23) и используй (5.19) и (5.22), имеем 0р со{дп{х -zx): гЄ QR(x% D)} = = со{дп{х - zx) П K+(zXl GR(X) : z Є Qa(x\ )}. (5.24)
Здесь, как было показано в п.2), все точки zx соответствующие точкам z QR(x\D) содержатся в Qp(x }Q(X)). Поэтому из (5.24) следуег (5.21). Необходимость доказана, причем, как это следует из п.2) и (5.7) радиус вложенного шара рп(А)(я ) — Х- R . Достаточность. Пусть точка х является центром шара максимального радиуса, вложенного в GR(X). Радиус этого шара, как было показано в процессе доказательства необходимости, ранен А — Л . Следовательно имеем включение Bn{x\X-R )cGR{X). (5.25) Поскольку множество GR(X) представимо в виде (5.5), то из (5.25) следует Вп{х\ А - Я ) С Вп(у, А), V у Є D. G3 Отсюда получаем х Є Вп(у, R ) или п(х у) R" для всех точок у D. Это и означает, что R(x ) = тахп(х - у) R\ то есть точка х явлется решением задачи (1.1). Теорема доказана. 2. Непосредственно из теоремы 5.1, шшду доказанной эквивалентности задач (1.1) и (5.2) получаем критерий единственности. Следствие 5.1. Для того, чтобы задача (1,1) имела единственное решение необходимо и достаточно, чтобы при некотором значепиги А R задача (5.2) имела единственное решение. Приведем следующее простое достаточное условие единственности решения задачи (1.1). Теорема 5.2. Еслип( ) является строго квазивыпуклой нормой, то решение задачи (1.1) единственно. Доказательство. Действительно, предположим, что решение задачи (1.1) неединственно и R(xi) = R(x2) = mh\R(x), (5.2G) ПОСКОЛЬКУ ДЛЯ ТОЧеК Х\ И Х2 уСЛОВИе б) ТСОремЫ Д1 ВЫПОЛНеНО, 10, учитывая (5.26), для а Є (0,1) получаем противоречие R(axi + (1- aba) aR(xA + (1- a)R(x2) min R(x). Теорема доказана. О Замечание 5.1. Приведенный далее пример 5.1 говорит о том, что строгая квазивыпуклость нормы « не является необходимым условием единственности решения задачи (1.1). Замечание 5.2. Легко представить пример, который показывает, что строгая выпуклость оцениваелюго множества D, при отсутствии строгой квазивыпуклости иормып( ), не гарантирует единственность решения задачи. В ситуации, когда мы имеем некоторую чочку х\ являющуюся решением задачи (1.1) и имеем возможность найти 0R(x ), можно іакже использовать следующий факт. Теорема 5.3. Если точка х такова, что для некоторого 5 О B{0p,5)cdR(x ), (5.27) то она является единственным решением ладани (1.1), причем для любой точки х Ш выполняется R(x) R{x ) + 5\\x-x \\. (5.28) Доказательство. Используя непосредственное определение субдифференциала, можем записать Щх) — Шх ) max v, х - х . 1 veQBix ) (5.29) Так как, ввиду (5.27), точка х — х еМИ, х — X то из (5.29) следует (5.27). Проиллюстрируем на примере утверждения теорем 5.2 и 5.3. Пример 5.1.Пусть размерность пространства р = 3, п(х) — тах{а; , [э ,а } - чебышсвская норма, D = {хі,Х2,хз}, где х, = (-1, -1,1), х2 = (1,1,1), жз = (1, -1, -1). Рассмотрим точку х = (0,0,0) = 03. Поскольку полярной к норме п(-) в данном случае является п (х) X 0) + X (2) + X (3) то, используя формулу (2.1), можем убедиться в том, что Щх" - х,) = со{(1,0,0), (0,1,0), (0,0, -1)}, сЫ(х -я2) = со{(-1,0,0),(0,-1,0), (0,0,-1)}, дп{х х3) = со{(-1,0,0), (0,1,0), (0,0,1)}. Нетрудно также проверить, что QR{x", D) = D и тогда в соответг гвии с формулой (3.2) х ) = со{дп(х -xt): г = 1,2,3} = = {х Є R : а; 0) + а; (2J + X (3) !} Так как 5(0з, -4) С Й(# ), то, по теореме 5.3, точка х — Оз является единственным решением задачи. Интересно отмстить, что х $ coD, -іо есть известное свойство центра описанного шара для евклидовой нормы в случае с неевклидовой нормой выполняется не всегда. Кроме того, чебышевская норма не является строго квазивыпуклой. Поэтому данный пример говорит о том, что строгая квазивыпуклость нормы не является необходимым условием единственности решения.
Свойства вспомогательной функции RQ(X)
Ранее в 3 нами использовалась вспомогательная функция RQ(X). Приведем здесь некоторые ее свойства для случая евклидовой нормы. И іак, для пары точек х\ ф x-i понимаем под RQ(X) = тах\\х-у\\, yeDa где Д, = В{хи R{xi)) ПВ(х2, RH). Лемма 8.1. Для мнооїсестеа Q ix, Д ) = {у Є D0 : R0(x) = \\x - y} при любом а Є (0,1) справедлива формула QIh{ax1 + {l-a)x2,DQ) = {у Є Г : Цап - у\\ = R(xi), \\х2 - у\\ = R(x2)}. (8.1) Доказательство. Евклидова норма является строго квазивыпуклой. Следовательно, по лемме 3.2, справедливо включение Qft(aa:i + (l-ff)s2,A))cQo = di{yeW: \\Х1 - у\\ = Rfa), \\х2 у\\ = R(x2)} (8.2) Возьмем произвольную точку у Є Qo- Для нее и точки xQ = ах\ + (1 - сх)х2 выполняется \\у - ха\\2 = а(у - хх) + (1 - а)(у - х2)\\2 = а2Я2(яі)+ +(1 - a)2R2(x2) + 2a(l - а) у - хи у - х2 . (8.3) С другой стороны имеем XI х2\\2 = \\xi -у + у- х2\\2 = R2{xy) + R2(x2) + 2 Xi - у, у - x2 . (8.4) Выражая x{ - у, у - х2 из (8.4) и подставляя в (8.3) получаем ? - xQf = a2R2( i) + (1- «)2Л2Ы+ +а(1 - а)(Д2(я:і) + Я2(о:2) - я;і - я22).
Отсюда, учитывая, что у = [z = 1, следует равенство R — р, противоречащее условию леммы. Таким образом, данный случай значений Ао, Ai и А2 невозможен. 2. Случай, когда Ао = 0 и при этом Aj или Аг обращаются в нуль, ввиду того, что z ф Ор и у ф 0, ведег из (9.11) к тому, что все множители Лагранжа равны нулю. 3. Случай Ао = 1, Ai = А2 = 0 также ведег, ввиду (9.11), к противоречию. 4. Пусть теперь Асі = 1, AJ = О, A2 Ф 0. Тогда из (9.11) получаем Отсюда, поскольку \\z\\ = \д\ = 1 следует, что множитель А2 может принимать значения А2 = 0,5 и А2 = -0,5. 4а) Если Аг — 0,5, то z = — д и целенаи функция ,# = —], то есть, вийду z = у = 1, принимает самое минимальное значение из возможных. Однако, для того, чтобы данное значение действикзлыю было решением задачи (9.8)-(9.9) надо, чтобы выполнялось ограничение (9.9). А это значит, что в этом случае z,y =- y,g (9.18) Но поскольку, в соответствии с обозначениями, у,д 5, то из (9.18) следует 5 — . Это означает, что значение z — д дает решение задачи (9.8)-(9.9) на минимум при выполнении условия 5 —, только для 5 = — . Именно при этом значении -,/(i- )(i- i. Ввиду (9.4) и обозначения для z, мы тем самым доказали справедливость оценки (9.2) при 6 — . 46) Если же А2 = —0,5, то z = д и целевая функция z}g = 1, гю есть принимает самое максимальное значение из возможных. При зі ом ограничение (9.9) приводит нас к неравенству zfy = y,g =6 -. Однако в соответствии с условием леммы для оценки сверху надо считать 6 . Поэтому значение z д дает решение задачи (9.8)-(9.9) на максимум при выполнении условия 5 f{ только при = д. Именно для этого значения Тем самым мы доказали справедливость оценки (9.3) при значении 5. Пусть Ао = ІДі ф 0,Л2 = 0. Тогда из (9.11)-(9.12) имеем М «,$ =. (9.2( Поскольку \\у\\ — \\д\\ — 1, то из (9.19) следует Ах = ±1. 5а) Если Лі = 1, то у = —д. При этом 6 = у,д = —1, а, ввид\ (9.20), значение целевой функции z,g = - . Именно это значение принимает правая часть в неравенстве (9.2) при 5 — —1. 56) Если Ai = -1, то у д. При этом 5 = ,# = 1, а значение целевой функции z,g = . Именно эго значение принимает правая часть неравенства (9.3) при 5 = 1. 6. Осталось рассмотреть случай, Ао = 1, Аі ф 0, \ і ф 0. Итак, из (9.11)-(9.12) имеем д + Aiy + 2A2z - 0Р) (9.21) ,У - = 0. (9.2Г Выразим z из (9.21) г = -2 Ь + А1Й- (-23) Умножая левую и правую части (9.23) сначала на z, потом на у и заісм на д, учитывая (9.13), (9.22) и 5 — у,д , соответственно получаем 1 = -2 ( г 0 +Аіл) ( 24) і-ІР + АО, (9-25) Z 5 ="2 (1 + Al5) (9 26) Из (9.24)-(9.25) имеем ,P = - + Ai(--). (9.27) Приравняем правые части (9.26)и (9.27) и подставим А2, выраженное из (9.25) p(l + X,5) _5R Ял Д + ЛО р +Мр Rj Это приводит нас к квадратному уравнению относительно Л] А2(Я2 - р2) + 2Xl(R2 - р2)5 + R42 - р2 = 0. Запишем значения корней ,1,2 _ - (Д2 - р2) ± у/Р(& - р2)2 - (Да - рЗ)(ДФ - р2) _ r J{R2 p2){52R2 - 82pl - R42 + p2) = 5± w = Подстановка этих значений в (9.27) даст SR ( ., h-p\ (R p\ z s =T+{-5±p\}w j{j-R) = = ± (І- )(Я»-Л, то есть соответственно правые части в неравенствах (9,2) и (9.3), кою-рые дают максимальное и минимальное значение для целевой функции в задаче (9.8)-(9.9), а значит, ввиду (9.4), и для р п(я, #) при выполнении условий леммы на выбор направления д. Лемма доказана полностью .
Ввиду эквивалентности задач (7.1) и (7.2) для нас большой интерес представляет функция Ф(х) = R(x) — рц(х). Поскольку функция R(x) является выпуклой на всем пространстве W, а функция рп(х), ввиду выпуклости множества D, вогнутой, по теореме ДЗ, на множестве D, то функция Ф(х) является выпуклой на D. Кроме того, так как функция R(x), как выпуклая и конечная функция, дифференцируема по направлениям в любой точке х Є Шр, а функция рп(ж), являясь вогнутой и конечной на D, дифференцируема по направлениям в любой точке х D, то и функция Ф(х) дифференцируема по любому направлению д Є ШУ всюду на множестпе D.
Отметим, что поскольку евклидова норма является непрерывно дифференцируемой всюду на Rp, за исключением точки х — 0Р, то ее субдифференциал в любой точке х ф 0р состоит из единствен но [ О элемента, причем ІИІ Используя это обстоятельство, формулу производной по направлениям выпуклой функции R{x), учитывая формулу ее субдифференциала (3.2), можно записать в виде R\x,g)= max v,g = «ЄЙЕ(г) = max f yu,g , VgRp. (10.3) Лемма 10.2. Если точка XQ является решением задачи (7.1) и при этом intD ф 0, то Доказательство. Точка х$, являясь центром шара наилучшего приближения для множества D, является, в соответствии с теоремой НС2, одновременно точкой минимума функции Ф(х) на D, причем XQ Є intD.
Свойства целевой функции Ф(х)
Задачи по оценке множеств находят обширные приложения в естествознании, в том числе и в самой математике. Известны многочисленные работы, связанные с внешними и внутренними эллипсоидальными оценками множеств и многозначных отображений (напр., работы Н.З. Шора [24], Ф.Л. Черноусько [23], А.Б. Куржанского и др.). Можно также указать на работы по внешним и внутренним оценкам заданных множеств ориентированными параллелепипедами и их приложениями (см., напр., [1]). Е.С, Половинкиным в [15] рассматривались внутренние и внешние многогранные аппроксимации выпуклых множеств.
Наряду с эллипсоидом и многогранником к числу наиболее простых множеств, как в геометрическом смысле, так и по числу задающих параметров, относится шар любой нормы. Задача о внешней оценке компакта шаром произвольной нормы, которая заключается в построении шара используемой нормы с наименьшим радиусом, содержащего оцениваемый компакт, рассматривались Б.Н. Пшеничным в [17]. Задача о наилучшем приближении (равномерной оценке) в метрике Хаусдорфа выпуклого компакта евклидовым шаром была поставлена и изучалась в работе М.С. Никольского и Д.Б. Силина [12]. Основная цель диссертации- исследование устойчивости решения этих двух задач относительно погрешности задания оцениваемого (приближаемого) компакта. 2. Приведем математическую формализацию задачи о внешней оценке, которую также называют задачей об описанном шаре или задачей о чебышсвском центре множества. Пусть D заданный компакт из конечномерного действительною пространства W, а функция п(х) удовлетворяет на W аксиомам нормы. Тогда задачу о внешней оценке компакта D шаром нормы п(-) можно записать в виде R(x) = maxnfa; — у) - min. (0.1)
Значение функции R(x) выражает радиус наименьшего шара с центром в точке х, содержащего в себе компакт D. Точка % , доставляющая минимальное значение функции R{x), является центром искомого описанного шара, аЛ = R(x ) - его радиус.
Известно([2]), что для случая, когда п(х) — \\х\\ - евклидова норма, решение задачи (0.1) единственно. При этом центр описанного шара принадлежит выпуклой оболочке точек, одновременно принадлежащих границе компакта D и поверхности описанного шара (то есть его граничной сферы). Верно и обратное, а именно, шар, содержащий компакт и обладающий указанными выше точками множества D на его границе, есть описанный шар. Следовательно центр описанного шара всегда принадлежит выпуклой оболочке компакта D.
Диаметр компакта D d — max Ця; — у\] x,yD и радиус описанного евклидова шара R связаны неравенством, полученным Г. Юнгом (см. [11, с.73]). -\J2{p+l) Как показывают примеры, если п(х) не является евклидовой нормой, А то задача (0.1) может иметь неединственное решение, а центр описанного шара может не принадлежать выпуклой оболочке компакта D. В практических ситуациях информация об оцениваемом компакте D может носить приближенный характер, то есть вместо компакта D нам может быть известен некоторый компакт D такой, что h(D,D) e. Здесь є 0 - известная погрешность задания компакта D, а k(A, В) = max{sup inf п(а — Ь), sup inf п(а — Ь)} - расстояние Хаусдорфа между множествами А и В в норме п(-). И, таким образом, о решении задачи (0.1) мы можем судить по решению приближенной задачи RJx) = maxn(x — у) —l? min. (0.2) Получение условия устойчивости и оценка характера устойчивости задачи (0.1) ошосительио оптимального значения целевой функции Щх) и центра описанного шара - один из вопросов, решаемых в диссертации.
Любая норма, как следует из ее аксиом, является выпуклой функцией на всем пространстве. Поэтому, легко видегь, и функция R(x), являющаяся результатом операции максимума от выпуклых функций, также выпукла на W. Следовательно задача (0.1) является задачей выпуклого программирования. Известно (см. [10, с.42]), что вопрос о характериза-ции устойчивости задачи выпуклого программирования легко решается, если целевая функция является сильно выпуклой ([3, с.181]). Однако ни при каких условиях на компакт D и используемую норму п(-) функция R(x) не является сильно выпуклой не только на IRP, но и любом выпуклом множестве с непустой внутренностью. Именно это обстоятельство затрудняет исследование устойчивости задачи (0.1).
Приведем математическую формализацию второй задачи, исследуемой на устойчивость решения. Пусть D непустой выпуклый компакт из W, h(A,B)- расстояние Ха-усдорфа между множествами Аи В в евклидовой норме, В(х,г) = {у =№:\\х-у\\ г} - евклидов шар с центром в точке х и радиусом г. Тогда задачу о наилучшем приближении о і ого выпуклого компакта D евклидовыми шарами в метрике Хаусдорфа можно записать в виде h(D,B(x,r))- min . (0.3)
Задача (0.3) впервые была поставлена и рассматривалась в работе М.С.Никольского и Д.В.Силина [12]. В пси доказаны существование и единственность решения, получено необходимое условие решения. Отметим, что задача (0.3) рассматривалась авторами [12] в рамках более общей задачи о наилучшем приближении элемента пространства непустых выпуклых компактов с метрикой Хаусдорфа элементами его подпространства, которое представляет собой всевозможные линейные комбинации фиксированного набора элементов данного пространства.
