精华内容
下载资源
问答
  • 柔性互联配电网是电网目前一个热门的重点研究方向,潮流是分析电力系统稳定的一个重要工具,该方法是用交替迭代法计算混合交直流潮流
  • 简单的二维抛物线方程例子 采用二维交替方向隐格式求解 并且附有matlab程序 适合借鉴
  • ADI(交替方向隐格式)求解二维抛物方程(含matlab程序)其中包括了ADI算法的解析步骤和计算例子,最后附上MATLAB程序以供参考
  • 交替方向乘子是用于求解低秩和稀疏最优化问题的有效算法,这个包提供了交替方向乘子的matlab代码。This package solves several sparse and low-rank optimization problems by M-ADMM proposed in our work
  • ADMM 参考资料: :
  • 交替方向乘子(Alternating Direction Method of Multipliers, ADMM)在信号处理、图像处理、机器学习等领域中应用广泛,其通常用于求解两个优化变量且只含等式约束条件的优化问题,其一般表示形式为: ...

    1.一般形式

    交替方向乘子法(Alternating Direction Method of Multipliers, ADMM)在信号处理、图像处理、机器学习等领域中应用广泛,其通常用于求解两个优化变量且只含等式约束条件的优化问题,其一般表示形式为:

    \begin{array}{ll} \underset{x, y}{\min} & f(x)+g(y) \\ \text { s.t. } & A x+B y=c \end{array}

    其中,xy是优化变量,f(\cdot )g(\cdot)都是凸函数。

    其增广拉格朗日(Augmented Lagrangian)函数可表示为如下:

    L_{\rho }(x, y, \lambda ) = f(x) + g(y) + \lambda ^{T}(Ax + By - c) + \frac{\rho}{2}\left \| Ax + By - c \right \|^{2}_{2}

    其中,\lambda为拉格朗日乘子,\rho为惩罚系数(\rho > 0)

    2.重建中的形式

    在磁共振重建领域,一种将传统压缩感知(CS)算法与深度神经网络结合的重建方法近年来引起了广泛的关注,其相较于传统重建方法具有收敛快,参数可学习的优点,而相比于深度神经网络方法而言,其可解释性强,所需训练样本少。ADMM-Net就是其中的一种典型方法,其将ADMM算法与神经网络进行融合,实现了不错的图像重建质量。本篇文章就讲讲ADMM算法在磁共振领域的应用以及相应的推导过程。

    在磁共振重建中,待优化的数学模型可表示如下:

    \min_{\mathbf{x}} \frac{1}{2} \left \| \mathbf{A} \mathbf{x} - \mathbf{y} \right \|^{2}_{2} + \sum^{L}_{l = 1} \lambda_{l} g(\mathbf{D}_{l} \mathbf{x})

    其中,\mathbf{x}是待重建的图像,\mathbf{y}是k空间(也即傅里叶变换域)观测值,\mathbf{A}是编码矩阵,\mathbf{A} = \mathbf{P} \mathbf{F}\mathbf{P}是欠采样矩阵,\mathbf{F}是傅里叶变换矩阵。\mathbf{D}_{l}表示变换矩阵,其作用就是将原图像变换到另外一个域使其具备一定的特性,比如,原图像\mathbf{x}可能自身不具备稀疏性,但其在某个变换域(傅里叶变换域,小波变换域等等)具有稀疏性。g(\cdot)表示从数据先验中得到的正则化项,\lambda_{l}则表示为相应的正则化系数。

    引入辅助变量\mathbf{z}_{l} = \mathbf{D}_{l} \mathbf{x},则上式就变为两个变量带等式约束的优化问题:

    \begin{array}{ll} \underset{\mathbf{x}}{\min} & \frac{1}{2} \left \| \mathbf{A} \mathbf{x} - \mathbf{y} \right \|^{2}_{2} + \sum^{L}_{l = 1} \lambda_{l} g(\mathbf{z}_{l}) \\ \text { s.t. } & \mathbf{z}_l = \mathbf{D}_l \mathbf{x} \end{array}

    其增广拉格朗日函数为:

    L_{\rho}(\mathbf{x}, \mathbf{z}, \mathbf{\alpha}) = \frac{1}{2}\left \| \mathbf{A} \mathbf{x} - \mathbf{y} \right \|^{2}_{2} + \sum^{L}_{l = 1} [\lambda_{l}g(\mathbf{z}_{l}) + \mathbf{\alpha}_{l}^{T}(\mathbf{D}_{l} \mathbf{x} - \mathbf{z}_{l}) + \frac{\rho_{l}}{2}\left \| \mathbf{D}_{l} \mathbf{x} - \mathbf{z}_{l} \right \|^{2}_{2}]

    其中,\mathbf{\alpha}_{l}为拉格朗日乘子,\rho_{l}为惩罚系数。为了简化该式,我们在此处可以引入一个等价公式:

    2\mathbf{a}^{T}\mathbf{b} + \left \| \mathbf{b} \right \|^{2}_{2} = \left \| \mathbf{a} + \mathbf{b} \right \|^{2}_{2} - \left \| \mathbf{a} \right \|^{2}_{2}

    从而上述增广拉格朗日函数中的项就可以进行如下的替换:

    \mathbf{\alpha}_{l}^{T}(\mathbf{D}_{l} \mathbf{x} - \mathbf{z}_{l}) + \frac{\rho_{l}}{2}\left \| \mathbf{D}_{l} \mathbf{x} - \mathbf{z}_{l} \right \|^{2}_{2} = \frac{\rho_{l}}{2} \left \| \mathbf{D}_{l} \mathbf{x} - \mathbf{z}_{l} + \frac{\alpha_{l}}{\rho_{l}} \right \|^{2}_{2} - \frac{\rho_{l}}{2} \left \| \frac{\alpha_{l}}{\rho_{l}} \right \|^{2}_{2}

    将上式代入,再令\beta_{l} = \frac{\alpha_{l}}{\rho_{l}},从而增广拉格朗日函数则可以表示为:

    L_{\rho}(\mathbf{x}, \mathbf{z}, \mathbf{\beta}) = \frac{1}{2}\left \| \mathbf{A} \mathbf{x} - \mathbf{y} \right \|^{2}_{2} + \sum^{L}_{l = 1} [\lambda_{l}g(\mathbf{z}_{l}) + \frac{\rho_{l}}{2} \left \| \mathbf{D}_{l} \mathbf{x} - \mathbf{z}_{l} + \beta_{l} \right \|^{2}_{2} - \frac{\rho_{l}}{2} \left \| \beta_{l} \right \|^{2}_{2}]

    ADMM算法求解该函数时是交替进行优化的,即先固定其中两个变量,然后再优化另外一个变量,如此重复进行,从而求解形式为迭代公式,忽略无关项,则可以表示为:

    \mathbf{x}^{k+1} := \underset{\mathbf{x}}{\arg \min} L_{\rho}(\mathbf{x}, \mathbf{z}^k_l, \beta^k_l) = \underset{\mathbf{x}}{\arg \min} \frac{1}{2} \left \| \mathbf{A} \mathbf{x} - \mathbf{y} \right \|^2_2 + \sum^L_{l = 1} \frac{\rho_l}{2} \left \| \mathbf{D}_{l} \mathbf{x} - \mathbf{z}^k_{l} + \beta^k_{l} \right \|^2_2

    \mathbf{z}^{k+1}_l := \underset{\mathbf{z}_l}{\arg \min} L_{\rho}(\mathbf{x}^{k+1}, \mathbf{z}_l, \beta^k_l) = \underset{\mathbf{z}_l}{\arg \min} \sum^L_{l = 1} \lambda_l g(\mathbf{z}_l) + \frac{\rho_l}{2} \left \| \mathbf{D}_l \mathbf{x}^{k+1} - \mathbf{z}_l + \beta^k_l \right \|^2_2

    \beta^{k+1}_l := \underset{\beta_l}{\arg \min} L_{\rho}(\mathbf{x}^{k+1}, \mathbf{z}^{k+1}_l, \beta_l) = \underset{\beta_l}{\arg \min} \sum^L_{l = 1} (\beta_l \rho_l)^T(\mathbf{D}_l \mathbf{x}^{k+1} - \mathbf{z}^{k+1}_l)

    对于上述第一项我们可以使用简单的矩阵向量求导公式就能得出相应的解,而对于第二项,则不能使用简单的求导得到解,因为正则化项g(\cdot)是从数据先验中得到的,一般我们是不知其具体表达形式的,此时,可以利用非线性收缩函数进行求解,第三项是来自于未进行替换的拉格朗日函数,对拉格朗日乘子的更新使用最速下降法。从而具体的迭代求解公式可表示为如下:

    \mathbf{x}^{k+1} = (\mathbf{A}^T \mathbf{A} + \sum^L_{l = 1} \rho_l \mathbf{D}^T_l \mathbf{D}_l)^{-1} (\mathbf{A}^T \mathbf{y} + \sum^L_{l = 1} \mathbf{D}^T_l(\mathbf{z}^k_l - \beta^k_l))

    \mathbf{z}^{k+1}_l = S(\mathbf{D}_l \mathbf{x}^{k+1} + \beta^k_l; \frac{\lambda_l}{\rho_l})

    \beta^{k+1}_l = \beta^k_l + \eta _l (\mathbf{D}_l \mathbf{x}^{k+1} - \mathbf{z}^{k+1}_l)

    其中,S(\cdot)为非线性收缩函数,\eta_l为迭代步长。整个迭代流程为先更新原变量\mathbf{x}^{k+1},再更新辅助变量\mathbf{z}^{k+1}_l,最后更新拉格朗日乘子\beta^{k+1}_l。最后,再把\mathbf{A}=\mathbf{P} \mathbf{F}代入第一项,做一些小变换(\mathbf{I} = \mathbf{F}^{-1} \mathbf{F}),就可以得到和ADMM-Net中一模一样的迭代公式了。

    3.迭代公式

    \mathbf{x}^{k+1} = \mathbf{F}^T[\mathbf{P}^T \mathbf{P} + \sum^L_{l = 1} \rho_l \mathbf{F} \mathbf{D}^T_l \mathbf{D}_l \mathbf{F}^T]^{-1} [\mathbf{P}^T \mathbf{y} + \sum^L_{l = 1} \rho_l \mathbf{F} \mathbf{D}^T_l(\mathbf{z}^k_l - \mathbf{\beta}^k_l)]

    \mathbf{z}^{k+1}_l = S(\mathbf{D}_l \mathbf{x}^{k+1} + \beta^k_l; \frac{\lambda_l}{\rho_l})

    \beta^{k+1}_l = \beta^k_l + \eta _l (\mathbf{D}_l \mathbf{x}^{k+1} - \mathbf{z}^{k+1}_l)

    至此,ADMM算法就推导完成了。不同的函数形式,相同的推导流程。

    如有错误,敬请指教。

    展开全文
  • 交替方向乘子(ADMM)的数学基础

    千次阅读 2019-12-31 19:23:18
    交替方向乘子(ADMM) 网上的一些资料根本就没有把ADMM的来龙去脉说清楚,发现只是一个地方简单写了一下流程,别的地方就各种抄,共轭函数,对偶梯度上升什么的,都没讲清楚,给跪了。下面我来讲讲在机器学习中用...

    交替方向乘子法(ADMM)

    网上的一些资料根本就没有把ADMM的来龙去脉说清楚,发现只是一个地方简单写了一下流程,别的地方就各种抄,共轭函数,对偶梯度上升什么的,都没讲清楚,给跪了。下面我来讲讲在机器学习中用得很多的ADMM方法到底是何方神圣。

    共轭函数

    给定函数 f : R n → R f: \mathbb{R}^{n} \rightarrow \mathbb{R} f:RnR,那么函数
    f ∗ ( y ) = max ⁡ x ( y T x − f ( x ) ) f^{*}(y)=\max _{x}( y^{T} x-f(x)) f(y)=xmax(yTxf(x))
    就叫做它的共轭函数。其实一个更直观的理解是:对一个固定的 y y y,将 y T x y^Tx yTx看成是一条斜率为 y y y的直线,它和 f ( x ) f(x) f(x)关于 x x x的距离的最大值,就是 f ∗ ( y ) f^*(y) f(y)百度百科有关于这个直观说法的一个解释,看看就明白了。

    关于共轭函数有几点重要的说明:

    • 不管 f f f凸不凸,它的共轭函数总是一个凸函数。

    • 如果 f f f是闭凸的(闭指定义域是闭的),那么 f ∗ ∗ = f f^{**}=f f=f

    • 如果 f f f是严格凸的,那么
      ∇ f ∗ ( y ) = argmin ⁡ z ( f ( z ) − y T z ) \nabla f^{*}(y)=\underset{z}{\operatorname{argmin}} (f(z)-y^{T} z) f(y)=zargmin(f(z)yTz)

    • 共轭总是频频出现在对偶规划中,因为极小问题总是容易凑出一个共轭: − f ∗ ( y ) = min ⁡ x ( f ( x ) − y T x ) -f^{*}(y)=\min _{x} (f(x)-y^{T} x) f(y)=minx(f(x)yTx)

    关于 f ∗ f^* f的凸性,这篇博客给了一个比较直观的图示说明,下面我从数学上,不太严格地做个简单证明。以一维的情况说明。

    假设 f f f是一个凸函数,下面都不妨考虑函数的最值都不再边界处取到。 max ⁡ x ( y x − f ( x ) ) \max _{x} (yx-f(x)) maxx(yxf(x))的极值点在 f x ′ ( x ) = y f'_x(x)=y fx(x)=y处取到,定义 g : = ( f x ′ ) − 1 g:=(f'_x)^{-1} g:=(fx)1,那么 x = g ( y ) x=g(y) x=g(y)可能会是一堆点。则有
    f ∗ ( y ) = max ⁡ x ( y x − f ( x ) ) = y g ( x ) − f ( g ( y ) ) f^*(y)=\max _{x}(yx-f(x))=yg(x)-f(g(y)) f(y)=xmax(yxf(x))=yg(x)f(g(y)) 进而
    ( f ∗ ( y ) ) y ′ = g ( y ) + y g y ′ ( y ) − f x ′ ( g ( y ) ) g y ′ ( y ) = g ( y ) (f^*(y))'_y = g(y)+yg'_y(y)-f'_x(g(y))g'_y(y) = g(y) (f(y))y=g(y)+ygy(y)fx(g(y))gy(y)=g(y) 那么
    ( f ∗ ( y ) ) y ′ ′ y = g y ′ ( y ) = ( ( f x ′ ) − 1 ) y ′ ≥ 0 (f^*(y))''_yy=g'_y(y)=((f'_x)^{-1})'_y \geq 0 (f(y))yy=gy(y)=((fx)1)y0 故而, f ∗ f^* f是凸的。

    关于 f ∗ ∗ = f f^{**}=f f=f,也是容易证明的。我们假设 f f f是闭凸的。 max ⁡ y ( z y − f ∗ ( y ) ) \max _y(zy-f^*(y)) maxy(zyf(y))的值在 g ( y ) = z g(y)=z g(y)=z处取到,那么
    f ∗ ∗ ( z ) = max ⁡ y ( z y − f ∗ ( y ) ) = f ( g ( g − 1 ( z ) ) ) = f ( z ) f^{**}(z) = \max_y(zy-f^{*}(y))=f(g(g^{-1}(z)))=f(z) f(z)=ymax(zyf(y))=f(g(g1(z)))=f(z)
    z z z换成 x x x就是 f ( x ) f(x) f(x)

    第三条非常重要,它说明了共轭函数的梯度,其实就是共轭函数取到极大值对应的 x x x值,它从 ( f ∗ ( y ) ) y ′ = g ( y ) (f*(y))'_y = g(y) (f(y))y=g(y)就可以看出来。

    对偶梯度上升法

    有了上知识的铺垫,我们就可以说清楚对偶上升方法了。以考虑等式约束问题为例(一般约束问题也是类似的流程),假设 f ( x ) f(x) f(x)是严格凸的,我们考虑问题:
    min ⁡ x f ( x )  subject to  A x = b \min _{x} f(x) \text { subject to } A x=b xminf(x) subject to Ax=b 它的拉格朗日对偶问题是:
    max ⁡ u min ⁡ x ( f ( x ) + u T ( A x − b ) ) \max _{u}\min _{x} (f(x)+u^T(Ax-b)) umaxxmin(f(x)+uT(Axb))
    有理论表明,若原问题和对偶问题满足强对偶条件,即对偶函数关于 u u u的最大值等价于原优化问题关于 x x x的最小。那么原问题和对偶问题对于 x x x是同解的。也就是说只要找到使得对偶问题对应最大的 u u u,其对应的 x x x就是原优化问题的解,那么我们就解决了原始优化问题。

    所以,下面我们来求解这个对偶问题。先把和 x x x无关的变量提出 min ⁡ x \min _x minx,再想办法凑出 f ∗ f^* f,因为我们要用到对偶的性质。
    KaTeX parse error: No such environment: split at position 7: \begin{̲s̲p̲l̲i̲t̲}̲ \max _u \min…

    那么对偶问题就成了 max ⁡ u − f ∗ ( − A T u ) − b T u \max _{u}-f^{*}\left(-A^{T} u\right)-b^{T} u umaxf(ATu)bTu
    这里 f ∗ f^* f f f f的共轭,这里 max ⁡ u \max _u maxu后面不加括号,表示它管着下面的所有,下同,不再重述。定义 g ( u ) = − f ∗ ( − A T u ) − b T u g(u)=-f^{*}\left(-A^{T} u\right)-b^{T} u g(u)=f(ATu)bTu,我们希望能极大化 g ( u ) g(u) g(u),一个简单的想法是沿着 g ( u ) g(u) g(u)梯度上升的方向去走。注意到,
    ∂ g ( u ) = A ∂ f ∗ ( − A T u ) − b \partial g(u)=A \partial f^{*}\left(-A^{T} u\right)-b g(u)=Af(ATu)b
    因此,利用共轭的性质,
    ∂ g ( u ) = A x − b  where  x ∈ argmin ⁡ z f ( z ) + u T A z \partial g(u)=A x-b \text { where } x \in \underset{z}{\operatorname{argmin}} f(z)+u^{T} A z g(u)=Axb where xzargminf(z)+uTAz
    因为 f f f是严格凸的, f ∗ f^* f是可微的,那么,就有了所谓的对偶梯度上升方法。从一个对偶初值 u ( 0 ) u^{(0)} u(0)开始,重复以下过程:
    x ( k ) = argmin ⁡ x f ( x ) + ( u ( k − 1 ) ) T A x u ( k ) = u ( k − 1 ) + t k ( A x ( k ) − b ) \begin{aligned} &x^{(k)}=\underset{x}{\operatorname{argmin}} f(x)+\left(u^{(k-1)}\right)^{T} A x\\ &u^{(k)}=u^{(k-1)}+t_{k}\left(A x^{(k)}-b\right) \end{aligned} x(k)=xargminf(x)+(u(k1))TAxu(k)=u(k1)+tk(Ax(k)b)
    这里的步长 t k t_k tk使用标准的方式选取的。近端梯度和加速可以应用到这个过程中进行优化。

    交替方向乘子法

    交替方向乘子法(ADMM)是一种求解具有可分离的凸优化问题的重要方法,由于处理速度快,收敛性能好,ADMM算法在统计学习、机器学习等领域有着广泛应用。ADMM算法一般用于解决如下的凸优化问题:
    min ⁡ x , y f ( x ) + g ( y )  subject to  A x + B y = c \min _{x, y} f(x)+g(y) \text { subject to } A x+B y=c x,yminf(x)+g(y) subject to Ax+By=c
    其中的 f f f g g g都是凸函数。

    它的增广拉格朗日函数如下:
    L p ( x , y , λ ) = f ( x ) + g ( y ) + λ T ( A x + B y − c ) + ( ρ / 2 ) ∥ A x + B y − c ∥ 2 2 , ρ > 0 L_{p}(x, y, \lambda)=f(x)+g(y)+\lambda^{T}(A x+B y-c)+(\rho / 2)\|A x+B y-c\|_{2}^{2}, \rho>0 Lp(x,y,λ)=f(x)+g(y)+λT(Ax+Byc)+(ρ/2)Ax+Byc22,ρ>0

    ADMM算法求解思想和推导同梯度上升法,最后重复迭代以下过程:
    x k + 1 : = arg ⁡ min ⁡ x L p ( x , y , λ ) x k + 1 : = arg ⁡ min ⁡ y L p ( x , y , λ ) λ k + 1 : = λ k + ρ ( A x k + 1 + B y k + 1 − c ) \begin{aligned} x^{k+1} &:=\arg \min _x L_{p}(x, y, \lambda) \\ x^{k+1} &:=\arg \min _y L_{p}(x, y, \lambda) \\ \lambda^{k+1} &:=\lambda^{k}+\rho\left(A x^{k+1}+B y^{k+1}-c\right) \end{aligned} xk+1xk+1λk+1:=argxminLp(x,y,λ):=argyminLp(x,y,λ):=λk+ρ(Axk+1+Byk+1c) 上述迭代可以进行简化。

    • 第一步简化,通过公式 ∥ a + b ∥ 2 2 = ∥ a ∥ 2 2 + ∥ b ∥ 2 2 + 2 a T b \|a+b\|_{2}^{2}=\|a\|_{2}^{2}+\|b\|_{2}^{2}+2 a^{T} b a+b22=a22+b22+2aTb,替换掉拉格朗日函数中的线性项 λ T ( A x + B y − c ) \lambda^{T}(A x+B y-c) λT(Ax+Byc)和二次项 ρ / 2 ∥ A x + B y − c ∥ 2 2 \rho/2\|A x+B y-c\|_{2}^{2} ρ/2Ax+Byc22,可以得到
      λ T ( A x + B y − c ) + ρ / 2 ∥ A x + B y − c ∥ 2 2 = ρ / 2 ∥ A x + B y − c + λ / ρ ∥ 2 2 − ρ / 2 ∥ λ / ρ ∥ 2 2 \lambda^{T}(A x+B y-c)+\rho/2\|A x+B y-c\|_{2}^{2}=\rho / 2\|A x+B y-c+\lambda/\rho\|_{2}^{2}-\rho / 2\|\lambda / \rho\|_{2}^{2} λT(Ax+Byc)+ρ/2Ax+Byc22=ρ/2Ax+Byc+λ/ρ22ρ/2λ/ρ22
      那么ADMM的过程可以化简如下: x k + 1 : = arg ⁡ min ⁡ x ( f ( x ) + ρ / 2 ∥ A x + B y k − c + λ k / ρ ∥ 2 2 y k + 1 : = arg ⁡ min ⁡ y ( g ( y ) + ρ / 2 ∥ A x k + 1 + B y − c + λ k / ρ ∥ 2 2 λ k + 1 : = λ k + ρ ( A x k + 1 + B y k + 1 − c ) \begin{aligned} x^{k+1} &:={\arg \min _x}\left(f(x)+\rho / 2\left\|A x+B y^{k}-c+\lambda^{k} / \rho\right\|_{2}^{2}\right.\\ y^{k+1} &:={\arg \min _y}\left(g(y)+\rho / 2\left\|A x^{k+1}+B y-c+\lambda^{k} / \rho\right\|_{2}^{2}\right.\\ \lambda^{k+1} &:=\lambda^{k}+\rho\left(A x^{k+1}+B y^{k+1}-c\right) \end{aligned} xk+1yk+1λk+1:=argxmin(f(x)+ρ/2Ax+Bykc+λk/ρ22:=argymin(g(y)+ρ/2Axk+1+Byc+λk/ρ22:=λk+ρ(Axk+1+Byk+1c)

    • 第二步化简,零缩放对偶变量 u = λ / ρ u = \lambda/\rho u=λ/ρ,于是ADMM过程可化简为:
      x k + 1 : = arg ⁡ min ⁡ ( f ( x ) + ρ / 2 ∥ A x + B y k − c + u k ∥ 2 2 y k + 1 : = arg ⁡ min ⁡ ( g ( y ) + ρ / 2 ∥ A x k + 1 + B y − c + u k ∥ 2 2 u k + 1 : = u k + ( A x k + 1 + B y k + 1 − c ) \begin{aligned} x^{k+1} &:={\arg \min}\left(f(x)+\rho / 2\left\|A x+B y^{k}-c+u^{k}\right\|_{2}^{2}\right.\\ y^{k+1} &:={\arg \min}\left(g(y)+\rho / 2\left\|A x^{k+1}+B y-c+u^{k}\right\|_{2}^{2}\right.\\ u^{k+1} &:=u^{k}+\left(A x^{k+1}+B y^{k+1}-c\right) \end{aligned} xk+1yk+1uk+1:=argmin(f(x)+ρ/2Ax+Bykc+uk22:=argmin(g(y)+ρ/2Axk+1+Byc+uk22:=uk+(Axk+1+Byk+1c)

    ADMM相当于把一个大的问题分成了两个子问题,缩小了问题的规模,分而治之。

    展开全文
  • 为了降低FMT重建的病态性和提升大规模数据集下的重建效率,结合对偶坐标下降(DCA)和交替方向乘子(ADMM)提出了一种改进的随机变量的交替方向乘子重建优化方法。在原始ADMM方法的基础上,增加了一个随机更新规则...
  • 使用 交替方向乘子(ADMM) 解 线性规划问题 (LP)

    原问题

    min ⁡ x    c T x s . t .    A x = b x ≥ 0 (1) \min_x \;c^Tx\\s.t. \;Ax=b\\x\geq 0 \tag{1} xmincTxs.t.Ax=bx0(1)

    对偶问题

    max ⁡ y    b T y s . t .    A T y + s = c s ≥ 0 (2) \max_y\;b^Ty\\s.t.\;A^Ty+s=c\\s\geq 0\tag{2} ymaxbTys.t.ATy+s=cs0(2)
    A ∈ R m × n , x ∈ R n , s ∈ R n , y ∈ R m A \in \R^{m\times n}, x \in \R^{n}, s \in \R^{n}, y \in \R^{m} ARm×n,xRn,sRn,yRm


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

    首先,写出对偶问题的增广拉格朗日函数 L t ( x , y , s ) = − b T y + x T ( A T y + s − c ) + t 2 ∣ ∣ A T y + s − c ∣ ∣ 2 2 s . t . s ≥ 0 L_t(x,y,s) = -b^Ty+x^T(A^Ty+s-c) + \frac{t}{2}||A^Ty+s-c||_2^2 \\ s.t. \quad s \geq 0 Lt(x,y,s)=bTy+xT(ATy+sc)+2tATy+sc22s.t.s0
    基于ADMM的迭代规则: y k + 1 = a r g min ⁡ y L t ( y ; x k , s k ) s k + 1 = a r g min ⁡ s L t ( s ; x k , y k + 1 ) , s ≥ 0 x k + 1 = x k + t ∗ ( A T y k + 1 + s k + 1 − c ) y^{k+1} = arg \min_y L_t(y;x^k,s^k) \\ s^{k+1} = arg \min_s L_t(s;x^k,y^{k+1}), \quad s\geq 0 \\ x^{k+1} = x^{k} +t*(A^Ty^{k+1}+s^{k+1}-c) yk+1=argyminLt(y;xk,sk)sk+1=argsminLt(s;xk,yk+1),s0xk+1=xk+t(ATyk+1+sk+1c)直到结果收敛。针对该问题,其增广拉格朗日函数非常简单,可以写出迭代步的显式形式: y k + 1 = a r g min ⁡ y L t ( y ; x k , s k ) = − ( A A T ) − 1 ( ( A x k − b ) / t + A ( s k − c ) ) y^{k+1} = arg \min_y L_t(y;x^k,s^k) \\ =-(AA^T)^{-1}\bigg((Ax^k-b)/t+A(s^k-c)\bigg) yk+1=argyminLt(y;xk,sk)=(AAT)1((Axkb)/t+A(skc))
    s k + 1 = a r g min ⁡ s L t ( s ; x k , y k + 1 ) , s ≥ 0 = m a x ( c − A T y k + 1 − x k t , 0 ) s^{k+1} = arg \min_s L_t(s;x^k,y^{k+1}), \quad s\geq 0 \\ = max(c-A^Ty^{k+1}-\frac{x^k}{t},0) sk+1=argsminLt(s;xk,yk+1),s0=max(cATyk+1txk,0)
    x k + 1 = x k + t ∗ ( A T y k + 1 + s k + 1 − c ) x^{k+1} = x^{k} +t*(A^Ty^{k+1}+s^{k+1}-c) xk+1=xk+t(ATyk+1+sk+1c)

    代码如下:

    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 = 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', t1, errfun(x1, xs));
    
    

    在这里插入图片描述

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

    又快又准!!!

    在这里插入图片描述

    展开全文
  • 坐标下降属于一种非梯度优化的方法,它在每步迭代中沿一个坐标的方向进行线性搜索(线性搜索是不需要求导数的),通过循环使用不同的坐标方法来达到目标函数的局部极小值。 假设目标函数是求解的极小值,其中是一...

    坐标下降法属于一种非梯度优化的方法,它在每步迭代中沿一个坐标的方向进行线性搜索(线性搜索是不需要求导数的),通过循环使用不同的坐标方法来达到目标函数的局部极小值

    假设目标函数是求解f(x)的极小值,其中x=(x_1,x_2,\ldots,x_n)是一个n维的向量,我们从初始点x^0开始(x^0是我们猜想的一个初值)对k进行循环:

    相当于每次迭代都只是更新x的一个维度,即把该维度当做变量,剩下的n-1个维度当作常量,通过最小化f(x)来找到该维度对应的新的值。坐标下降法就是通过迭代地构造序列x^0,x^1,x^2,\ldots来求解问题,即最终点收敛到期望的局部极小值点。通过上述操作,显然有:

    流程总结:

    1.  首先,我们把x向量随机取一个初值。记为x^0,上面的括号里面的数字代表我们迭代的轮数,当前初始轮数为0。
    2.  对于第k轮的迭代。我们从x^k_1开始,到x^k_n为止,依次求x_i^{k}x_i^{k}的计算表达式如上文所描述。
    3. 检查x^k向量和x^{k-1}向量在各个维度上的变化情况,如果在所有维度上变化都足够小,那么x^k即为最终结果,否则转入第二步,继续第k+1轮的迭代。

    坐标轴下降法的求极值过程,可以和梯度下降做一个比较:

    1. 坐标轴下降法在每次迭代中在当前点处沿一个坐标方向进行一维搜索 ,固定其他的坐标方向,找到一个函数的局部极小值。而梯度下降总是沿着梯度的负方向求函数的局部最小值。
    2. 坐标轴下降优化方法是一种非梯度优化算法。在整个过程中依次循环使用不同的坐标方向进行迭代,一个周期的一维搜索迭代过程相当于一个梯度下降的迭代。
    3. 梯度下降是利用目标函数的导数来确定搜索方向的,该梯度方向可能不与任何坐标轴平行。而坐标轴下降法法是利用当前坐标方向进行搜索,不需要求目标函数的导数,只按照某一坐标方向进行搜索最小值。
    4. 两者都是迭代方法,且每一轮迭代,都需要O(mn)的计算量(m为样本数,n为系数向量的维度)

    参考文章:

    Lasso回归算法: 坐标轴下降法与最小角回归法小结

    机器学习笔记——简述坐标下降法

    坐标下降法(Coordinate descent)

    【机器学习】坐标下降法(Coordinate descent)

     

    ADMM(交替方向乘子法)

    作者:大大大的v
    链接:https://www.zhihu.com/question/36566112/answer/118715721
    来源:知乎
    著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
     

    1) 优化问题是什么:

    最常见的优化问题长这样(公式1):

    min_x\quad f(x)\\

    其中 x 是优化变量,也就是可以改变的数值,通过调节 x 的大小,使得目标函数 f(x) 的数值达到最小。

    像(1)式那样,只有函数,对于变量 x 没有要求的话,其实是最简单的一类优化问题:无约束优化问题(我们只考虑凸问题的情况下,如果你不知道什么是凸问题的话,没关系,那不重要,只要记住越凸越好=凸=)。

    实际上我们对于优化变量 x 可能会有很多要求:

    x 要满足什么集合啦, 什么等式约束,不等式约束啦巴拉巴拉,这就好比我们希望通过学习升级打怪成为高知女性就可以吊金龟婿一样,这里优化变量 x 暗指学历,函数 f(x) 对应的是一个评分,也就是优质金龟婿不愿意跟你处对象的评分(因为是要最小化),金龟婿肤白貌美大长腿,那我小学学历肯定是不够的,初中文凭貌似也不太够?所以我学啊学,学啊学,以为学历越高越好,结果好不容易读了博,回头一看,好嘞原来男神对另一半学历是有要求的(也就是优化里所说的约束):高中< x <=硕士。博士不做女人啦,这大概就是基于学历的一个优化问题→_→

    等式约束: subject. to  \quad Ax=b

    不等式约束: subject. to \quad Ax\leqslant b

    所以一个等式约束的优化问题长这样(公式2):

    min_x\quad f(x)\\sub.to \quad Ax=b

     

    2)ADMM解决什么优化问题:

    min_{x,z}\quad f(x)+g(z)\\sub.to\quad Ax+Bz=c

    也就意味着ADMM通常解决的是等式约束的优化问题,而且这个优化问题还有两个优化变量 xz

    回到刚刚找男朋友的问题上来,如果之前我们只考量学历因素 x 的话,现在我们还要考量颜值因素 z!而且这两个变量之间还是有等式关系的!(至于这个关系。。。大概就是那个什么学历越高,颜值就越。。。=凸=,荒谬,荒谬至极!)

    事实上分布式中的一致性优化问题(consensus),分享问题(sharing problem)等等都很好写成这样的形式,因为每个节点的变量还要跟周围节点变量产生关联,但真正用ADMM的原因可能还是因为ADMM又快又好用吧。。。

     

    3)解决优化问题的方法:

    方法中与ADMM最为相关的大概就是原对偶方法中的增广拉格朗日法(ALM)。

    对偶方法:把公式2中的minimize问题与约束条件sub to通过一个对偶变量 \lambda 耦合在一起,形成一个叫做Lagrange函数的东西:

    L(x,\lambda) = f(x)+\lambda^T(Ax-b)\\

    原来带约束求解 min_x f(x) ,现在求解对偶问题 \max_{\lambda}\min_{x}L(x,\lambda) ,两个问题的最优解等价(原问题凸的情况下。为什么?公式好多,我再想想(查查)有没有什么直观的解释),而且现在没了约束,岂不美哉(❁´◡`❁)*✲゚*

    方法是对偶上升法:

    step1:\ \ \ \ \ \ x^{k+1}=\arg\min_x \ L(x,\lambda^k)\\ step2: \ \ \ \lambda^{k+1} = \lambda^k+\rho(Ax^{k+1}-b)

    对偶上升法其实很好理解,它把 \max_{\lambda}\min_{x}L(x,\lambda) ,也就是 \max_{\lambda}(\min_{x}L(x,\lambda)) 拆成了两步:

    第一步是固定对偶变量 \lambda ,求解\min_xL(x,\lambda)

    第二步固定住变量 x ,像众所周知的梯度下降法那样操作,只不过这里是arg max 问题所以变成了上升法。

     

    后来有人嫌弃这个Lagrange函数还不够凸,又对约束增加一个惩罚项,变成增广拉格朗日函数

    L(x,\lambda) = f(x)+\lambda^T(Ax-b)+\frac{\rho}{2}\|Ax-b\|^2\\

    这样就迈向更凸,算法也更强啦~

     

    4)ADMM的流程:

    ADMM的想法跟上面的思路就很一致啦,作为一个primal-dual原对偶方法,首先,它要有个对偶函数,也就是增广拉格朗日函数:

    L(x,z,\lambda)=f(x)+g(z)+\lambda^T(Ax+Bz-c)+\frac{\rho}{2}\|Ax+Bz-c\|^2

    然后,它像对偶上升法一样分别固定另外两个变量,更新其中一个变量:(也就是其名:交替方向)

    step1:\ \ \ \ \ \ \  \  x^{k+1}=\arg\min_x \ L(x,z^{k},\lambda^k)\\  step2:\ \ \ \ \  z^{k+1}=\arg\min_z \ L(x^{k+1},z,\lambda^k)\\  step3: \lambda^{k+1} = \lambda^k+\rho(Ax^{k+1}+Bz^{k+1}-c)

    重复直到不怎么变化了,也就是收敛了。。。

    至于怎么求解 \arg\min L ,因为无约束,梯度下降法啊,牛顿法啊等等都可以~其实就是大循环里嵌套的小循环,step1~3是大循环,求解里面的 \arg\min L 是小循环。

     

    5)其他一些杂七杂八的话:

    ADMM相当于把一个大的问题分成了两个子问题,缩小了问题的规模,分而治之(?)

    实际上有些算法用ADMM的思路,你看从ALM到ADMM相当于增加一个变量z,增加一个step就大大提升了算法性能,如果我再增加一个变量一个step呢~?但有工作指出理论上只有两个block的ADMM能够保证收敛(忘记在哪里看到的,不对的话,我就把这句话删掉!)

    转载自https://www.zhihu.com/question/36566112/answer/118715721

     

    展开全文
  • 凸优化交替方向乘子

    千次阅读 2016-05-24 15:51:48
    原文在这里:... 最近开始对凸优化(convex optimization)中的ADMM(Alternating Direction Method of Multipliers)交替方向乘子算法开始感兴趣,接下来我会写一系列关于ADMM(Alternating Direction
  • 最近研究二次判别分析(Quadratic Discriminant Analysis,QDA),发现运用到了交替方向乘数(ADMM),就很迷。(关键是太菜) 很多博主都是直接翻译或者搬运的,搜罗且了解了很多相关知识,那就来个大总结及其...
  • ADMM算法(交替方向乘子

    千次阅读 多人点赞 2020-02-05 13:57:58
    有了前面标准Lagrangian乘子与对偶上升和增广Lagrangian的基础,理解ADMM就容易了很多。本文主要来自张贤达《矩阵分析与优化(第二版)》4.7.4节。 ADMM算法 ADMM认为,在统计学与机器学习中,经常会遇到大...
  • 二维ADI(交替方向隐式求解)

    千次阅读 2018-09-22 09:40:07
    用ADI求解二维抛物线问题 2.物理模型: 3.数学描述: 4.算法描述: 对于时间层n,增加虚拟时间层n+1\2; 对uxx在时间层n+1\2上进行前向差分,对uyy在时间层上n上进行后向差分; 对uxx在时间层n+1\2上进行向...
  • 我们前面说过,拉格朗日在实际中应用不大。为什么呢?因为α\alphaα的取值很难取,这就导致拉格朗日鲁棒性很低,收敛很慢,解很不稳定。于是就有了今天的增广拉格朗日和ADMM。 学习笔记 一、增广拉格朗日...
  • Introduction 上一节我们介绍了对偶梯度上升...那就是本节要介绍的交替方向乘子(Alternating Direction Method of Multipliers,ADMM)。 交替方向乘子 考虑如下形式的问题 min⁡x,zf(x)+g(z)subject toAx+
  • 基于HanD提出的交替方向法,通过一系列的改进,对YeC提出的结构型单调变分不等式问题给出了一种新的投影类交替方向法新方法具有如下特点:每次迭代只需计算一次正交投影和几个函数值,这比YeC的方法简单;方法产生的迭代...
  • 在该方法中,表征器件全矢量特性的偏振耦合项被引入光束传播方程,并使用新型的交替方向隐式进行高效处理。数值模拟的结果表明,相比于传统的迭代方法,该方法在保持较高精度的同时,计算效率有了显著的提高。
  • ADMM随堂笔记(二):方向交替乘子

    千次阅读 2019-09-03 23:20:06
    罚参数搞来搞去是改进经典算法的火热方向。比如:下面这个: 就是从固定罚参数进化为迭代变化的罚参数,中间的变化规则是(3.13)。仅从这个式子上好像有点道理,原始残差和 对偶残差,这两个相爱相杀, ρ \...
  • 我和乘子交替方向法admmProblem statement: 问题陈述: Given a sequence of numbers, you have to find the maximum sum alternating subsequence and print the value. A sequence is an alternating sequence ...
  • ADMM:交替方向乘子算法

    千次阅读 2017-08-22 09:44:13
    ADMM(Alternating Direction Method of Multipliers)  ...如下文所述,ADMM是一个旨在将对偶上升的可分解性和乘子的上界收敛属性融合在一起的算法。  2.1 具体描述  设有如下优化问题:  min f
  • 浅谈VMD(变分模态分解)

    万次阅读 多人点赞 2019-12-02 11:41:40
    而对求最优解采用二次惩罚和拉格朗日乘数将上诉约束问题转换为非约束问题,并用交替方向乘子求解这个非约束问题, 通过迭代更新最终得到信号分解的所有模态。分解的所有模态中有包含主要信号的模态和包含噪声的...
  • 在我看来,牛顿至少有两个应用方向,1、求方程的根,2、最优化。牛顿涉及到方程求导,下面的讨论均是在连续可微的前提下讨论。   1、求解方程。 并不是所有的方程都有求根公式,或者求根公式很复杂,导致...
  • [本文链接:http://www.cnblogs.com/breezedeus/p/3496819.html,转载请注明出处]最近开始对凸优化(convex optimization)开始感...本文主要对ADMM(Alternating Direction Method of Multipliers)交替方向乘子算法做一
  • 凸优化:ADMM(Alternating Direction Method of Multipliers)交替方向乘子算法系列之三:ADMM 本文地址:http://blog.csdn.net/shanglianlm/article/details/46808793
  • 软件构造Lab1实验总结

    2019-06-19 22:49:54
    2.开始绘制多边形,首先将turtle的方向顺时针转过270度,使其指向正左方,然后通过之前实现过的函数由边数求出内角,然后求出外角,最后通过一个for循环让turtle每次前进多边形边长的距离,顺时针转过外角大小的角度...
  • 极大似然 梯度下降 所以logistic回归算法实现为logistic回归是分类问题。前面我们讲的分类问题的输出都是 “yes”或者“no”。但是在现实生活中,我们并不是总是希望结果那么肯定,而是概率(发生的可能性)。...
  • 迭代求解最优化问题——步长确定

    万次阅读 2017-12-25 02:06:36
    线搜索 前面提到迭代求解最优化问题的一般形式是xk+1=xk+Δx_{k+1}=x_k+...梯度下降和牛顿其实在某种程度上只是确定了下降的方向。而下降的步长还需要我们自己确定。而对于不同的问题下降的步长往往也是不一样的。
  • 提出的低秩交替乘子表明,相比原始的磁共振指纹重建、仅用低秩逼近以及仅用交替乘子而没有低秩逼近,此方法有更小的根均方误差。合并领灵敏度编码可以进一步减少伪影。 结论 相比提到的其它磁共振指纹...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 3,416
精华内容 1,366
热门标签
关键字:

交替方向迭代法