剛體幾何中位數

Question

我需要實現一個適用於剛體的「幾何中值」型算法，這意味着它不僅可以找到一個最小化距離一組點的距離的點，而且還會考慮到身體的方向。我還沒有找到解決這類問題的辦法，而對於幾何中位數（或韋伯或費馬托裏利問題或設施位置問題），有很多信息可用，包括Weiszfeld算法（和現代改進）。我希望有人會提及可能的解決方案。我會認爲這是一個相對常見的問題在註冊，但也許我只是沒有找到合適的詞搜索...

我的問題可以公式化如下：說我有一個「參考」剛體與3個非共線點（一個三角形），我測量了3次點的座標（有一些錯誤，或者物體移動了一點）。我想找到一個好的「中心位置」，這樣可以最小化每個測量點與其相應的中心位置對象點之間的距離總和（非平方距離）。這相當於「多設施選址問題」，但是「設施」之間的固定距離有額外的限制，並且每個點預先分配給一個設施（不一定是最近的一個）。

實際上，我在考慮不是最小化所有點的總和，而只是爲每次測量保留3點的最大距離。 （那就是所謂的「極大極小」？）但我認爲這不會對我必須使用的算法類型產生很大的影響。

與幾何中位數相比，一個可能的困難可能是隨着旋轉的自由度增加，要最小化的量不再是凸的（不是100％確定，但我認爲）。我希望我仍然可以使用與Weiszfeld（這是次梯度方法）類似的算法，並且希望以前已經對此進行了調查。謝謝你的幫助！

P.S.我將在Matlab中完成這項工作。

Answer 1

我在這個問題上找不到任何研究。我要做的第一件事就是使用沒有剛度約束的Weiszfeld算法來找到各個點的幾何中值，定義對應於對象邊緣與期望值偏差的拉格朗日乘子，並使用梯度下降找到約束局部最小值。我無法證明它始終有效，但直觀地說，只要偏差足夠小，就應該這樣做。