Math——凸优化问题和拉格朗日对偶性

Posted on

问题定义

  • 一般优化问题的定义:

$$
\begin{align}
\min_{w}\quad &f(w) \\
s.t. \quad &g_{i}(w) \leq 0, i = 1,2,\dots,k \\
&h_{j}(w) = 0, j = 1,2,\dots,l
\end{align}
$$

凸优化问题

  • 如果原始优化问题满足:
    • \(f(w)\)和\(g_{i}(w)\)都是\(\mathbb{R}^{n}\)上连续可微的凸函数
    • \(h_{j}(w)\)为\(\mathbb{R}^{n}\)上的仿射函数 (仿射函数是满足\(h_{j}(x) = a\cdot x + b\)的函数)
  • 那么,原始优化问题是凸优化问题

凸二次优化问题

  • 若上述凸优化问题还满足:
    • \(f(w)\)是二次函数
    • \(g_{i}(w)\)是\(\mathbb{R}^{n}\)上的仿射函数
  • 那么,原始优化问题是凸二次优化问题

朗格朗日对偶性

拉格朗日对偶性的推导
  • 原始问题定义为

$$
\begin{align}
\min_{w}\quad &f(w) \\
s.t. \quad &g_{i}(w) \leq 0, i = 1,2,\dots,k \\
&h_{j}(w) = 0, j = 1,2,\dots,l
\end{align}
$$

  • 引进拉格朗日函数有
    $$
    \begin{align}
    L(x,\alpha, \beta) = f(w) + \sum_{i=1}^{k}\alpha_{i}g_{i}(w) + \sum_{j=1}^{l}\beta_{j}h_{j}(w)
    \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}\)不是最优参数,是最优参数对应的函数值,参数应该用\(\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}
    $$

  • 满足下面条件的最优化问题,\(x^{\star}\)和\((\alpha^{\star}, \beta^{\star})\)分别是原始问题和对偶问题的解的充分必要条件是\((x^{\star}, \alpha^{\star}, \beta^{\star})\)满足KKT条件

    • 原始问题是凸优化问题
    • 不等式约束\(c_{i}(x) < 0\)是严格可行的,即:
      $$\exists x \quad \forall i, \quad c_{i}(x) < 0$$

  • 需要强调的是:

    • KKT条件是强对偶性成立的必要条件
    • 当原始问题是凸优化问题且不等式约束\(c_{i}(x) < 0\)是严格可行的时: KKT条件是强对偶性成立的充要条件
KKT条件:

$$
\begin{align}
\nabla_{x}L(x^{\star}, \alpha^{\star}, \beta^{\star}) &= 0 \\
\nabla_{\alpha}L(x^{\star}, \alpha^{\star}, \beta^{\star}) &= 0 \\
\nabla_{\beta}L(x^{\star}, \alpha^{\star}, \beta^{\star}) &= 0 \\
h_{j}(x^{\star}) &= 0 \quad j=1,2,\dots,l \\
c_{i}(x^{\star}) &\leq 0, i=1,2,\dots,k \\
\alpha_{i}^{\star} &\geq 0, i=1,2,\dots,k \\
\alpha_{i}^{\star}c_{i}(x^{\star}) &= 0, i=1,2,\dots,k
\end{align}
$$

  • 补充说明:
    • \(x^{\star}\)是原始问题的解
    • \((\alpha^{\star}, \beta^{\star})\)是对偶问题的解
  • 理解:
    • 前三个无约束最优化时求极值的方法,导数为0
    • 中间两个是原始问题中的要求
    • 倒数第二个\(\alpha_{i}^{\star} \geq 0\)是为了保证\(f(x)\)的梯度和\(c_{i}(x)\)的梯度方向相反,详情参考周志华<<机器学习>>P404
    • 最后一个KKT条件可通过梯度方向推出,详情参考周志华<<机器学习>>P404