文章目录

引言

在约束最优化问题中,常常利用拉格朗日对偶性(Lagrange duality)将原始问题转化为对偶问题,通过解对偶问题得到原始问题的解。该方法应用在许多统计学习方法中,例如最大熵模型与支持向量机。

原始问题

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

$$
\begin{aligned}
\min_{x\in\Bbb R^n}\qquad &f(x)\\
s.t.\qquad &c_i(x)\le 0,\quad i=1,2,\cdots,k\\
&h_j(x)=0,\quad j=1,2,\cdots,l
\end{aligned}\tag{1~3}
$$

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

首先引入广义拉格朗日函数(generalized Lagrange function)$$L(x,\alpha,\beta)=f(x)+\sum_{i=1}^k\alpha_ic_i(x)+\sum_{j=1}^l\beta_jh_i(j)\tag{4}$$

这里,$x=(x^{(1)},x^{(2)},\cdots,x^{(n)})^T\in \Bbb R^n$,$\alpha_i,\beta_j$是拉格朗日乘子,$\alpha_i\ge 0$。考虑$x$的函数:$$\theta_P(x)=\max_{\alpha,\beta:\alpha_i\ge 0}\;L(x,\alpha,\beta)\tag{5}$$

其中下标P表示此为原始问题。

假设给定某个$x$。如果$x$违反原始问题的约束条件,即存在某个$i$使得$c_i(w)\gt 0$或者存在某个$j$使得$c_i(w)\ne 0$(说白了就是$x$不在可行域内),那么就有$$\theta_P(x)=\max_{\alpha,\beta:\alpha_i\ge 0}\;\left[f(x)+\sum_{i=1}^k\alpha_ic_i(x)+\sum_{j=1}^l\beta_jh_j(j)\right]=+\infty\tag{6}$$

某因为若个$i$使约束$c_i(w)\gt 0$,则可令$\alpha_i \to +\infty$,若某个$j$使得$c_i(w)\ne 0$,则可令$\beta_j$使$\beta_jh_j(x)\to +\infty$,而将其余各$\alpha_i,\beta_j$均取为0。

相反地,如果$x$满足约束条件式$s.t.$,则由上文的$(5)$式和$(6)$式可知,$\theta_P(x)=f(x)$。因此,

$$
\theta_P(x)=
\begin{cases}
f(x),&\text{$x$满足原始问题约束}\\[3ex]
+\infty,&\text{其他}
\end{cases}\tag{7}
$$

所以考虑极小化问题$$min_x\theta_P(x)=\min_x\max_{\alpha,\beta:\alpha_i\ge 0}\;L(x,\alpha,\beta)\tag{8}$$

它是与原始最优化问题$(1-3)$等价的,即它们有相同的解。问题$\min_x\max_{\alpha,\beta:\alpha_i\ge 0}\;L(x,\alpha,\beta)\tag{8}$称为广义拉格朗日函数的极小极大问题。这样一来,就把原始最优化问题表示为广义拉格朗日问题的极小极大问题。为了方便,定义原始问题的最优值$$p*=\min_x\theta_P(x)\tag{9}$$称为原始问题的值。

对偶问题

定义$$\theta_D(\alpha,\beta)=\min_xL(x,\alpha,\beta)\tag{10}$$

再考虑极大化$\theta_D(\alpha,\beta)=\min_xL(x,\alpha,\beta)$,即$$\max_{\alpha,\beta:\alpha_i\ge 0}\theta_D(\alpha,\beta)=\max_{\alpha,\beta:\alpha_i\ge 0}\min_xL(x,\alpha,\beta)\tag{11}$$问题$\max_{\alpha,\beta:\alpha_i\ge 0}\min_xL(x,\alpha,\beta)$称为广义拉格朗日函数的极大极小问题。

可以将广义拉格朗日函数的极大极小问题表示为约束最优化问题:$$\max_{\alpha,\beta}\theta_D(\alpha,\beta)=\max_{\alpha,\beta}\min_xL(x,\alpha,\beta)\tag{12}$$$$s.t.\quad \alpha_i\ge 0,\quad i=1,2,\cdots,k\tag{13}$$称为原始问题的对偶问题。定义对偶问题的最优值:$$d^*=\max_{\alpha,\beta:\alpha_i\ge 0}\theta_D(\alpha,\beta)\tag{14}$$称为对偶问题的值。

凸集、凸函数与凸优化

凸集的定义

在凸几何中,凸集(convex set)是在凸组合下闭合的仿射空间的子集。更具体地说,在欧氏空间中,凸集是对于集合内的每一对点,连接该对点的直线段上的每个点也在该集合内。例如,立方体是凸集,但是任何中空的或具有凹痕的例如月牙形都不是凸集。
特别的,凸集,实数R上(或复数C上)的向量空间中,如果集合S中任两点的连线上的点都在S内,则称集合S为凸集。即$$\forall x_1,x_2\in S,0\le \theta \le 1\Rightarrow \theta x_1+(1-\theta)x_x\in S$$

常见凸集

若$$\forall x_1,x_2\in S,\theta \in \Bbb R\Rightarrow \theta x_1+(1-\theta)x_x\in S$$这里$\theta x_1+(1-\theta)x_x\in S$亦可写成$C=\{x|W^Tx+b=0\}$

其中$S$是仿射集,仿射集一定是凸集。

若$S_1,S_2,S_3$都是仿射集,那么$S_1\cap S_2\cap S_3$还是凸集吗?

如上图所示,$S_1\cap S_2\cap S_3$后是一个空集,空集虽然属于凸集,但无实际意义。

接着观察上述四个图片,三个一维直线相交为一个点,二位则是交出线,三维面,四维长方体,它们全部都属于凸集。

若$$W \in \Bbb R^n,b\in \Bbb R,S=\{x|W^Tx+b\le 0\} $$

那么$S$是半空间,半空间一定是凸集。且与仿射集一样,半空间的交集也一定是凸集。

凹函数与凸函数

其中,不管是凹函数、凸函数还是凹凸函数,都属于凸集。

凸优化问题

定义于凸集中的凸函数最小化的问题。即目标函数为凸函数,可行域为凸集的优化问题。凸优化问题的局部最优解就是全局最优解。

拉格朗日对偶问题一定是凸优化问题

已知原始问题为:

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

其拉格朗日对偶问题为:

$$\theta_D(\alpha,\beta)=\min_xL(x,\alpha,\beta)$$

即$\theta_D(\alpha,\beta)$是把拉格朗日乘子$\alpha,\beta$作为自变量,找到因变量$x$的最小值,用$x^*$表示,此时有$$g(\alpha,\beta)=f(x^*)+\sum\alpha_i c_i(x^*)+\sum\beta_j h_j(x^*)\tag{15}$$

由$(15)$式可知,此时$f(x^*),\alpha,\beta$均为常数,故$g(\alpha,\beta)$表示一个平面,在对应对偶函数的求最大值,知对偶函数$\theta_D$是一个凹函数,因此对偶问题一定是一个凸优化问题。

原问题解大于等于对偶问题解

原问题为$$\min_x\max_{\alpha,\beta:\alpha\ge 0}L(x,\alpha,\beta)$$

对偶问题为$$\max_{\alpha,\beta:\alpha\ge 0}\min_xL(x,\alpha,\beta)$$

则$$d^*=\min_x\max_{\alpha,\beta:\alpha\ge 0}L(x,\alpha,\beta)\le \max_{\alpha,\beta:\alpha\ge 0}\min_xL(x,\alpha,\beta)=p^*$$

证明

由$(12)$和$(5)$式,对任意$\alpha,\beta$和$x$,有$$\theta_D(\alpha,\beta)=\min_xL(x,\alpha,\beta)\le L(x,\alpha,\beta)\le \max_{\alpha,\beta:\alpha_i\ge 0}L(x,\alpha,\beta)=\theta_P(x)$$

即$$\theta_D(\alpha,\beta)\le \theta_P(x)$$

由于原始问题和对偶问题均有最优值,所以$$\max_{\alpha,\beta:\alpha_i\ge 0}\theta_D(\alpha,\beta)\le \min_x\theta_P(x)$$

即$$d^*=\min_x\max_{\alpha,\beta:\alpha\ge 0}L(x,\alpha,\beta)\le \max_{\alpha,\beta:\alpha\ge 0}\min_xL(x,\alpha,\beta)=p^*$$

强对偶问题$p^*=d^*$

符合强对偶关系的原问题和对偶问题是等价的,即$p^*=d^*$,一般条件下(大多数日常接触到的问题),只要问题可行域为凸集,则该问题就是强对偶关系。

Slater条件

KKT条件