Y a-t-il une bibliothèque de programmation quadratique en C ++?

Il y a plusieurs bibliothèques qui incluent QP solveurs. Il y a à la fois open-source et les options commerciales. Les questions /réponses de la liste de quelques-uns de ces. Je tiens à clarifier la question avec la matrice.

Je suppose que vous faites référence à l'objectif de la matrice. La contrainte de la matrice ne doit conduire à un non-vide possible ensemble. Vous avez mentionné que la matrice n'est pas adapté pour la décomposition de Cholesky. Depuis la décomposition de Cholesky peut être formé pour toute matrice définie positive, l'implication est que votre matrice est définie positive.

Si la matrice est semi-définie positive (c'est à dire qu'il a un ou plusieurs zéro les valeurs propres) alors le problème est convexe QP et peuvent être résolus de manière efficace. Cependant, de nombreux problèmes nécessitent positif de l'objectif défini. Étant donné que l'objectif d'un semi-définie positive QP est un non-trivial nullspace, il peut y avoir beaucoup de solutions. En fait, l'ensemble des solutions peut-être même sans bornes. Algorithmes numériques ne fera que donner une solution approximative de toute façon, de sorte qu'il est rarement important que la matrice de valeurs propres qui sont exactement zéro. Vous pouvez faire de la matrice définie positive par l'ajout d'une matrice diagonale avec une petite valeur positive sur la diagonale. Ce sera l'essentiel de sélectionner la solution avec le plus petit 2-norme. Dans la pratique, c'est une bonne idée de faire ce même lorsque la matrice est définie positive, car les matrices qui ont des valeurs propres proches de zéro peuvent souvent causer des problèmes avec les solveurs numériques. Combien diagonale à ajouter dans est un compromis entre la stabilité et de la précision.

Si la matrice est à durée indéterminée (c'est même une valeur propre négative), alors le problème est NP-dur. Cela signifie que tous les codes basés sur les algorithmes disponibles auront déraisonnable des cas les pires temps d'exécution, même modérée de la taille des problèmes. Si votre problème a une certaine structure spéciale ou vous n'avez pas besoin d'une solution globalement optimale, alors vous pourriez être ok. Une approche classique consiste à regarder pour une relaxation convexe.

CGAL ressemble beaucoup pour la programmation quadratique. Il en est de même un manuel.

  //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));

Code de le premier exemple.

Si vous êtes prêt à payer, vous pouvez utiliser Mosek. Il y a un essai gratuit de 30 jours, si. Il est généralement considéré comme le plus rapide du solveur disponible (pas de citation, désolé), L'interface est de type C, même si évidemment perfectally callalbe à partir de C++. Mosek est vraiment plus d'une conique solveur de programmation, mais si vous n'avez pas envie de reformuler votre problème comme une conique problème (Mosek a beaucoup de documentation sur la façon de le faire), vous pouvez toujours utiliser ses la descente de gradient stochastique solveur pour résoudre votre formulation quadratique.