चेबिशेव केंद्र

ज्यामिति में, परिबद्ध समुच्चय का चेबीशेव केंद्र $Q$ गैर-खाली इंटीरियर (टोपोलॉजी) पूरे सेट को घेरने वाली न्यूनतम-त्रिज्या गेंद का केंद्र है $Q$, या वैकल्पिक रूप से (और गैर-समतुल्य रूप से) सबसे बड़ी खुदी हुई गेंद का केंद्र $Q$.

पैरामीटर आकलन के क्षेत्र में, चेबिशेव केंद्र दृष्टिकोण एक अनुमानक खोजने की कोशिश करता है ${\hat {x}}$ के लिए $x$ व्यवहार्यता सेट दिया $Q$, ऐसा है कि ${\hat {x}}$ एक्स के लिए सबसे खराब संभावित अनुमान त्रुटि को कम करता है (उदाहरण के लिए सबसे खराब स्थिति)।

गणितीय प्रतिनिधित्व

चेबिशेव केंद्र के लिए कई वैकल्पिक अभ्यावेदन मौजूद हैं। सेट पर विचार करें $Q$ और इसके चेबिशेव केंद्र को निरूपित करें ${\hat {x}}$. ${\hat {x}}$ हल करके गणना की जा सकती है:

$\min _{{\hat {x}},r}\left\{r:\left\|{\hat {x}}-x\right\|^{2}\leq r,\forall x\in Q\right\}$

यूक्लिडियन दूरी के संबंध में $\|\cdot \|$, या वैकल्पिक रूप से हल करके:

$\operatorname {\underset {\mathit {\hat {x}}}{argmin}} \max _{x\in Q}\left\|x-{\hat {x}}\right\|^{2}.$

इन गुणों के बावजूद, चेबिशेव केंद्र का पता लगाना कठिन संख्यात्मक अनुकूलन समस्या हो सकती है। उदाहरण के लिए, ऊपर दिए गए दूसरे प्रतिनिधित्व में, आंतरिक अधिकतमकरण गैर-उत्तल अनुकूलन है | गैर-उत्तल यदि सेट Q उत्तल सेट नहीं है।

गुण

आंतरिक उत्पाद रिक्त स्थान और द्वि-आयामी रिक्त स्थान में, यदि $Q$ बंद है, घिरा हुआ है और उत्तल है, तो चेबिशेव केंद्र अंदर है $Q$. दूसरे शब्दों में, चेबिशेव केंद्र की खोज अंदर की जा सकती है $Q$ व्यापकता के नुकसान के बिना। अन्य स्थानों में, चेबीशेव केंद्र नहीं हो सकता है $Q$, भले ही $Q$ उत्तल है। उदाहरण के लिए, अगर $Q$ अंक (1,1,1), (-1,1,1), (1,-1,1) और (1,1,-1) के उत्तल पतवार द्वारा गठित टेट्राहेड्रोन है, फिर चेबीशेव की गणना केंद्र का उपयोग कर रहा है $\ell _{\infty }$ आदर्श उपज

$0=\operatorname {\underset {\mathit {\hat {x}}}{argmin}} \max _{x\in Q}\left\|x-{\hat {x}}\right\|_{\infty }^{2}.$

आराम से चेबीशेव केंद्र

उस मामले पर विचार करें जिसमें सेट है $Q$ के प्रतिच्छेदन के रूप में दर्शाया जा सकता है $k$ दीर्घवृत्त।

$\min _{\hat {x}}\max _{x}\left\{\left\|{\hat {x}}-x\right\|^{2}:f_{i}(x)\leq 0,0\leq i\leq k\right\}$

साथ

$f_{i}(x)=x^{T}Q_{i}x+2g_{i}^{T}x+d_{i}\leq 0,0\leq i\leq k.\,$

एक अतिरिक्त मैट्रिक्स चर का परिचय देकर $\Delta =xx^{T}$, हम चेबिशेव केंद्र की आंतरिक अधिकतमकरण समस्या को इस प्रकार लिख सकते हैं:

$\min _{\hat {x}}\max _{(\Delta ,x)\in G}\left\{\left\|{\hat {x}}\right\|^{2}-2{\hat {x}}^{T}x+\operatorname {Tr} (\Delta )\right\}$

कहाँ $\operatorname {Tr} (\cdot )$ ट्रेस (रैखिक बीजगणित) है और

$G=\left\{(\Delta ,x):{\rm {f}}_{i}(\Delta ,x)\leq 0,0\leq i\leq k,\Delta =xx^{T}\right\}$

$f_{i}(\Delta ,x)=\operatorname {Tr} (Q_{i}\Delta )+2g_{i}^{T}x+d_{i}.$

हमारी मांग को शिथिल करते हुए $\Delta$ मांग कर $\Delta \geq xx^{T}$, अर्थात। $\Delta -xx^{T}\in S_{+}$ कहाँ $S_{+}$ सकारात्मक अर्ध-निश्चित मैट्रिक्स का सेट है | सकारात्मक अर्ध-निश्चित मैट्रिक्स, और न्यूनतम अधिकतम से अधिकतम न्यूनतम के क्रम को बदलना (अधिक विवरण के लिए संदर्भ देखें), अनुकूलन समस्या को इस प्रकार तैयार किया जा सकता है:

$RCC=\max _{(\Delta ,x)\in {T}}\left\{-\left\|x\right\|^{2}+\operatorname {Tr} (\Delta )\right\}$

साथ

${T}=\left\{(\Delta ,x):f_{i}(\Delta ,x)\leq 0,0\leq i\leq k,\Delta \geq xx^{T}\right\}.$

इस अंतिम उत्तल अनुकूलन समस्या को रिलैक्स्ड चेबिशेव सेंटर (RCC) के रूप में जाना जाता है। आरसीसी में निम्नलिखित महत्वपूर्ण गुण हैं:

• आरसीसी सटीक चेबीशेव केंद्र के लिए ऊपरी सीमा है।
• आरसीसी अद्वितीय है।
• आरसीसी व्यवहार्य है।

कम से कम वर्ग बाधित

यह दिखाया जा सकता है कि सुप्रसिद्ध विवश न्यूनतम वर्ग (सीएलएस) समस्या चेबिशेव केंद्र का एक आरामदेह संस्करण है।

मूल सीएलएस समस्या को इस प्रकार तैयार किया जा सकता है:

${\hat {x}}_{CLS}=\operatorname {*} {\arg \min }_{x\in C}\left\|y-Ax\right\|^{2}$

साथ

${C}=\left\{x:f_{i}(x)=x^{T}Q_{i}x+2g_{i}^{T}x+d_{i}\leq 0,1\leq i\leq k\right\}$

$Q_{i}\geq 0,g_{i}\in R^{m},d_{i}\in R.$

यह दिखाया जा सकता है कि यह समस्या निम्नलिखित अनुकूलन समस्या के बराबर है:

$\max _{(\Delta ,{x})\in {V}}\left\{{-\left\|{x}\right\|^{2}+\operatorname {Tr} (\Delta )}\right\}$

साथ

$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 \leq 0,{\rm {{}\Delta \geq xx^{T}}}\\\end{array}}\right\}.$

कोई देख सकता है कि यह समस्या चेबीशेव केंद्र की छूट है (हालांकि ऊपर वर्णित आरसीसी से अलग है)।

आरसीसी बनाम सीएलएस

एक समाधान सेट $(x,\Delta )$ आरसीसी के लिए भी सीएलएस के लिए एक समाधान है, और इस प्रकार $T\in V$. इसका मतलब यह है कि सीएलएस अनुमान आरसीसी की तुलना में शिथिल छूट का समाधान है। इसलिए सीएलएस आरसीसी के लिए एक ऊपरी सीमा है, जो वास्तविक चेबिशेव केंद्र के लिए एक ऊपरी सीमा है।

मॉडलिंग की कमी

चूंकि आरसीसी और सीएलएस दोनों वास्तविक व्यवहार्यता सेट की छूट पर आधारित हैं $Q$, जिस रूप में $Q$ परिभाषित किया गया है इसके आराम से संस्करणों को प्रभावित करता है। यह निश्चित रूप से आरसीसी और सीएलएस आकलनकर्ताओं की गुणवत्ता को प्रभावित करता है। एक साधारण उदाहरण के रूप में रैखिक बॉक्स बाधाओं पर विचार करें:

$l\leq a^{T}x\leq u$

जिसे वैकल्पिक रूप से लिखा जा सकता है

$(a^{T}x-l)(a^{T}x-u)\leq 0.$

यह पता चला है कि पहला प्रतिनिधित्व दूसरे के लिए एक ऊपरी बाध्य अनुमानक के साथ परिणाम देता है, इसलिए इसका उपयोग करने से परिकलित अनुमानक की गुणवत्ता नाटकीय रूप से कम हो सकती है।

यह सरल उदाहरण हमें दिखाता है कि व्यवहार्यता क्षेत्र में छूट का उपयोग करते समय बाधाओं के निर्माण पर बहुत ध्यान दिया जाना चाहिए।

रैखिक प्रोग्रामिंग समस्या

इस समस्या को एक रेखीय प्रोग्रामिंग समस्या के रूप में तैयार किया जा सकता है, बशर्ते कि क्षेत्र Q सूक्ष्म रूप से कई हाइपरप्लेन का एक प्रतिच्छेदन हो। एक पॉलीटॉप, क्यू को निम्नानुसार परिभाषित किया गया है, तो इसे निम्न रैखिक कार्यक्रम के माध्यम से हल किया जा सकता है।

$Q=\{x\in R^{n}:Ax\leq b\}$

${\begin{aligned}&\max _{r,{\hat {x}}}&&r\\&{\text{s.t.}}&&a_{i}{\hat {x}}+\|a_{i}\|r\leq b_{i}\\&{\text{and}}&&r\geq 0\end{aligned}}$

यह भी देखें

• सीमा क्षेत्र
• सबसे छोटी-वृत्त समस्या
• परिबद्ध वृत्त (परिकेंद्र को ढकता है)
• केंद्र (ज्यामिति)
• केन्द्रक

संदर्भ

• 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).