CGAL::Quadratic_program二次目标函数交叉项及约束条件设置咨询

Hey there! Let's tackle your CGAL quadratic programming questions one by one—this stuff can feel a bit opaque at first, but it clicks once you get the hang of how the library structures quadratic terms.

1. 设置目标函数的交叉项（45xy） #

First, let's recall how CGAL defines the quadratic program's objective function: it's structured as minimize (1/2) * xᵀQx + cᵀx, where Q is a symmetric matrix.

You already nailed the diagonal terms:

• qp.set_d(X, X, 50) translates to (1/2)*50x² = 25x², which matches your target
• qp.set_d(Y, Y, 2) translates to (1/2)*2y² = y², perfect for your y² term

For the cross term 45xy: since Q is symmetric, Q[X][Y] equals Q[Y][X]. The combined contribution of these two matrix entries to the objective function is (1/2)*Q[X][Y]xy + (1/2)*Q[Y][X]xy. To get exactly 45xy, we just need Q[X][Y] = 45 (since (1/2)*45 + (1/2)*45 = 45).

So all you need to add is:

qp.set_d(X, Y, 45);

CGAL handles the symmetry automatically, so you don't need to set qp.set_d(Y, X, 45) separately (though doing so won't break anything either).

2. 正确添加约束条件 #

Your constraint (25 + y) + 25x ≤ 1 needs to be rearranged into CGAL's standard linear constraint form: a₁x + a₂y ≤ b.

Let's rearrange the terms:
25x + y + 25 ≤ 1 → 25x + y ≤ 1 - 25 → 25x + y ≤ -24

Your code for setting the coefficients is correct (qp.set_a(X, 0, 25) and qp.set_a(Y, 0, 1)), but you need to fix the right-hand side value. Instead of qp.set_b(0, 1), use:

qp.set_b(0, -24);

By default, CGAL uses LESS_EQUAL as the constraint type, which is exactly what we need here—no extra setup required for that.

Full Example Snippet #

Here's how all the pieces fit together in code:

#include <CGAL/Quadratic_program.h>
#include <CGAL/Quadratic_program_solution.h>

typedef CGAL::Quadratic_program<double> Program;
typedef CGAL::Quadratic_program_solution<double> Solution;

int main() {
    // Initialize program: adjust variable bounds as needed (here, no fixed bounds)
    Program qp(CGAL::SMALLER, false, 0, false, 0);
    const int X = 0;
    const int Y = 1;

    // Set objective function: 25x² + 45xy + y²
    qp.set_d(X, X, 50);
    qp.set_d(Y, Y, 2);
    qp.set_d(X, Y, 45);

    // Set constraint: 25x + y ≤ -24
    qp.set_a(X, 0, 25);
    qp.set_a(Y, 0, 1);
    qp.set_b(0, -24);

    // Solve the program
    Solution solution = CGAL::solve_quadratic_program(qp, CGAL::Gmpq());

    // Process the solution (example output)
    if (solution.is_optimal()) {
        std::cout << "Optimal value: " << solution.objective_value() << std::endl;
        std::cout << "x = " << solution.variable_value(X) << std::endl;
        std::cout << "y = " << solution.variable_value(Y) << std::endl;
    }

    return 0;
}

内容的提问来源于stack exchange，提问作者Pavel Sedlář