拉格朗日

拉格朗日对偶性是解决带约束的最优化问题的方法，在实际应用中，通过拉格朗日对偶原理将原始问题转换成对偶问题，将原来不容易解决的问题转化为一个容易解决的问题，如支持向量机，最大熵模型。

原始问题

假设$f(x)，c_i(x),h_j(x)$是定义在$\mathbb{R}^{n}$上的连续可微函数。我们需要求解约束最优化问题：

$$\underset{x\in \mathbb{R}^n}{min} f(x)$$ $$\begin{align} \mathbb{s.t.}\quad &c_i(x) \le 0,\quad i=1,2,\cdots,k\\ &h_j(x)=0,\quad j=1,2,\cdots,l \end{align}$$

广义拉格朗日函数

为了求解原始问题，我们首先引入广义拉格朗日函数(generalized Lagrange function)：

$$L(x,\alpha,\beta)=f(x)+\sum_{i=1}^k \alpha_ic_i(x) + \sum_{j=1}^l\beta_jh_j(x) \tag{4}$$

其中，$x=(x_1,x_2,\cdots,x_n)^T \in \mathbb{R}^n$，$\alpha_i$和$\beta_j$是拉格朗日乘子，特别要求$\alpha_i\geqslant 0$

原始问题的等价转换：极小极大问题

如果把$L(x,\alpha,\beta)$看作是$\alpha、\beta$的函数，求其最大值，即$\theta_p(x)=\max_{\alpha,\beta:\alpha_i\ge0}L(x,\alpha,\beta) \tag 5$

确定$\alpha、\beta$使$L(x,\alpha,\beta)$取得最大值，（此过程中把$x$看做常量）下面通过$x$是否满足约束条件两方面来分析这个函数

• 如果$x$ 满足原始问题中约束，
  由(2)、(3)、(4)、(5)可知 $θ(x)=f(x)$。（少的两项一个是非正的，一个是0，要取最大值的话当然得令两者都为0
• 如果 $x$ 不满足原始问题中的约束，那么 $θ(x)=+∞$。若某个$i$使约束$c_i(x)>0$，则可令则可令$\alpha \rightarrow +∞$，若某个$j$使得$h_j(x)\neq 0,$,则可令$\beta_j h_j(x) \rightarrow +∞$，而将其余各$\alpha _i、\beta_j$均取为0。

综上：

$$\theta_p(x)=\left\{\begin{matrix} f(x),&x 满足原始问题约束\\ +\infty,&其他 \end{matrix}\right.$$

求解原问题的最小值与原始问题等价

$$\color{red}{\underset{x\in \mathbb{R}^n}{min}\; \theta_p(x)= \underset{x\in \mathbb{R}^n}{min}\; f(x)= \underset{x\in \mathbb{R}^n}{min}\;\max_{\alpha,\beta:\alpha_i\ge0}L(x,\alpha,\beta) }$$

原始问题和对偶问题的关系

• 弱对偶关系：弱对偶关系一定存在，
  若原始问题和对偶问题都有最优值，则 $$\color{red}{\underset{\alpha,\beta:\alpha_i\ge0}{max}\; \underset{x\in\mathbb{R}^{n}}{min}\; L(x,\alpha,\beta) \leqslant \underset{x\in \mathbb{R}^n}{min}\;\max_{\alpha,\beta:\alpha_i\ge0}L(x,\alpha,\beta) ={min}\; f(x)}$$

• 强对偶关系
  设$x^\ast$和$a^\ast$,$β^\ast$分别是原始问题$\underset{x\in \mathbb{R}^n}{min}\;\underset{\alpha,\beta:\alpha_i\ge0}{max}\; L(x,\alpha,\beta)$和对偶问题$\underset{\alpha,\beta:\alpha_i\ge0}{max}\; \underset{x\in\mathbb{R}^{n}}{min}\; L(x,\alpha,\beta)$的可行解，并且 $$\underset{\alpha,\beta:\alpha_i\ge0}{max}\; \underset{x\in\mathbb{R}^{n}}{min}\; L(x,\alpha,\beta) = \underset{x\in \mathbb{R}^n}{min}\;\max_{\alpha,\beta:\alpha_i\ge0}L(x,\alpha,\beta) ={min}\; f(x)$$ $$\color{red}{\underset{x\in\mathbb{R}^{n}}{min}\; L(x,\alpha^\ast ,\beta^\ast ) = \max_{\alpha,\beta:\alpha_i\ge0}L(x^\ast ,\alpha,\beta)={min}\; f(x^\ast )}$$ 则$x^\ast$和$a^\ast$,$β^\ast$分别是原始问题和对偶问题的最优解。

弱对偶关系

若原始问题和对偶问题都有最优值，则

$$\underset{x\in\mathbb{R}^{n}}{min}\; L(x,\alpha,\beta) \leqslant L(x,\alpha,\beta) \leqslant \max_{\alpha,\beta:\alpha_i\ge0}L(x,\alpha,\beta)$$ $$\color{red}{\underset{\alpha,\beta:\alpha_i\ge0}{max}\; \underset{x\in\mathbb{R}^{n}}{min}\; L(x,\alpha,\beta) \leqslant \underset{x\in \mathbb{R}^n}{min}\;\max_{\alpha,\beta:\alpha_i\ge0}L(x,\alpha,\beta) ={min}\; f(x)}$$

推论：设$x^\ast$和$a^\ast$,$β^\ast$分别是原始问题$\underset{x\in \mathbb{R}^n}{min}\;\underset{\alpha,\beta:\alpha_i\ge0}{max}\; L(x,\alpha,\beta) $和对偶问题$\underset{\alpha,\beta:\alpha_i\ge0}{max}\; \underset{x\in\mathbb{R}^{n}}{min}\; L(x,\alpha,\beta) $的可行解，并且$\underset{x\in \mathbb{R}^n}{min}\;\underset{\alpha,\beta:\alpha_i\ge0}{max}L(x,\alpha,\beta) =\underset{\alpha,\beta:\alpha_i\ge0}{max}\; \underset{x\in\mathbb{R}^{n}}{min}\; L(x,\alpha,\beta) $，则$x^\ast$和$a^\ast$,$β^\ast$分别是原始问题和对偶问题的最优解。

强对偶关系

• 定理1：判断强对偶关系
  假设函数$f(x)$和$c_i(x)$是凸函数，$h_j(x)$是仿射函数，并且不等式约束$c_i(x)$是严格可行的，即存在$x$,对所有$i$有$c_i(x)<0$，则存在$x^\ast$和$a^\ast,β^\ast$分别是原始问题和对偶问题的解,并且满足

  $$\color{red}{\underset{\alpha,\beta:\alpha_i\ge0}{max}\; \underset{x\in\mathbb{R}^{n}}{min}\; L(x,\alpha^\ast ,\beta^\ast ) =L(x^\ast,\alpha^\ast ,\beta^\ast )= \underset{x\in \mathbb{R}^n}{min}\;\max_{\alpha,\beta:\alpha_i\ge0}L(x^\ast ,\alpha,\beta) ={min}\; f(x^\ast )}$$

• 定理2：KKT条件(求最优解)
  假设函数$f(x)$和$c_i(x)$是凸函数，$h_j(x)$是仿射函数，并且不等式约束$c_i(x)$是严格可行的，则$x^\ast$和$a^\ast,β^\ast$分别是原始问题和对偶问题的解的充分必要条件是$x^\ast,a^\ast,β^\ast$满足下面的Karush-Kuhn-Tucker(KKT)条件：（判断极值、其余项为0）

  $$\begin{align*} \nabla_xL(x^\ast,\alpha^\ast,\beta^\ast)&=0\\ \nabla_{\alpha}L(x^\ast,\alpha^\ast,\beta^\ast) &=0 \\ \nabla_{\beta}L(x^\ast,\alpha^\ast,\beta^\ast)&=0 \end{align*}$$ $$\begin{align*} \alpha_i^*c_i(\boldsymbol{x}^*)&=0,\quad i=1,2,\cdots,k\\ c_i(\boldsymbol{x}^*)&\le0,\quad i=1,2,\cdots,k \\ \alpha_i^*&\ge0,\quad i=1,2,\cdots,k \\ h_j(\boldsymbol{x}^*)&=0,\quad j=1,2,\cdots,l \end{align*}$$

  当原问题是凸优化问题时，满足KKT条件的点也是原、对偶问题的最优解。

  • 仿射函数 $$f(x)=A\cdot x+b$$ 仿射函数就是一个线性函数，其输入是$n$ 维向量，参数 $A$ 可以是常数，也可以是 $m×n$ 的矩阵，$b$可以是常数，也可以是 $m$ 维的列向量，输出是一个 $m $维的列向量。在几何上，仿射函数是一个线性空间到另一个线性空间的变换。