400-123-4567

恒耀新闻 分类
21 有约束优化算法：增广拉格朗日法和ADMM发布日期：2024-03-12 浏览次数：

我们还是假设问题是凸的(非凸难啊)、目标函数可微(不可微可以用次梯度和无梯度)，且限定一下优化问题只有一个等式约束(不等式可以用内点法，但是额我还没看(?))。即，我们的标准问题(P)为：

\\min ~f(x)\\\\s.t.~Ax=b

看看改进的拉格朗日法-增广拉格朗日法是如何推导出来的。

1.增广拉格朗日法Augmented Lagrangian Method：

\\begin{align}x^{k+1}=&\\arg\\min\\limits_xL_c(x,v^k)\\\\v^{k+1}=&v^k+c(Ax^{k+1}-b)\\end{align}

【忘了提醒一下，步长\\alpha^k都是要自己找的，比如精确线搜索orArmijo线搜索等等】

推导思路：

? 先要介绍一下增广拉格朗日函数是什么。它是由拉格朗日函数加上一个罚项得到的，记为：

? L_c(x,v)=f(x)+v^T(Ax-b)+\\frac{c}{2}\\Vert Ax-b\\Vert_2^2

? 它实际上是下面这个优化问题(P1)的拉格朗日函数：

? \\min~f(x)+\\frac{c}{2}\\Vert Ax-b\\Vert_2^2\\\\s.t.~Ax=b

? 也就是把原问题的等式约束罚到目标函数里面去，得到的优化问题的拉格朗日函数，被称为原问题拉格朗日函数的增广拉格朗日函数。

? 【接下来很容易可以验证，上面(P1)这个问题和开头的标准问题(P)的最优解相同，两个问题是等价的。】

  • 对(P)，其拉格朗日函数为：L(x,v)=f(x)+v^T(Ax-b)，假设拉格朗日函数的最优解为(x^*,v^*)，则L(x^*,v^*)=0，即：
    ? \ abla_x\\{f(x^*)+v^{*T}(Ax^*-b)\\}=0
    【先不求出来】
  • 对(P1)，其拉格朗日函数为：L_c(x,v)=f(x)+v^T(Ax-b)+\\frac{c}{2}\\Vert Ax-b\\Vert_2^2，假设拉格朗日函数的最优解为(x_1^*,v_1^*)，则L_c(x_1^*,v_1^*)=0，即：
    ? \ abla_x\\{f(x_1^*)+v_1^{*T}(Ax_1^*-b)\\}+cA^T(Ax_1^*-b)=0
    又因为Ax_1^*-b=0，所以实际上上式为
    \ abla_x\\{f(x_1^*)+v_1^{*T}(Ax_1^*-b)\\}=0
    这和(P)的结论是一样的。所以说(x^*,v^*)=(x_1^*,v_1^*)，即(P)\\Leftrightarrow(P1)。

既然两个问题是等价的，也就是它们各自的拉格朗日函数的最优值是等价的。那么，自然可以想到用\ abla L_c(x,v)去替换掉\ abla L(x,v)。

? 回顾拉格朗日法：

? \\begin{cases}x^{k+1}=x^k-\\alpha^k\ abla_xL(x^k,v^k)=x^k-\\alpha^k(\ abla f(x^k)+A^Tv^k)\\\\v^{k+1}=v^k+\\alpha^k\ abla_vL(x^k,v^k)=v^k+\\alpha^k(Ax^k-b)\\end{cases}

? 替换成增广拉格朗日函数的梯度后，变为：

? \\begin{cases}x^{k+1}=x^k-\\alpha^k\ abla_xL_c(x^k,v^k)=x^k-\\alpha^k(\ abla f(x^k)+A^Tv^k+cA^T(Ax^k-b))\\\\v^{k+1}=v^k+\\alpha^k\ abla_vL_c(x^k,v^k)=v^k+\\alpha^k(Ax^k-b)\\end{cases}

? 但是上面这组迭代式子，有个东西没有利用起来，就是第一个式子更新好的x^{k+1}。在第二个式子计算v^{k+1}时用的还是x^k的信息，这是把它替换成新的x^{k+1}，那么整个算法变为：

? \\begin{cases}x^{k+1}=x^k-\\alpha^k(\ abla f(x^k)+A^Tv^k+cA^T(Ax^k-b))\\\\v^{k+1}=v^k+\\alpha^k(Ax^{k+1}-b)\\end{cases}

? 如果增广拉格朗日函数L_c(x,v)性质比较理想或者比较容易被优化的话，不一定非要用梯度法，比如二阶可微也可以用牛顿法，等等。所以统一改成用\\arg\\min的形式来表达上面这个算法为：

? \\begin{cases}x^{k+1}=\\arg\\min\\limits_xL_c(x,v^k)\\\\v^{k+1}=v^k+\\alpha^k(Ax^{k+1}-b)\\end{cases}

? 那么问题又来了(还想呢，这tm也太折腾人了)，增广拉格朗日函数里面的罚参数 c 还没利用到呢。为了让罚参数起作用，我们还可以把第二个式子的步长替换为罚参数，得到最终的增广拉格朗日法：

? \\begin{cases}x^{k+1}=\\arg\\min\\limits_xL_c(x,v^k)\\\\v^{k+1}=v^k+c(Ax^{k+1}-b)\\end{cases}

【坦白：c 对于算法的收敛性是有帮助的，并不是上面我掰扯的单纯加上去利用起来，但是事实上因为我没看懂收敛性分析，所以只能暂时这样强词夺理了 。】

? 注：这里c 要自己选定，但是选定c 肯定比去线搜索\\alpha 简单多了。特别的，如果选择c=1，基本上可以保证增广拉格朗日算法收敛。而且，从收敛性分析可以知道，c也可以是递增序列，不用担心不收敛。

2.算法性质[为什么增广拉格朗日函数行]：

  • **1)：**若\\lim\\limits_{k\ o+\\infty}v_k=v^*，则\\forall c>0，x^*=\\arg\\min\\limits_xL_c(x,v^*)
    【只要v\ o v^*，c 管你怎么选都可以收敛】
  • 2)：若c\ o+\\infty，则\\forall v，x^*=\\arg\\min\\limits_xL_c(x,v)
    【步长c 可以选择递增序列\\{c^k\\}，此时一定收敛】

3.用一个例子验证这两个性质：

  • \\min~\\frac{1}{2}x_1^2+\\frac{1}{2}x_2^2\\\\s.t.~x_1=1
    \\Rightarrow L(x,v)=\\frac{1}{2}x_1^2+\\frac{1}{2}x_2^2+v(x_1-1)
    \\Rightarrow KKT:\\begin{cases}x_1=1\\\\x_1+v=0\\\\x_2=0\\end{cases}
    \\Rightarrow x_1*=1,x_2^*=0.v^*=-1
    \\Rightarrow L_c(x,v)=\\frac{1}{2}x_1^2+\\frac{1}{2}x_2^2+v(x_1-1)+\\frac{c}{2}(x_1-1)^2
    • 如果知道v^*：
      \\begin{align}\\arg\\min\\limits_xL_c(x,v^*)=&\\arg\\min\\limits_xL_c(x,-1)\\\\=&\\arg\\min\\limits_x\\{\\frac{1}{2}x_1^2+\\frac{1}{2}x_2^2-x_1+1+\\frac{c}{2}(x_1-1)^2\\}\\end{align}
      \ abla_xL_c(x,v^*)=\\left[\\begin{array}{c}x_1-1+c(x_1-1)=0\\\\x_2=0\\end{array}\\right]\\Leftrightarrow x_1^*=1,x_2^*=0
      【只要c>0，不论取多少都能求出x^*】
    • 如果v^*不知道：
      0=\ abla_xL_c(x,v)=\\begin{cases}x_1+v+c(x_1-1)=0\\\\x_2=0\\end{cases}
      \\Rightarrow x_1=\\frac{c-v}{c+1},x_2=0
      【若c\ o+\\infty\\Rightarrow x_1\ o1=x^*\\Rightarrow 性质1)】
      【若v\ o v^*=-1\\Rightarrow x_1\ o1=x^*\\Rightarrow 性质2)】


  • 收敛情况讨论：
    因为L_c(x,v)=f(x)+v^T(Ax-b)=\\frac{c}{2}\\Vert Ax-b\\Vert_2^2，所以这个例子的增广拉格朗日算法为：
    \\begin{align}x^{k+1}=&\\arg\\min\\limits_xL_c(x,v^k)=\\left[\\begin{array}{c}\\frac{c-v^k}{c+1}\\\\0\\end{array}\\right]\\\\v^{k+1}=&v^k+c(x_1^{k+1}-1)=v^k-\\frac{c}{c+1}(v^k+1)\\end{align}
    \\Rightarrow\\frac{v^{k+1}-v^*}{v^k-v^*}=\\frac{1}{c+1}<1(c>0)
    是线性收敛的。

4.交替方向乘子法ADMM：Alternating Direction Method of Multiplier

这里只从无约束优化问题引出ADMM法的思路，带约束的优化问题分块儿后可以一样求。对于一种目标函数可以分成两个部分的无约束优化问题，它的目标问题形式为(P)：

\\min\\limits_x~f(x)+g(x)

比如有的时候单独f或g都好优化，但是放到一块儿去就不好优化了。亦或是咱们把约束优化问题的约束想办法丢到目标函数上去，转化成无约束问题了，那就可以假设为上面这个形式，也可以用ADMM法。

先对(P)做等价变换为问题(P1)：

\\min\\limits_{x,z}~f(x)+g(z)\\\\s.t.~x=z

这不是在tkzfp，而是像和之前的增广拉格朗日函数联系起来。(P1)的增广拉格朗日函数为：

L_c(x,z,v)=f(x)+g(z)+v^T(x-z)+\\frac{c}{2}\\Vert x-z\\Vert_2^2

则该问题的增广拉格朗日算法为：

\\begin{align}\\{x^{k+1}&,z^{k+1}\\}=\\arg\\min\\limits_{x,z}\\{f(x)+g(z)+v^T(x-z)+\\frac{c}{2}\\Vert x-z\\Vert_2^2\\}\\\\v^{k+1}&=v^k+c(x^{k+1}-z^{k+1})\\end{align}

注意到，在x^{k+1},z^{k+1}的计算上，右边式子还是可以整理成只和x和只和z有关的函数。这就让人联想起了坐标轮换法里的块坐标下降。我们对第一个式子进行改进，变成先单独对x求解，再单独对z求解，则可以得到所谓的ADMM算法如下：

\\begin{align}x^{k+1}&=\\arg\\min\\limits_x\\{f(x)+\\frac{c}{2}\\Vert x-z^k+\\frac{v^k}{c}\\Vert_2^2\\}\\\\z^{k+1}&=\\arg\\min\\limits_z\\{g(z)+\\frac{c}{2}\\Vert z-x^{k+1}-\\frac{v^k}{c}\\Vert_2^2\\}\\\\v^{k+1}&=v^k+c(x^{k+1}-z^{k+1})\\end{align}

注：前两个式子里的函数形式做了一些整理和等价变换，里面的函数最优值与变化前的函数最优值是相同的，我看的时候一下子没有理解，以为是老师写错了，其实是没问题的，用原函数表达式也没问题。

额外：之前提到ADMM迭代有点块坐标下降的意思，就是先求一个变量的最优，再求另一个。其实也完全可以真的做坐标轮换，先对x做坐标轮换(x是n维的话就要轮换n次 )，再对z做坐标轮换，再得到v^{k+1}。但是，一方面，每一个维度坐标轮换后，都要做一次线搜索，很麻烦。另一方面，把完整算法格式写出来也很长。所以就不贴坐标轮换版的ADMM了。

  • ADMM算法其实是解决如下经典问题的一个算法：
    \\min~f(x)+g(z)\\\\s.t.~Ax+Bz=c
    有了前面的铺垫，可以很自然的写出经典ADMM算法形式如下：
    \\begin{align}x^{k+1}&=\\arg\\min\\limits_xL_c(x,z^k,v^k)\\\\z^{k+1}&=\\arg\\min\\limits_zL_c(x^{k+1},z,v^k)\\\\v^{k+1}&=v^k+c(Ax^{k+1}+Bz^{k+1}-c)\\end{align}
    以上。

平台注册入口