О подходе к приближенному решению задачи наилучшего приближения выпуклого тела шаром фиксированного радиуса

7. Sierpinski W. General topology. Toronto, Univ. Toronto Press, 1952, 304 p.

8. Gross W. Eine ganze Funktion, für die jede Komplexe Zahl Konvergenzwert ist. Math. Ann., 1918, vol. 79, iss. 1-2, pp. 201-208.

9. Heins M. The set of asymptotic values of an entire function. Proceedings of the Scandinavian Math. Congress, Lund, 1953, 1954, pp. 56-60.

10. Ganenkova E. G., Starkov V. V. Asymptotic values of functions, analytic in planar domains. Issues of Analysis, 2013, vol. 2(20), no. 1, pp. 38-42.

11. Ganenkova E. G., Starkov V. V. Analytic in planar domains functions with preassigned asymptotic set. J. Appl. Anal., 2014, vol. 20, iss. 1, pp. 7-14. DOI: 10.1515/jaa2014-0002.

УДК 519.853

12. Liczberski P., Starkov V. V. On locally biholomorhic mappings from multi-connected onto simply connected domains. Ann. Polon. Math., 2005, vol. 85, no. 2, pp. 135-143.

13. Goluzin G. M. Geometricheskaja teorija funkcij kompleksnogo peremennogo [Geometric theory of functions of complex variables]. Moscow, Nauka, 1966, 628 p.

14. Pommerenke Ch. Boundary behaviour of conformal maps. Berlin, Heidelberg, Springer-Verlag, 1992, 301 p.

15. Ahlfors L. V. Untersuchungen zur Theorie der konformen Abbildung und der ganzen Funktionen. Acta Soc. Sci. Fenn. Nova Series A, 1930, vol. 1, no. 9, pp. 1-40.

16. Bagemihl F. Curvilinear cluster sets of arbitrary functions. Proc. Natl. Acad. Sci. USA, 1955, vol. 41, no. 6, pp. 379-382.

О ПОДХОДЕ К ПРИБЛИЖЕННОМУ РЕШЕНИЮ ЗАДАЧИ НАИЛУЧШЕГО ПРИБЛИЖЕНИЯ ВЫПУКЛОГО ТЕЛА ШАРОМ ФИКСИРОВАННОГО РАДИУСА

С. И. Дудов1, М. А. Осипцев2

1 Доктор физико-математических наук, заведующий кафедрой математической экономики, Саратовский государственный университет им. Н. Г. Чернышевского, DudovSI@info.sgu.ru

2Старший преподаватель кафедры математического анализа, Саратовский государственный университет им. Н. Г. Чернышевского, Osipcevm@gmail.com

Рассматривается конечномерная задача о наилучшем приближении в метрике Хаусдорфа выпуклого тела шаром произвольной нормы с фиксированным радиусом. Показано, что в случае, когда приближаемое тело и шар нормы являются многогранниками, задача сводится к задаче линейного программирования. Это позволяет предложить получение приближённого решения задачи через предварительную аппроксимацию приближаемого компакта и единичного шара нормы многогранниками.

Ключевые слова: выпуклое тело, метрика Хаусдорфа, функция расстояния, аппроксимация, субдифференциал.

1. Пусть D — заданное выпуклое тело из конечномерного действительного пространства , а n(x) — некоторая норма на Рассматривается задача

ф

Здесь Bn(x, r) = {y <G : n(x — y) ^ r} — шар радиуса r с центром в точке х,

h

расстояние Хаусдорфа между множествами A и B, индуцированное нормой n(-).

Впервые задача о приближении выпуклого компакта евклидовым шаром в метрике Хаусдорфа, причём произвольного радиуса, т.е. когда функция Ф(х,г) минимизируется по (x,r) <G х R+, рассматривалась в [1]. Для случая произвольной нормы эта задача исследовалась в работе [2].

В работе [3] показано, что задача (1) своими решениями для значений радиуса r из определённых диапазонов, выражает решения задач об описанном и вписанном шарах для D и задачи наилучшего приближения шаром произвольного радиуса. Авторам известны и другие задачи по шаровым оценкам выпуклого компакта (например, задача об асферичности [4]), на которое распространяется это универсальное свойство задачи (1).

Важное значение имеет полученная в [2] формула, выражающая расстояние Хаусдорфа (2) между выпуклым компактом D и шаром Bn(x,r):

h

Здесь функция Я(х) выражает расстояние в норме п(-) от точки х до самой удалённой от неё точки из Б, т. е.

Д(х) = тах п(х — у), уев

а функция Р(х) определяется формулой

Р (х) = рв (х) — рп (х),

где О = Rp \ D, рА(x) = minn(x — y) — расстояние от точки x до множества A в норме n(-).

y&A

Известно [5-7], что функции R(x) и pD(x) выпуклы на Rp, а р^(x) вогнута на D. Функция P(x), введённая в [8], также является выпуклой на Rp. Эти факты позволяют считать задачу (1) задачей выпуклого программирования и применять для её численного решения широкий спектр методов оптимизации, например [6,9], используя формулы субдифференциалов функций R(x) и P(x) (см., например, [2]).

Цель данной работы — показать, что в случае, когда выпуклое тело D и шар нормы n(-) являются многогранниками, задача (1) сводится к задаче линейного программирования. Этот факт может быть положен в основу подхода к получению приближённого решения задачи (1) через предварительную аппроксимацию компакта D и единичного шара нормы n(-) многогранниками. Отметим, что данный приём уже применялся для других задач по шаровым оценкам выпуклого компакта, например, [4,10].

В работе будут использованы следующие обозначения:

A, int A, co A — замыкание, внутренность, выпуклая оболочка множества A;

(x, y) — скалярное произведение элементов x и у;

K(x, A) — конус возможных направлений множества A в точке x;

K + — сопряжённый конус к конусу K;

K(A) — коническая оболочка множества A;

df (x) — субдифференциал выпуклой функции в точке x;

n*(x) — полярная норма по отношению к норме n(-); 0p = (0,0,..., 0) e Rp, A + B = (a + b : a e A, b e B}.

2. Если шар нормы n(-) является многогранником, норма представима в виде

n

i=1,m

При этом вектора (±Bi : i = 1,m} — это нормали к граням многогранников, являющихся шарами. Естественно считать (±Bi : i = 1,m} угловыми точками множества M = co (±Bi : i = 1,m} и 0p e int M. Очевидно, полярная норма n*(v) = max (v,x) является функцией Минковского множества M.

Для нормы (4) легко получается представление функции R(x) в виде максимума от аффинных функций:

R

i=1,m

где bil = min(Bi, y), bi2 = max(Bi, y).

yeD yeD

Пусть также выпуклое тело D является многогранником, заданным в виде

D =

где Aj e Rp, aj e R. Предполагается, что 0p e intco(Aj : j = 1, 1}, а также без потери общности n*(Aj) = 1, j = 1,1. Очевидно, для точки x e D справедливо

pn

j=i,i j

где oj = (y e Rp : (Aj, y) — aj = 0}, j = 1, 1, — гиперплоскости, образующие грани многогранника D. Известно, что

р

P-j

Поэтому из (6)-(8), учитывая и*(Aj) = 1, получаем:

Pn

j=i,i

3. Теперь, как и для функции R(x) (см. (5)), получим представление функции P(ж) в виде максимума от аффинных функций. Обозначим G(a) = {ж е Rp : pD(ж) ^ а}. Нетрудно доказать, что справедлива

Лемма 1. Если а ^ 0, то

G

Поскольку множества D и Eu(0p, а) являются многогранниками, то из леммы 1 вытекает, что и множество £(а) также является многогранником. Предположим, что нам известно его представление в виде

ОД = {y е Rp :

где Cj е Rp, dj (а) е R, u* (Cj) = 1 и все гиперплоскости

{y е Rp : (Cj ,y) = dj (а), j =^}

являются опорными к 0(а).

Замечание 1. Нетрудно видеть, что набор нормалей {Cj : j = 1,k} к граням многогранника £(а) можно считать инвариантными относительно значений а > 0. Как следует из (4), (6) и (10), в этот набор входят {Aj : j = 1,1} и {Ei : i = 1,m}, но при этом, как показывают простые примеры, могут содержаться и другие элементы. Вопрос практического получения набора {Cj : j = 1, k} обсудим в §4.

Лемма 2. Для точек ж / D справедлива формула

PD

j=l,k

где Cj = max(Cj, y).

yeD

Доказательство. Гиперплоскости

П = {y е Rp : (Cj, y) = Cj}, j =1Tfe являются опорными для тела D, причём

D С j = {y е Rp : (Cj, y) ^ Cj}, j = 1"k. Поэтому имеют место неравенства

PD

Поскольку n*(Cj) = 1, то, учитывая формулу (8) расстояния от точки до гиперплоскости, получаем:

Pn+

Из (13) и (14) следует

PD

j=l,k

Точка ж / D является граничной для множества £(а) при а = pd(ж), а значит, ввиду представления £(а) в виде (11),

J(ж) = {j е [1 : k] : (Cj, ж) = dj (а)} = 0. Покажем, что для произвольного индекса j0 е J(ж) выполняется

PD

Предположим противное, т. е. учитывая (13),

PD

Пусть точка уо принадлежит проекции точки x на гиперплоскость nj0:

Гиперплоскость nj0 является опорной к D, а гиперплоскость {у е : (Cj0, ) = dj0(а)}, содержащая точку x, является опорной к G(a). Поэтому из (10), (11) следует D с intG(a), а следовательно,

j0 0

Пусть точка z е nj0 P| D. Рассмотрим точку

z* = z + PD

n

Поскольку точки z и уо содержатся в nj0, то (Cj0, z) = (Cj0, уо). Учитывая также (Cj0, x) = dj0(а), из (17)-(21) получаем:

Это противоречит тому, что z* е D + Bn(0p, а) ввиду (10), (11). Тем самым мы доказали справедливость равенства (16). А тогда ввиду (20) имеем:

PD

Из (15) и (22) получаем (12). Лемма доказана.

Теорема 1. Для любого x е справедлива формула

P

j = 1,k

где {Cj j = 1, k} — нормали к граням многогранника £(а) в представлении (11), причём n* (Cj) = 1, а Cj = max(Cj, у).

yeD

Доказательство. Гиперплоскости nj = {у е : (Cj, у) = Cj}, j = 1,k, являются опорными к D. Поэтому расстояние от точки x е D до любой из них не меньше чем до множества О = \ D. Таким образом, имеем:

Po

j=1,k j=1,k

Как указывалось в замечании 1, набор {Aj : j = 1,1} входит в набор нормалей {Cj : j = 1,k}. Поэтому и опорные гиперплоскости ^j = {у е : (Aj, у) = aj}, j = 1,1 к многограннику D (см. (6)) входят в набор {nj : j = 1, k}. А тогда из (9) и (24) следует

Pn

j=1,k

Теперь из (12) и (25) для функции P(x) = pD(x) —p^(x) получаем формулу (23). Теорема доказана.

4. Рассмотрим вопрос практического отыскания набора нормалей {Cj : j = 1,k} через заданные наборы нормалей {Aj : j = 1,1} в (6) и {Bj : j = 1,m} в (4).

Известна [7] формула субдифференциала функции pD(x) для точки x / D:

dpD

где z — любая точка из Qp(x, D) = {у е D : n(x — у) = pD(x)}. Исходя из задания тела D в виде (6), нетрудно получить формулу [6, гл. 2, § 6]

—K +

Здесь I(г) = е [1 :1] : (А, г) = }. Известна также формула субдифференциала нормы [5]:

|(vG Rp : n*(v) ^ 1}, если x = 0p,

dn(x) = <

(vG Rp : n*(v) = 1, (v, x) = n(x)}, если x = 0p.

Из формы (4) представления нормы n(-) вытекает, что многогранник M = co (±B^ : i = 1,m} является единичным шаром полярной нормы, т.е. M = (v G : n*(v) ^ 1}. Поэтому в силу (28) возможными значениями для dn(x) при x = 0p являются вершины и грани многогранника M размерности от 1 до р. Таким образом, пересечение многогранника dn(x — z) с многогранным конусом (27) также является многогранником.

С другой стороны, с соответствии с субдифференциальным исчислением (см. например, [6, гл. 1, §5]) из (12) следует

dpD

где Jp(x) = (j G [1 : k] : pD(x) = (Cj, x) — Cj}. Это означает, что вектора (Cj : j = 1,k} является вершинами для многогранников dpD(x) в различных точках x / D. Таким образом, сравнение (26) и (29) говорит о том, что для отыскания набора нормалей (Cj : j = 1,k} достаточно найти вершины многогранников вида dn(x — z) Р|K(co(Aj : j G I(z)}), которых в силу конечности наборов (Aj : j = 1,1} и (Bj : j = 1,m} также конечное число.

5. Формулы (3), (5) и (23) позволяют записать задачу (1) в виде

0

j=Tk 1 2 \ / \ j / J J x£Rp

i=1,m

где bi1 = min(Bi, y), = max(B*, y), Cj = max(Cj, y). 1 yeD 2 yeD yeD J

Известным приёмом (см., например, [11]) это задача сводится к задаче линейного программирова-Теорема 2. Задача (30) эквивалентна задаче

z ^ min

^

bi2 — (B^, x) — r ^ z, i = 1, m, (Cj, x) — Cj + r ^ z, j = 1, k.

При этом, если х* — одно из решений задачи (30), то х* = (х*, г*) е где г* = ф(х*, г), одно

из решений (31). И наоборот, если х* = (х*, г*) — одно из решений задачи (31), то х* — одно из решений задачи (30), а г* = ф(х*, г) — оптимальное значение целевой функции ф(х,г).

В итоге мы можем предложить следующий подход к получению приближённого решения задачи (1). Следует аппроксимировать выпуклое тело многогранником, представив его в виде (6), а также аппроксимировать единичный шар нормы п(-), представив его в виде Вп(0р, 1) = (х е :

(±В, х) ^ М = 17т}.

Отметим, наличие широкого спектра методов полиэдральной аппроксимации выпуклых тел (см. например, обзор [12]). После этого остаётся решить задачу линейного программирования вида (31). Конечно, при этом возникает вопрос об устойчивости решения задачи (1) и его чувствительности к погрешности приближения тела Б и единичного шара нормы многогранниками.

Работа выполнена при финансовой поддержке РФФИ (проекты № 13-01-00238, 13-01-00175).

Библиографический список

1. Никольский M. C., Силин Д. Б. О наилучшем приближении выпуклого компакта элементами аддиала // Тр. МИАН. 1995. Т. 211. С. 338-354.

2. Дудов C. И., Златорунская И. В. Равномерная оценка выпуклого компакта шаром произвольной нормы // Мат. сб. 2000. Т. 191, № 10. С. 13-38. 001: 10.4213/зш513.

3. Дудов C. И. Взаимосвязь некоторых задач по оценке выпуклого компакта шаром // Мат. сб. 2007. Т. 198, № 1. С. 43-58. 001: 10.4213Дш1479.

4. Дудов C. И., Мещерякова Е. А. О методе приближённого решения задачи об асферичности выпуклого тела // Журн. вычисл. мат. и мат. физ. 2013. Т. 53, № 10. С. 1668-1678. 001: 10.7868/Б0044466913100050.

5. Пшеничный Б. Н. Выпуклый анализ и экстремальные задачи. М. : Наука, 1980.

6. Демьянов В. Ф., Васильев Л. В. Недифференцируе-мая оптимизация. М. : Наука, 1981.

7. Дудов C. И. Субдифференцируемость и супердиффе-ренцируемость функции расстояния // Мат. заметки. 1997. Т. 64, № 4. C. 530-542. DOI: 10.4213/mzm1532.

8. Hiriart-Urruty J. B. Tangent cones, generalized gradients and mathematical programming in Banach spaces // Math. Oper. Research. 1979. Vol. 4, № 1. P. 79-97.

9. Васильев Ф. П. Методы оптимизации. М. : МЦН-МО, 2011.

10. Dudov S. I., Zlatorunskaya I. V. Best approximation of compact set by a ball in an arbitrary norm // Adv. Math. Res. 2003. Vol. 2. P. 81-114.

11. Зуховицкий С. И., Авдеева Л. И. Линейное и выпуклое программирование. М. : Наука, 1964.

12. Bronstein E. M. Approximation of convex sets by polytopes // J. of Math. Sciences. 2008. Vol. 153, № 6. P. 727-762. DOI: 10.1007/s10958-008-9144-x.

On an Approach to Approximate Solving of the Problem for the Best Approximation for Compact Body by a Ball of Fixed Radius

S. I. Dudov, M. A. Osipcev

Saratov State University, 83, Astrakhanskaya str., Saratov, 410012, Russia, Dudov@info.sgu.ru, Osipcevm@gmail.com

In this paper, we consider the problem of the best approximation of a compact body by a fixed radius ball with respect to an arbitrary norm in the Hausdorff metric. This problem is reduced to a linear programming problem in the case, when compact body and ball of the norm are polytops.

Key words: convex compact body, Hausdorff metric, function of distance, approximation, subdifferential.

This work was supported by the Russian Foundation for Basic Research (projects no. 13-01-00238, 13-01-00175).

References

1. Nilol'skii M. S., Silin D. B. On the best approximation of a convex compact set by elements of addial. Proc. Steklov Inst. Math., 1995, vol. 211, pp. 306-321.

2. Dudov S. I., Zlatorunskaya I. V. Best approximation of compact set by a ball in an arbitrary norm. Sb. Math., 2000, vol. 191, no. 10, pp. 1433-1458. DOI: http:// dx.doi.org/10.1070/SM2000v191n10ABEH000513.

3. Dudov S. I. Relations between several problems of estimating convex compacta by balls. Sb. Math., 2007, vol. 198, no. 1, pp. 43-58. DOI: http://dx.doi.org/ 10.1070/SM2007v198n01ABEH003828.

4. Dudov S. I., Meshcheryakova E. A. Method for finding an approximate solution of the asphericity problem for a convex body. Comp. Math. and Math. Physics, 2013, vol. 53, no. 10, pp. 1483-1493. DOI: 10.1134/S0965542513100059.

5. Pschemichnyi B. N. Vypuklyj analiz i jekstremal'nye zadachi [Convex Analysis and Extremal Problems]. Moscow, Nauka, 1980 (in Russian).

6. Dem'yanov V. F., Vasil'ev L. V. Nondifferetiable opti-

mization. New York, Optimization software, Inc., Publications Division, 1985.

7. Dudov S. I. Subdifferentiability and superdifferentiability of distance functions. Math. Notes, 1997, vol. 61, no. 4, pp. 440-450. DOI: 10.1007/BF02354988.

8. Hiriart-Urruty J. B. Tangent cones, generalized gradients and mathematical programming in Banach spaces. Math. Oper. Research, 1979, vol. 4, no. 1, pp. 79-97.

9. Vasil'ev F. P. Metody optimizacii [Methods of Optimization]. Moscow, MCSMO, 2011 (in Russian).

10. Dudov S. I., Zlatorunskaya I. V. Best approximation of compact set by a ball in an arbitrary norm. Adv. Math. Res., 2003, vol. 2, pp. 81-114.

11. Zuhovickij S. I., Avdeeva L. I. Linejnoe i vypukloe programmirovanie [Linear and convex programming]. Moscow, Nauka, 1964 (in Russian).

12. Bronstein E. M. Approximation of convex sets by polytopes. J. of Math. Sciences, 2008, vol. 153, no. 6, pp. 727-762. DOI: 10.1007/s10958-008-9144-x.