兩個多邊形/多面體的最佳近似對

Question

R^3中有兩個多面體A和B，具有空的交點。多面體是由它的面來定義的，即它的超空間只有不等式，頂點是未知的。問題是找到A中的點a和B中的b，使得|| a-b || = d（A，B） - A和B之間的距離。當d> 3時，我們也可以爲R^2或R^d提出這個問題。這個問題的方法是什麼。這個問題有一些應用嗎？

Answer 1

This paper闡述了找出兩個通用凸集之間距離的問題。

他們繼續並提供大量的應用程序，包括兩個凸多面體之間的距離。兩個多面體之間的最小距離是尋找最大分離超平面的對偶。他們提供這個問題的表述，並顯示爲一個實現Gordan's Theorem of Alternatives的證明。公式（11.1）提供了你所要求的公式，但需要一些操作來將多面體帶到這種形式。根據選定的標準，問題可以重新排列爲線性（L1標準），二次（L2標準）或通用程序。

另外，其中所給出的參考文獻（關於找到多面體中最近的點）是相關的。

摘要：

在本文中，我們探索表徵至少 規範問題，對偶關係。本文首先介紹了一個新的最小規範 對偶（MND）定理，它考慮了兩個凸集之間的距離。粗略地說，新定理說，兩組之間的最短距離等於組之間的最大「分離」 ，其中術語「分離」是指分離兩組的平行超平面之間的距離 。

本文的第二部分介紹了幾個應用實例。 這些例子教授關於雙重性在至少 規範問題中的作用的寶貴經驗，並揭示這些問題的新特徵。一課 揭示極性分解，其表徵線性不等式的不一致系統的「解決方案」的特徵。另一個教訓揭示了MND定理，替代定理，最速下降方向和建構性最優性條件之間的密切聯繫。

我希望這有助於！