C++에 이차 프로그래밍 라이브러리가 있습니까?

Question

내가 찾은 유일한 Google 검색 결과는 QuadProg ++이지만 Matrix가 Cholesky 분해에 적용 할 수없는 이차 프로그래밍 문제를 해결할 수 없습니다.

다른 사람이 나에게 어떤 제안을 할 수 있습니까? 감사.

Answer 1

LAPACK에는 Cholesky 분해 루틴 (Cholesky 분해)이 있습니다. LAPACK에는 C++ 래퍼가 있습니다 (목록을 보려면 SO question 참조).

그 게시물의 Anycom으로부터의 대답은 다소 수수께끼지만 Boost의 선형 대수 라이브러리 uBLAS과 함께 사용할 수있는 LAPACK 바인딩이 있다는 것을 의미합니다. OOQP (이차 프로그래밍을위한 객체 지향 소프트웨어) :

---

나는이 라이브러리를 발견했습니다. 해당 페이지를 아래로 스크롤하면 연구 논문과 사용자 가이드를 찾을 수 있습니다. 해당 라이브러리에 대한 C++ API가있는 것 같습니다. 희망이 도움이됩니다.

Answer 2

CGAL은 2 차 프로그래밍에 적합합니다. 심지어 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.

Answer 3

지불하려는 경우 Mosek을 사용할 수 있습니다. 30 일 무료 평가판이 있습니다. 일반적으로 가장 빠른 해결사로 간주됩니다 (인용문 없음, 미안). 인터페이스는 C 스타일이지만 C++의 callalbe는 분명히 완벽합니다. Mosek은 원추형 프로그래밍 솔버가 더 많습니다 만 원추형 문제로 문제를 재구성하려는 느낌이 들지 않는다면 (Mosek는이를 수행하는 방법에 대한 많은 문서를 가지고 있습니다.) 여러분은 여전히 ​​확률적인 그래디언트 디센트 솔버를 사용하여 해결할 수 있습니다 당신의 2 차 공식.

Answer 4

위의 답 중 많은 부분이 누락되어있는 미묘한 점은 매트릭스가 양의 반 (半) 명확한 (PSD)인지 아니면 실제로는 한정이없는 것인지입니다. 나는 quadprog를 사용하지 않았지만 PSD 목표 매트릭스에서 실패한 경우 소프트웨어의 견고성이 결여 된 것입니다 (볼록 QP는 종종 PSD이며 단지 만 볼록한 QP는 양수입니다). Golub의 저서 "Matrix Computations"에 따르면, Cholesky 분해가 PSD 행렬에 적용될 수 있지만 수치 안정성이 떨어지는 경향이 있습니다.

일반 비선형 프로그래밍 소프트웨어 (볼록 및 비 볼록)의 경우 COIN-OR 프로젝트는 무료 및 비 자유 소프트웨어 목록을 유지 관리합니다. IPOPT는 문제를 해결할 능력이있는 IPOPT입니다. IPOPT는 내부 문제 알고리즘을 사용합니다. 내부 알고리즘은 작은 문제의 경우 일반적으로 활성 집합 방법 (예 : quadprog 사용)보다 속도가 느립니다. 대안으로, 선형 보 상 문제 (LCP)로 QP를 공식화 한 다음 LCP 솔버를 사용하여 QP를 풀 수 있습니다. 필자는 Fackler와 Miranda의 Matlab 코드 LEMKE가 C++에 쉽게 이식 가능하다는 것을 발견했다.

Answer 5

QP 해결사를 포함하는 여러 라이브러리가 있습니다. 오픈 소스 및 상업용 옵션이 모두 있습니다. 기존 답변에는 몇 가지가 나와 있습니다. 행렬 문제를 명확히하고 싶습니다.

객관적인 매트릭스를 말하는 것으로 가정합니다. 제약 조건 행렬은 비어 있지 않은 실현 가능한 집합으로 이어질 필요가있다. 당신은 행렬이 콜레 스키 분해에 적합하지 않다고 언급했습니다. 콜리스키 분해는 양의 명확한 행렬에 대해 형성 될 수 있기 때문에 행렬이 양의 확률이 아니라는 의미가됩니다.

행렬이 양의 반자동 (즉, 하나 이상의 0 고유치를 가짐) 인 경우 문제는 볼록 QP이며 효율적으로 해결할 수 있습니다. 그러나 많은 솔버는 긍정적 인 명확한 목표를 요구합니다. 양의 반자성 QP의 목적은 단순한 영 공간을 가지므로 많은 해결책이있을 수 있습니다. 실제로 솔루션 세트는 무제한적일 수 있습니다. 수치 알고리즘은 어쨌든 근사 솔루션을 제공 할 것이므로 매트릭스가 정확히 0 인 고유치를 갖는 것은 거의 없습니다. 대각선에 작은 양의 값을 가진 대각선 행렬을 추가하여 행렬을 양의 값으로 만들 수 있습니다. 이것은 본질적으로 최소 2- 놈의 해를 선택합니다. 실제로는 0에 가까운 고유 값을 갖는 행렬은 종종 수치 해석을하는 데 문제를 일으킬 수 있기 때문에 행렬이 양의 값인 경우에도이를 수행하는 것이 좋습니다. 추가 할 대각선은 안정성과 정확성 사이의 균형입니다.

행렬이 부정한 경우 (즉, 하나의 음의 고유 값을 갖는 경우) 문제는 NP 하드입니다. 즉, 현재 사용 가능한 알고리즘을 기반으로하는 모든 코드는 중간 크기의 문제에 대해서조차도 부당한 최악의 실행 시간을 갖게됩니다. 문제가 특별한 구조를 가지고 있거나 전 세계적으로 최적의 솔루션을 필요로하지 않는다면 괜찮을 것입니다. 전형적인 접근법은 볼록 이완을 찾는 것입니다.