在C++中是否有一個二次編程庫？

我發現唯一的Google搜索結果是QuadProg ++，但它不能解決其矩陣不適用於Cholesky分解的二次規劃問題。在C++中是否有一個二次編程庫？

那麼任何人都可以給我一些關於其他圖書館的建議嗎？謝謝。

2011-11-06 Daniel Gao

對不起，說明明顯的，但我不得不查看維基百科，以找出什麼二次編程是什麼，我看到它包含幾個實現的引用，你檢查了那些？或者http://hqp.sourceforge.net/index.html或http://www.gnu.org/s/gsl/會有所幫助？ – rve

@rve我檢查了gsl，它沒有二次編程求解器函數。我也檢查過維基，其中大部分都不是用C/C++編寫的，或者很難安裝。我將檢查hqp是否有效，謝謝 –

矩陣如何不適用於Cholesky分解？任何對稱正半定矩陣都適用（並且分解需要〜n^3/3個FLOP）。表達式$ x^TQx $總是可以（重新）寫入，$ Q $是對稱的。你的意思是說，這不是正面的 - 半定的？ – fiktor

LAPACK有一些Cholesky分解例程（他們稱之爲Cholesky分解）。有些C++包裝器可用於LAPACK（有關列表，請參閱此SO question）。

Anycom在該帖子中的答案有點神祕，但他表示有LAPACK綁定可以和Boost的線性代數庫uBLAS一起使用。

我發現這個庫：OOQP（二次規劃面向對象的軟件）。如果您向下滾動該頁面，您會發現一份研究論文和一份用戶指南。該庫似乎有一個C++ API。希望這可以幫助。

來源

2011-11-06 17:46:49

但這並不能解決我的問題。我試圖解決的二次規劃問題中的對稱矩陣不適用於Cholesky分解。 –

糟糕，我沒有仔細閱讀你的問題。抱歉。 –

@DanielGao：更新了我的答案。 –

CGAL對於二次編程看起來不錯。甚至有a manual。

// 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));

從the first example代碼。

來源

2012-11-08 13:16:43 Wok

如果您願意付款，您可以使用Mosek。不過，有30天的免費試用期。它通常被認爲是最快速的求解器（沒有引用，對不起）。界面是C風格，但明顯來自C++的完美callalbe。 Mosek實際上更像是一個圓錐形編程解算器，但如果你不想將問題重新表達爲一個圓錐形問題（Mosek有很多關於如何做的文檔），你仍然可以使用它的隨機梯度下降解算器來解決你的二次方公式。

來源

2012-11-08 13:28:04 frankc

以上許多答案所遺漏的微妙之處在於矩陣是僅爲正半定（PSD）還是實際上是不確定的。我沒有使用quadprog，但是如果它在PSD目標矩陣上失敗，這是軟件缺乏魯棒性的標誌（凸QPs通常是PSD，其中只有嚴格凸QPs是肯定的）。根據Golub的「矩陣計算」一書，Cholesky分解可應用於PSD矩陣，但數值穩定性往往受到影響。對於一般的非線性編程軟件 - 凸和非凸，COIN-OR項目都維護着免費和非免費軟件列表。他們列出的解決方案之一是IPOPT，它當然能夠解決您的問題。 IPOPT使用內點算法，對於小問題，它通常比活動集方法（如quadprog使用）慢。或者，您可以將您的QP制定爲線性互補問題（LCP），然後使用LCP求解器進行求解。我發現Fackler和Miranda的Matlab代碼LEMKE可以輕鬆移植到C++中。

來源

2013-07-25 22:33:53

有幾個庫包含QP求解器。有開源和商業兩種選擇。現有的答案列出了其中的一些。我想用矩陣來說明問題。

我假設你指的是客觀矩陣。約束矩陣只需要導致一個非空的可行集合。你提到矩陣不適用於Cholesky分解。由於Cholesky分解可以爲任何正定矩陣形成，暗示你的矩陣不是正定的。

如果矩陣是正半定的（即它有一個或多個零特徵值），那麼問題是一個凸QP並且可以有效地求解。但是，許多求解者需要一個肯定的目標。由於半正定QP的目標有一個不平凡的零空間，因此可能有很多解決方案。事實上，這套解決方案甚至可能是無限的。數值算法只會給出一個近似解，所以矩陣的特徵值恰好爲零是很重要的。您可以通過在對角線上添加一個正值很小的對角矩陣使矩陣正定。這將基本上選擇具有最小2-範數的解。在實踐中，即使在矩陣爲正定的情況下做這個也是一個好主意，因爲特徵值接近零的矩陣常常會導致數值求解器的問題。要在穩定性和準確性之間進行權衡，需要添加多少對角線。

如果矩陣是不確定的（即它甚至有一個負特徵值），那麼問題就是NP難。這意味着即使對於中等規模的問題，基於當前可用算法的任何代碼都將具有不合理的最壞情況運行時間。如果你的問題有一些特殊的結構，或者你不需要一個全球最佳的解決方案，那麼你可能會沒事。一種典型的方法是尋找凸放鬆。

來源

2013-12-30 03:12:09 MichaelJ

所有有趣的，但OP是要求指向其他圖書館，而不是如何解決QP問題的論文。 –

在這種情況下，似乎OP *實際需要的「關於如何解決QP問題的論文」，無論他們是否意識到這一點。 – zwol

在C++中是否有一個二次編程庫？

回答

相關問題