12

私が見つけた唯一のGoogle検索結果はQuadProg ++ですが、行列がコレスキー分解に適用できない二次計画問題を解くことはできません。

他のライブラリについて誰か提案してもらえますか？ありがとう。

4

5 に答える 5

5

CGALは二次計画法に最適です。マニュアルまであります。

  // by default, we have a nonnegative QP with Ax <= b
  Program qp (CGAL::SMALLER, true, 0, false, 0); 

  // now set the non-default entries: 
  const int X = 0; 
  const int Y = 1;
  qp.set_a(X, 0,  1); qp.set_a(Y, 0, 1); qp.set_b(0, 7);  //  x + y  <= 7
  qp.set_a(X, 1, -1); qp.set_a(Y, 1, 2); qp.set_b(1, 4);  // -x + 2y <= 4
  qp.set_u(Y, true, 4);                                   //       y <= 4
  qp.set_d(X, X, 2); qp.set_d (Y, Y, 8); // !!specify 2D!!    x^2 + 4 y^2
  qp.set_c(Y, -32);                                       // -32y
  qp.set_c0(64);                                          // +64

  // solve the program, using ET as the exact type
  Solution s = CGAL::solve_quadratic_program(qp, ET());
  assert (s.solves_quadratic_program(qp));

最初の例のコード。

于 2012-11-08T13:16:43.100 に答える
4

LAPACKには、いくつかのコレスキー分解ルーチンがあります（コレスキー分解と呼ばれます）。LAPACKで使用できるC++ラッパーがあります（リストについては、このSOの質問を参照してください）。

その投稿のAnycomからの回答は少しわかりにくいですが、Boostの線形代数ライブラリuBLASと一緒に使用できるLAPACKバインディングがあることを意味しました。

私はこのライブラリを見つけました：OOQP（二次計画法のためのオブジェクト指向ソフトウェア）。そのページを下にスクロールすると、研究論文とユーザーガイドが表示されます。そのライブラリにはC++APIがあるようです。お役に立てれば。

于 2011-11-06T17:46:49.897 に答える
2

上記の答えの多くが欠けている微妙な点は、行列が正の半正定値 (PSD) だけなのか、実際には不定なのかということです。私は quadprog を使用していませんが、PSD 目的行列で失敗した場合、それはソフトウェアの堅牢性の欠如の兆候です (凸 QP は多くの場合 PSD であり、厳密に凸QP のみが正定値です)。Golub の著書 "Matrix Computations" によると、Cholesky 分解は PSD 行列に適用できますが、数値の安定性が損なわれる傾向があります。

一般的な非線形プログラミング ソフトウェア (凸型と非凸型の両方) について、COIN-OR プロジェクトはフリー ソフトウェアと非フリー ソフトウェアのリストを維持しています。リストされているソルバーの 1 つに IPOPT があり、これは確かに問題を解決することができます。IPOPT は内点法アルゴリズムを使用します。これは、小さな問題の場合、一般にアクティブ セット法 (quadprog が使用するものなど) よりも遅くなります。別の方法として、QP を線形相補性問題 (LCP) として定式化し、LCP ソルバーを使用して解くことができます。私は、Fackler と Miranda の Matlab コード LEMKE が C++ に簡単に移植できることを発見しました。

于 2013-07-25T22:33:53.507 に答える
1

支払う意思がある場合は、Mosekを使用できます。ただし、30日間の無料トライアルがあります。これは一般的に利用可能な最速のソルバーと考えられています (引用なし、申し訳ありません) インターフェイスは C スタイルですが、C++ から完全に呼び出すことができます。Mosek は実際には円錐計画法のソルバーですが、問題を円錐問題として再定式化する気がない場合 (Mosek には、これを行う方法に関する多くのドキュメントがあります)、確率的勾配降下法ソルバーを使用して解くことができます。あなたの二次方程式。

于 2012-11-08T13:28:04.770 に答える