Có thư viện lập trình bậc hai trong C++ không?

Question

Kết quả tìm kiếm Google duy nhất tôi tìm thấy là QuadProg ++ nhưng không thể giải quyết được vấn đề lập trình bậc hai mà ma trận không áp dụng cho phân tách Cholesky.

Vì vậy, bất kỳ ai cũng có thể cho tôi một số gợi ý về thư viện khác không? Cảm ơn.

Answer 1

LAPACK có một số quy trình phân tách Cholesky (chúng gọi là hệ số Cholesky). Có các trình bao bọc C++ có sẵn cho LAPACK (xem SO question này cho một danh sách).

Câu trả lời từ Anycom trong bài đăng đó hơi khó hiểu nhưng có nghĩa là có các ràng buộc LAPACK có thể được sử dụng cùng với thư viện đại số tuyến tính của Boost, uBLAS.

---

Tôi đã tìm thấy thư viện này: OOQP (Phần mềm hướng đối tượng cho lập trình bậc hai). Nếu bạn cuộn xuống trang đó, bạn sẽ tìm thấy một tài liệu nghiên cứu và hướng dẫn sử dụng. Dường như có một API C++ cho thư viện đó. Hi vọng điêu nay co ich.

Answer 2

CGAL có vẻ tuyệt vời cho lập trình bậc hai. Thậm chí còn có 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)); 

Mã từ the first example.

Answer 3

Nếu bạn sẵn sàng trả tiền, bạn có thể sử dụng Mosek. Tuy nhiên, có 30 ngày dùng thử miễn phí. Nó thường được coi là giải quyết nhanh nhất có sẵn (không có trích dẫn, xin lỗi) Giao diện là phong cách C, mặc dù rõ ràng là hoàn hảo callalbe từ C + +. Mosek thực sự là một giải pháp lập trình conic, nhưng nếu bạn không muốn cải thiện vấn đề của mình như một vấn đề conic (Mosek có rất nhiều tài liệu về cách làm điều này), bạn vẫn có thể sử dụng trình giải mã gốc ngẫu nhiên của nó để giải quyết công thức bậc hai của bạn.

Answer 4

Sự tinh tế mà nhiều câu trả lời ở trên bị thiếu là liệu ma trận chỉ có bán xác định dương (PSD) hoặc thực sự không xác định. Tôi đã không sử dụng quadprog, nhưng nếu nó thất bại trên một ma trận mục tiêu PSD, đó là một dấu hiệu của sự thiếu mạnh mẽ của phần mềm (QP lồi thường PSD, nơi chỉ nghiêm lồi QPs là xác định dương). Theo cuốn sách "Ma trận tính toán" của Golub, hệ số Cholesky có thể được áp dụng cho các ma trận PSD, nhưng độ ổn định số có xu hướng bị ảnh hưởng.

Đối với phần mềm lập trình phi tuyến tính chung - cả lồi và không lồi, dự án COIN-OR duy trì danh sách phần mềm miễn phí và không miễn phí. Một trong những người giải quyết họ liệt kê là IPOPT, chắc chắn có khả năng giải quyết vấn đề của bạn. IPOPT sử dụng thuật toán điểm nội tại, cho các vấn đề nhỏ, thường chậm hơn so với các phương thức thiết lập hoạt động (như sử dụng quadprog). Thay vào đó, bạn có thể xây dựng QP của bạn như là một vấn đề bổ sung tuyến tính (LCP) và sau đó giải quyết nó bằng cách sử dụng bộ giải mã LCP. Tôi đã tìm thấy mã Matlab của Fackler và Miranda là LEMKE để dễ dàng chuyển sang C++.

Answer 5

Có một số thư viện bao gồm trình giải mã QP. Có cả hai tùy chọn mã nguồn mở và thương mại. Các câu trả lời hiện có liệt kê một vài trong số này. Tôi muốn làm rõ vấn đề với ma trận.

Tôi giả sử bạn đang đề cập đến ma trận mục tiêu. Ma trận ràng buộc chỉ cần dẫn đến một tập hợp khả thi không trống. Bạn đã đề cập rằng ma trận không phù hợp để phân tách Cholesky. Vì việc phân tách Cholesky có thể được hình thành cho bất kỳ ma trận xác định dương nào, nên hàm ý là ma trận của bạn không xác định dương.

Nếu ma trận là bán xác định dương (nghĩa là ma trận có một hoặc nhiều giá trị riêng) thì vấn đề là QP lồi và có thể được giải quyết một cách hiệu quả. Tuy nhiên, nhiều người giải quyết yêu cầu một mục tiêu xác định tích cực. Vì mục tiêu của một QP bán xác định dương có một không gian vô giá trị, có thể có nhiều giải pháp. Trong thực tế, bộ giải pháp thậm chí có thể không bị chặn. Thuật toán số sẽ chỉ đưa ra một giải pháp gần đúng, vì vậy hiếm khi quan trọng là ma trận có giá trị riêng là chính xác bằng không. Bạn có thể làm cho ma trận xác định dương bằng cách thêm một ma trận đường chéo với một giá trị dương nhỏ trên đường chéo. Về cơ bản, điều này sẽ chọn giải pháp với 2-norm nhỏ nhất. Trong thực tế, nó là một ý tưởng tốt để làm điều này ngay cả khi ma trận là xác định dương vì ma trận có giá trị riêng gần bằng không thường có thể gây ra vấn đề với giải quyết số. Làm thế nào nhiều đường chéo để thêm vào là một sự cân bằng giữa sự ổn định và chính xác.

Nếu ma trận không xác định (nghĩa là ma trận thậm chí có một giá trị riêng biệt âm) thì vấn đề là NP-hard. Điều đó có nghĩa là bất kỳ mã nào dựa trên các thuật toán hiện có sẽ có thời gian chạy trường hợp xấu nhất không hợp lý ngay cả đối với các vấn đề có kích thước vừa phải. Nếu vấn đề của bạn có một số cấu trúc đặc biệt hoặc bạn không yêu cầu một giải pháp tối ưu toàn cầu thì bạn có thể ổn. Một cách tiếp cận điển hình là tìm kiếm một sự thư giãn lồi.