HOME

TheInfoList



OR:

In
geometry Geometry (; ) is a branch of mathematics concerned with properties of space such as the distance, shape, size, and relative position of figures. Geometry is, along with arithmetic, one of the oldest branches of mathematics. A mathematician w ...
, the Chebyshev center of a bounded set Q having non-empty interior is the center of the minimal-radius ball enclosing the entire set Q, or alternatively (and non-equivalently) the center of largest inscribed ball of Q. In the field of parameter estimation, the Chebyshev center approach tries to find an estimator \hat x for x given the feasibility set Q , such that \hat x 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 Q and denote its Chebyshev center by \hat. \hat can be computed by solving: : \min_ \left\ with respect to the
Euclidean norm Euclidean space is the fundamental space of geometry, intended to represent physical space. Originally, in Euclid's ''Elements'', it was the three-dimensional space of Euclidean geometry, but in modern mathematics there are ''Euclidean spaces'' ...
\, \cdot\, , or alternatively by solving: : \operatorname \max_ \left\, x - \hat x \right\, ^2. 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 or convexity may refer to: Science and technology * Convex lens, in optics Mathematics * Convex set, containing the whole line segment that joins points ** Convex polygon, a polygon which encloses a convex set of points ** Convex polytop ...
.


Properties

In inner product spaces and two-dimensional spaces, if Q is closed, bounded and convex, then the Chebyshev center is in Q . In other words, the search for the Chebyshev center can be conducted inside Q
without loss of generality ''Without loss of generality'' (often abbreviated to WOLOG, WLOG or w.l.o.g.; less commonly stated as ''without any loss of generality'' or ''with no loss of generality'') is a frequently used expression in mathematics. The term is used to indicat ...
. In other spaces, the Chebyshev center may not be in Q , even if Q is convex. For instance, if Q is the tetrahedron formed by the
convex hull In geometry, the convex hull, convex envelope or convex closure of a shape is the smallest convex set that contains it. The convex hull may be defined either as the intersection of all convex sets containing a given subset of a Euclidean space, ...
of the points (1,1,1), (-1,1,1), (1,-1,1) and (1,1,-1), then computing the Chebyshev center using the \ell_ norm yields : 0 = \operatorname\max _\left\, x-\right\, _^.


Relaxed Chebyshev center

Consider the case in which the set Q can be represented as the intersection of k ellipsoids. : \min_ \max_x \left\ with : f_i (x) = x^T Q_i x + 2g_i^T x + d_i \le 0,0 \le i \le k. \, By introducing an additional matrix variable \Delta = x x^T , we can write the inner maximization problem of the Chebyshev center as: : \min_ \max_ \left\ where \operatorname(\cdot) is the
trace operator In mathematical analysis, the trace operator extends the notion of the restriction of a function to the boundary of its domain to "generalized" functions in a Sobolev space. This is particularly important for the study of partial differential equ ...
and : G = \left\ : f_i (\Delta ,x) = \operatorname(Q_i \Delta ) + 2g_i^T x + d_i. Relaxing our demand on \Delta by demanding \Delta \ge xx^T , i.e. \Delta - xx^T \in S_+ where S_+ 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: : RCC = \max_ \left\ with : = \left\. 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

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: : _ = \operatorname*_ \left\, y - Ax \right\, ^2 with : = \left\ : Q_i \ge 0,g_i \in R^m ,d_i \in R. It can be shown that this problem is equivalent to the following optimization problem: : \max_ \left\ with : V = \left\. 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 (x,\Delta) for the RCC is also a solution for the CLS, and thus T \in V . 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 Q, the form in which Q 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: : l \leq a^T x \leq u which can alternatively be written as : (a^T x - l)(a^T x - u) \leq 0. 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 Linear programming (LP), also called linear optimization, is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements and objective are represented by linear function#As a polynomia ...
problem, provided that the region Q is an intersection of finitely many hyperplanes. Given a
polytope In elementary geometry, a polytope is a geometric object with flat sides ('' faces''). Polytopes are the generalization of three-dimensional polyhedra to any number of dimensions. Polytopes may exist in any general number of dimensions as an ...
, Q, defined as follows then it can be solved via the following linear program. : Q = \ : \begin & \max_ && r\\ & \text && a_i \hat x + \, a_i\, r \leq b_i \\ & \text && r\geq 0 \end


See also

* Bounding sphere *
Smallest-circle problem The smallest-circle problem (also known as minimum covering circle problem, bounding circle problem, least bounding circle problem, smallest enclosing circle problem) is a computational geometry problem of computing the smallest circle that cont ...
*
Circumscribed circle In geometry, a circumscribed circle for a set of points is a circle passing through each of them. Such a circle is said to ''circumscribe'' the points or a polygon formed from them; such a polygon is said to be ''inscribed'' in the circle. * Circu ...
(covers ''circumcenter'') *
Centre (geometry) In geometry, a centre (English in the Commonwealth of Nations, Commonwealth English) or center (American English) () of an shape, object is a point (geometry), point in some sense in the middle of the object. According to the specific definiti ...
*
Centroid In mathematics and physics, the centroid, also known as geometric center or center of figure, of a plane figure or solid figure is the arithmetic mean position of all the points in the figure. The same definition extends to any object in n-d ...


References

{{Reflist * Y. C. Eldar, A. Beck, and M. Teboulle
"A Minimax Chebyshev Estimator for Bounded Error Estimation,"
IEEE Trans. Signal Process., 56(4): 1388–1397 (2007). * A. Beck and Y. C. Eldar
"Regularization in Regression with Bounded Noise: A Chebyshev Center Approach,"
SIAM J. Matrix Anal. Appl. 29 (2): 606–625 (2007). Estimation methods Geometric centers Mathematical optimization