数学教学系列7:拉格朗日对偶问题

在优化理论中,目标函数 f(x) 会有多种形式:如果目标函数和约束条件都为变量 xx 的线性函数, 称该问题为线性规划; 如果目标函数为二次函数, 约束条件为线性函数, 称该最优化问题为二次规划; 如果目标函数或者约束条件均为非线性函数, 称该最优化问题为非线性规划。每个线性规划问题都有一个与之对应的对偶问题,对偶问题有非常良好的性质,以下列举几个:

  1.     对偶问题的对偶是原问题;
  2.     无论原始问题是否是凸的,对偶问题都是凸优化问题;
  3.     对偶问题可以给出原始问题一个下界;
  4.     当满足一定条件时,原始问题与对偶问题的解是完全等价的;

求取有约束条件的优化问题时,拉格朗日乘子法(Lagrange Multiplier) 和KKT条件是非常重要的两个求取方法,对于等式约束的优化问题,可以应用拉格朗日乘子法去求取最优值;如果含有不等式约束,可以应用KKT条件去求取。当然,这两个方法求得的结果只是必要条件,只有当是凸函数的情况下,才能保证是充分必要条件。KKT条件是拉格朗日乘子法的泛化。下文,我们将详细说明拉格朗日对偶问题和原问题的联系。

拉格朗日对偶性

 

$\ \ $在约束最优化问题中,常常利用拉格朗日对偶性(Lagrange duality)将原始问题转换为对偶问题,通过解对偶问题而得到原始问题的解.该方法应用在许多统计学习方法中,例如,最大熵模型与支持向量机.这里简要叙述拉格朗日对偶性的主要概念和结果.

1.原始问题

$\ \ $假设$f(x),c_i(x),h_j(x)$是定义在$R^n$上的连续可微函数.考虑约束最优化问题

$$\min_{\propto R^+}f(x) \tag{C.1}

$$$$s.t. \ \ \ c_i(x)\leq0, \ \ \ i=1,2,\cdots,k \tag{C.2}$$$$
h_j(x)=0,\ \ \ j=1,2,\cdots,l \tag{C.3}$$

称此约束最优化问题为原始最优化问题或原始问题.

首先,引进广义拉格朗日函数(generalized Lagrange function)

$$

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

这里,$x=(x^(1),x^(2),\cdots,x^(n))^T\in R^n,\alpha_i,\beta_j$是拉格朗日乘子.$a_i\geq0$考虑$x$的函数:
$$\theta_P(x)=\max_{\alpha,beta,\alpha_i\geq0}L(x,\alpha,\beta) \tag{C.5}$$
这里,下标$P$表示原始问題.

$\ \ $假设给定某个$x$.如果$x$违反原始问題的约束条件,即存在某个$i$使得$c_i(w)>0$,或者存在某个$j$使得$h_j(w)\neq0$,那么就有

$$\theta_P(x)=\max_{\alpha,\beta,\alpha_i\geq)}[f(x)+\sum^{t}_{j=1}\beta_jh_j(x)]=+\infty \tag{C.6}$$
因为若某个$i$使约束$c_i(x)>0$,则可令$\alpha_i\to +\infty$,若某个$j$使$h_j(x)\neq0$,可令使在$\beta_j$,使$\beta_jh_j(x)\to +\infty$,而将其余各$\alpha_i,\beta_j$均取为0.

$\ \ $相反地,如果满足约束条件式(C.2)和式(C.3),则由式(C.5)和式(C.4)可知,$\theta_P(x)=f(x)$.因此,
$$\theta_P(x)= \begin{cases}
f(x), & \text{x满足原始问题约束} \\
+\infty, & \text{其他} \tag{C.7}
\end{cases}$$
所以如果考虑极小化问题
$$\min_{x}\theta_P(x)=\min_{x}\max_{\alpha,\beta,\alpha}L(x,\alpha,\beta) \tag{C.8}$$
它是与原始最优化问题$(C.1)\sim(C.3)$等价的,即它们有相同的解.问題$\min_{x}\max_{\alpha,\beta,\alpha}L(x,\alpha,\beta) $,称为广义拉格朗日函数的极小极大问题.这样一来,就把原始最优化问题表示为广义拉格朗日函数的极小极大问题.为了方便,定义原始问题的最优值
$$p^*=\min_{x}\theta_P(x) \tag{C.9}$$
称为原始问题的值.

2.对偶问题

$\ \ $定义
$$\theta_D(\alpha,\beta)=\min_{x}L(x,\alpha,\beta) \tag{C.10}$$
再考虑极大化$\theta_D(\alpha,\beta)=\min_{x}L(x,\alpha,\beta)$,即
$$\max_{\alpha,\beta,\alpha_i\geq0}\theta_D(\alpha,\beta)=\max_{\alpha,\beta,\alpha_i\geq0}\max_{x}L(x,\alpha,\beta) \tag{C.11}$$
问题$\max_{\alpha,\beta,\alpha_i\geq0}\max_{x}L(x,\alpha,\beta)$称为广义拉格朗日函数的极大极小问题.

$\ \ $可以将广义拉格朗日函数的极大极小问题表示为约束最优化问题:
$$\max_{\alpha,\beta}\theta_D(\alpha,\beta)=\max_{\alpha,\beta}\min_{x}L(x,\alpha,\beta) \tag{C.12}$$

$$s.t.\ \ \ \ \alpha_i\geq0,\ \ \ i=1,2,\cdots,k \tag{C.13}$$

称为原始问题的对偶问题.定义对偶问题的最优值
$$d^*=\max_{\alpha,\beta,\alpha_i\geq0}\theta_D(x,\alpha,\beta) \tag{C.14}$$

称为对偶问题的值.

 

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

下面讨论原始问题和对偶问题的关系.

定理C.若原始问题和对偶问题都有最优值,则
$$d^*=\max_{\alpha,\beta,\alpha_i\geq0}\min_x L(x,\alpha,\beta)\leq\min_x\max_{\alpha,\beta,\alpha_i\geq0}L(x,\alpha,\beta)=p^* \tag{C.15}$$

证明 $\ \ \ \ $ 由式(C.12)和式(C.5).对任意的$\alpha,\beta,x$,有
$$\theta_D(\alpha,\beta)=\min_xL(x,\alpha,\beta)\leq\max_{\alpha,\beta,\alpha_i\geq0}L(x,\alpha,\beta)=\theta_P(x) \tag{C.16}$$

$$\theta_D(\alpha,\beta)\leq\theta_P(x) \tag{C.17}$$
由于原始问题和对偶问题均有最优值,所以,
$$d^*=\max_{\alpha,\beta,\alpha_i\geq0}\min_x L(x,\alpha,\beta)\leq\min_x\max_{\alpha,\beta,\alpha_i\geq0}L(x,\alpha,\beta)=p^* \tag{C.19}
$$$\ \ \ \ $推论C.1$\ \ \ $设$x^*$和$\alpha^*,\beta^*$ 分别是原始问题(C.1)$\sim$(C.3)和对偶问题(C.12)$\sim$(C.13)的可行解,并且$d^*=p^*$,则$x^*$和$\alpha^*,\beta^*$分别是原始问题和对偶问题的最优解.

$\ \ $在某些问题下去,原始问题和对偶问题的最优值相等,$d^*=p^*$.这时可以用解对偶问题替代解原始问题.下面以定理的形式叙述有关的重要结论而不予证明.

$\ \ $定理C.2$\ \ $考虑原始问题(C.1)$\sim$(C.3)和对偶问题(C.12)$\sim$(C.13).假设函数$f(x)$和$c_i(x)$是凸函数,$h_j(x)$是仿射函数;并且假设不等式约束$c_i(x)$是严格可行的,即存在$x$,对所有$i$有$c_i(x)<0$,则存在$x^*$,$\alpha^*,\beta^*$,使$x^*$是对偶问题的解,并且
$$p^*=d^*=L(x^*,\alpha^*,\beta^*) \tag{C.20}$$

$\ \ $定理C.3,对原始问题(C.1)$\sim$(C.3)和对偶问题(C.12)$\sim$(C.13),,假设函数$f(x)$和$c_i(x)$是凸函数,$h_i(x)$是仿射函数 ,并且不等式约束$c_i(x)$是严格可行的,则$x^*$和$\alpha^*,\beta^*$分别是原始问题和对偶问题的解的充分必要条件是$x^*$,$\alpha^*,\beta^*$下面的Kanish-Kuhn-Tucker (KKT)条件:$$

\nabla_xL(x^*,\alpha^*,\beta^*)=0 \tag{C.21}\\$$

$$\nabla_\alpha L(x^*,\alpha^*,\beta^*)=0 \tag{C.22}$$

$$\nabla_\beta L(x^*,\alpha^*,\beta^*)=0 \tag{C23}$$

$$a^*_ic_i(x^*)=0, \ \ \ i=1,2,\cdots,k \tag{C.24}$$

$$c_i(x^*)\leq0, \ \ \ i=1,2,\cdots,k \tag{C.25}$$

$$a^*_i\geq0, \ \ \ i=1,2,\cdots,k \tag{C.26}$$

$$h_j(x^*)=0, \ \ \ j=1,2,…,l \tag{C.27}$<p>

$\ \ ​$特别指出,式(C.24)称为KKT的对偶互补条件,由此条件可知:若$a^*_i>0,​$则$c_i(x^*)=0​$.
<font>

In [ ]:
 

 


机器学习系列目录

1. 机器学习系列1:算法基础-Logistic回归
2. 机器学习系列2:算法基础-K-Means
3. 机器学习系列3:算法基础-决策树
4. 机器学习系列4:进阶算法-SVM
5. 机器学习系列5:进阶算法-随机森林
6. 数学教学系列6:ARMA模型
当前阅读>  7. 数学教学系列7:拉格朗日对偶问题
8. 数学教学系列8:梯度下降法
9. 数学教学系列9:B-S期权定价模型