约束优化方法

2019-07-11 本文已影响3人有苦向瓜诉说

在机器学习中，常常需要对损失函数进行优化，但是我们可能希望在给定的集合中来搜索函数的最大值或者最小值，这就是约束优化。一个简单的方法是考虑约束条件后进行修改后的梯度下降，或者直接设计一个不同的、无约束的优化问题，其解可以转化为原始优化问题的解。

对于等式约束，可以直接采用拉格朗日方法，而对于不等式约束，可以使用KKT方法转换到广义的朗格朗日乘子中求解。

Karush-Kuhn-Tucker（KKT）方法是一种针对约束优化的通用的解决方案，假设优化目标存在等式约束和不等式约束
$S = \left \{ x|\forall i,g^{(i)}(x)=0 \space and \space \forall j,h^{(j)}(x) \leq 0 \right \}$

可以定义广义lagangian函数为
$L(x,\lambda,\alpha)=f(x)+\sum_i \lambda_{i} g^{(i)}(x) + \sum_{j} \alpha_{j} h^{(j)}(x)$
其中， $\alpha \geq 0,\lambda$ 是KKT乘子。

则约束可以转换为约束最小化问题，则为
$\min_{x} \max_{\lambda} \max_{\alpha,\alpha \geq 0} L(x,\lambda,\alpha)$
如果是要求约束最大化，则可以取上式的f(x)为负或者把整个式子设为负号，上式的等式约束所对应的符号并不重要。

可以用一组性质来描述约束优化问题的最优点，称为KKT条件，这是确定一个点的必要条件，而非充分条件。这些条件是

广义lagrangian函数的梯度为0。
满足所有关于 $x$ 和KKT乘子的约束。（其中 $\alpha \geq 0$ )
不等式约束满足： $\alpha \odot h(x) = 0$ .(即两个中至少一个为0)

对不等式约束的直观解释，这个解为不等式强加的边界，可以通过KKT乘子影响最优解，或者消除不等式对解的影响。

欢迎大家关注公众号“计算机视觉与机器学习”

计算机视觉和机器学习

约束优化方法

猜你喜欢

热点阅读