线性规划——交替方向乘子法（ADMM）

原问题

$\min_x \;c^Tx\\s.t. \;Ax=b\\x\geq 0 \tag{1}$xmin​cTxs.t.Ax=bx≥0(1)

对偶问题

$\max_y\;b^Ty\\s.t.\;A^Ty+s=c\\s\geq 0\tag{2}$ymax​bTys.t.ATy+s=cs≥0(2)
$A \in \R^{m\times n}, x \in \R^{n}, s \in \R^{n}, y \in \R^{m}$A∈Rm×n,x∈Rn,s∈Rn,y∈Rm

---

本文用交替方向乘子法（Alternating Direction Method of Multipilers）实现线性规划问题的求解器。

代码如下：

function [x] = LP_ADMM_dual(c, A, b, opts, x0)

m = size(A,1);
n = size(A,2);

% 随机初始化
y = randn(m,1);
x = x0; 
s = randn(n,1);

t = 0.1;  % ALM rate

S = A*A';
U = chol(S);
L = U'; %cholesky decomposition: S = L*U = U'*U

err = 1;
x_old = x;
while(err > 1e-6)
    
    y = -U\(L\((A*x-b)/t+A*(s-c)));  % 固定 x,s, 更新 y
    
    s = max(c-A'*y-x/t,0); % 固定 y,x, 更新 s
    
    x = x + (A'*y+s-c)*t;  % 固定 y,s, 更新 x
    
    err = norm(x-x_old);
    x_old = x;
end

end

测试：

% 生成数据
n = 100;
m = 20;
A = rand(m,n);
xs = full(abs(sprandn(n,1,m/n)));
b = A*xs;
y = randn(m,1);
s = rand(n,1).*(xs==0);
c = A'*y + s;

% 计算误差
errfun = @(x1, x2) norm(x1-x2)/(1+norm(x1));

% 标准答案
figure(1);
subplot(2,1,1);
stem(xs,'fill','k-.')
title('exact solu');

% ADMM 求解
opts = [];
tic;
[x1, out] = LP_ADMM_dual(c, A, b, opts, x0);
t1 = toc;
subplot(2,1,2);
stem(x1,'fill','k-.');
title('lp_admm_dual');

fprintf('lp-alm-dual: cpu: %5.2f, err-to-exact: %3.2e\n', t2, errfun(x1, xs));

lp-admm-dual: cpu:  0.08, err-to-exact: 1.17e-04

又快又准！！！