Chebyshev center
Encyclopedia
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, the center of largest inscribed ball of 
.
In the field of parameter estimation, the Chebyshev center approach tries to find an estimator
for 
given the feasibility set 
, such that 
minimizes the worst possible estimation error for x (e.g. best worst case).
Consider the set
and denote its Chebyshev center by 
. 
can be computed by solving:
or alternatively by solving:
Some important optimization properties of the Chebyshev Center are:
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
.
can be represented as the intersection of 
ellipsoids.
with
By introducing an additional matrix variable
, we can write the inner maximization problem of the Chebyshev center as:
where
is the trace operator
and
Relaxing our demand on
by demanding 
, i.e. 
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:
(CLS) problem is a relaxed version of the Chebyshev center.
The original CLS problem can be formulated as:
with
Geometry
Geometry arose as the field of knowledge dealing with spatial relationships. Geometry was one of the two fields of pre-modern mathematics, the other being the study of numbers ....
, the Chebyshev center of a bounded set
having non-empty interiorInterior (topology)
In mathematics, specifically in topology, the interior of a set S of points of a topological space consists of all points of S that do not belong to the boundary of S. A point that is in the interior of S is an interior point of S....
is the center of the minimal-radius ball enclosing the entire set
, or, alternatively, the center of largest inscribed ball of .In the field of parameter estimation, the Chebyshev center approach tries to find an estimator
for given the feasibility set , such that minimizes the worst possible estimation error for x (e.g. best worst case).Mathematical representation
There exist several alternative representations for the Chebyshev center.Consider the set
and denote its Chebyshev center by . can be computed by solving:
or alternatively by solving:
Some important optimization properties of the Chebyshev Center are:
- The Chebyshev center is unique.
- The Chebyshev center is feasible.
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
Convex set
In Euclidean space, an object is convex if for every pair of points within the object, every point on the straight line segment that joins them is also within the object...
.
Relaxed Chebyshev center
Let us consider the case in which the set can be represented as the intersection of ellipsoids.
with
By introducing an additional matrix variable
, we can write the inner maximization problem of the Chebyshev center as:
where
is the trace operatorTrace (linear algebra)
In linear algebra, the trace of an n-by-n square matrix A is defined to be the sum of the elements on the main diagonal of A, i.e.,...
and
Relaxing our demand on
by demanding , i.e. 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:
- The RCC is an upper bound for the exact Chebyshev center.
- The RCC is unique.
- The RCC is feasible.
Constrained least squares
With a few simple mathematical tricks, it can be shown that the well-known constrained least squaresLeast squares
The method of least squares is a standard approach to the approximate solution of overdetermined systems, i.e., sets of equations in which there are more equations than unknowns. "Least squares" means that the overall solution minimizes the sum of the squares of the errors made in solving every...
(CLS) problem is a relaxed version of the Chebyshev center.
The original CLS problem can be formulated as:
with
-
It can be shown that this problem is equivalent to the following optimization problem:
with-
One can see that this problem is a relaxation of the Chebyshev center (though different than the RCC described above).
RCC vs. CLS
A solution set
for the RCC is also a solution for the CLS, and thus 
.
This means that the CLS estimate is the solution of a looser relaxation than that of the RCC.
Hence the CLS is an upper bound for the RCC, which is an upper bound for the real Chebyshev center.
Modeling constraints
Since both the RCC and CLS are based upon relaxation of the real feasibility set
, the form in which 
is defined affects its relaxed versions. 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. -
-
