Fermat-Weber Problem
给定 R n \mathbb{R}^n Rn中的 m m m个点: a 1 , ? ? , a m \mathbf{a}_{1},\cdots,\mathbf{a}_m a1,?,am,也叫做锚点
然后 m m m个权重 ω 1 , ? ? , ω m > 0 \omega_1,\cdots,\omega_m>0 ω1,?,ωm>0,找到一个点，使得加权距离最近，即 min x ∈ R n { f ( x ) = ∑ i = 1 m ω i ∥ x − a i ∥ } \min_{\mathbf{x}\in\mathbb{R}^n}\left\{f\left(\mathbf{x}\right)=\sum_{i=1}^{m}\omega_{i}\|\mathbf{x}-\mathbf{a}_{i}\|\right\} x∈Rnmin{ f(x)=i=1∑mωi∥x−ai∥} 求驻点 ∇ f ( x ) = 0 \nabla f\left(\mathbf{x}\right)=0 ∇f(x)=0 即 ∑ i = 1 m ω i x − a i ∥ x − a i ∥ = 0 \sum_{i=1}^{m}\omega_{i}\frac{\mathbf{x}-\mathbf{a}_i}{\|\mathbf{x}-\mathbf{a}_i\|}=0 i=1∑mωi∥x−ai∥x−ai=0 于是 x = 1 ∑ i = 1 m ω i ∥ x − a i ∥ ∑ i = 1 m ω i a i ∥ x − a i ∥ \mathbf{x}=\frac{1}{\sum_{i=1}^{m}\frac{\omega_{i}}{\|\mathbf{x}-\mathbf{a}_i\|}}\sum_{i=1}^{m}\frac{\omega_{i}\mathbf{a}_i}{\|\mathbf{x}-\mathbf{a}_i\|} x=∑i=1m∥x−ai∥ωi1i=1∑m∥x−ai∥ωiai 令 T ( x ) = 1 ∑ i = 1 m ω i ∥ x − a i ∥ ∑ i = 1 m ω i a i ∥ x − a i ∥ T\left(\mathbf{x}\right)=\frac{1}{\sum_{i=1}^{m}\frac{\omega_{i}}{\|\mathbf{x}-\mathbf{a}_i\|}}\sum_{i=1}^{m}\frac{\omega_{i}\mathbf{a}_i}{\|\mathbf{x}-\mathbf{a}_i\|} T(x)=∑i=1m∥x−ai∥ωi1i=1∑m∥x−ai∥ωiai 于是问题就转为 x = T ( x ) \mathbf{x}=T\left(\mathbf{x}\right) x=T(x) 这就是在找不动点 x k + 1 = T ( x k ) \mathbf{x}_{k+1}=T\left(\mathbf{x}_k\right) xk+1=T(xk)
Weiszfeld’s Method
初始化：选一个点 x 0 ∈ R n \mathbf{x}_0\in\mathbb{R}^n x0∈Rn,使得 x 0 ≠ a 1 , ⋯ , a m \mathbf{x}_0\neq \mathbf{a}_1,\cdots,\mathbf{a}_m x0=a1,⋯,am 步骤： x k + 1 = T ( x k ) = 1 ∑ i = 1 m ω i ∥ x k − a i ∥ ∑ i = 1 m ω i a i ∥ x k − a i ∥ \mathbf{x}_{k+1}=T\left(\mathbf{x}_{k}\right)=\frac{1}{\sum_{i=1}^{m} \frac{\omega_{i}}{\left\|\mathbf{x}_{k}-\mathbf{a}_{i}\right\|}} \sum_{i=1}^{m} \frac{\omega_{i} \mathbf{a}_{i}}{\left\|\mathbf{x}_{k}-\mathbf{a}_{i}\right\|} xk+1=T(xk)=∑i=1m∥xk−ai∥ωi1i=1∑m∥xk−ai∥ωiai
Weiszfeld’s Method是一个梯度方法，因为 x k + 1 = 1 ∑ i = 1 m ω i ∥ x k − a i ∥ ∑ i = 1 m ω i a i ∥ x k − a i ∥ = x k − 1 ∑ i = 1 m ω i ∥ x k − a i ∥ ∑ i = 1 m ω i x k − a i ∥ x k − a i ∥ = x k − 1 ∑ i = 1 m ω i ∥ x k − a i ∥ ∇ f ( x k ) \begin{aligned} \mathbf{x}_{k+1}&=\frac{1}{\sum_{i=1}^{m} \frac{\omega_{i}}{\left\|\mathbf{x}_{k}-\mathbf{a}_{i}\right\|}} \sum_{i=1}^{m} \frac{\omega_{i} \mathbf{a}_{i}}{\left\|\mathbf{x}_{k}-\mathbf{a}_{i}\right\|}\\ &=\mathbf{x}_{k}-\frac{1}{\sum_{i=1}^{m} \frac{\omega_{i}}{\left\|\mathbf{x}_{k}-\mathbf{a}_{i}\right\|}} \sum_{i=1}^{m} \omega_{i}\frac{ \mathbf{x}_{k}-\mathbf{a}_{i}}{\left\|\mathbf{x}_{k}-\mathbf{a}_{i}\right\|}\\ &=\mathbf{x}_{k}-\frac{1}{\sum_{i=1}^{m} \frac{\omega_{i}}{\left\|\mathbf{x}_{k}-\mathbf{a}_{i}\right\|}}\nabla f\left(\mathbf{x}_{k}\right) \end{aligned} xk+1=∑i=1m∥xk−ai∥ωi1i=1∑m 标签： weber传感器captor