Weber問題

1. 三角不等式から $f(x)\ge\sum_iw_i(\lvert x\rvert-\lvert a_i\rvert)=W\lvert x\rvert-C$（$C:=\sum_iw_i\lvert a_i\rvert$）である。$R:=(f(a_1)+C)/W$ とすると、$\lvert x\rvert>R$ なら $f(x)>f(a_1)$ である。連続関数 $f$ は有界閉集合 $\{\lvert x\rvert\le R\}$ で最小値をとり、それが全体の最小値である。最小値を $f^\ast$ とすると、最小点の全体 $\{f\le f^\ast\}$ は凸関数の下位集合なので凸で、連続性から閉じていて、$R$ の球に含まれる。
2. 最小点 $x\ne y$ があるとする。$x,y$ を通る直線 $\{x+s(y-x)\}$ の上にない母点 $a_j$ がある。$a_j$ からこの直線までの距離を $h>0$、直線の上で $a_j$ に最も近い点のパラメータを $s_j$ とすると、$\lvert x+s(y-x)-a_j\rvert=\sqrt{\lvert y-x\rvert^2(s-s_j)^2+h^2}$ で、これは $s$ の関数として 2 階導関数 $\lvert y-x\rvert^2h^2/(\cdots)^{3/2}>0$ をもち、狭義凸である。よって $f(\frac{x+y}2)<\frac12f(x)+\frac12f(y)=f^\ast$ となり矛盾する。
3. 要点：$L$ への正射影で距離はすべて縮むので最小点は $L$ の上にあり、$L$ の上では片側微分係数の符号で判定する。
   詳しい証明を開く

   $x\notin L$ の $L$ への正射影を $x'$ とすると、三平方の定理から $\lvert x'-a_i\rvert^2=\lvert x-a_i\rvert^2-\lvert x-x'\rvert^2<\lvert x-a_i\rvert^2$ なので $f(x')< f(x)$ で、$x$ は最小点でない。$L$ の上では $\varphi(t):=f(p+tv)=\sum_iw_i\lvert t-t_i\rvert$ で、右微分係数・左微分係数は

   $$\varphi'_+(t)=\sum_{t_i\le t}w_i-\sum_{t_i>t}w_i,\qquad\varphi'_-(t)=\sum_{t_i< t}w_i-\sum_{t_i\ge t}w_i$$

   である。凸関数 $\varphi$ について、$t$ が最小点であることは $\varphi'_-(t)\le0\le\varphi'_+(t)$ と同値である（凸関数 の定理「開区間上の凸関数の連続性と片側微分」と、傾きの単調性による）。$\varphi'_+(t)\ge0$ は $\sum_{t_i>t}w_i\le\frac W2$、$\varphi'_-(t)\le0$ は $\sum_{t_i< t}w_i\le\frac W2$ と同値である。最小点の全体は (1) により $L$ の上の有界閉凸集合、つまり 1 点か線分である。$\square$

段 1（方向微分係数）。$x,v\in\mathbb{R}^d$ について $f'(x;v):=\lim_{s\to+0}\frac{f(x+sv)-f(x)}{s}$ を計算する。$a\ne x$ なら $s\mapsto\lvert x+sv-a\rvert=\sqrt{\lvert x-a\rvert^2+2s\langle x-a,v\rangle+s^2\lvert v\rvert^2}$ は $s=0$ で微分でき、微分係数は $\frac{\langle x-a,v\rangle}{\lvert x-a\rvert}$ である。$a=x$ なら $\frac{\lvert sv\rvert}{s}=\lvert v\rvert$ である。足し合わせて
$$ f'(x;v)=\langle G(x),v\rangle+w(x)\lvert v\rvert $$
を得る。ここで $w(x)$ は、$x$ が母点 $a_k$ なら $w_k$、母点でなければ $0$ とする（母点は相異なるので高々 1 つ）。
段 2（最小 ⇔ 方向微分係数が非負）。$x$ が最小点なら、$f(x+sv)-f(x)\ge0$ を $s>0$ で割って極限をとり $f'(x;v)\ge0$ である。逆に、すべての $v$ で $f'(x;v)\ge0$ とする。$y\in\mathbb{R}^d$ をとり $v:=y-x$、$\varphi(s):=f(x+sv)$ とおくと、$\varphi$ は凸なので $\frac{\varphi(s)-\varphi(0)}{s}$ は $s>0$ について単調非減少である（凸関数 の命題「凸関数の傾きの単調性」）。よって
$$ f(y)-f(x)=\frac{\varphi(1)-\varphi(0)}{1}\ge\lim_{s\to+0}\frac{\varphi(s)-\varphi(0)}{s}=f'(x;v)\ge0 $$
で、$x$ は最小点である。
段 3（条件の書き換え）。$\lvert v\rvert=1$ の $v$ について $\langle G(x),v\rangle\ge-\lvert G(x)\rvert$ で、$G(x)\ne0$ なら $v=-G(x)/\lvert G(x)\rvert$ で等号が成り立つ。$v$ を正の数 $c$ 倍すると $f'(x;v)$ も $c$ 倍になるので、「すべての $v$ で $f'(x;v)\ge0$」は「$\lvert v\rvert=1$ のすべての $v$ で $f'(x;v)\ge0$」と同じで、これは
$$ w(x)-\lvert G(x)\rvert\ge0 $$
と同値である。$x$ が母点でなければ $w(x)=0$ なので $G(x)=0$、$x=a_k$ なら $\lvert G(a_k)\rvert\le w_k$ である。段 2 と合わせて定理を得る。$\square$

$\lvert G(a_k)\rvert\le\sum_{i\ne k}w_i=W-w_k\le w_k$ なので、thm-wbp-main の 2 による。$\square$

$\delta_i:=\lvert x-a_i\rvert>0$ とおく。
(1) $\lambda(x)(\Phi(x)-x)=\sum_i\frac{w_i}{\delta_i}(a_i-x)=-G(x)$ である。$x$ は母点でないので、thm-wbp-main の 1 から後半を得る。
(2) $y$ の関数
$$ g(y):=\sum_i\frac{w_i}{\delta_i}\lvert y-a_i\rvert^2=\lambda(x)\lvert y\rvert^2-2\Bigl\langle y,\sum_i\frac{w_i}{\delta_i}a_i\Bigr\rangle+\sum_i\frac{w_i}{\delta_i}\lvert a_i\rvert^2=\lambda(x)\lvert y-\Phi(x)\rvert^2+(\text{定数}) $$
は $y=\Phi(x)$ でただ 1 つの最小をとる。$g(x)=\sum_iw_i\delta_i=f(x)$ なので、$g(\Phi(x))\le f(x)$ で、$\Phi(x)\ne x$ なら $g(\Phi(x))< f(x)$ である。$e_i:=\lvert\Phi(x)-a_i\rvert$ とおくと、Cauchy–Schwarzの不等式 により
$$ f(\Phi(x))=\sum_i\sqrt{\frac{w_i}{\delta_i}}e_i\cdot\sqrt{w_i\delta_i}\le\Bigl(\sum_i\frac{w_i}{\delta_i}e_i^2\Bigr)^{1/2}\Bigl(\sum_iw_i\delta_i\Bigr)^{1/2}=\sqrt{g(\Phi(x))\,f(x)}\le f(x) $$
である。$\Phi(x)\ne x$ なら最後の不等号は $f(x)>0$ と $g(\Phi(x))< f(x)$ により狭義である。$\square$