使用jac和hess时linear_sum_assignment与minimize结果差异过大问题

开发者阿泽

2026-6-13

问题：scipy中linear_sum_assignment与minimize带jac/hess时结果不一致

我在使用scipy库的linear_sum_assignment和minimize函数解决指派问题时遇到了困扰。为了对比更复杂的问题，我需要确保minimize给出的最优结果与linear_sum_assignment一致，但使用梯度（jac）或海森矩阵（hess）时，两者结果差异显著。

指派问题的定义可参考维基百科的指派问题线性规划解法章节。

linear_sum_assignment直接处理二维数组形式的成本（或权重）矩阵，假设变量以矩阵X存储，并内置处理以下约束：

X的每个元素取值在[0,1]区间内
X的每行、每列元素之和均为1

当我尝试用minimize函数获取相同结果时，使用梯度和/或海森矩阵会导致结果差异很大。

以下是使用两个函数进行指派问题优化的代码：

import numpy as np
from scipy.optimize import linear_sum_assignment, minimize, LinearConstraint 

# example of cost matrix
cost = np.array(((54,54,51,53),(51,57,52,52),(50,53,54,56),(56,54,55,53)))

# number of variables:
n = 4 # matrix size
n2 = n*n # the real number of variables

# OPTIMAL ASSIGNMENT USING linear_sum_assignment:
row_ind, col_ind = linear_sum_assignment(cost)
X = np.zeros_like(cost)
X[row_ind, col_ind] = 1
# print(X)

# OPTIMAL ASSIGNMENT USING minimize:

# function definition
fun  = lambda x, c: c.dot(x)
jac  = lambda x, c: c
hess = lambda x, c: np.zeros((len(c), len(c)))

# argument:
cost2 = cost.flatten().astype(float)

# matrix of the linear constraints:
A = np.zeros((2*n,n2))
for i in range(n):
    A[i, i*n:(i+1)*n] = 1
    A[n+i, i::n] = 1
# print(A)

# array of ones for the rhs of the equality constraints:
ones = np.ones(2*n)

# linear constraints:
lin_constraints = LinearConstraint(A, lb=ones, ub=ones)

# bounds of variables:
bounds = [(0,1)]*n2

# initial condition:
x0 = np.eye(n).flatten()

# call to minimize:
res = minimize(fun, x0, args=(cost2,), constraints=[lin_constraints], bounds=bounds,
                   method='trust-constr', jac=jac, hess=hess)

# COMPARE RESULTS
X2 = res.x.reshape((n,n))
print(np.abs(X2-X).max())

当设置jac=None、hess=None调用minimize时，结果最优，误差约为1.5e-7；但使用海森矩阵时，误差增至8e-4；同时使用梯度和海森矩阵时，误差超过0.07。

这是为什么？似乎梯度和海森矩阵的定义存在问题，但我多次检查仍未发现错误，恳请各位提供帮助。

原因分析与解决方案

核心问题：海森矩阵定义不符合`trust-constr`的要求

trust-constr方法要求传入的海森矩阵是拉格朗日函数的海森矩阵，而非原目标函数的海森矩阵。你的目标函数是线性的，原海森矩阵确实是零矩阵，但拉格朗日函数包含约束项，在trust-constr的优化逻辑中，需要的是考虑约束后的海森近似，而非单纯的零矩阵。

当你手动传入hess=np.zeros(...)时，优化器会错误地认为拉格朗日函数的海森矩阵为零，导致信任域的更新方向计算偏差，最终无法收敛到精确的0-1最优解（指派问题的最优解是0-1矩阵）。

而不指定jac和hess时，scipy会自动用数值方法计算梯度和拉格朗日海森矩阵，这种数值计算更适配trust-constr的需求，因此能收敛到更接近真实解的结果。

解决方案

仅指定jac，不手动传入hess：如果需要用解析梯度，可以只设置jac=jac，让scipy自动计算拉格朗日海森矩阵。修改后的调用代码：

res = minimize(fun, x0, args=(cost2,), constraints=[lin_constraints], bounds=bounds,
               method='trust-constr', jac=jac)

这种情况下误差会大幅降低，接近不指定jac/hess的效果。

换用线性规划专用求解器：指派问题本质是0-1线性规划，scipy的linprog函数专门针对这类问题优化，能直接得到更精确的结果。示例代码：

from scipy.optimize import linprog

# 目标函数系数是cost2，求最小值
res_lp = linprog(cost2, A_eq=A, b_eq=ones, bounds=bounds, method='highs')
X_lp = res_lp.x.reshape(n, n)
print(np.abs(X_lp - X).max())

这种方法的误差远小于trust-constr，因为linprog是为线性规划场景设计的。

正确构造拉格朗日海森矩阵（可选）：如果一定要手动传入hess，需要构造考虑约束的拉格朗日海森矩阵。不过对于线性约束+线性目标的场景，这种做法性价比极低，不如直接使用专用求解器。

补充说明

linear_sum_assignment是指派问题的专用算法（匈牙利算法），能直接输出精确的0-1解；而trust-constr是通用非线性优化器，对于线性规划这类特殊问题，收敛精度和效率都不如专用工具。如果你的最终目标是扩展到复杂问题，建议先在简单线性场景下选对求解器，再逐步迭代。

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

使用jac和hess时linear_sum_assignment与minimize结果差异过大问题

核心问题：海森矩阵定义不符合trust-constr的要求 #

解决方案 #

补充说明 #

核心问题：海森矩阵定义不符合`trust-constr`的要求

解决方案

补充说明