ช่วงกลางผ่าน minimax

Sep 11 2020

_{คำเตือน: crossposted at Mathematics SE.}

ให้เวกเตอร์ ${\rm a} \in \Bbb R^n$,

$$\begin{array}{ll} \displaystyle\arg\min_{x \in {\Bbb R}} & \left\| x {\Bbb 1}_n - {\rm a} \right\|_2^2\end{array} = \frac1n {\Bbb 1}_n^\top {\rm a} \tag{mean}$$

คือค่าเฉลี่ย (เลขคณิต) ของรายการเวกเตอร์${\rm a} \in \Bbb R^n$ในขณะที่

$$\begin{array}{ll} \displaystyle\arg\min_{x \in {\Bbb R}} & \left\| x {\Bbb 1}_n - {\rm a} \right\|_1\end{array} \tag{median}$$

คือค่ามัธยฐานของรายการของเวกเตอร์${\rm a} \in \Bbb R^n$. ใช้$\infty$- บรรทัดฐานแทนสิ่งต่อไปนี้คืออะไร?

$$\color{blue}{\boxed{\,\\\begin{array}{ll} \displaystyle\arg\min_{x \in {\Bbb R}} & \left\| x {\Bbb 1}_n - {\rm a} \right\|_{\infty}\end{array}}}$$

มันดูเหมือนจะเป็นช่วงกลางเดือน ฉันผนวกหลักฐานตามโปรแกรมเชิงเส้น สมมติว่าผมได้ทำผิดพลาดและไม่มีหลักฐานของฉันถูกต้องแน่นอนผมสนใจอื่น ๆ ในการพิสูจน์และการอ้างอิง

หลักฐานของฉัน

$$\begin{array}{ll} \underset{x \in {\Bbb R}}{\text{minimize}} & \left\| x {\Bbb 1}_n - {\rm a} \right\|_{\infty}\end{array} $$

แนะนำตัวแปรการเพิ่มประสิทธิภาพ $y \in {\Bbb R}$,

$$\begin{array}{ll} \underset{x, y \in {\Bbb R}}{\text{minimize}} & \qquad\qquad y\\ \text{subject to} & -y {\Bbb 1}_n \leq x {\Bbb 1}_n - {\rm a} \leq y {\Bbb 1}_n\end{array} $$

หรืออีกทางหนึ่งคือ

$$\begin{array}{lrl} \underset{x, y \in {\Bbb R}}{\text{minimize}} & y & \\ \text{subject to} & {\rm a} & \leq (x + y) {\Bbb 1}_n \\ & (x - y) {\Bbb 1}_n & \leq {\rm a}\end{array}$$

ให้รายการของเวกเตอร์ ${\rm a} \in \Bbb R^n$ แสดงโดย $a_1, a_2, \dots, a_n$. โปรดทราบว่ามีอสมการซ้ำซ้อนมากมาย:

ชุดของ $n$ อสมการ ${\rm a} \leq (x + y) {\Bbb 1}_n$ สามารถแทนที่ได้ด้วย $$x + y \geq \max \{ a_1, a_2, \dots, a_n \}$$
ชุดของ $n$ อสมการ $(x - y) {\Bbb 1}_n \leq {\rm a}$ สามารถแทนที่ได้ด้วย $$x - y \leq \min \{ a_1, a_2, \dots, a_n \}$$

ดังนั้น

$$\begin{array}{ll} \displaystyle\arg\min_{x \in {\Bbb R}} & \left\| x {\Bbb 1}_n - {\rm a} \right\|_{\infty}\end{array} = \color{blue}{\frac{ \min \{ a_1, a_2, \dots, a_n \} + \max \{ a_1, a_2, \dots, a_n \} }{2}}$$

บางคนเรียกค่านี้ว่าช่วงกลางของ$\{ a_1, a_2, \dots, a_n \}$.

คำตอบ

3 whuber Sep 18 2020 at 00:55

1. การสาธิตแบบกราฟิก

ส่วนประกอบของเวกเตอร์ $a$ แสดงด้วยเห็บสีน้ำเงิน ("พล็อตพรม") $\tilde m$คือระดับกลาง มันเกิดขึ้นที่ค่าต่ำสุดที่เป็นไปได้ของซองด้านบนของกราฟของฟังก์ชันระยะทาง$x\to |x-a_i|,$ แสดงเป็นสีแดง

2. การสาธิตระดับประถมศึกษาโดยใช้คุณสมบัติของจำนวน

การสาธิตนี้อธิบายกราฟอย่างเคร่งครัดโดยชี้ให้เห็นว่าซองจดหมายสีแดงส่วนบนประกอบด้วยแขนสองข้างที่เอียงมาบรรจบกันที่เสียงกลาง

ก่อนอื่นมาตั้งค่าสัญกรณ์กันก่อน

ฟังก์ชันวัตถุประสงค์นี้คือระยะห่างสูงสุดระหว่างจำนวน $x$ และชุดส่วนประกอบของ $a$(ส่วนย่อยของจำนวนจริง) เขียน$a_1$ สำหรับส่วนประกอบเหล่านั้นอย่างน้อยที่สุดและ $a_n$เพื่อสิ่งที่ยิ่งใหญ่ที่สุด ปล่อย$\tilde m = (a_1+a_n)/2$ เป็นระดับกลางซึ่งระยะทางสูงสุดคือ $r = (a_n-a_1)/2.$