다면체가 엄격한 제약 조건의 행렬을 사용하여 선을 포함하지 않는 경우에만 극단 점을 포함 함을 증명
나는 다면체가 $P = \{x\in\mathbb{R}^n\;:\;Ax\leq b\}$ 선을 포함하지 않는 경우에만 극단적 인 지점이 있지만 특정 방식으로 그렇게하고 싶습니다 (유도에 의한 증명을 알고 있습니다 $n$이것은 닫힌 볼록 세트에 대해이 결과를 일반화하지만 여기에서 증명에 대해 가고 싶은 방법이 아닙니다.) 특히 다음과 같은 결과를 활용하고 싶습니다.
$x$ 의 극단적 인 지점입니다 $P$ 경우에만 $\text{rank}(A^=) = n$, 어디 $A^=$ 타이트 / 액티브 제약의 매트릭스 $x$.
나는 이미 증명하는 방법을 알고 있습니다. $P$ 다음 줄을 포함 $P$극단적 인 점은 없지만 내 질문은 그 반대에 관한 것입니다. 비공식적 인 증거 스케치가 있지만이를 엄격하게 만드는 데 도움을 주시면 감사하겠습니다. 나는 그것을 보여주고 싶다$P$극단 점이없는 경우 선을 포함해야합니다. 내 대략적인 아이디어는 다음과 같습니다.
허락하다 $x\in P$. 우리는 그것이 극단적이지 않다는 것을 알고 있습니다.$d_1\in\mathbb{R}^n$ 그런 $x + td_1\in P$ ...에 대한 $t\in (-\varepsilon_1, \varepsilon_1)$ 충분히 작게 $\varepsilon_1$. 어느 한 쪽$x + td_1$ 에 포함 된 라인 $P$,이 경우 완료됩니다. 또는 $x \pm td_1$ 일부에 대해 활성 / 밀폐 제약이 있습니다. $t = t_1$. WLOG는 '+'케이스를 가정합니다. 즉$x + t_1d_1$활성 제약이 있습니다. 가정하면$x + t_1d_1$ 극단적 인 지점이 아니므로 $d_2\in\mathbb{R}^n$ 에없는 $\text{span}(d_1)$ 그런 $(x + t_1d_1) \pm td_2\in P$ ...에 대한 $t\in (-\varepsilon_2, \varepsilon_2)$ 충분히 작게 $\varepsilon_2$. 어느 한 쪽$P$ 라인을 포함 $(x + t_1d_1) + td_2$ 이 경우 우리는 완료되거나 존재합니다 $t = t_2$ 그런 $(x + t_1d_1) \pm t_2d_2$활성 제약이 있습니다. 다시 WLOG는 '+'케이스를 가정합니다. 이후$d_2$ 에 없다 $\text{span}(d_1)$그러면 이전의 활성 제약 조건이 계속 활성화되고 이제 새 제약 조건도 활성화됩니다. 우리는이 프로세스를 반복하여$d_3\in\mathbb{R}^n$ 아니 $\text{span}(d_1, d_2)$ 그런 $(x + t_1d_1 + t_2d_2) \pm td_3$ 에 포함되어 있습니다 $P$ 작은 $t$ 그리고 이것은 라인입니다 $P$ 또는있다 $t_3$ 그런 $x + t_1d_1 + t_2d_2 + t_3d_3$활성 제약이 있습니다. 이후$d_3\notin\text{span}(d_1, d_2)$, 원래 두 개의 활성 제약 조건이 여전히 활성화되어 있으므로 이제 세 번째 활성 제약 조건 등이 있습니다. 어느 시점에서 우리는 선을 찾거나 $x + t_1d_1 + \cdots + t_nd_n$ 어느 것이 $n$활성 제약. 그러나 이것은 활성 제약의 행렬이$A^=$ 이 점은 순위입니다 $n$, 즉 $x + t_1d_1 + \cdots + t_nd_n$가설과 모순되는 극단적입니다. 따라서이 과정을 반복 할 때 반드시 방향을 찾았을 것입니다.$d_i$ 그 방향의 선이 $P$.
내 직감은 이런 식으로 작동해야한다고 말하지만이를 엄격하게 만들기 위해 고군분투하고 있습니다. 구체적으로는 각각$d_i$ 이전의 범위에 있지 않습니다. $d_1,\dots, d_{i - 1}$, 그러나 이것이 사실임을 보장하는 방법을 모르겠습니다. 둘째, 나는$d_i$ 이전 기간이 아닙니다. $d_1,\dots, d_{i - 1}$ 그런 다음 이전에 활성화 된 제약 조건은 방향으로 이동 한 후에도 여전히 활성화되어 있습니다. $d_i$. 사실이되어야 할 것 같지만 어떻게 증명해야할지 모르겠습니다. 마지막으로, 내 주장으로 적어도$n$ 우리가 반복하는 경우 활성 제약 $n$ 시간,하지만 실제로 그 순위를 증명하는 방법을 모르겠어요 $A^=$ 실제로 같다 $n$이 경우 (이 단계에 도달하면 원하는 모순을 제공합니다). 아마도$\text{rank}(A^=)$ 여전히 엄격히 $n$, 비록 우리가 $n$활성 제약. 불가능하기를 바라지 만 어떻게 증명해야할지 모르겠습니다.
누군가가 이러한 요점을 엄격하게 만들어 이것이 유효한 증거가되게하거나 대신이 증거가 작동하지 않는 이유를 보여줄 수 있다면 매우 감사 할 것입니다.
답변
나는 당신의 증거가 엄격해질 수 있다고 확신합니다. 시술의 각 단계에서$\ A_j^=\ $ 엄격한 제약의 매트릭스이고 $\ A_j^<\ $ 슬랙 제약의 행렬 $\ \displaystyle x_j=x+\sum_{i=1}^jt_id_i\ $. 때문에$\ x_j \ $ 극단적 인 지점이 아닙니다. $\ A_j^=\ $ 보다 작다 $\ n\ $, 선택할 수 있습니다. $\ d_{j+1}\ $커널에 있습니다. 그런 다음 행렬의 모든 제약$\ A_j^=\ $ 꽉 유지됩니다 $\ x_j+td_{j+1}\ $ (여부에 관계없이 $\ d_{j+1}\in\text{span}\left(d_1,d_2,\dots,d_j\right)\ $여부). 만약$\ x_j+td_{j+1}\ $ 선이 아닌 경우 행렬이있는 하나 이상의 제약 조건 $\ A_j^<\ $ 빡빡해야한다 $\ x_{j+1}=x_j+t_{j+1}d_{j+1}\ $. 따라서$\ A_j^=\ $ 엄격한 부분 행렬이어야합니다. $\ A_{j+1}^=\ $. 이후$\ A\ $ 한정된 수의 행만있는 경우 프로시 저는 한 줄로 종료해야합니다. $\ x_k+td_{k+1}\ $ 일부 $\ k\ $, 또는 $\ A_k^==A\ $, 따라서 $\ Ax_k=b\ $. 후자의 경우$\ x_k\ $ 극단적 인 지점이 아니라면 $\ A\ $ 보다 작아야합니다 $\ n\ $따라서 비어 있지 않은 커널이 있습니다. 만약$\ d\ $ 커널의 0이 아닌 구성원 인 경우 $\ x_k+td\ $ 줄이 될 것입니다 $\ P\ $.