matlab - MATLAB：特定线性程序的快速且内存高效的解决方案

Question

我有一点编程经验，所以我很确定我没有以最佳方式对问题进行编码，所以我很乐意听到任何提示。

我有两个参数：问题的维度n和N x N约束矩阵Bwhere N = 2n。在我的情况下B是对称的，只有正值。我需要解决以下问题

优化问题

也就是说，我需要最大化某个平均距离，并受到由给出的成对距离的约束B(i,j)。

我现在这样做的方式是linprog(-f,A,b)where的实现

f = ones([1,n])/n;
f = [f -f]

和

b = reshape(B',numel(B),[])

并A定义如下

 A = zeros([N^2,N]);
 for i = 1:N
  for j = 1:N
    if i ~= j
      A((i-1)*N + j,i)   =  1;
      A((i-1)*N + j,j)   = -1;
   end
 end
end

然而，n = 500即使是一个简单的构造也A需要相当长的时间，更不用说线性程序的解需要多长时间了。任何提示都非常感谢，请随时重新标记。

score 2 · Accepted Answer

首先，尝试A像这样构建：

AI = eye(N);
AV = ones(N, 1);
A = kron(AI, AV) - kron(AV, AI);

我认为它的运行速度至少应该比你创建它的方式快一个数量级。

score 1 · Accepted Answer

除了以更有效的方式创建问题矩阵之外，您可能还想考虑将glpk与 MATLAB 的glpkmex接口一起使用。我发现我的解决时间可以大大减少。根据问题的大小，您可能会看到另一个数量级的减少。

如果您是一名学者，您可以免费获得 CPLEX 或 Gurobi 许可证，这应该可以让您进一步减少求解时间，而无需大量摆弄求解器参数。对于您描述的大小问题，这可能是必要的。

2 回答 2