algorithm - 不等式の多項式システムに解があるかどうかを判断するための高速なアルゴリズム

Question

n 変数の k 多項式不等式の特定のシステムに解があるかどうかを判断する高速なアルゴリズムを探しています (解は必要ありません)

k > n の場合。

Cylindrical Algebraic Decomposition について読んだことがありますが、これまでのところそれ以上のものを見つけることができませんでした。

編集：

それは、実数に対する実数係数を持つ多項式に関するものです。

Answer 1

Maple のパッケージの通常のチェーンには、IsEmpty? コマンドがあります。

コマンド IsEmpty(sys, R) は、一連の制約 sys のゼロ セットが空かどうかをチェックします。sys の制約は、任意の多項方程式、不等式、または R の多項式によって与えられる不等式にすることができます。sys のゼロ セットは、sys によって定義される多項式システムの実数解のセットと見なされます。これは、R が標数 0 を持つことを前提としています。

使用されているアルゴリズムが何であるかはわかりませんが、次を参照してください。

Xia、Bican、Lu Yang。「半代数系の実解を分離するためのアルゴリズム。」Journal of Symbolic Computation 34、いいえ。5 (2002): 461-477.

Answer 2

多項式不等式のシステムが実現可能かどうかを判断することは、非常に難しい数学的問題であり、実際の代数幾何学における多くの研究がそれに関係しています。

円筒代数分解とは別に、これらの集合に対する代替定理もあります。最も注目すべき結果はStengle の Positivstellensatzであり、それが実行不可能である場合、結果が -1 になるように制約からの正の要件を正の方法で組み合わせることにより、実行不可能であることを証明できると大まかに述べています。この矛盾は実行不可能性を証明しています。

これらの証明書を見つけることは、アルゴリズム的に非常に悪い場合がありますが、セットのいわゆる瞬間緩和を調べることができます。これらはやや大きな集合であり、その実現可能性は半限定プログラミングで決定できます。このためのアルゴリズムは十分に開発されています。

全体として、実行不可能性の問題の解決策を最終的に見つける、より大きな凸最適化問題の階層があります。もちろん、実際には、これらすべてが数値の問題などによって台無しになる可能性があります。これの実装は、Matlab パッケージyalip です。

Answer 3

パラメータが実数であると仮定すると、多項式の根を見つけることができ (n を多項式に含めると仮定)、解は X が 0 より大きい間隔のセットになります。

導関数の結果を使用して、関数の傾向を判断することもできます。