Geodesic
Covering a Set by a Convex Compactum: Error Estimates and Computation
Matematičeskie zametki, Tome 112 (2022) no. 3, pp. 337-349.

Voir la notice de l'article provenant de la source Math-Net.Ru

A problem related to that of finding the Chebyshev center of a compact convex set in $\mathbb R^n$ is considered, namely, the problem of calculating the center and the least positive ratio of a homothety under which the image of a given compact convex set in $\mathbb R^n$ covers another given compact convex set. Both sets are defined by their support functions. A solution algorithm is proposed which consists in discretizing the support functions on a grid of unit vectors and reducing the problem to a linear programming problem. The error of the solution is estimated in terms of the distance between the given set and its approximation in the Hausdorff metric. For the stability of the approximate solution, it is essential that the sets be uniformly convex and a certain set in the dual space has a nonempty interior.
Keywords: Chebyshev center, stability of minimization problem, Hausdorff metric, linear programming, support function. 
@article{MZM_2022_112_3_a1,
     author = {M. V. Balashov},
     title = {Covering a {Set} by a {Convex} {Compactum:} {Error} {Estimates} and {Computation}},
     journal = {Matemati\v{c}eskie zametki},
     pages = {337--349},
     publisher = {mathdoc},
     volume = {112},
     number = {3},
     year = {2022},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MZM_2022_112_3_a1/}
}
TY  - JOUR
AU  - M. V. Balashov
TI  - Covering a Set by a Convex Compactum: Error Estimates and Computation
JO  - Matematičeskie zametki
PY  - 2022
SP  - 337
EP  - 349
VL  - 112
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MZM_2022_112_3_a1/
LA  - ru
ID  - MZM_2022_112_3_a1
ER  - 
%0 Journal Article
%A M. V. Balashov
%T Covering a Set by a Convex Compactum: Error Estimates and Computation
%J Matematičeskie zametki
%D 2022
%P 337-349
%V 112
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MZM_2022_112_3_a1/
%G ru
%F MZM_2022_112_3_a1
M. V. Balashov. Covering a Set by a Convex Compactum: Error Estimates and Computation. Matematičeskie zametki, Tome 112 (2022) no. 3, pp. 337-349. http://geodesic.mathdoc.fr/item/MZM_2022_112_3_a1/

[1] A. L. Garkavi, “O chebyshevskom tsentre i vypukloi obolochke mnozhestva”, UMN, 19:6 (120) (1964), 139–145 | MR | Zbl

[2] A. R. Alimov, I. G. Tsarkov, “Chebyshevskii tsentr mnozhestva, konstanta Yunga i ikh prilozheniya”, UMN, 74:5 (449) (2019), 3–82 | DOI | MR

[3] Alexey R. Alimov, Igor' G. Tsar'kov, Geometric Approximation Theory, Springer, Cham, 2021 | MR

[4] A. Beck, A. C. Eldar, “Regularization in regression with bounded noise: a Chebyshev center approach”, SIAM J. Matrix Anal. Appl., 29:2 (2007), 606–625 | DOI | MR

[5] Duzhi Wu, Jie Zhou, Aiping Hu, “A new approximate algorithm for the Chebyshev center”, Automatica, 49 (2013), 2483–2488 | DOI | MR

[6] V. Cerone, D. Piga, D. Regruto, “Set-Membership Error-in-Variables IdentificationThrough Convex Relaxation Techniques”, IEEE Trans. Automat. Control, 57:2 (2012), 517–522 | DOI | MR

[7] Sheng Xu, R. M. Freund, “Solution Methodologies for the Smallest Enclosing Circle Problem”, Comput. Optim. Appl., 25 (2003), 283–292 | DOI | MR

[8] Y. Xia, M. Yang, S. Wang, “Chebyshev center of the intersection of balls: complexity, relaxation and approximation”, Math. Program. Ser. A, 187:1-2 (2021), 287–315 | DOI | MR

[9] M. Milanese, R. Tempo, “Optimal algorithms theory for robust estimation and prediction”, IEEE Trans. Automat. Control, 30:8 (1985), 730–738 | DOI | MR

[10] N. D. Botkin, V. L. Turova-Botkina, “An algorithm for finding the Chebyshev center of a convex polyhedron”, Appl. Math. Optim., 29 (1994), 211–222 | DOI | MR

[11] S. I. Dudov, A. S. Dudova, “Ob ustoichivosti resheniya zadach o vneshnei i vnutrennei otsenke vypuklogo kompakta sharom”, Zh. vychisl. matem. i matem. fiz., 47:10 (2007), 1657–1671 | MR

[12] B. B. Abramova, S. I. Dudov, M. A. Osiptsev, “Vneshnyaya otsenka kompakta lebegovym mnozhestvom vypukloi funktsii”, Izv. Sarat. un-ta. Nov. ser. Ser. Matematika. Mekhanika. Informatika, 20:2 (2020), 142–153 | DOI

[13] S. I. Dudov, “Sistematizatsiya zadach po sharovym otsenkam vypuklogo kompakta”, Matem. sb., 206:9 (2015), 99–120 | DOI | MR | Zbl

[14] M. V. Balashov, “Approximate calculation of the Chebyshev center for a convex compact set in $\mathbb R^n$”, J. Convex Anal., 29:1 (2022), 157–164 | MR

[15] M. V. Balashov, “Chebyshev center and inscribed balls: properties and calculations”, Optim. Lett., 2021 (2021) | DOI

[16] Z. Xu, Y. Xia, J. Wang, “Cheaper relaxation and better approximation for multi-ball constrained quadratic optimization and extension”, J. Global Opt., 80 (2021), 341–356 | DOI | MR

[17] L. Dantser, B. Gryunbaum, V. Kli, Teorema Khelli i ee primeneniya, Mir, M., 1968 | MR | Zbl

[18] Dzh. Distel, Geometriya banakhovykh prostranstv. Izbrannye glavy, Vischa shkola, Kiev, 1980 | MR | Zbl

[19] E. S. Polovinkin, M. V. Balashov, Elementy vypuklogo i silno vypuklogo analiza, Fizmatlit, M., 2007 | Zbl

[20] M. V. Balashov, E. S. Polovinikin, “$M$-silno vypuklye podmnozhestva i ikh porozhdayuschie mnozhestva”, Matem. sb., 191:1 (2000), 27–64 | DOI | MR | Zbl

[21] E. S. Polovinikin, “Silno vypuklyi analiz”, Matem. sb., 187:2 (1996), 103–130 | DOI | MR

[22] M. V. Balashov, “On polyhedral approximations in an $n$-dimensional space”, Comput. Math. Math. Phys., 56:10 (2016), 1679–1685 | DOI | MR

[23] M. V. Balashov, D. Repovs, “Polyhedral approximations of strictly convex compacta”, J. Math. Anal. Appl., 374 (2011), 529–537 | DOI | MR

[24] P. M. Gruber, “Approximation of convex bodies”, Convexity and Its Applications, Birkhäuser, Basel, 1983, 131–162 | MR

[25] D. Rosca, “New uniform grids on the sphere”, Astron. Astrophys., 520 (2010), A63 | DOI

[26] D. Rosca, G. Plonka, “Uniform spherical grids via equal area projection from the cube to the sphere”, J. Comput. Appl. Math., 236:3 (2011), 1033–1041 | DOI | MR