利用矩阵线性等式约束最小化 L1 范数

Question

我需要在 Mx = y 的情况下最小化 L_1(x)。

x 是维度为 b 的向量，y 是维度为 a 的向量，M 是维度为 (a,b) 的矩阵。

经过一番阅读后，我决定使用 scipy.optimize.minimize：

import numpy as np
from scipy.optimize import minimize

def objective(x):     #L_1 norm objective function
    return np.linalg.norm(x,ord=1)

constraints = [] #list of all constraint functions
for i in range(a):
    def con(x,y=y,i=i):
        return np.matmul(M[i],x)-y[i]
    constraints.append(con)

#make constraints into tuple of dicts as required by scipy 
cons = tuple({'type':'eq','fun':c} for c in constraints)

#perform the minimization with sequential least squares programming
opt = minimize(objective,x0 = x0,
                        constraints=cons,method='SLSQP',options={'disp': True})

首先， x0 我可以用什么？ x 未知，我需要一个满足约束 M*x0 = y 的 x0：如何找到满足约束的初始猜测？ M 是独立高斯变量的矩阵 (~N(0,1)) 如果有帮助的话。

第二， 是我设置的方式有问题吗？当我使用真实的 x（我在开发阶段碰巧知道）作为 x0 时，我希望它能够快速返回 x = x0。相反，它返回一个零向量 x = [0,0,0...,0]。这种行为是出乎意料的。

编辑：

这是使用 cvxpy** 求解 min(L_1(x)) 的解决方案，且满足 Mx=y：

import cvxpy as cvx

x = cvx.Variable(b) #b is dim x  
objective = cvx.Minimize(cvx.norm(x,1)) #L_1 norm objective function
constraints = [M*x == y] #y is dim a and M is dim a by b
prob = cvx.Problem(objective,constraints)
result = prob.solve(verbose=False)

#then clean up and chop the 1e-12 vals out of the solution
x = np.array(x.value) #extract array from variable 
x = np.array([a for b in x for a in b]) #unpack the extra brackets
x[np.abs(x)<1e-9]=0 #chop small numbers to 0 

Answer 1

基于近端梯度的方法可以非常有效地解决此类问题。

让我们来表述这个问题（使用 $ oldsymbol{A} = oldsymbol{M}, ; oldsymbol{y} = oldsymbol{b}$:

其中 $\delta$ 是与 $ oldsymbol{A} oldsymbol{x} = oldsymbol{b}$ 相等的指示函数。

需要的是约束集的投影算子。
它在具有线性等式约束的线性最小二乘 - 迭代求解器中定义。

每次迭代的计算主要是通过求解大小为

(m x m)

的线性系统来控制，其中矩阵 $ oldsymbol{A} \in \mathbb{R}^{m imes n}$:

上图显示了迭代过程中优化的目标值（以 dB 为单位）。参考文献是使用凸求解器求解问题 (

Convex.jl

)。

Julia 代码可在我的 StackOverflow Q49787068 GitHub 存储库 中获取（查看

StackOverflow\Q49787068

文件夹）。

备注：最好给流程添加加速（FISTA风格）。这将使收敛速度更快。

备注：另一种选择是将问题表述为线性规划。请参阅用线性等式约束（基追求/稀疏表示）将 L1 范数最小化表述为线性规划。