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