볼록 선체의 극점 검출을위한 선형 프로그램

Question

임의의 점 x [j] ∈ X (X = {x1, ..., xn} ⊂ Rn인지 여부를 알려주는 선형 프로그램을 어떻게 공식화 할 수 있습니까? X의 convex hull의 극점, 즉 conv (X)입니까?

이 선형 프로그램의 해법에 따르면 우리는 '그렇습니다, x [j]는 극한점입니다'또는 '아니오'라고 주장 할 수 있어야합니다.

글쎄, 나는 내 마음 속에했습니다 어떤 그 같은 것입니다 :

{min: 0} s.t. x[ j ] = Σi (a[ i ] * x[ i ]); i ∈ {1, ... ,k}, ∀ j ∈ {1, ... ,k}

만약 이러한 [내가]의 존재, X [J]를 의미 다른 X 년대의 선형 조합, 이것은 극한의 정의에 대한 위반처럼 보입니다.

그러나이 LP가 전체적인 맥락을 다루지는 않는다고 생각합니다. 즉, conv (X) 안에 있고 (가장자리가 아닌) x [j]를 선택하면 다른 것들의 선형 조합이 아닙니다. 그러면 모델은 잘못된 결과를 낳을 것입니다. 그것은 위의 모델, 괜찮을 것입니다 iff 선택된 x [j]는 conv (X)의 가장자리에 선다.

감사합니다.

Answer 1

아주 가까이 있습니다. 포인트는이 포인트의 볼록한 조합으로 쓰여질 수있는 경우에만 convex hull of a finite set of points에 속합니다. 또한 점은 그것들의 볼록한 조합으로 쓰여질 수있는 두 개의 다른 점이없는 경우에만 극단 점입니다.

관심 지점을 x_k로합시다. 그런 다음, 다음과 같은 선형 프로그램은 일을 할 것입니다 :

을 X_ {IK가}이 (포인트 k)를 검사 할 점의 좌표 번째 i입니다. 이 점은 방정식의 오른쪽에 포함 된 점 중 하나 여야합니다 (즉, 문제는 항상 lambda_k = 1이고 다른 모든 람다는 0과 같음).

If 그 점이 극단적 인 점이면, 얻을 수있는 유일한 해결책은 lambda_k = 1, 다른 lambda = 0입니다. 그렇지 않으면 다른 솔루션 (작은 lambda_k)이 나타납니다.

(문제 설명 모두에서 점의 수와 차원은 n입니다. 따라서 해당 색인 (j 및 i)은 1에서 n까지입니다.

나는 희망합니다. 도움이됩니다!