一般的约束优化问题

约束优化问题常常可以化简为以下不等式，

\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 \\

对偶问题的解小于原问题，有两种情况：

1. 强对偶，能取等于号
2. 弱对偶，不能取等于号

几何解释

特别的，二次规划问题都满足 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{ 表示相对内部（不包含边界的内部）。}\\

1. 对于大多数凸优化问题，Slater 条件成立。
2. 对于不满足条件的，可以松弛 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 条件对最优解的条件为：

1. 可行域：

   \begin{aligned}
   m_i(x^*)\le0\\
   n_j(x^*)=0\\
   \lambda^*\ge0
   \end{aligned}

2. 互补松弛 \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条件，对于第二个不等于号需要满足互补松弛条件。

3. 梯度为0： \frac{\partial L(x,\lambda^*,\eta^*)}{\partial x}|_{x=x^*}=0