Abstract:
This paper is dedicated to an optimization problem. Let $A$, $B \subset\mathbb{R}^n$ be compact convex sets. Consider the minimal number $t_0>0$ such that $t^0B$ covers $A$ after a shift to a vector $x_0\in\mathbb{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.
Keywords:optimization, Chebyshev center, gradient descent.
Fulltext:
PDF file (316 kB)
First page:
PDF file