Единственный результат поиска Google, который я нашел, — это QuadProg++, но он не может решить задачу квадратичного программирования, матрица которой неприменима для разложения Холецкого.
Так может ли кто-нибудь дать мне какое-нибудь предложение по другой библиотеке? Спасибо.
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));
Код из первого примера.
LAPACK имеет несколько процедур декомпозиции Холецкого (они называют это факторизацией Холецкого). Для LAPACK доступны оболочки C++ (см. этот SO вопрос для списка).
Ответ Anycom в этом сообщении немного загадочен, но он имел в виду, что существуют привязки LAPACK, которые можно использовать вместе с библиотекой линейной алгебры Boost, uBLAS.
Я нашел эту библиотеку: OOQP (объектно-ориентированное программное обеспечение для квадратичного программирования ). Если вы прокрутите эту страницу вниз, вы найдете исследовательскую работу и руководство пользователя. Кажется, для этой библиотеки есть C++ API. Надеюсь это поможет.
Есть несколько библиотек, которые включают решатели QP. Существуют как открытые, так и коммерческие варианты. В существующих ответах перечислены некоторые из них. Хочу уточнить вопрос с матрицей.
Я предполагаю, что вы имеете в виду объективную матрицу. Матрица ограничений должна привести только к непустому допустимому множеству. Вы упомянули, что матрица не подходит для разложения Холецкого. Поскольку разложение Холецкого может быть сформировано для любой положительно определенной матрицы, подразумевается, что ваша матрица не является положительно определенной.
Если матрица является положительно полуопределенной (т. е. имеет одно или несколько нулевых собственных значений), то задача является выпуклой КП и может быть решена эффективно. Однако многие решатели требуют положительно определенной цели. Поскольку цель положительно полуопределенного QP имеет нетривиальное нулевое пространство, может быть много решений. На самом деле множество решений может быть даже неограниченным. Численные алгоритмы в любом случае дадут только приближенное решение, поэтому редко важно, чтобы собственные значения матрицы были точно равны нулю. Вы можете сделать матрицу положительно определенной, добавив диагональную матрицу с небольшим положительным значением на диагонали. Это по существу выберет решение с наименьшей 2-нормой. На практике рекомендуется делать это, даже если матрица положительно определена, потому что матрицы с собственными значениями, близкими к нулю, часто могут вызывать проблемы с численными решателями. Сколько диагонали добавить — это компромисс между стабильностью и точностью.
Если матрица неопределенная (т. е. имеет хотя бы одно отрицательное собственное значение), то задача является NP-трудной. Это означает, что любые коды, основанные на доступных в настоящее время алгоритмах, будут иметь необоснованное время работы в худшем случае даже для задач среднего размера. Если ваша проблема имеет какую-то особую структуру или вам не требуется глобально оптимальное решение, то вы можете быть в порядке. Типичный подход состоит в поиске выпуклой релаксации.
Тонкость, которая отсутствует во многих приведенных выше ответах, заключается в том, является ли матрица только положительно-полуопределенной (PSD) или на самом деле неопределенной. Я не использовал quadprog, но если он дает сбой на целевой матрице PSD, это признак недостаточной надежности программного обеспечения (выпуклые QP часто являются PSD, где только строго выпуклые QP являются положительно определенными). Согласно книге Голуба «Матричные вычисления», факторизация Холецкого может применяться к матрицам PSD, но числовая стабильность имеет тенденцию страдать.
Для общего программного обеспечения для нелинейного программирования, как выпуклого, так и невыпуклого, проект COIN-OR поддерживает списки бесплатного и несвободного программного обеспечения. Одним из решателей, которые они перечисляют, является IPOPT, который, безусловно, способен решить вашу проблему. IPOPT использует алгоритм внутренней точки, который для небольших задач обычно медленнее, чем методы с активным набором (например, использует quadprog). В качестве альтернативы вы можете сформулировать свою QP как проблему линейной дополнительности (LCP), а затем решить ее с помощью решателя LCP. Я обнаружил, что код Fackler и Miranda Matlab LEMKE легко переносим на C++.
Если вы готовы платить, вы можете использовать Mosek. Однако есть бесплатная 30-дневная пробная версия. Как правило, он считается самым быстрым из доступных решателей (извините, без ссылок). Интерфейс выполнен в стиле C, хотя очевидно, что он идеально подходит для C++. Mosek на самом деле больше похож на решатель конического программирования, но если вам не хочется переформулировать свою проблему как коническую задачу (у Mosek есть много документации о том, как это сделать), вы все равно можете использовать его решатель стохастического градиентного спуска для решения Ваша квадратичная формулировка.
