مركز تشيبيشيف

في الهندسة ، مركز تشيبيشيف لمجموعة محدودة${\displaystyle Q}$إن وجود مساحة داخلية غير فارغة يمكن أن يعني شيئين مختلفين: ^{[ 1 ]}

• يمكن أن يكون مركز الكرة ذات نصف القطر الأدنى التي تحيط بالمجموعة بأكملها${\displaystyle Q}$، أو
• يمكن أن يكون مركز أكبر كرة منقوشة من${\displaystyle Q}$.

ولإثبات أن هذين الأمرين غير متكافئين، يكفي أن ننظر إلى ما يلي:${\displaystyle Q}$المثلث الذي يكون فيه أحد أضلاعه أقصر بكثير من الضلعين الآخرين؛ يقع مركز تشيبيشيف المغلق بالقرب من منتصف الضلعين الطويلين، بينما يقع مركز تشيبيشيف المحيط بالقرب من الضلع القصير، حيث يكون المثلث أكثر سمكًا. تتناول هذه المقالة بشكل أساسي مركز تشيبيشيف المغلق.

في مجال تقدير المعلمات ، تحاول طريقة مركز تشيبيشيف إيجاد مُقدِّر${\displaystyle {\hat {x}}}$ل${\displaystyle x}$بالنظر إلى مجموعة الجدوى${\displaystyle Q}$بحيث${\displaystyle {\hat {x}}}$يقلل هذا من أسوأ خطأ تقديري ممكن لـ x (أي أفضل حالة أسوأ). وهذا يكافئ نوع مركز تشيبيشيف المحيط.

توجد عدة تمثيلات بديلة لمركز تشيبيشيف. لننظر إلى المجموعة${\displaystyle Q}$ويرمز إلى مركز تشيبيشيف الخاص به بـ${\displaystyle {\hat {x}}}$.${\displaystyle {\hat {x}}}$يمكن حسابها عن طريق حل:

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

فيما يتعلق بالمعيار الإقليدي${\displaystyle \|\cdot \|}$أو بدلاً من ذلك عن طريق حل ما يلي:

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

على الرغم من هذه الخصائص، قد يكون إيجاد مركز تشيبيشيف مسألة تحسين عددي صعبة . على سبيل المثال، في التمثيل الثاني أعلاه، تكون عملية التعظيم الداخلية غير محدبة إذا لم تكن المجموعة Q محدبة .

في فضاءات الضرب الداخلي والفضاءات ثنائية الأبعاد، إذا${\displaystyle Q}$إذا كانت المنطقة مغلقة ومحدودة ومحدبة، فإن مركز تشيبيشيف يقع فيها.${\displaystyle Q}$بمعنى آخر، يمكن إجراء البحث عن مركز تشيبيشيف في الداخل${\displaystyle Q}$دون الإخلال بعمومية الموضوع . ^{[ 2 ]}

في أماكن أخرى، قد لا يكون مركز تشيبيشيف موجودًا ${\displaystyle Q}$حتى لو ${\displaystyle Q}$محدب. على سبيل المثال، إذا${\displaystyle Q}$هل هو رباعي الأوجه المتكون من الغلاف المحدب للنقاط (1,1,1)، (-1,1,1)، (1,-1,1)، و(1,1,-1)؟ ثم حساب مركز تشيبيشيف باستخدام${\displaystyle \ell _{\infty }}$ينتج المعيار ^{[ 3 ]}

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

لنفترض الحالة التي تكون فيها المجموعة${\displaystyle Q}$يمكن تمثيلها على أنها تقاطع${\displaystyle k}$الأشكال الإهليلجية.

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

مع

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

عن طريق إدخال متغير مصفوفة إضافي${\displaystyle \Delta =xx^{T}}$يمكننا كتابة مسألة التعظيم الداخلي لمركز تشيبيشيف على النحو التالي:

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

أين${\displaystyle \operatorname {Tr} (\cdot )}$هو عامل التتبع و

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

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

تخفيف مطالبنا بشأن${\displaystyle \Delta }$من خلال المطالبة${\displaystyle \Delta \geq xx^{T}}$، أي${\displaystyle \Delta -xx^{T}\in S_{+}}$أين${\displaystyle S_{+}}$هي مجموعة المصفوفات شبه المحددة الموجبة ، وبتغيير ترتيب min max إلى max min (انظر المراجع لمزيد من التفاصيل)، يمكن صياغة مشكلة التحسين على النحو التالي:

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

مع

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

تُعرف مسألة التحسين المحدب الأخيرة هذه باسم مركز تشيبيشيف المُرخى (RCC). يتميز مركز تشيبيشيف المُرخى بالخصائص المهمة التالية:

• يمثل RCC حدًا أعلى لمركز تشيبيشيف الدقيق.
• مركز الأبحاث السريرية فريد من نوعه.
• إن إنشاء مركز التحكم في الإنشاءات أمر ممكن.

يمكن إثبات أن مشكلة المربعات الصغرى المقيدة المعروفة (CLS) هي نسخة مخففة من مركز تشيبيشيف.

يمكن صياغة مشكلة CLS الأصلية على النحو التالي:

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

مع

${\displaystyle {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\}}$

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

يمكن إثبات أن هذه المشكلة تعادل مشكلة التحسين التالية:

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

مع

${\displaystyle 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\}.}$

يمكن للمرء أن يرى أن هذه المشكلة هي تخفيف لمركز تشيبيشيف (على الرغم من أنها تختلف عن مركز RCC الموصوف أعلاه).

مجموعة حلول${\displaystyle (x,\Delta )}$يُعدّ مركز التحكم في الاحتراق (RCC) حلاً أيضاً لنظام التحكم في الاحتراق (CLS)، وبالتالي${\displaystyle T\in V}$هذا يعني أن تقدير CLS هو حل لتقريب أقل صرامة من تقريب RCC. وبالتالي، فإن CLS يمثل حدًا أعلى لـ RCC ، والذي بدوره يمثل حدًا أعلى لمركز تشيبيشيف الحقيقي.

بما أن كلاً من RCC و CLS يعتمدان على تخفيف مجموعة الجدوى الحقيقية${\displaystyle Q}$، الشكل الذي${\displaystyle Q}$يؤثر تعريفها على صيغها المُخففة. وهذا بدوره يؤثر على جودة مُقدِّرات RCC وCLS. كمثال بسيط، لنأخذ قيود الصندوق الخطية:

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

والتي يمكن كتابتها أيضاً على النحو التالي

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

اتضح أن التمثيل الأول ينتج عنه مقدر ذو حد أعلى للتمثيل الثاني، وبالتالي فإن استخدامه قد يقلل بشكل كبير من جودة المقدر المحسوب.

يوضح لنا هذا المثال البسيط أنه ينبغي إيلاء عناية كبيرة لصياغة القيود عند استخدام تخفيف منطقة الجدوى.

يمكن صياغة الشكل الداخلي لمسألة مركز تشيبيشيف كمسألة برمجة خطية ، بشرط أن تكون المنطقة${\displaystyle Q}$هو تقاطع عدد محدود من أنصاف الفضاءات . ^{[ 4 ]} بالنظر إلى متعدد السطوح${\displaystyle Q=\{x\in \mathbb {R} ^{n}:Ax\leq b\}}$يمكن الوصول إلى مركز تشيبيشيف عبر البرنامج الخطي التالي. $${\displaystyle {\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}}}$$ الفكرة هي أن${\displaystyle r}$نصف قطر كرة محاطة بنقطة منتصف${\displaystyle {\hat {x}}}$.

• YC 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 YC Eldar, “Regularization in Regression with Bounded Noise: A Chebyshev Center Approach,” SIAM J. Matrix Anal. Appl. 29 (2): 606–625 (2007).