SVM 进阶:约束优化问题

内容纲要

一般的约束优化问题

约束优化问题常常可以化简为以下不等式,

\begin{aligned}

&\min_{x\in\mathbb{R^p}}f(x)\\
&s.t.\ m_i(x)\le0,i=1,2,\cdots,M\\
&\ \ \ \ \ \ \ \ n_j(x)=0,j=1,2,\cdots,N

\end{aligned}

可以写成拉格朗日函数

L(x,\lambda,\eta)=f(x)+\sum\limits_{i=1}^M\lambda_im_i(x)+\sum\limits_{i=1}^N\eta_in_i(x)

那么原问题可以等价于无约束形式:

\min_{x\in\mathbb{R}^p}\max_{\lambda,\eta}L(x,\lambda,\eta)\  \\s.t.\ \lambda_i\ge0

求偏导后, n_i(x) 会等于0。当未满足约束时, m_i(x) 0\lambda_i 可以调整为最大值 \infin\max_{\lambda,\eta}L(x,\lambda,\eta)\ = \infin ;满足其约束时, m_i(x) \le 0\max_{\lambda,\eta}L(x,\lambda,\eta) 为常数。取 min 显然过滤了不满足约束情况。

这个问题的对偶形式:

\max_{\lambda,\eta}\min_{x\in\mathbb{R}^p}L(x,\lambda,\eta)\ s.t.\ \lambda_i\ge0

对偶问题是关于 \lambda, \eta 的最大化问题。

\max_{\lambda_i,\eta_j}\min_{x}L(x,\lambda_i,\eta_j)\le\min_{x}\max_{\lambda_i,\eta_j}L(x,\lambda_i,\eta_j)

证明,理解为L的值域,值域里面的任何一个数,大于等于它的最小值,小于等于它的最大值

   \min\limits_{x}L\le L\le\max\limits_{\lambda,\eta}L \\  
  \Rightarrow \max\limits_{\lambda,\eta}\min\limits_{x}L\le L   , \min\limits_{x}\max\limits_{\lambda,\eta}L\ge L \\

对偶问题的解小于原问题,有两种情况:

  1. 强对偶,能取等于号
  2. 弱对偶,不能取等于号

几何解释

img

特别的,二次规划问题都满足 slater 条件。对于一个凸优化问题,有如下定理:

凸优化问题满足某些条件如 Slater 条件 \Rightarrow 它和其对偶问题满足强对偶关系。

注意是充分不必要条件。记问题的定义域为: \mathcal{D}=\mathrm{dom}f(x)\cap \mathrm{dom} m_i(x)\cap \mathrm{dom}n_j(x) 。 Slater 条件为:

\exist\hat{x}\in \mathrm{relint}\mathcal{D}\ \text{s.t. } \forall i=1,2,\cdots,M,m_i(x)\lt0 \\  \mathrm{relint} \text{ 表示相对内部(不包含边界的内部)。}\\
  1. 对于大多数凸优化问题,Slater 条件成立。
  2. 对于不满足条件的,可以松弛 Slater 条件,如果 M 个不等式约束中,有 K 个函数为仿射函数,那么只要其余的 (M - K) 个函数满足 Slater 条件即可。

KKT 条件

原问题及其拉格朗日函数为

\begin{aligned}

&\min_{x\in\mathbb{R^p}}f(x)\\
&s.t.\ m_i(x)\le0,i=1,2,\cdots,M\\
&\ \ \ \ \ \ \ \ n_j(x)=0,j=1,2,\cdots,N
\\
&L(x,\lambda,\eta)=f(x)+\sum\limits_{i=1}^M\lambda_im_i(x)+\sum\limits_{i=1}^N\eta_in_i(x) \\
&\text{令 } g(\lambda, \eta) = \min_{x} L(x,\lambda,\eta)
\end{aligned}

对偶问题有

\begin{aligned}
&\max_{\lambda, \eta} g(\lambda, \eta) \\
&\text{s.t. } \lambda_i\ge0
\end{aligned}

原问题和对偶问题满足强对偶关系的充要条件为其满足 KKT 条件,KKT 条件 \Leftrightarrow 强对偶关系。关于原问题, p^* 是最优解, x^* 是最优解参数。关于对偶问题, d^* 是最优解, \lambda^*, \eta^* 是最优解参数。证明弱对偶性实际上就是证明 d^* \le p^* ,强对偶性是证明 d^* = p^* 。KKT 条件对最优解的条件为:

  1. 可行域:
    \begin{aligned}
    m_i(x^*)\le0\\
    n_j(x^*)=0\\
    \lambda^*\ge0
    \end{aligned}
  2. 互补松弛 \lambda^*m_i(x^*)=0,\forall m_i
    \begin{aligned}
    d^*&=\max_{\lambda,\eta}g(\lambda,\eta)=g(\lambda^*,\eta^*) \\
    &=\min_{x}L(x,\lambda^*,\eta^*) \\
    &\le L(x^*,\lambda^*,\eta^*) \\
    &=f(x^*)+\sum\limits_{i=1}^M\lambda^*m_i(x^*) \\
    &\le f(x^*)=p^*
    \end{aligned}

    为了满足相等,两个不等式必须成立,于是,对于第一个不等于号,需要有梯度为0条件,对于第二个不等于号需要满足互补松弛条件。

  3. 梯度为0: \frac{\partial L(x,\lambda^*,\eta^*)}{\partial x}|_{x=x^*}=0

发表评论

邮箱地址不会被公开。 必填项已用*标注