最適化・線形計画法の問題

制約を具体的に書くと、各 $i$ について $-t\le y_i-a-b{x}_i\le t$ である。

下界を作る（双対的な考え方）

制約のうち次の 3 つに注目する。
- $i=1$（点 $(0,0)$）の $0-a\ge -t$ より $a\le t(1)$
- $i=2$（点 $(1,4)$）の $4-a-b\le t(2)$
- $i=3$（点 $(3,2)$）の $2-a-3b\ge -t$ より $a+3b-2\le t(3)$

$a,b$ が消えるように、非負の重み ${\lambda }_1,{\lambda }_2,{\lambda }_3$（和は $1$）を選んで $(1),(2),(3)$ を足し合わせる。$a$ の係数 ${\lambda }_1-{\lambda }_2+{\lambda }_3=0$、$b$ の係数 $-{\lambda }_2+3{\lambda }_3=0$、${\lambda }_1+{\lambda }_2+{\lambda }_3=1$ を解くと
$${\lambda }_1=\frac{1}{3},{\lambda }_2=\frac{1}{2},{\lambda }_3=\frac{1}{6}.$$
これらはすべて正なので、不等式の向きを保ったまま足せて
$$\frac{1}{3}a+\frac{1}{2}(4-a-b)+\frac{1}{6}(a+3b-2)\le t.$$
左辺は $a\left(\frac{1}{3}-\frac{1}{2}+\frac{1}{6}\right)+b\left(-\frac{1}{2}+\frac{1}{2}\right)+2-\frac{1}{3}=\frac{5}{3}$ となるので、任意の実行可能解について
$$t\ge \frac{5}{3}.$$

下界を達成する解

$t=\frac{5}{3}$ となるには、重みがすべて正なので $(1),(2),(3)$ がすべて等号で成り立つ必要がある。
$$a=\frac{5}{3},4-a-b=\frac{5}{3},a+3b-2=\frac{5}{3}.$$
第 1 式から $a=\frac{5}{3}$、第 2 式から $b=4-\frac{5}{3}-\frac{5}{3}=\frac{2}{3}$。このとき第 3 式は $\frac{5}{3}+2-2=\frac{5}{3}$ で成り立つ。よって $t=\frac{5}{3}$ を与える $(a,b)$ は $\left(\frac{5}{3},\frac{2}{3}\right)$ しかない。

実行可能性の確認

$(a,b,t)=\left(\frac{5}{3},\frac{2}{3},\frac{5}{3}\right)$ のとき、残差 $y_i-a-b{x}_i$ は
- $i=1$: $0-\frac{5}{3}=-\frac{5}{3}$
- $i=2$: $4-\frac{5}{3}-\frac{2}{3}=\frac{5}{3}$
- $i=3$: $2-\frac{5}{3}-2=-\frac{5}{3}$
- $i=4$: $6-\frac{5}{3}-\frac{8}{3}=\frac{5}{3}$

となり、すべて $-\frac{5}{3}$ 以上 $\frac{5}{3}$ 以下なので制約を満たす（残差の符号が $-,+,-,+$ と交互に最大値をとっている）。

以上より、最適値は $\frac{5}{3}$、最適解はただ一つで
$$(a,b,t)=\left(\frac{5}{3},\frac{2}{3},\frac{5}{3}\right).$$

チェビシェフ近似の最適性条件(等振動)を使う。残差を $r_i=y_i-a-b{x}_i$ とする。3点で符号が交互になり、絶対値が $t$ に等しい直線を求める。

点 1, 2, 3 を選び、$r_1=-t,r_2=+t,r_3=-t$ とおくと、
- $-a=-t$ より $a=t$
- $4-a-b=t$ より $b=4-2t$
- $2-a-3b=-t$ より $2-t-12+6t=-t$ なので $6t=10$

よって $t=5/3$、$a=5/3$、$b=2/3$ となる。

検算として、直線 $y=5/3+(2/3)x$ の残差を全点で計算する。
- $x=0$: $0-5/3=-5/3$
- $x=1$: $4-7/3=5/3$
- $x=3$: $2-11/3=-5/3$
- $x=4$: $6-13/3=5/3$

全点で $|r_i|\le 5/3$ となり、実行可能である。符号は $-,+,-,+$ と交互になる。

最適性は双対(等振動)で確かめられる。3点 1, 2, 3 で符号が交互なので、$\sum {\lambda }_i{r}_i$ の係数 $\lambda$ を $\sum {\lambda }_i=0,\sum {\lambda }_i{x}_i=0$ を満たす形で取れる。具体的には $\lambda \propto (3,-\mathrm{4...})$ ではなく、${\lambda }_1+{\lambda }_2+{\lambda }_3=0$ かつ ${\lambda }_2+3{\lambda }_3=0$ より $\lambda =(2,-3,1)$ である。符号 $(-,+,-)$ と $\lambda$ の符号 $(+,-,+)$ が逆なので、$\sum |{\lambda }_i||r_i|$ の形で下界 $t\ge 5/3$ が得られる。したがって $t=5/3$ が最小値である。

一意性は問題文で保証されている。

答え: $(a,b,t)=(5/3,2/3,5/3)$