List of types of functions: Difference between revisions
en>ClueBot NG m Reverting possible vandalism by 75.63.144.107 to version by SchreiberBike. False positive? Report it. Thanks, ClueBot NG. (1112797) (Bot) |
en>Addbot m Bot: Migrating 1 interwiki links, now provided by Wikidata on d:q12802481 |
||
Line 1: | Line 1: | ||
{{more footnotes|date=October 2011}} | |||
In [[geometry]], the '''Chebyshev center''' of a bounded set <math>Q</math> having non-empty [[Interior (topology)|interior]] is the center of the minimal-radius ball enclosing the entire set <math>Q</math>, or, alternatively, the center of largest inscribed ball of <math>Q</math>.<ref>{{cite book|title=Convex optimization|year=2004|publisher=Cambridge|location=New York|isbn=978-0-521-83378-3|author=Boyd, Stephen P.; Vandenberghe, Lieven}}</ref> | |||
In the field of [[parameter estimation]], the Chebyshev center approach tries to find an estimator <math> \hat x </math> for <math> x </math> given the feasibility set <math> Q </math>, such that <math>\hat x</math> 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 <math>Q</math> and denote its Chebyshev center by <math>\hat{x}</math>. <math>\hat{x}</math> can be computed by solving: | |||
: <math> \min_{{\hat x},r} \left\{ r:\left\| {\hat x} - x \right\|^2 \leq r, \forall x \in Q \right\} </math> | |||
or alternatively by solving: | |||
:<math> \operatorname*{\arg\min}_{\hat{x}} \max_{x \in Q} \left\| x - \hat x \right\|^2. </math><ref name="BV">{{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|format=pdf|accessdate=October 15, 2011}}</ref> | |||
Despite these properties, finding the Chebyshev center may be a hard numerical [[mathematical optimization|optimization problem]]. For example, in the second representation above, the inner maximization is [[nonconvex optimization|non-convex]] if the set ''Q'' is not [[convex set|convex]]. | |||
== Relaxed Chebyshev center == | |||
Let us consider the case in which the set <math>Q</math> can be represented as the intersection of <math>k</math> ellipsoids. | |||
: <math> \min_{\hat x} \max_x \left\{ \left\| {\hat x} - x \right\|^2 :f_i (x) \le 0,0 \le i \le k \right\} </math> | |||
with | |||
: <math> f_i (x) = x^T Q_i x + 2g_i^T x + d_i \le 0,0 \le i \le k. \, </math> | |||
By introducing an additional matrix variable <math>\Delta = x x^T </math>, we can write the inner maximization problem of the Chebyshev center as: | |||
: <math> \min_{\hat x} \max_{(\Delta ,x) \in G} \left\{ \left\| {\hat x} \right\|^2 - 2{\hat x}^T x + \operatorname{Tr}(\Delta ) \right\} </math> | |||
where <math>\operatorname{Tr}(\cdot)</math> is the [[trace (linear algebra)|trace operator]] and | |||
: <math> G = \left\{(\Delta ,x):{\rm{f}}_i (\Delta ,x) \le 0,0 \le i \le k,\Delta = xx^T \right\} </math> | |||
: <math> f_i (\Delta ,x) = \operatorname{Tr}(Q_i \Delta ) + 2g_i^T x + d_i. </math> | |||
Relaxing our demand on <math>\Delta</math> by demanding <math> \Delta \leq xx^T </math>, i.e. <math>xx^T - \Delta \in S_+</math> where <math>S_+</math> is the set of [[positive semi-definite matrix|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: | |||
: <math> RCC = \max_{(\Delta ,x) \in {T}} \left\{ - \left\| x \right\|^2 + \operatorname{Tr}(\Delta ) \right\} </math> | |||
with | |||
: <math> {T} = \left\{ (\Delta ,x):\rm{f}_i (\Delta ,x) \le 0,0 \le i \le k,\Delta \le xx^T \right\}. </math> | |||
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 squares]] (CLS) problem is a relaxed version of the Chebyshev center. | |||
The original CLS problem can be formulated as: | |||
: <math> {\hat x}_{CLS} = \operatorname*{\arg\min}_{x \in C} \left\| y - Ax \right\|^2 </math> | |||
with | |||
: <math> { C} = \left\{ x:f_i (x) = x^T Q_i x + 2g_i^T x + d_i \le 0,1 \le i \le k \right\} | |||
</math> | |||
: <math> Q_i \ge 0,g_i \in R^m ,d_i \in R. </math> | |||
It can be shown that this problem is equivalent to the following optimization problem: | |||
: <math> \max_{(\Delta ,{{x}}) \in {V}} \left\{ { - \left\| {{x}} \right\|^2 + \operatorname{Tr}(\Delta )} \right\} </math> | |||
with | |||
: <math> V = \left\{ \begin{array}{c} | |||
(\Delta ,x):x \in C{\rm{ }} \\ | |||
\operatorname{Tr}(A^T A\Delta ) - 2y^T A^T x + \left\| y \right\|^2 - \rho \le 0,\rm{ }\Delta \ge xx^T \\ | |||
\end{array} \right\}.</math> | |||
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 <math> (x,\Delta) </math> for the RCC is also a solution for the CLS, and thus <math> T \in V </math>. | |||
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 <math>Q</math>, the form in which <math>Q</math> 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: | |||
: <math> l \leq a^T x \leq u </math> | |||
which can alternatively be written as | |||
: <math> (a^T x - l)(a^T x - u) \leq 0. </math> | |||
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. | |||
== See also == | |||
* [[Bounding sphere]] | |||
* [[Smallest-circle problem]] | |||
* [[Centre (geometry)]] | |||
* [[Centroid]] | |||
== References == | |||
{{Reflist}} | |||
* Y. C. Eldar, A. Beck, and M. Teboulle, [http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=4471880 "A Minimax Chebyshev Estimator for Bounded Error Estimation,"] IEEE Trans. Signal Processing, 56(4): 1388–1397 (2007). | |||
* A. Beck and Y. C. Eldar, [http://dx.doi.org/10.1137/060656784 "Regularization in Regression with Bounded Noise: A Chebyshev Center Approach,"] SIAM J. Matrix Anal. Appl. 29 (2): 606–625 (2007). | |||
[[Category:Estimation theory]] | |||
[[Category:Geometric centers]] | |||
[[Category:Mathematical optimization]] |
Revision as of 17:35, 7 May 2013
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 .[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 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:
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.
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 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:
- 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 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 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.
See also
References
43 year old Petroleum Engineer Harry from Deep River, usually spends time with hobbies and interests like renting movies, property developers in singapore new condominium and vehicle racing. Constantly enjoys going to destinations like Camino Real de Tierra Adentro.
- Y. C. Eldar, A. Beck, and M. Teboulle, "A Minimax Chebyshev Estimator for Bounded Error Estimation," IEEE Trans. Signal Processing, 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).
- ↑ 20 year-old Real Estate Agent Rusty from Saint-Paul, has hobbies and interests which includes monopoly, property developers in singapore and poker. Will soon undertake a contiki trip that may include going to the Lower Valley of the Omo.
My blog: http://www.primaboinca.com/view_profile.php?userid=5889534 - ↑ 20 year-old Real Estate Agent Rusty from Saint-Paul, has hobbies and interests which includes monopoly, property developers in singapore and poker. Will soon undertake a contiki trip that may include going to the Lower Valley of the Omo.
My blog: http://www.primaboinca.com/view_profile.php?userid=5889534