词条 | Chebyshev center |
释义 |
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 .[1] 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 representationThere 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: [1] 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. PropertiesIn inner product spaces and two-dimensional spaces, if is closed, bounded and convex, then the Chebyshev center is in . In other words, the search for the Chebyshev center can be conducted inside without loss of generality.[2] In other spaces, the Chebyshev center may not be in , even if is convex. For instance, if 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 norm yields[3] Relaxed Chebyshev centerLet 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 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:
Constrained least squaresIt can be shown that the well-known constrained least squares (CLS) problem is a relaxed version of the Chebyshev center.{{citation needed|date=May 2015}} 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. CLSA 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 constraintsSince 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. Linear programming problemThis problem can be formulated as a linear programming problem, provided that the region Q is an intersection of finitely many hyperplanes.[4] See also
References1. ^1 {{cite book|title=Convex Optimization|first1=Stephen P.|last1=Boyd|first2=Lieven|last2=Vandenberghe|year=2004|publisher=Cambridge University Press|isbn=978-0-521-83378-3|url=http://www.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf|accessdate=October 15, 2011}} 2. ^{{cite book|last1=Amir|first1=Dan|title=International Series of Numerical Mathematics / Internationale Schriftenreihe zur Numerischen Mathematik / Série internationale d'Analyse numérique|date=1984|publisher=Birkhäuser|isbn=9783034862530|pages=19–35|chapter=Best Simultaneous Approximation (Chebyshev Centers)}} 3. ^{{cite journal|last1=Dabbene|first1=Fabrizio|last2=Sznaier|first2=Mario|last3=Tempo|first3=Roberto|title=Probabilistic Optimal Estimation With Uniformly Distributed Noise|journal=IEEE Transactions on Automatic Control|date=August 2014|volume=59|issue=8|pages=2113–2127|doi=10.1109/tac.2014.2318092}} 4. ^{{Cite web |url=http://www.ifor.math.ethz.ch/teaching/lectures/intro_ss11/Exercises/solutionEx11-12.pdf |title=Archived copy |access-date=2014-09-12 |archive-url=https://web.archive.org/web/20140912204904/http://www.ifor.math.ethz.ch/teaching/lectures/intro_ss11/Exercises/solutionEx11-12.pdf |archive-date=2014-09-12 |dead-url=yes |df= }}
3 : Estimation methods|Geometric centers|Mathematical optimization |
随便看 |
|
开放百科全书收录14589846条英语、德语、日语等多语种百科知识,基本涵盖了大多数领域的百科知识,是一部内容自由、开放的电子版国际百科全书。