私の問題の一部は、特定の数の加重和の絶対値を最小にすることです。私は体重を見つけなければならない。数値の加重和の絶対値を最小にする
最小重量は、たとえば、0.1であるように（A1、A2> 0）、（< 0 A4、A3、）は、A3とA4、A2、A1、のは、私は番号Aのセットを持っているとしましょう（10％）、最大値は0.4（40％）です。私は、加重和がゼロになるように加重値wを探しています。ゼロが不可能な場合、ゼロに最も近い可能性があります。
Minimise E
E >= SUM w * a
E >= -(SUM w * a)
SUM w = 1
w >= 0.1 for all w
w <= 0.4 for all w
単純な線形モデルを使用すると、解を非常に速く見つけることができます。しかし、私はこの問題の多項式アルゴリズムや数式を探したいと思っています。何か案は？この問題はよく知られていますか？
ありがとうございます！
最小化（最大化）SUM w * aは簡単です。すべての重みを最小値に設定し、最小値から最大値（最大値と最小値）を設定すると、グローバル最大値に達するまで、ローカル最大値を考慮した重みが増えます。
[最小、最大]間隔に0が含まれている場合、これら2つのソリューションの凸面の組み合わせとして最適解を実現できます。それ以外の場合は、解を0に近づけます。
ellipsoid algorithmは、線形計画法の最初のワーストケースの多項式時間アルゴリズムでした。
しかし、あなたは問題を速く解決したいと思うので、多項式時間アルゴリズムに興味があります。
この場合、シンプレックスの方法を使用する方がよいでしょう。たとえシンプレックスが最悪の場合に指数関数的であっても、ほとんどの実用的なアプリケーションには最良の選択肢のようです。驚くことではないが、それは私が知っている良質のソルバに実装されている。
こんにちはアリ、あなたの答えをありがとうが、実際に私はすでにシンプレックスで非常に速くそれを解決します。ここでの問題は、私がより速くそれを解決したいのではなく、私は単に私が線形計画モデルに頼らずにこの問題を解決するための特殊なアルゴリズムを考え出すことを確認したいと思うのです。 – Chicoscience
OKです。そして、線形計画モデルを避ける理由は何ですか？アプリケーションにLPソルバーを依存しないようにしたいのですか？ – Ali
実際に私の意図は、問題がどれほど簡単かを数学的に証明するものです。 – Chicoscience
これは興味深い考えです。私はそれを試してみて、それについてコメントします。 – Chicoscience