問題タブ [convex-optimization]

GLPK への Python インターフェイスを使用しています。次のようなソリューション X を探しています。

• c を最小化します。
• G * X <= H
• A * X = b

私は次のステートメントを使用しています

それは私のGマトリックスです：

それが私のh行列です

それが私のA行列です

それが私のBマトリックスです

それでも、次を実行することによって：

次の解決策が得られます。

これは明らかに間違っています。

A * X != b なので

これをトラブルシューティングする方法はありません。ドキュメントが不足しています。

Pythonでscikitパッケージを使用してSVMを実装しています。plot_separating_hyperplane.pyの「 alphai」値の解釈に問題があります

サンプル出力

Dual_coef_は、「alpha i *yi」値を提供します。「alphai*y i」の合計が0（0.04825885 + 0.56891844 --0.61717729 = 0）であることを確認できます。

「alphai」の値を知りたいと思いました。「alphai*y i」の値があるので、簡単なはずです。しかし、私はすべての「アルファi」を負にしています。たとえば、点（0.95144703、0.57998206）は線の上にあります（リンクを参照）。したがって、y=+1です。y = +1の場合、アルファは-0.61717729になります。同様に、ポイント（-1.02126202、0.2408932）は線の下にあります。したがって、y = -1、したがってalpha=-0.04825885です。

アルファ値が負になるのはなぜですか？ 私の解釈は間違っていますか？どんな助けでもありがたいです。

ご参考までに、

サポートベクター分類器（SVC）の場合、

2つのクラスのトレーニングベクトルi=1、...、nと、SVCが次のような主要な問題を解決するようなベクトルが与えられます。

そのデュアルは

ここで、「e」はすべてのベクトル、C> 0は上限、Qはn行n列の正の半確定行列であり、カーネルです。ここで、トレーニングベクトルは、関数によって高次元（おそらく無限）の次元空間にマッピングされます。

半正定プログラミングを解決するためのパッケージcvxoptに基づいて、Python で半正定埋め込みアルゴリズム (こちらを参照)を実装しようとしています。半正定値プログラムの定義を cvxopt のインターフェースにマッピングする際にいくつか問題があります (これを参照してください)。

これは私の現在の実装です:

ValueErrorプログラムを実行すると、 (Rank(A) < p or Rank([G; A]) < n)がスローされます。ここで何がうまくいかないのかヒントはありますか？

これは、stackoverflow への私の最初の投稿であるため、これが正しい領域でない場合はお詫び申し上げます。L1正規化システムの最小化に取り組んでいます。

今週末は最適化への私の最初のダイビングです。私は基本的な線形システム Y = X*B を持っています。X は n 行 p 列の行列、B はモデル係数の p 行 1 列のベクトル、Y は n 行列です。 -1 出力ベクトル。

モデル係数を見つけようとしています。勾配降下アルゴリズムと座標降下アルゴリズムの両方を実装して、L1 正則化システムを最小化しました。バックトラッキング アルゴリズムを使用しているステップ サイズを見つけるために、勾配のノルム 2 を見てアルゴリズムを終了し、ゼロに「十分近い」場合は終了します (今のところ 0.001 を使用しています)。

私が最小化しようとしている関数は、次の (0.5)*(norm((Y - X*B),2)^2) + lambda*norm(B,1) です。(注: norm(Y,2) とは、ベクトル Y のノルム 2 値を意味します) 私の X 行列は 150 行 5 列で、スパースではありません。

正則化パラメーター ラムダをゼロに設定すると、最小二乗解に収束するはずです。両方のアルゴリズムがこれをかなりうまく、かなり迅速に行うことを確認できます。

ラムダを増やし始めると、モデル係数はすべてゼロに向かう傾向があります。これは私が期待することですが、勾配のノルム 2 は常に正の数であるため、アルゴリズムは決して終了しません。たとえば、1000 のラムダは 10^(-19) 範囲の係数を与えますが、私の勾配の norm2 は ~1.5 です。範囲、私のステップ サイズは非常に小さくなります (10^(-37) 範囲)。アルゴリズムを長時間実行しても状況が改善されない場合は、何らかの理由でスタックしているように見えます。

私の勾配と座標降下アルゴリズムの両方が同じ点に収束し、終了条件に同じ norm2(gradient) 数を与えます。また、0 のラムダでも非常にうまく機能します。非常に小さなラムダ (0.001 など) を使用すると収束します。0.1 のラムダは、1 時間か 2 時間実行すると収束するように見えます。収束率が小さすぎて使い物になりません。

問題に関連していると思われるいくつかの質問がありましたか?

勾配の計算では、h が 10^(-5) の有限差分法 (f(x+h) - f(xh))/(2h)) を使用しています。この h の値について何か考えはありますか?

別の考えでは、これらの非常に小さなステップでは、最小値とほぼ直交する方向に前後に移動し、収束速度が非常に遅くなり、役に立たなくなるというものでした.

私の最後の考えは、収束速度が非常に遅い場合は、おそらく収束速度を見て、おそらく別の終了方法を使用する必要があるということでした。これは一般的な終了方法ですか？

次の形式の線形計画問題を解こうとしています。

輸送の問題のため。

ただし、CVXOPT を使用するには、lp(G,h,A,b) ソルバーの変数 Gx <= h を定義する必要があります。

A および b 行列を作成しようとしました。G および h 行列については、G には単位行列 (-1 を掛けたもの) を使用し、h にはゼロのベクトルを使用して、x>=0 の制約を課します。

ただし、コードを実行すると、「特異な KKT マトリックス」が返されます。

何が問題なのか、または G 変数と h 変数なしで CVXOPT ソルバーを実行する方法を教えてください。

私は解決する必要があります (多くの場合、多くのデータに対して、他の多くのことと一緒に) 2 次コーン プログラムに要約すると思われるものを解決する必要があります。CVXで簡潔に表現すると、次のようになります。

示されているデータ長と等式制約パターンは、一部のテスト データからの任意の値にすぎませんが、一般的な形式はほとんど同じで、2 つの客観的項 (1 つはエラーを最小化し、もう 1 つはスパース性を促進します) と多数の等式制約があります。最適化変数の変換されたバージョンの要素 (それ自体は非負になるように制約されています)。

これはかなりうまく機能しているように見えます。私の以前のアプローチよりもはるかに優れています。問題は、これに関する他のすべてが R で行われていることであり、Matlab に移植する必要があるのは非常に面倒です。R でこれを行うことは実行可能ですか?

これは、2 つの別々の質問に要約されます。

1)これに適したRリソースはありますか? CRAN タスク ページからわかる限り、SOCP パッケージ オプションはCLSCOPとDWDであり、分類器の補助として SOCP ソルバーが含まれています。どちらも似ていますがかなり不透明なインターフェースを持ち、ドキュメントと例が少し薄いため、次のことがわかります。

2) これらのパッケージで使用される制約ブロック形式で上記の問題を表現する最良の方法は何ですか? 上記の CVX 構文は、追加の変数などを使った多くの退屈ないじりを隠しています。これを正しく行うために何週間も費やしていることがわかります。正しい方向に私を微調整するためのヒントやポインターは大歓迎です...

Pythonで記述されたアルゴリズムにネステロフのメソッドを実装することを検討しています。このメソッドの実装に関して、私が始めるのに役立つドキュメントを教えてください。私は職業上のプログラマーであるため、非理論的なバージョンを検討しています。

私はこのhttp://www.ee.ucla.edu/~vandenbe/236C/lectures/fgrad.pdfを試してみましたが、prox 演算子について言及した時点で感銘を受けました。prox operator とは何ですか? prox operator を実装するための指針はありますか?

お時間をいただきありがとうございます。

matlab で凸最適化ツールボックスを使用していますが、目的関数が最小化され、値が表示されます。しかし、最小値が達成される最適化変数が見つかりません。誰かがそれを見つける方法を教えてくれますか?

matlab 最適化ツールボックスでは、最適化変数を 4D 行列にすることは可能ですか? その場合、開始点を指定するにはどうすればよいですか? すべてゼロとして与えることはできますか？4D マトリックスとは、マトリックスのマトリックスを意味します。したがって、値を修正するには 4 つのインデックスが必要です。