补充，鞍点与强对偶

1. 原问题和对偶问题

• 用原问题(Primal Problem)中的P表示原问题，具体如下：
  $$\begin{array}{c}\begin{array}{rl}& (P)\min f(x)\\ & st.g_i(x)\le 0,i=1,\cdots ,m,\\ & h_i(x)=0,i=1,\cdots ,l,\\ & x\in X\end{array}\end{array}$$
• 用对偶问题(duality Problem)中的D表示对偶问题，具体如下：
  $$\begin{array}{c}\begin{array}{rl}& (D)\underset{\lambda \ge 0,\mu }{\max }\underset{x\in X}{\min }\mathrm{L}(x,\lambda ,\mu )\\ & \mathrm{L}(x,\lambda ,\mu )=f(x)+\sum _{i=1}^m{\lambda }_i{g}_i(x)+\sum _{i=1}^l{\mu }_i{h}_i(x),x\in X\end{array}\end{array}$$
• 原问题的拉格朗日函数形式：
  $$\begin{array}{c}\begin{array}{rl}& (P)\underset{x\in X}{\min }\underset{\lambda \ge 0,\mu }{\max }\mathrm{L}(x,\lambda ,\mu )\\ & \mathrm{L}(x,\lambda ,\mu )=f(x)+\sum _{i=1}^m{\lambda }_i{g}_i(x)+\sum _{i=1}^l{\mu }_i{h}_i(x),x\in X\end{array}\end{array}$$

2. Slater 条件

• 假设：
  1） 集合X为非空凸集，$f(x)$及$g_i(x),i=1,2,\cdots ,m$是凸函数，$h_i(x),i=1,2,\cdots ,l$均为线性函数。
  2） 假设存在 $\hat{x}\in X$使得$g_i(\hat{x})<0,i=1,\cdots ,m,h_i(\hat{x})=0,i=1,\cdots ,l$,且
  $0\in \mathrm{int}h(X)$,其中$h(X)=\{[h_1(x),h_2(x),\cdots ,h_l(x){]}^T|x\in X\}$,则强对偶成立，即：
  min ⁡ { f ( x ) ∣ x ∈ S } = max ⁡ { d ( λ , μ ) ∣ λ ≥ 0 , μ } \begin{equation} \min \{f(x)|x\in S\}=\max \{d(\lambda,\mu)\big|\lambda \ge 0,\mu\} \end{equation} min{f(x)∣x∈S}=max{d(λ,μ) ​λ≥0,μ}​​

3. xxx

• 假设原问题P有最优解 $\bar{x}$,其对偶问题D有最优解$(\bar{\lambda },\bar{\mu })$,满足强对偶关系，$v(P)=v(D)$，且可得：
  $$\begin{array}{c}{g}_i(\bar{x})\le 0,h_i(\bar{x})=0,\bar{x}\le X,\bar{\lambda }\ge 0,f(\bar{x})=d(\bar{\lambda },\bar{\mu })\end{array}$$
• 因为$f(\bar{x})$为原问题最小值，所以其他值必然大于此值：
  $$\begin{array}{c}v(P)=f(\bar{x})\le f(x)\end{array}$$
• 因为$d(\bar{\lambda },\bar{\mu })$为对偶函数的最大值，则其他值必然小于此值：
  $$\begin{array}{c}d(\lambda ,\mu )\le d(\bar{\lambda },\bar{\mu })\end{array}$$
• 因为$g_i(x)\le 0,{\lambda }_i>0,h_i(x)=0$可得：
  $$\begin{array}{c}d(\bar{\lambda },\bar{\mu })\le f(\bar{x})\end{array}$$
• 综上所述，弱对偶定理可得：
  $$\begin{array}{c}d(\lambda ,\mu )\le d(\bar{\lambda },\bar{\mu })=v(D)\le v(P)=f(\bar{x})\le f(x)\end{array}$$
• 转换为拉格朗日函数可得：
  $$\begin{array}{c}L(\bar{x},\lambda ,\mu )\le L(\bar{x},\bar{\lambda },\bar{\mu })\le L(x,\bar{\lambda },\bar{\mu })\end{array}$$
• 我们发现此时的点$(\bar{x},\bar{\lambda },\bar{\mu })$在左边函数是最大值，在右边函数里面时最小值，是不是就是我们图像里面的鞍点。