CGAL求解一个二次规划问题

Question

我有一个qp问题:

Minimize: -5x0 - x1 - 4x2 - 5x5 + 1000x0x2 + 1000x1x2 + 1000x0x3 
      + 1000x1x3 + 1000x0x4 +1000x1x4
Subject to: x0>=0 x1>=0 x2>=0 x3>=0 x4>=0 x5>=0
        x0+x1+x5<=5      
        x2+x3+x4<=5

答案应该是X0=0 X1=0 X2=5 X3=0 X4=0 X5=5和obj=-45

但是CGAL给出X0=5 X1=0 X2=0 X3=0 X4=0 X5=0 obj=-25

代码粘贴如下:

如有任何建议，不胜感激。

凯利

#include <iostream>
#include <climits>
#include <cassert>
#include <CGAL/basic.h>
#include <CGAL/QP_models.h>
#include <CGAL/QP_functions.h>
// choose exact integral type
#ifdef CGAL_USE_GMP
#include <CGAL/Gmpz.h>
typedef CGAL::Gmpz ET;
#else
#include <CGAL/MP_Float.h>
typedef CGAL::MP_Float ET;
#endif
using namespace std;
// program and solution types
typedef CGAL::Quadratic_program<int> Program;
typedef CGAL::Quadratic_program_solution<ET> Solution;
int
main(){
    Program qp (CGAL::SMALLER, true, 0.0, false, 0.0);
    qp.set_c(0, -5);
    qp.set_c(1, -1);
    qp.set_c(2, -4);
    qp.set_c(5, -5);
    int g = 1000;
    qp.set_d(2, 0, g);
    qp.set_d(2, 1, g);
    qp.set_d(3, 0, g);
    qp.set_d(3, 1, g);
    qp.set_d(4, 0, g);
    qp.set_d(4, 1, g);
    int nRow = 0;
    qp.set_a(0, nRow,  1.0);
    qp.set_a(1, nRow,  1.0);
    qp.set_a(5, nRow,  1.0);
    qp.set_b(nRow, 5);
    nRow++;
    qp.set_a(2, nRow,  1.0);
    qp.set_a(3, nRow,  1.0);
    qp.set_a(4, nRow,  1.0);
    qp.set_b(nRow, 5);
    Solution s = CGAL::solve_quadratic_program(qp, ET());
    assert (s.solves_quadratic_program(qp));
    CGAL::print_nonnegative_quadratic_program(std::cout, qp, "first_qp");
    std::cout << s;
    return 0;
}          

Answer 1

由于您的矩阵D(二次目标函数)不是正半定的，因此您的结果并不那么令人惊讶。CGAL不保证收敛到全局最小值，但保证收敛到局部最小值。你得到的是一个局部最小值，尊重你施加的约束。

如果您通过写qp.set_l(2,true,1); qp.set_l(5,true,1);将x2和x5的最小边界设置为1，您将看到您收敛于您计算的解。