解决约束优化问题:投影梯度与对偶?

机器算法验证 机器学习 优化 正则化
2022-04-04 19:56:24

我最近了解了投影梯度下降并有一个问题。我的理解是,当你有约束优化问题时,你使用对偶来解决一个更简单的对偶问题,这也给出了原始问题的答案。投影梯度下降只是解决约束优化问题的另一种方法吗?如果是这样,人们什么时候使用投影梯度下降而不是对偶,反之亦然?

2个回答

基本上是的,投影梯度下降是解决约束优化问题的另一种方法。它仅在投影操作简单或具有封闭形式时才有用,例如框约束或线性约束集。

除了直接用简单的约束集解决约束问题外,它还可以用于对偶,在某些问题上效果很好。例如,在许多问题中,原始项不受约束但涉及非平滑项。通过取对偶,可以(通常)将非平滑项转换为简单约束,从而使问题的其余部分可区分。然后可以使用投影梯度下降。这方面的例子包括 L1 范数正则化问题;我特别喜欢这种技术的应用。

AaronDefazio 有一个很好的答案:

它仅在投影操作简单或具有封闭形式时才有用,例如框约束或线性约束集。

我只是添加一些细节和这个陈述的一个例子。

请注意,在 Projected Gradient Decent 中,投影步骤是另一个优化问题。在这个问题中,我们想找到一个点C(约束集),这个点最接近给定点x. 哪个是

arg minxCxx

在某些情况下,这个优化问题很容易解决并且已经关闭。AaronDefazio 提到了框约束和线性约束集。我将使用一个更简单的例子,球体约束来演示(球体约束是L2,盒子约束是L1)。

arg minxCxx={xxrrxxotherwise

该等式表明,如果该点位于约束域内,则投影就是该点本身。

我将用图形演示的情况,检查蓝色轨道和红色轨道中的点(用数字标记),关系很简单:将蓝色点与中心连接圆(灰色虚线),与圆的交点是投影。rxx

在此处输入图像描述

这个例子的重点是试图表明在这种情况下找到投影是容易和直观的,并且它有一个封闭形式的解决方案。另一方面,如果我们有一个非常复杂的,解决不会这么小。在这种情况下,我们可能不会使用投影梯度下降。Carg minxCxx