一般的约束优化问题
约束优化问题常常可以化简为以下不等式,
\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 \\
对偶问题的解小于原问题,有两种情况:
- 强对偶,能取等于号
- 弱对偶,不能取等于号
几何解释
特别的,二次规划问题都满足 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{ 表示相对内部(不包含边界的内部)。}\\
- 对于大多数凸优化问题,Slater 条件成立。
- 对于不满足条件的,可以松弛 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 条件对最优解的条件为:
- 可行域:
\begin{aligned} m_i(x^*)\le0\\ n_j(x^*)=0\\ \lambda^*\ge0 \end{aligned}
- 互补松弛
\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条件,对于第二个不等于号需要满足互补松弛条件。
- 梯度为0:
\frac{\partial L(x,\lambda^*,\eta^*)}{\partial x}|_{x=x^*}=0