机器学习系列（九）- 拉格朗日对偶问题

• 视频参考：“拉格朗日对偶问题”如何直观理解？“KKT条件” “Slater条件” “凸优化”打包理解
• 视频参考：机器学习之凸优化

拉格朗日乘数法

• 拉格朗日乘数法主要解决当存在约束条件时，求函数的最值。

• 定义：其中 $\lambda_i$ 称为拉格朗日乘子

  $\begin{align} min & \enspace f_0(x),x\in\mathbb{R} \newline s.t. & \enspace f_i(x) \le 0,其中i=1,2,3,…,m\end{align} \Rightarrow L(x,y)=f_0(x)+\sum\lambda_i f_i(x)$

• 拉格朗日函数与梯度的关系

  定义函数：$\begin{align} & minf(x),x\in\mathbb{R}^n \newline & s.t. \enspace g_i(x)=a_i^T·x+b \le 0,其中i=1,2,3,…,m;a_i\in\mathbb{R}^n;b_i\in\mathbb{R} \end{align}$ ，设约束条件如图所示；

  

  1. 拉格朗日乘子式：$L(x,\lambda)=f(x)+\sum\lambda_ig_i(x)$

  2. 导数求极值点：$\nabla L(x,\lambda)=0\Rightarrow-\nabla f(x)=\sum\lambda_i·\nabla g_i(x)$

  3. 由图可知最优解在点 $x^{\ast}$ 处，为约束条件 $\nabla g_{\alpha}(x^\ast)$ 与 $\nabla g_{\beta}(x^{\ast})$ 构成直线的交点；且橙色区域为约束条件区域，区域内 $\le0$ ；

     则 $g_{\alpha}(x^{\ast})=g_{\beta}(x^{\ast})=0$

  4. 最优梯度为垂直于约束条件 $\nabla g_\alpha(x^{\ast})$ 与 $\nabla g_\beta(x^{\ast})$ 向量在点 $x^\ast$ 处的和的反方向；

     则 $\lambda_\alpha·\nabla g_\alpha(x^{\ast})+\lambda_\beta·\nabla g_\beta(x^{\ast})=-\nabla f(x)$

     又因最优梯度不为 $0$，且 $g_\alpha(x^\ast)=g_\beta(x^\ast)=0$ ，则可推导 $\lambda_{\alpha},\lambda_{\beta}\ne 0$

  5. 其它约束条件 $g_i(x^\ast)<0$ ，则可推导 $\lambda _i·\nabla g_i(x)=0\Rightarrow \lambda_i=0(i\ne \alpha,\beta)$

     对于所有的 $\lambda_i\ge0,\begin{cases}\lambda_i=0,&g_i(x)松弛 \newline \lambda_i>0,&g_i(x)紧致(发挥作用) \end{cases}$

基础定义

凸问题

• 通过拉格朗日乘数法求导所得可能为极值点或鞍点，而非最值点；但在凸问题的情况下，极值点即为最值点；
• “凸问题”对应“非凸问题”，而非“凹问题”；

凸集

• 凸集定义：$\forall x_1,x_2\in C,0\le\theta\le1 \Rightarrow \theta·x_1+(1-\theta)·x_2\in C$

  即在集合内任意两点，两点连线上的任意点也在集合内部，则为凸集；

• 仿射集定义：$\forall x_1,x_2\in C,\theta\in\mathbb{R} \Rightarrow \theta·x_1+(1-\theta)·x_2\in C$

  变型可得：$x\in\mathbb{R},W\in\mathbb{R},b\in\mathbb{R},C={x\vert W^T·x+b=0}$

  则 $C$ 为仿射集，仿射集为凸集；直线、平面、三维坐标系，均为仿射集（无限延展）；

• 半空间定义：$W\in\mathbb{R},b\in\mathbb{R},C={x\vert W^T·x+b\le 0}$

  则 $C$ 为半空间，半空间为凸集；（直线切割平面）

凸函数

• “凸函数”开口朝上，存在最小值；“凹函数”则与之相反，存在最大值；（与直观理解概念相反）

  

拉格朗日函数对偶问题

对偶问题推导

1. 定义初始问题：

   $\begin{align} min & \enspace f_0(x),x\in\mathbb{R} \newline s.t. & \begin{cases} \enspace f_i(x) \le 0,其中i=1,2,3,…,m \newline \enspace h_i(x) = 0,其中i=1,2,3,…,q \end{cases} \end{align}$

2. 拉格朗日乘数式：$L(x,\lambda,\nu)=f_0(x)+\sum\lambda_i f_i(x)+\sum \nu_i h_i(x)$

   定义原问题：$\begin{align} & min_{x}max_{\lambda,\nu}L(x,\lambda,\nu) \newline & s.t. \lambda\ge0 \end{align}$

   初始问题与原问题等价证明：

   • 将约束条件融入式中后，则该式 $x$ 可任取值；则存在情况：

     $\begin{align} & min_x\begin{cases} x不在初始问题可行域内:max_{\lambda,\nu}L(x,\lambda,\nu)=f_0(x)+\infty+\infty \newline x在初始问题可行域内:max_{\lambda,\nu}L(x,\lambda,\nu)=f_0(x)+0+0 \end{cases} \newline \Rightarrow & min_x max_{\lambda,\nu}L(x,\lambda,\nu) = min_x{\infty,f_0(x)} = minf_0(x) \end{align}$

3. 对偶函数：$g(\lambda,\nu)=min_{x}L(x,\lambda,\nu)$

   对偶问题：$\begin{align} & max_{\lambda,\nu}g(\lambda,\nu)=max_{\lambda,\nu}min_{x}L(x,\lambda,\nu) \newline & s.t. \lambda\ge0 \end{align}$

对偶问题性质

• 拉格朗日函数的对偶问题，对偶函数一定是凹函数，凸优化问题

  • 凸优化问题：对应问题函数为凸函数，可行域为凸集；

  • 函数 $g(\lambda,\nu)$ 为一条直线，既是凸函数，又是凹函数；因求 $max\enspace g(\lambda,\nu)$，则认为是凹函数；则可知求 $max \Rightarrow -min$ ，则函数为凸函数；

    又因 $\lambda\ge 0$ ，则可行域为半空间，半空间为凸集；

    故对偶问题一定是凸优化问题；

原问题与对偶问题等价性

• 原问题：$\begin{align} & P^{\ast}=min_{x}max_{\lambda,\nu}L(x,\lambda,\nu) \newline & s.t. \lambda\ge0\end{align}$

  对偶问题：$\begin{align} & D^{\ast}=max_{\lambda,\nu}g(\lambda,\nu)=max_{\lambda,\nu}min_{x}L(x,\lambda,\nu) \newline & s.t.\lambda\ge0\end{align}$

• 验证过程：

  $\begin{array} max_{\lambda,\nu}\ge L(x,\lambda,\nu)\ge min_{x}L(x,\lambda,\nu) \newline A(x)=max_{\lambda,\nu}\ge L(x,\lambda,\nu)\ge min_{x}L(x,\lambda,\nu)=I(\lambda,\nu) \newline A(x)\ge I(\lambda,\nu) \newline A(x) \ge min_{x}A(x) \ge max_{\lambda,\nu I(\lambda,\nu)} \ge I(\lambda,\nu) \newline P^{\ast}=min_{x}A(x) \ge max_{\lambda,\nu I(\lambda,\nu)}=D^{\ast} \end{array}$

• 理解过程：

  乘子式变型：$L(x,\lambda,\nu)=f_0(x)+\sum\lambda_i f_i(x)+ \sum \nu_i h_i(x) \Rightarrow t+\lambda^T·u$ ，其中 $\sum \nu_i h_i(x)$ 为 $0$ 忽略；

  原问题变型：

  $\begin{array}{l} & min f_0(x),x\in\mathbb{R} \newline & s.t. \begin{cases} f_i(x) \le 0,其中i=1,2,3,…,m \newline h_i(x) = 0,其中i=1,2,3,…,q \end{cases} \newline \Rightarrow & {(t,u)\vert t=f_{0}(x),u_i=f_i(x),x\in D}=G_1 \newline & D = \begin{Bmatrix} x \bigg\vert \begin{array}{l} f_i(x)\le 0,其中i=1,2,3,…,m \newline h_i(x) = 0,其中i=1,2,3,…,q \end{array} \end{Bmatrix} \newline \Rightarrow & min_x {t\vert (t,u)\in G_1,u\le 0} \end{array}$

  对偶问题变型：

  $\begin{array}{l} & max_{\lambda,\nu}min_{x}L(x,\lambda,\nu) \newline & s.t.\lambda\ge0 \newline \Rightarrow & {(t,u)\vert t=f_0(x),u_i=f_i(x),x\in \mathbb{R} }=G_2 \newline \Rightarrow & max_{\lambda} min_x{t+\lambda^T·u\vert(t,u)\in G_2,\lambda\ge0} \end{array}$

  绘制图像：

  

  当集合为非凸集时，情况如上；原问题求最小值，即在定义域内做 $t$ 轴垂线；对偶问题可看作线性函数，$t$ 为截距，$\lambda\ge 0$ 为斜率，做定义域内两最低点切线即可（原因参照机器学习之凸优化集20分左右）；

  

  

  当集合为凸集时，原问题的解 $P^{\ast}$ 等于对偶对题的解 $D^{\ast}$ ；

• 结论：当大于成立时为弱对偶问题，当等于成立时为强对偶问题；

Slater 条件

• 当凸优化问题满足 $Slater$ 条件时，一定是强对偶关系；但强对偶关系，不一定满足 $Slater$ 条件；

• $\begin{array}{l} 存在一个点x\in relint D \newline 使得f_i(x)\lt0，其中i=1,2,3,…,m,Ax=b \newline (relintD表示可行域D的相对内部) \end{array}$

  

KKT 条件

• 当凸优化问题是强对偶关系，一定满足 $KKT$ 条件；但满足 $KKT$ 条件的，不一定是强对偶关系；
• $\begin{array}{rl} 原问题可行条件 & \begin{cases} f_i(x) \le 0 \newline h_i(x) = 0 \end{cases} \newline 对偶可行条件 & \begin{cases} \nabla _xL(x,\lambda,\nu)=0 \newline \lambda\ge0 \end{cases} \newline 互补松弛条件 & \begin{cases} \lambda_i f_i(x)=0 \end{cases}\end{array}$