0 赞 0 踩
其他回答
萌新回答一下这个问题，求指导。
我认为这是两个层面的问题。考虑Lasso，
写成标准形式就是
lambda=0 是 penalty method， rho=0 是 Lagrange Multiplier method。
当然也可以同时不为0，那就是ALM/ADMM.
在Lipschitz 假设下，
代入式子，相当于优化
，这个时候我们既可以直接针对每一步更新写出闭式解（在实际应用中不会有人使用这种方法，因为求逆的代价太大。）
也可以使用数值方法求解这个问题（线性化，注意到那个eta了吧）
看了 @周君豹 大佬的答案很有启发，补充两句。罚函数法求解的时候，rho 可以不断增大，最后当rho跑到足够大的时候就类似障碍函数，变成硬约束了。而乘子法的lambda在这里是对偶变量，每一步都需要求解更新。当然如果在ADMM当中我们既会让rho增大，也会维护lambda。
成丰 1小时前 0条评论 0 赞 0 踩
半夜醒来，然后失眠了，答个题
Penalty methods和Multiplier Methods的形式紧密相关，甚至可以互相解释，所以要清晰而精确地论述二者的本质差异并不容易。
先理清一些误解吧。解析与不解析无非就是个符号而已，只要是唯一确定并且可以计算就够了，不要强迫症地认为"x=log(2)"是解析解，"x是x^3-x-100=0的最大根"就不是解析解。我看到评论中的说法，惩罚函数法适用于不等式约束，拉式乘子法适用于等式约束。这样的描述就很尴尬。通常书本上确实喜欢这么举例，但这并不意味着惩罚函数法不可以用于等式约束，拉式乘子法不可以用于不等式约束。因为很显然我们可以把等式约束写成两个不等式约束，而把类似于g(x)<=0的不等式约束写成max(g(x),0)=0这样的等式约束，所以等式约束问题和不等式约束问题在形式上总可以互相等价转换。
正是这样的等价转换使得二者形式高度相关。惩罚函数是一个约束违背的度量(measure of constraint violation),使得当约束满足时取零，约束违背时取非零。作为一种度量，我们通常要求它非负和单调递增。举个例子，只需要考虑最简单的一维约束y<=0,有很多常用的惩罚函数，比如G(y)=0 if y<=0, infinity else，和 G(y)= max(y,0)^p。简单起见，考虑如下只有一个约束的优化问题: min{F(x): g(x)<=0}。应用上述函数可以得到如下等价变换min{F(x): G[g(x)]=0}。对于这个等价问题，我们写出惩罚函数形式L(x,r)=F(x)+rG[g(x)]，然而这正是拉格朗日函数，所以说惩罚函数法与拉式乘子法形式紧密相关。当然如果拉式乘子法用于原问题，得到的是L(x,r)=F(x)+rg(x)，这个时候效果就不一样了，如果我们放松对惩罚函数非负的要求，形式上拉式乘子法就可以解释为linear penalty method。
个人认为，区分惩罚函数法与拉式乘子法不是上述形式，而是二者对于参数r的意义的理解以及由此导致的求解思路不同。在惩罚函数里，r是作为一个固定的参数来对待的，求解L(x,r)时一直保持不变(当然实际中为了提高求解效率，会使用path-following或SUMT，目的还是求解最终那个惩罚常数对应的问题)。对于惩罚函数法，大多数的理论结果类似于，当r趋于无穷时，L(x,r)的解趋于原问题的解。而在拉式乘子法中，r是作为对偶变量出现的，求解过程中是要不断更新的，而且更多的是会考虑Lagrange Duality。Duality Theory是拉式乘子法的最核心的理论支撑。即便是比较path-following惩罚法和乘子法，关于参数r的更新方法也是不同的，惩罚法中r通常是自适应地按照固定倍率不断增大，因而对于所有的问题案例，r序列都是相同且给定的，而在乘子法中r是一步梯度更新，更新过程中r可能增大也可能减小，对于不同的问题案例，更新得到的r序列是不同的。
为了更进一步说明二者之间的联系和差异，我们考虑凸优化问题，假设F(x)和g(x)都是光滑的凸函数，并且存在x0满足Slater condition即g(x0) < 0。考虑摄动问题V(u)=min{F(x): g(x)<=u}，这个问题至关重要。首先，Lagrange Duality可以根据函数V(u)的性质来构建，具体结论是，对于凸优化问题，如果V(u)在u=0处下半连续，那么strong duality 成立。此时，拉式乘子法可以正常使用。其次，有意思的是，对于惩罚函数法有如下exact penalty theory : 当r > sup{ [V(0)-V(u)]/u : u>0 }时，f(x)=F(x)+rG[g(x)]的解一定是V(0)的解，这里G(y)= max(y,0)。第三，比较无约束凸优化问题min f(x)的最优性条件与约束问题min{F(x): g(x)<=0}的KKT条件，可以进一步发现两个方法内在的相通性: 乘子法是寻找变量x和r使得F'(x)+rg'(x)=0，而惩罚法是寻找变量x使得F'(x)+h(x)=0，这里h(x)是非光滑凸函数rG[g(x)]的一个次梯度subgradient。
总结来看，惩罚法是pure primal method, 乘子法是primal-dual method。从发展历史来看，惩罚法是上个世纪60年代的成果和主流方法，很快在70年代就被两者的结合体ALM: Augmented Lagrangian methods 取代了，并进一步演化出了ADMM: Alternating direction method of multipliers。在凸优化问题中，这些演进有时候并不仅仅是既有思路的简单结合，甚至会有更深刻的理论结果。比如，通常大家会把ADMM当作是Augmented Lagrangian问题的alternating optimization求解方法而已，然而，可以构造出一些特殊问题使得标准的ALM会发散，而ADMM依然可以求得最优解。所以，形式相似虽然很有启发意义，更重要的是研究弄清背后的机理和理论基础。 热心网民 1小时前 0条评论
Penalty methods和Multiplier Methods的形式紧密相关，甚至可以互相解释，所以要清晰而精确地论述二者的本质差异并不容易。
先理清一些误解吧。解析与不解析无非就是个符号而已，只要是唯一确定并且可以计算就够了，不要强迫症地认为"x=log(2)"是解析解，"x是x^3-x-100=0的最大根"就不是解析解。我看到评论中的说法，惩罚函数法适用于不等式约束，拉式乘子法适用于等式约束。这样的描述就很尴尬。通常书本上确实喜欢这么举例，但这并不意味着惩罚函数法不可以用于等式约束，拉式乘子法不可以用于不等式约束。因为很显然我们可以把等式约束写成两个不等式约束，而把类似于g(x)<=0的不等式约束写成max(g(x),0)=0这样的等式约束，所以等式约束问题和不等式约束问题在形式上总可以互相等价转换。
正是这样的等价转换使得二者形式高度相关。惩罚函数是一个约束违背的度量(measure of constraint violation),使得当约束满足时取零，约束违背时取非零。作为一种度量，我们通常要求它非负和单调递增。举个例子，只需要考虑最简单的一维约束y<=0,有很多常用的惩罚函数，比如G(y)=0 if y<=0, infinity else，和 G(y)= max(y,0)^p。简单起见，考虑如下只有一个约束的优化问题: min{F(x): g(x)<=0}。应用上述函数可以得到如下等价变换min{F(x): G[g(x)]=0}。对于这个等价问题，我们写出惩罚函数形式L(x,r)=F(x)+rG[g(x)]，然而这正是拉格朗日函数，所以说惩罚函数法与拉式乘子法形式紧密相关。当然如果拉式乘子法用于原问题，得到的是L(x,r)=F(x)+rg(x)，这个时候效果就不一样了，如果我们放松对惩罚函数非负的要求，形式上拉式乘子法就可以解释为linear penalty method。
个人认为，区分惩罚函数法与拉式乘子法不是上述形式，而是二者对于参数r的意义的理解以及由此导致的求解思路不同。在惩罚函数里，r是作为一个固定的参数来对待的，求解L(x,r)时一直保持不变(当然实际中为了提高求解效率，会使用path-following或SUMT，目的还是求解最终那个惩罚常数对应的问题)。对于惩罚函数法，大多数的理论结果类似于，当r趋于无穷时，L(x,r)的解趋于原问题的解。而在拉式乘子法中，r是作为对偶变量出现的，求解过程中是要不断更新的，而且更多的是会考虑Lagrange Duality。Duality Theory是拉式乘子法的最核心的理论支撑。即便是比较path-following惩罚法和乘子法，关于参数r的更新方法也是不同的，惩罚法中r通常是自适应地按照固定倍率不断增大，因而对于所有的问题案例，r序列都是相同且给定的，而在乘子法中r是一步梯度更新，更新过程中r可能增大也可能减小，对于不同的问题案例，更新得到的r序列是不同的。
为了更进一步说明二者之间的联系和差异，我们考虑凸优化问题，假设F(x)和g(x)都是光滑的凸函数，并且存在x0满足Slater condition即g(x0) < 0。考虑摄动问题V(u)=min{F(x): g(x)<=u}，这个问题至关重要。首先，Lagrange Duality可以根据函数V(u)的性质来构建，具体结论是，对于凸优化问题，如果V(u)在u=0处下半连续，那么strong duality 成立。此时，拉式乘子法可以正常使用。其次，有意思的是，对于惩罚函数法有如下exact penalty theory : 当r > sup{ [V(0)-V(u)]/u : u>0 }时，f(x)=F(x)+rG[g(x)]的解一定是V(0)的解，这里G(y)= max(y,0)。第三，比较无约束凸优化问题min f(x)的最优性条件与约束问题min{F(x): g(x)<=0}的KKT条件，可以进一步发现两个方法内在的相通性: 乘子法是寻找变量x和r使得F'(x)+rg'(x)=0，而惩罚法是寻找变量x使得F'(x)+h(x)=0，这里h(x)是非光滑凸函数rG[g(x)]的一个次梯度subgradient。
总结来看，惩罚法是pure primal method, 乘子法是primal-dual method。从发展历史来看，惩罚法是上个世纪60年代的成果和主流方法，很快在70年代就被两者的结合体ALM: Augmented Lagrangian methods 取代了，并进一步演化出了ADMM: Alternating direction method of multipliers。在凸优化问题中，这些演进有时候并不仅仅是既有思路的简单结合，甚至会有更深刻的理论结果。比如，通常大家会把ADMM当作是Augmented Lagrangian问题的alternating optimization求解方法而已，然而，可以构造出一些特殊问题使得标准的ALM会发散，而ADMM依然可以求得最优解。所以，形式相似虽然很有启发意义，更重要的是研究弄清背后的机理和理论基础。 热心网民 1小时前 0条评论
0 赞 0 踩
登录后可回答 提交回答
关键词 :
- 上一个：海乘人员申请条件与申请流程有什么样？
- 下一个：宝宝趴着睡对内脏有害吗？
推荐资讯
点击排行