In geometry, the Chebyshev center of a bounded set
Contents
- Mathematical representation
- Properties
- Relaxed Chebyshev center
- Constrained least squares
- RCC vs CLS
- Modeling constraints
- Linear programming problem
- References
In the field of parameter estimation, the Chebyshev center approach tries to find an estimator
Mathematical representation
There exist several alternative representations for the Chebyshev center. Consider the set
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.
Properties
In inner product spaces and two-dimensional spaces, if
In other spaces, the Chebyshev center may not be in
Relaxed Chebyshev center
Let us consider the case in which the set
with
By introducing an additional matrix variable
where
Relaxing our demand on
with
This last convex optimization problem is known as the relaxed Chebyshev center (RCC). The RCC has the following important properties:
Constrained least squares
It can be shown that the well-known constrained least squares (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
Modeling constraints
Since both the RCC and CLS are based upon relaxation of the real feasibility set
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.
Linear programming problem
This problem can be formulated as a linear programming problem, provided that the region Q is an intersection of finitely many hyperplanes.