MATLAB与Python中线性规划的冲突解

Question

我正在尝试运行一个大型线性程序，并正在将我以前的一些代码从MATLAB翻译成Python。然而，问题是，MATLAB和Python给我的答案是完全矛盾的：MATLAB代码找到了最佳的解决方案，而Python代码却说这个问题是不可行的。这是一个有限元模型的无限回归或极小极大回归。我对这两个功能的设置相当有信心。在

MATLAB代码：

function [ x_opt, f_opt, exitflag, output] = ell_infinity_reg_solver( A, b )
% Solves the ell_infinity regression problem ||Ax - b||_inf.  That is finds
% the least t for which Ax - b < t.ones and Ax - b > -t.ones.
[n,d] = size(A) ;  
if n == 0
    f_opt  = 0 ;
    x_opt = zeros(d,1) ;
    return
end

% infinity norm
f = [ zeros(d,1); 1 ];
A = sparse([ A, -ones(n,1) ; -A, -ones(n,1) ]);
b = [ b; -b ];
[xt, f_opt, exitflag, output] = linprog(f,A,b);
x_opt = xt(1:d,:);


end

Python代码

^{pr2}$

由于scipy方法不起作用，我还尝试了CVXOPT添加行

c = cvxopt.matrix(f)
G = cvxopt.matrix(X)
h = cvxopt.matrix(Y)
output = cvxopt.solvers.lp(c, G, h, solver='glpk')

但这又返回了一个dual-infeasible的标志，它与使用的MATLAB exitflag=1（成功）和dual-simplex算法形成对比。在

我测试的数据是一个500×11的数据矩阵，有一组相关的响应变量。在

我感兴趣的是，是什么导致了产出的如此显著的差异，哪一个是正确的。有一件事确实增加了混乱，那就是将输入的大小减少到小于满秩的值，这似乎不会影响MATLAB的输出标志，但是Python代码并没有找到一个最佳的解决方案（正如我所预期的那样）。在

数据位于https://www.dropbox.com/s/g4qcj1q0ncljawq/dataset.csv?dl=0，矩阵A是前11列，目标向量是最后一列。在

Answer 1

（1）默认变量边界几乎总是零和无穷大。一、 e.除非另有说明，大多数解算器都假设非负变量。Matlab使用不同的默认值。默认情况下变量是自由的。在

对于您的模型，这意味着您需要显式地告诉linprog变量是免费的。t变量可以是自由变量，也可以是非负变量。在

因此

output = linprog(f, A_ub=big_A, b_ub=big_b, bounds=(None,None),method='interior-point' )

对于单纯形法来说，模型有点大（单纯形实现有点像玩具算法）。新的内点法没有问题。在

（2）线路

^{pr2}$

应该读一下

big_A = np.hstack((np.vstack((A,-A)), -np.ones((2*n,1))))

（3）还要注意你的模型

min t :
Ax - b <= t * ones
b - Ax >= - t*ones

不正确。它应该是：

min t :
Ax - b <= t * ones
Ax - b >= - t*ones

作为LP输入：

min t :
 Ax - t <= b
-Ax - t  <= -b

（也有其他配方可以解决这个问题，有些配方不会储存两次。见[link]）