2 개의 다각형/폴리 토프에 대한 최적 근사 쌍

Question

빈 교차점을 갖는 R^3에는 두 개의 폴리 토프 A와 B가 있습니다. 폴리 토프는 그면에 의해 정의된다. 즉, 하이퍼 스페이스에 대한 부등식 만 있고, 정점은 알려지지 않았다. 문제는 B에서 A와 B의 점을 찾아서 || a-b || = d (A, B) - A와 B 사이의 거리. 또한 d> 3에 대해 R^2 또는 R^d에 대해이 문제를 공식화 할 수 있습니다. 이 문제에 대한 접근 방법은 무엇입니까? 그리고이 문제는 응용 프로그램을 가지고 있습니까?

Answer 1

This paper은 두 개의 일반적인 볼록 세트 사이의 거리를 찾는 문제를 공식화합니다.

두 개의 convex polytopes 사이의 거리를 포함하여 많은 응용 프로그램을 제공합니다. 두 개의 폴리 토프 사이의 최소 거리는 최대 분리 초평면을 찾는 이중입니다. 그들은이 문제의 공식을 제공하고 Gordan's Theorem of Alternatives이라는 증명을 구현으로 보여줍니다. 당신이 요구하는 공식을 제공하는 것은 공식 (11.1)이지만, polytopes를 그 형태로 가져 오기 위해서는 몇 가지 조작이 필요합니다. 선택한 표준에 따라 문제는 선형 (L1 놈), 2 차 (L2 놈) 또는 일반 프로그램으로 재 작성 될 수 있습니다.

또한 관련 문헌 (폴리 토프에서 가장 가까운 점을 찾음)을 참조하십시오.

초록 :이 논문에서는

우리는 적어도 규범 문제를 특징 짓는 이중성의 관계를 탐구한다. 이 논문은 새로운 최소 표준 인 이중성 (MND) 정리를 제시함으로써 시작됩니다.이 정리는 두 개의 볼록 세트 사이의 거리를 고려합니다. 대충 말해서 새로운 정리에 따르면 두 세트 사이의 가장 짧은 거리는 두 세트 사이의 최대 "분리" 과 같습니다. "분리"라는 용어는 두 세트를 분리하는 한 쌍의 평행 한 초평면 사이의 거리를 의미합니다 .

두 번째 부분에서는 여러 가지 응용 프로그램 예제를 제공합니다. 예제는 최소한 표준 문제에서 이원성의 역할에 대한 중요한 교훈을 가르치고 이러한 문제의 새로운 특징을 밝힙니다. 한 교훈 은 의 "해"를 특징 짓는 극성 분해를 일관성없는 선형 부등식 시스템에 노출합니다. 또 다른 교훈은 MND 정리, 대안의 정리, 가파른 하강 방향 및 건설적인 최적 조건 사이의 밀접한 관계를 보여줍니다.

이 정보가 도움이 되었기를 바랍니다.