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

ज्यामिति में, परिबद्ध समुच्चय का चेबीशेव केंद्र मुख्य रूप से $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).