An Algorithm for Finding the Generalized Chebyshev Center of Sets Defined via Their Support Functions
Abstract
This paper is dedicated to an optimization problem. Let A, B subset of R-n be compact convex sets. Consider the minimal number t(0) > 0 such that t(0)B covers A after a shift to a vector x(0) is an element of R-n. The goal is to find t(0) and x(0). In the special case of B being a unit ball centered at zero, x(0) and t(0) are known as the Chebyshev center and the Chebyshev radius of A. This paper focuses on the case in which A and B are defined with their black-box support functions. An algorithm for solving such problems efficiently is suggested. The algorithm has a superlinear convergence rate, and it can solve hundred-dimensional test problems in a reasonable time, but some additional conditions on A and B are required to guarantee the presence of convergence. Additionally, the behavior of the algorithm for a simple special case is investigated, which leads to a number of theoretical results. Perturbations of this special case are also studied.