2

湾曲した凸空間で線形関数を最大化することを含む「連続」線形計画問題があります。典型的な LP 問題では、凸空間は多面体ですが、この場合、凸空間は区分的に湾曲しています。つまり、面、エッジ、および頂点がありますが、エッジは直線ではなく、面は平坦ではありません。 . 有限数の線形不等式によって指定される代わりに、私は連続的に無限の数を持っています。私は現在、ポリトープで表面を近似することでこれに対処しています。これは、連続無限制約を非常に大きな有限数の制約に離散化することを意味します。

また、根本的な問題に対する小さな摂動の下で答えがどのように変化するかを知りたい状況にもあります。したがって、近くの解に基づいてソルバーに初期条件を提供できるようにしたいと考えています。この機能は「ウォーム スタート」と呼ばれるものだと思います。

誰かが私がそこにあるさまざまな LP パッケージを区別するのを手伝ってくれますか? 速度 (多数の制約の場合)、高精度の演算、およびウォーム スタートなどの使いやすさにはあまり関心がありません。

ありがとう！

編集: これまでの質問回答者との会話から判断すると、私が解決しようとしている問題についてより明確にする必要があります。簡略化されたバージョンは次のとおりです。

単一の実変数 y の N 個の固定関数 f_i(y) があります。制約に従って \sum_{i=1}^N x_i f_i(0) を最小化する x_i (i=1,...,N) を見つけたい:

  • \sum_{i=1}^N x_i f_i(1) = 1、および
  • \sum_{i=1}^N x_i f_i(y) >= 0 for all y>2

より簡潔に言えば、関数 F(y)=\sum_{i=1}^N x_i f_i(y) を定義すると、F(1)=1 という条件に従って F(0) を最小化し、 F(y) は区間全体 [2,infinity) で正です。この後者の正の条件は、実際には、各 y に対して 1 つずつ、x_i に対する無限の数の線形制約であることに注意してください。y はラベルと考えることができます。これは最適化変数ではありません。特定の y_0 は、x_i の空間で半空間 F(y_0) >= 0 に私を制限します。y_0 を 2 から無限大の間で変化させると、これらの半空間が連続的に変化し、湾曲した凸形状が形成されます。この形状のジオメトリは、関数 f_i に暗黙のうちに (そして複雑な方法で) 依存します。

4

3 に答える 3

2

  • LPソルバーの推奨事項については、GurobiとCPLEX（googleそれら）の2つが最適です。アカデミックユーザーは無料で、大規模な問題を解決することができます。彼らはあなたが必要とするすべての機能を持っていると思います。シャドウ価格（つまり、ラグランジュ乗数）から（摂動に対する）感度情報を取得できます。

  • しかし、私はあなたの元の問題にもっと興味があります。私が理解しているように、それは次のようになります：

S = {1,2、...、N}とします。ここで、Nは関数の総数です。yはスカラーです。f_ {i}：R ^ {1}-> R^{1}。

minimize sum{i in S} (x_{i} * f_{i}(0))
   x_{i}
s.t.
(1) sum {i in S} x_{i} * f_{i}(1) = 1
(2) sum {i in S} x_{i} * f_{i}(y) >= 0 for all y in (2,inf]

  • この問題をLPではなく凸型NLPとして解決してみてください。IPOPTのような大規模な内点NLPソルバーは、これらの問題を簡単に処理できるはずです。IPOPThttp ://www.coin-or.org/Ipoptを試すことを強くお勧めします

  • 数値の観点から：凸問題の場合、内部点ソルバーではウォームスタートは必要ありません。そして、アクティブセットの組み合わせサイクリングについて心配する必要はありません。あなたが「ウォームスタート」と表現したのは、実際にはソリューションを混乱させることです。これは、感度分析に似ています。最適化の用語では、ウォームスタートは通常、ソルバーに最初の推測を提供することを意味します。ソルバーはその推測を取得して同じソリューションになりますが、これは実際には必要なことではありません。唯一の例外は、アクティブセットが異なる初期推定で変化する場合ですが、一意の最適化を伴う凸問題の場合、これは発生しません。

さらに情報が必要な場合は、喜んで提供させていただきます。

編集：

非標準の表記については申し訳ありません。MathOverflow.netのようにLaTeXと入力できればと思います。（ちなみに、これをそこに投稿してみてください-そこの数学者はこの問題に興味があると思います）

ああ、今私は「y>2」について見ています。これは、スペースを定義する間隔ほど最適化の制約ではありません（上記の説明を編集しました）。私の間違い。問題を無限から有限に変換/投影できるかどうか疑問に思っていますか？今は何も思いつかないのですが、それが可能かと思っています。

したがって、あなたのアプローチは、（2、inf]でyの問題を離散化することです。infと細かい離散化グリッドを表すために非常に大きな数を選択していると思います。うーんトリッキーです。離散化がおそらく最善の策だと思います。たぶん、実際の分析を行う人はアイデアを持っています。

凸包内のすべての点でプロパティを適用する必要があるリアプノフ関数に関連する問題に対して、同様のことが行われているのを見てきました。しかし、その空間は有限でした。

于 2010-07-24T18:42:13.370 に答える
1

同様の問題が発生しました。Web を検索したところ、この問題が「半無限」の問題に分類される可能性があることがわかりました。MATLAB には、この種の問題を解決するためのツールがあります (関数 "fseminf")。しかし、私はこれを詳細にチェックしていません。確かに人々はこの種の質問に遭遇しました。

于 2012-02-22T23:09:13.017 に答える
0

LP ソルバーを使用して自分で離散化を行うべきではありません。まともな一般的な凸ソルバーを使用すると、はるかにうまくいく可能性があります。たとえば、cvxoptを確認してください。これにより、制約内のさまざまな関数を処理したり、独自の関数を記述したりできます。これは、自分で線形化を試みるよりもはるかに優れています。

ウォーム スタートに関しては、一般的なコンベックス プログラムよりも LP の方が理にかなっています。アルゴリズム全体を自分でコーディングする場合は、ウォーム スタートが役立つ可能性がありますが、通常はとにかくいくつかのニュートン ステップが必要になるため、メリットはそれほど大きくありません。ウォーム スタートの利点のほとんどは、ほとんど LP にのみ使用されるアクティブ セット メソッドなどで得られます。

于 2010-04-28T04:56:57.687 に答える