¿Hay una biblioteca de programación cuadrática en C++?

Question

El único resultado de búsqueda de Google que encontré es QuadProg ++ pero no puede resolver el problema de programación cuadrática cuya matriz no es aplicable para la descomposición de Cholesky.

¿Puede alguien darme alguna sugerencia en otra biblioteca? Gracias.

Answer 1

LAPACK tiene una serie de rutinas de descomposición de Cholesky (lo llaman la factorización de Cholesky). Hay contenedores de C++ disponibles para LAPACK (consulte este SO question para obtener una lista).

La respuesta de Anycom en esa publicación es un poco críptica, pero quiso decir que hay enlaces LAPACK que se pueden usar junto con la biblioteca de álgebra lineal de Boost, uBLAS.

---

que he encontrado esta biblioteca: OOQP (software orientado a objetos para la programación cuadrática). Si se desplaza hacia abajo en esa página, encontrará un documento de investigación y una guía del usuario. Parece que hay una API de C++ para esa biblioteca. Espero que esto ayude.

Answer 2

CGAL se ve muy bien para la programación cuadrática. Incluso hay 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)); 

Código de the first example.

Answer 3

Si usted está dispuesto a pagar, puede utilizar Mosek. Sin embargo, hay una prueba gratuita de 30 días. En general se considera el solucionador más rápido disponible (sin cita, lo siento). La interfaz es de estilo C, aunque obviamente es perfectamente callalbe de C++. Mosek es más un solucionador de programación cónica, pero si no tiene ganas de reformular su problema como un problema cónico (Mosek tiene mucha documentación sobre cómo hacerlo), puede usar su solucionador de pendiente gradiente estocástico para resolver tu formulación cuadrática

Answer 4

La sutileza de que muchas de las respuestas anteriores son falta es si la matriz es único positivo semi-definido (PSD) o es en realidad indefinida. No he utilizado quadprog, pero si falla en una matriz objetivo PSD, eso es un signo de falta de robustez del software (CPE convexas son a menudo PSD, donde sólo estrictamente convexas personas cualificadas son definida positiva). De acuerdo con el libro de Golub "Computación de matrices", la factorización de Cholesky se puede aplicar a las matrices de PSD, pero la estabilidad numérica tiende a sufrir.

Para la programación no lineal en general en software tanto convexo y no convexo, la O-COIN proyecto mantiene listas de software libre y no libre. Uno de los solucionadores que enumeran es IPOPT, que sin duda es capaz de resolver su problema. IPOPT usa un algoritmo de punto interior, que para problemas pequeños, generalmente es más lento que los métodos de conjunto activo (como quadprog usa). Como alternativa, puede formular su QP como un problema de complementariedad lineal (LCP) y luego resolverlo usando un solucionador LCP. He encontrado que el código LEMKE de Matlab de Fackler y Miranda es fácilmente transferible a C++.

Answer 5

Hay varias bibliotecas que incluyen solucionadores de QP. Hay opciones tanto de código abierto como comerciales. Las respuestas existentes enumeran algunas de ellas. Me gustaría aclarar el problema con la matriz.

Supongo que se está refiriendo a la matriz de objetivos. La matriz de restricciones solo necesita conducir a un conjunto factible no vacío. Usted mencionó que la matriz no es adecuada para la descomposición de Cholesky. Dado que la descomposición de Cholesky se puede formar para cualquier matriz definida positiva, la implicación es que su matriz no es positiva definida.

Si la matriz es positiva semi-definida (es decir, tiene uno o más valores propios cero), entonces el problema es una QP convexa y se puede resolver de manera eficiente. Sin embargo, muchos solucionadores requieren un objetivo definido positivo. Dado que el objetivo de una QP semidefinida positiva tiene un espacio nulo no trivial, puede haber muchas soluciones. De hecho, el conjunto de soluciones puede ser ilimitado. Los algoritmos numéricos solo darán una solución aproximada de todos modos, por lo que rara vez es importante que la matriz tenga valores propios que sean exactamente cero. Puede hacer la matriz positiva definida agregando una matriz diagonal con un pequeño valor positivo en la diagonal. Esto esencialmente seleccionará la solución con la norma de 2 más pequeña. En la práctica, es una buena idea hacer esto incluso cuando la matriz es positiva definida porque las matrices que tienen valores propios cercanos a cero a menudo pueden causar problemas con los solucionadores numéricos. Qué diagonal agregar es una compensación entre estabilidad y precisión.

Si la matriz es indefinida (es decir, tiene incluso un autovalor negativo), el problema es NP-hard. Esto significa que cualquier código basado en los algoritmos actualmente disponibles tendrá tiempos de ejecución irrazonable en el peor de los casos, incluso para problemas de tamaño moderado. Si su problema tiene alguna estructura especial o no requiere una solución globalmente óptima, entonces puede estar bien. Un enfoque típico es buscar una relajación convexa.