凸优化&拉个朗日对偶性的直观理解
凸优化相关书籍
- 参考链接：优化方法-资料集合
问题定义
- 一般优化问题的定义:
$$
\begin{align}
\min_{x}\quad &f(x) \\
s.t. \quad &g_{i}(x) \leq 0, i = 1,2,\dots,k \\
&h_{j}(x) = 0, j = 1,2,\dots,l
\end{align}
$$
凸优化问题
- 如果原始优化问题满足:
- \(f(x)\) 和 \(g_{i}(x)\) 都是 \(\mathbb{R}^{n}\) 上连续可微的凸函数
- \(h_{j}(x)\) 为 \(\mathbb{R}^{n}\) 上的仿射函数 (仿射函数是满足 \(h_{j}(x) = a\cdot x + b\) 的函数)
- 那么,原始优化问题是凸优化问题
凸二次优化问题
- 若上述凸优化问题还满足:
- \(f(x)\) 是二次函数
- \(g_{i}(x)\) 是 \(\mathbb{R}^{n}\) 上的仿射函数
- 那么,原始优化问题是凸二次优化问题
朗格朗日对偶性
拉格朗日对偶性的推导
- 原始问题定义为
$$
\begin{align}
\min_{x}\quad &f(x) \\
s.t. \quad &g_{i}(x) \leq 0, i = 1,2,\dots,k \\
&h_{j}(x) = 0, j = 1,2,\dots,l
\end{align}
$$
引进拉格朗日函数有
$$
\begin{align}
L(x,\alpha, \beta) = f(x) + \sum_{i=1}^{k}\alpha_{i}g_{i}(x) + \sum_{j=1}^{l}\beta_{j}h_{j}(x)
\end{align}
$$考虑到
$$
\begin{align}
\max_{\alpha,\beta:\alpha_{i}\geq 0}L(x,\alpha, \beta)
\end{align}
$$- 当 \(x\) 满足原始问题的解时,上面的式子等价与 \(f(x)\)
- 否则上面的式子等于无穷大 \(+\infty\)
所以假设原始问题的最优值为 \(p^{\star}\)，那么
$$
\begin{align}
p^{\star} = \min_{x}\max_{\alpha,\beta:\alpha_{i}\geq 0}L(x,\alpha, \beta)
\end{align}
$$- (\(p^{\star}\) 不是最优参数,是最优参数对应的函数值,参数应该用 \(\mathop{\arg\max}_{x}\) 而不是 \(\max_{x}\))
定义对偶问题为:
$$
\begin{align}
&\max_{\alpha,\beta:\alpha_{i}\geq 0}\min_{x}L(x,\alpha, \beta) \\
&s.t.\quad \alpha_{i} \geq 0,\quad i=1,2,\dots,k
\end{align}
$$假设原始问题的最优解为 \(d^{\star}\)，则原始问题与对偶问题的关系为:
$$
\begin{align}
d^{\star} = \max_{\alpha,\beta:\alpha_{i}\geq 0}\min_{x}L(x,\alpha, \beta) = \min_{x}\max_{\alpha,\beta:\alpha_{i}\geq 0}L(x,\alpha, \beta) = p^{\star}
\end{align}
$$
KKT条件
- 原始可行性 ： \(g_{i}(x) \leq 0\)， \(h_{j}(x) = 0\)
- 所有原始约束必须满足
- 对偶可行性 ： \(\alpha_i \geq 0\)
- 所有的不等式约束对应的拉格朗日乘子大于等于0
- 互补松弛性 ： \(\alpha_i g_i(x) = 0\)
- 对于每个不等式约束 \(g_i(x)\)，都有 \(\alpha_i g_i(x) = 0\)，这意味着如果一个约束是紧约束（即 \(g_i(x) = 0\) ），那么对应的 \(\alpha_i\) 可以是非零的；如果一个约束是松的（即 \(g_i(x) < 0\) ），那么对应的 \(\alpha_i\) 必须为零
- 梯度条件 ： \(\nabla_x L(x^, \alpha^, \beta^*) = 0\)
- 在最优解处，拉格朗日函数关于 \(x\) 的梯度必须为零
- 其他理解:
- 对KKT条件其他角度的理解可参考周志华<<机器学习>>P404