为何Cplex求解简单二次规划问题输出错误结果？

问题描述 #

需要极小化的目标函数：
$f = x^2 + y^2 + z^2$
其中x、y、z为连续变量。

约束条件：

• $x + 2y - z = 4$
• $x - y + z = -2$

理论最优解为$f≈2.8571$，对应$x≈0.2857$、$y≈1.4286$、$z≈-0.8571$，但使用CPLEX求解后得到次优解$f=4$，对应$x=0$、$y=2$、$z=0$。

原错误代码 #

import cplex

def solve_and_display(p):
    
    p.solve()

    # solution.get_status() returns an integer code
    print ("Solution status = " , p.solution.get_status(), ":",)
    # the following line prints the corresponding string
    print (p.solution.status[p.solution.get_status()])
    print ("Solution value  = ", p.solution.get_objective_value())

    numrows = p.linear_constraints.get_num()

    for i in range(numrows):
        print ("Row ", i, ":  ",)
        print ("Slack = %10f " %  p.solution.get_linear_slacks(i),)
        print ("Pi = %10f" % p.solution.get_dual_values(i))

    numcols = p.variables.get_num()

    for j in range(numcols):
        print ("Column ", j, ":  ",)
        print ("Value = %10f " % p.solution.get_values(j),)
        print ("Reduced Cost = %10f" % p.solution.get_reduced_costs(j))

import cplex
problem = cplex.Cplex()


problem.variables.add(names=['x', 'y', 'z'])

qmat = [[[0,1,2],[2, 0, 0]],
        [[0,1,2],[0, 2, 0]],
        [[0,1,2],[0, 0, 2]]]
problem.objective.set_quadratic(qmat)

# The solution is also wrong when using set_quadratic_coefficients
# problem.objective.set_quadratic_coefficients([('x', 'x', 1), ('y', 'y', 1), ('z', 'z', 1)])

problem.objective.set_sense(problem.objective.sense.minimize)

problem.linear_constraints.add(
    lin_expr=[[['x', 'y', 'z'], [1, 2, -1]], [['x', 'y', 'z'], [1, -1, 1]]],
    senses=['E', 'E'],
    rhs=[4, -2]
)

problem.solve()

print("Solution:")
print("Objective Value =", problem.solution.get_objective_value())
print("x =", problem.solution.get_values('x'))
print("y =", problem.solution.get_values('y'))
print("z =", problem.solution.get_values('z'))

错误原因 #

1. 二次项系数定义偏差：CPLEX的二次目标函数公式为 $0.5 \times x^T Q x + c^T x$，若要得到目标函数 $f = x^2 + y^2 + z^2$，Q矩阵的对角线元素应为2（因为 $0.5 \times 2x^2 = x^2$）。原代码注释中的set_quadratic_coefficients写法使用了系数1，导致目标函数被错误设置为 $0.5(x^2 + y^2 + z^2)$，干扰了求解结果。
2. 二次项矩阵冗余定义：原代码中qmat包含大量0系数的变量对，虽逻辑上正确，但可能引发求解器的异常处理；规范写法应仅保留非零系数的变量对。
3. 冗余模块导入：代码重复导入cplex模块，虽不影响功能，但属于不规范写法。

修正后的代码 #

import cplex

def solve_and_display(p):
    p.solve()
    print("Solution status = ", p.solution.get_status(), ":",)
    print(p.solution.status[p.solution.get_status()])
    print("Solution value  = ", p.solution.get_objective_value())

    numrows = p.linear_constraints.get_num()
    for i in range(numrows):
        print("Row ", i, ":  ",)
        print("Slack = %10f " %  p.solution.get_linear_slacks(i),)
        print("Pi = %10f" % p.solution.get_dual_values(i))

    numcols = p.variables.get_num()
    for j in range(numcols):
        print("Column ", j, ":  ",)
        print("Value = %10f " % p.solution.get_values(j),)
        print("Reduced Cost = %10f" % p.solution.get_reduced_costs(j))

# 创建问题实例
problem = cplex.Cplex()

# 添加连续变量
problem.variables.add(names=['x', 'y', 'z'], types=[problem.variables.type.continuous]*3)

# 正确设置二次目标函数：Q矩阵对角线元素为2，对应目标函数x²+y²+z²
# 方式1：使用set_quadratic_coefficients
problem.objective.set_quadratic_coefficients([('x', 'x', 2), ('y', 'y', 2), ('z', 'z', 2)])

# 方式2：使用精简的qmat（二选一即可）
# qmat = [[[0], [2]], [[1], [2]], [[2], [2]]]
# problem.objective.set_quadratic(qmat)

# 设置极小化目标
problem.objective.set_sense(problem.objective.sense.minimize)

# 添加线性约束
problem.linear_constraints.add(
    lin_expr=[[['x', 'y', 'z'], [1, 2, -1]], [['x', 'y', 'z'], [1, -1, 1]]],
    senses=['E', 'E'],
    rhs=[4, -2]
)

# 求解并输出结果
problem.solve()
print("\nSolution:")
print("Objective Value =", round(problem.solution.get_objective_value(), 4))
print("x =", round(problem.solution.get_values('x'), 4))
print("y =", round(problem.solution.get_values('y'), 4))
print("z =", round(problem.solution.get_values('z'), 4))

# 可选：调用自定义函数显示详细解信息
# solve_and_display(problem)

修正后结果 #

运行修正后的代码，将得到理论最优解：

• 目标函数值：$≈2.8571$
• 变量值：$x≈0.2857$，$y≈1.4286$，$z≈-0.8571$

内容的提问来源于stack exchange，提问作者FERRYSELING