点の集合を包含する球について

質問

n次元空間上に存在するm個の点を含む最小の球を非線形計画問題としてときたいのですがどうしてもわかりません。
Lagrange関数を用いて表すことでとけるようなのですが。。。
定式化さえできなくて困っているで助けてください。

回答No.4

hogehogeninja · ベストアンサー

Lagrange関数を使うとありますが、Lagrangeの未定乗数法を使うのではないでしょうか?
Lagrangeの未定乗数法というのは、制約条件のあるときに、関数の極値または鞍部を求める解法です。

解法の一部に「n+1≧lであるl個の点があり、球面上にこれらの点を含む球面のうち、最小のものを求めよ」という問題がでてきますが、それを解くのに使います。

------------------------------------------------------
未定乗数法とは、
「xがm個の制約条件
g1(x)=0,…,gm(x)=0
のもとで動くとき、
f(x)の極点（最大、最小の点）、鞍点はどこになるか」を求めるものです。

Lagrange関数を
L(x)=f(x)+λ1*g1(x)+…+λm*gm(x)
と定義し、
x1,…,xn, λ1,…,λmのn+m個の変数について偏微分し、0と等しいとします。
∂L(x)/∂x1 = 0
…
∂L(x)/∂xn = 0
∂L(x)/∂λ1 = 0
…
∂L(x)/∂λm = 0

これらn+m個の連立方程式によってn+m個の変数x1,…,xn, λ1,…,λmを解くと、
座標(x1,…,xn）がf(x)の極点／鞍点を与えます。

最小値を求めるには、その点が最小であるかどうか、さらに調べます。

λ1,…,λmを「未定乗数」といいます。

------------------------------------------------------
補題
「n+1≧kなるk個の点がそれぞれ座標X_1,X_2,…,X_kのk個のベクトルで与えられている。
このとき、ベクトルxがk-1個の制約条件
g_1(x) = |X_k-x|^2 - |X_1-x|^2 = 0,
…
g_k-1(x) = |X_k-x|^2 - |X_(k-1)-x|^2 = 0
を満たしながら動くとき、
f(x) = r^2 = |X_k-x|^2
の最小値を求めよ」

Lagrange関数は
L(x)=f(x)+λ_1*g1(x)+…+λ_(k-1)*g_(k-1)(x)
です。

未定乗数法で最小の点が求まります。

------------------------------------------------------------------

全体の解法のアルゴリズムとしては、

i)m個の点のうち、n+1≧k個の点を選び、補題によってこれらを球面上に含む最小の球をきめる。
もしm個のすべての点がこの球に内包されるなら、ok。（これらk個の点を含む最小のものであり、よって与えられたm個の点を含む最小のものである）
もしm個の点のうち、この球に含まれないものがあるのなら、球の中心からもっとも遠い点を加えたk+1個の点についてi)を繰り返す。

ii)初期として、l=2、m個の点のうち、もっとも遠い２点を選びだし、i)を行う。

-------------------------------------------------------------------

概略だけですが、参考になったらと思います。

参考URL：

http://dsl4.eee.u-ryukyu.ac.jp/DOCS/nlp/node7.html

お礼

おーめっちゃくちゃ詳細ですね!!
感動しました。ありがとうございます。
参考にしてやらせていただきます。

回答No.3

mcq

解けるかどうかは別として、
定式化は出来そうな気もします。

min Ｒ
subject to |ｒi-ｒ0| ≦ Ｒ (i=1,2,…,m)
ただし、ｒiはi番目の点の座標を表すｎ次元のベクトル
ｒ0は中心点の座標を表すｎ次元のベクトル

ベクトルを使わずに書けば、
min Ｒ
subject to Σ{j=1～n}(ｘij-ｘ0j)^2 ≦ Ｒ^2 (i=1,2,…,m)
ただし、ｒijはi番目の点の第j座標
ｒ0jは中心点の第j座標

お礼

ありがとうございます。参考になりました。

回答No.2

BLUEPIXY

すいません、＃１は間違いです。

お礼

わかりました。有り難う御座います。

回答No.1

BLUEPIXY

単純に２点間の距離が一番遠いものを直径とする球では、
計算量が多すぎますか？