Abstract

We present an approximate algorithm for calculation of the Chebyshev center for a convex compact subset from Rn\mathbb{R}^n which is given via its supporting function. We reduce the problem to the solution of a linear programming problem and estimate the error between an approximate and the exact solutions in terms of the step of a grid.

Author information

Contact details are reproduced from the original publication and may be historical.

Maxim V. Balashov

V. A. Trapeznikov Institute of Control Sciences, Moscow, Russia 117997

balashov73@mail.ru

Keywords

  • Chebyshev center
  • stability of minimization problem
  • Hausdorff distance
  • linear programming
  • supporting function

Mathematics Subject Classification

49J52, 49J53, 52A20; 52B12, 90C05

References

  1. M. V. Balashov: On polyhedral approximations in an n-dimensional space, Comput. Math. Math. Phys. 56/10 (2016) 1679–1685.https://doi.org/10.1134/S0965542516100031Google Scholar
  2. M. V. Balashov, D. Repovš: Polyhedral approximations of strictly convex compacta, J. Math. Analysis Appl. 374/2 (2011) 529–537.https://doi.org/10.1016/j.jmaa.2010.09.007Google Scholar
  3. M. Berger: Geometry I, Springer, Berlin (1987).Google Scholar
  4. 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.https://doi.org/10.1007/BF01204183Google Scholar
  5. V. Cerone, D. Piga, D. Regruto: Set-membership error-in-variables identification through convex relaxation techniques, IEEE Trans. Automatic Control 57/2 (2012) 517–522.https://doi.org/10.1109/TAC.2011.2168073Google Scholar
  6. A. L. Garkavi: On the Chebyshev center and convex hull of a set, Uspekhi Mat. Nauk, 19:6 (120) (1964) 139–145.Google Scholar
  7. M. Milanese, R. Tempo: Optimal algorithms theory for robust estimation and prediction, IEEE Trans. Automatic Control AC-30/8 (1985) 730–738.https://doi.org/10.1109/TAC.1985.1104056Google Scholar
  8. E. S. Polovinkin, M. V. Balashov: Elements of Convex and Strongly Convex Analysis (Russian), 2nd ed., Fizmatlit, Moscow (2007).Google Scholar
  9. L. S. Pontryagin: Linear differential games of pursuit, Math. USSR Sb. 40/3 (1981) 285–303.https://doi.org/10.1070/SM1981v040n03ABEH001815Google Scholar
  10. D. Wu, J. Zhou, A. Hu: A new approximate algorithm for the Chebyshev center, Automatica 49 (2013) 2483–2488.https://doi.org/10.1016/j.automatica.2013.04.029Google Scholar
  11. S. Xu, R. M. Freund: Solution methodologies for the smallest enclosing circle problem, Comp. Optimization Appl. 25 (2003) 283–292.https://doi.org/10.1023/A:1022977709811Google Scholar

Suggested citation

M. V. Balashov. “Approximate Calculation of the Chebyshev Center for a Convex Compact Set in ℝ^n.” Journal of Convex Analysis 29 (2022), No. 1, 157–164. https://doi.org/10.68381/jca29009

Download BibTeXPublished by Heldermann Verlag.

Published by Heldermann Verlag, 2022. Rights now held by Banach Press LLC.