均一な線形不等式のシステム

Aug 24 2020

線形不等式システムが存在する条件を見つけようとします $$ (S):\ Ax\ge0,\ x\ge0 $$

解決策があります $x\in\mathbb{R}^n$ それはゼロではありません($x\neq0$)。ここに$A$$n\times n$実数のエントリを持つ正方行列。もちろん、(S)の2つの不等式を1つにまとめて、次の形式で書くこともできます。$\tilde{A}x\ge0$ どこ $\tilde{A}$ です $2n\times n$

この問題は長い間解決されてきたと思います。この問題を攻撃する方法についての提案はありがたいです。

回答

NeutralElement Aug 26 2020 at 05:38

(S)は $$ [A\ -I_n] \left[\begin{array}{c} x\\ b \end{array}\right] =0,\ \left[\begin{array}{c} x\\ b \end{array}\right]\ge0\ \mathrm{and}\ \left[\begin{array}{c} x\\ b \end{array}\right]\neq0\ (\Leftrightarrow\ x\neq0) $$ ゴーダンの定理によると、(S)に解がない場合は、 $y\in\mathbb{R}^n$ そのような $\left[\begin{array}{c} A^{T}\\ -I_{n} \end{array}\right]y<0$ に来る $y>0$ そして $A^Ty<0$