In geometry, the Chebyshev center of a bounded set
having non-empty interior is the center of the minimal-radius ball enclosing the entire set
, or alternatively (and non-equivalently) the center of largest inscribed ball of
There exist several alternative representations for the Chebyshev center.
can be computed by solving: with respect to the Euclidean norm
, or alternatively by solving: Despite these properties, finding the Chebyshev center may be a hard numerical optimization problem.
For example, in the second representation above, the inner maximization is non-convex if the set Q is not convex.
is closed, bounded and convex, then the Chebyshev center is in
In other words, the search for the Chebyshev center can be conducted inside
is the tetrahedron formed by the convex hull of the points (1,1,1), (-1,1,1), (1,-1,1) and (1,1,-1), then computing the Chebyshev center using the
, we can write the inner maximization problem of the Chebyshev center as: where
is the set of positive semi-definite matrices, and changing the order of the min max to max min (see the references for more details), the optimization problem can be formulated as: with This last convex optimization problem is known as the relaxed Chebyshev center (RCC).
The RCC has the following important properties: It can be shown that the well-known constrained least squares (CLS) problem is a relaxed version of the Chebyshev center.
This means that the CLS estimate is the solution of a looser relaxation than that of the RCC.
Since both the RCC and CLS are based upon relaxation of the real feasibility set
This of course affects the quality of the RCC and CLS estimators.
As a simple example consider the linear box constraints: which can alternatively be written as It turns out that the first representation results with an upper bound estimator for the second one, hence using it may dramatically decrease the quality of the calculated estimator.
This simple example shows us that great care should be given to the formulation of constraints when relaxation of the feasibility region is used.
This problem can be formulated as a linear programming problem, provided that the region Q is an intersection of finitely many hyperplanes.
[4] Given a polytope, Q, defined as follows then it can be solved via the following linear program.