7.15最优化

约束优化一阶最优性条件

优化模型

$$\begin{array}{rl}& \min f\left(x\right)\\ & \\ & s.t.g_i\left(x\right)\ge 0,i=1,2,\cdots ,m\\ & h_j\left(x\right)=0\\ & x\in R^n\end{array}$$

可行域 (集): $S=\{x\in R^n\left|\begin{array}{ll}{g}_i\left(x\right)\ge 0,& i=1,2,\cdots ,m\\ h_j\left(x\right)=0,& j=1,2,\cdots ,l\end{array}\right\}$

不等式约束的KKT条件

• 下降方向与可行方向:
  可行方向锥: $D=\{d\mid d\ne 0,\exists \delta >0,\forall \lambda \in \left(0,\delta \right)$ ,有 $\overline{\mathbf{x}}+\lambda \mathbf{d}\in S\}$
  下降方向锥: $F_0=\left\{d|\nabla f{\left(\bar{x}\right)}^{T}d<0\right\}$
• 几何最优性条件:
  局部最优解处不存在可行且下降的方向
  设考虑约束优化问题 $\underset{x\in S}{\min }f\left(x\right)$ ,其中 $S\subset {\mathbb{R}}^n$ 为非空集合, $\bar{x}\in S$ . $f$ 在 $\overline{\mathbf{x}}$ 处可微. 若 $\overline{\mathbf{x}}$ 是该问题的一个局部最优解,则 $D\cap F_0=\varnothing$ .

---

Proof.
反证法. 假设存在 $d\in F_0\cap D$ ,则 $d\in F_0,d\in D$ .
$\because d\in F_0,\therefore \exists {\delta }_1>0$ ,对 $\forall \lambda \in \left(0,{\delta }_1\right)$ ,有 $f\left(\bar{x}+\lambda d\right)<f\left(\bar{x}\right)$ ;
$\because d\in D,\therefore \exists {\delta }_2>0$ ,对 $\forall \lambda \in \left(0,{\delta }_2\right)$ ,有 $\bar{x}+\lambda d\in S$ .
取 $\delta =\min \left({\delta }_1,{\delta }_2\right)$ ,则当 $\lambda \in \left(0,\delta \right)$ ,有 $\bar{x}+\lambda d\in S$ 且 $f\left(\bar{x}+\lambda d\right)<f\left(\bar{x}\right)$ , 与 $\bar{x}$ 为局部最优解矛盾.

---

• 几何最优性条件的化简:
  用局部约束方向锥描述可行方向锥
  $\bar{x}\in S$ ,记 $I\text{:=}\left\{i|g_i\left(\bar{x}\right)=0\right\},G_0=\left\{d|\nabla g_i{\left(\bar{x}\right)}^{T}d>0,i\in I\right\}$ 称 $G_0$ 为 $S$ 在点 $\bar{x}$ 处的局部约束方向锥 (或内方向锥).
  其中 $I$ 称为积极约束指标集.
  于是以上几何约束条件可简化为: 设 $\bar{x}\in S,f\left(x\right)$ 和 $g_i\left(x\right)\left(i\in I\right)$ 在 $\bar{x}$ 处可微, $g_i\left(x\right)\left(i\notin I\right)$ 在 $\bar{x}$ 处连续,如果 $\bar{x}$ 是局部最优解,则 $F_0\cap G_0=\varnothing$ .
• FJ条件
  将交集为空视为不等式联立无解
  设 $\bar{x}\in S,I=\left\{i\mid g_i\left(\bar{x}\right)=0\right\},f\left(x\right),g_i\left(x\right)\left(i\in I\right)$ 在 $\bar{x}$ 处可微, $g_i\left(x\right)\left(i\notin I\right)$ 在 $\bar{x}$ 处连续,若 $\bar{x}$ 是局部最优解,则存在不全为零的数 $w_0,w_i\left(i\in I\right)$ ,使得

$$\{\begin{array}{l}{w}_0\nabla f\left(\bar{x}\right)-\sum _{i\in I}{w}_i\nabla g_i\left(\bar{x}\right)=0\\ w_0,w_i\ge 0,i\in I.\end{array}$$

也可写作:

$$\{\begin{array}{l}{w}_0\nabla f\left(\bar{x}\right)-\sum _{i=1}^m{w}_i\nabla g_i\left(\bar{x}\right)=0\\ w_i{g}_i\left(\overline{x}\right)=0,i=1,2,\cdots ,m\\ w_0,w_i\ge 0,i=1,2,\cdots ,m\end{array}$$

---

Proof. 由几何最优性条件和Gordan定理直接可得.
Gordan定理: 设 $A$ 为 $m\times n$ 矩阵,那么 $Ax<0$ 有解的充要条件是不存在非零向量 $y\ge 0$ ,使得 $A^{T}y=0$ .

---

• KKT条件 通过线性无关保证目标函数信息得到反映
  考虑问题 $\{\begin{array}{l}\min f\left(x\right)\\ \text{ s.t. }{g}_i\left(x\right)\ge 0,i=1,\cdots ,m\end{array}$ 设 $\bar{x}\in S,f,g_i\left(i\in I\right)$ 在 $\bar{x}$ 处可微, $g_i\left(i\notin I\right)$ 在 $\bar{x}$ 连续, $\left\{\nabla g_i\left(\bar{x}\right)\mid i\in I\right\}$ 线性无关,若 $\bar{x}$ 是局部最优解,则存在非负数 $w_i,i\in I$ ,使得

$$\nabla f\left(\bar{x}\right)-\sum _{i\in I}{w}_i\nabla g_i\left(\bar{x}\right)=0.$$

其中$\left\{\nabla g_i\left(\bar{x}\right)\mid i\in I\right\}$ 线性无关称为约束规格 (Constraint Qualification)
也可写作:

$$\{\begin{array}{l}\nabla f\left(\bar{x}\right)-\sum _{\mathrm{i}=1}^m{w}_i\nabla g_i\left(\bar{x}\right)=0\\ w_i{g}_i\left(\bar{x}\right)=0i=1,2,\cdots ,m\\ w_i\ge 0i=1,2,\cdots ,m.\end{array}$$

---

Proof.
由FJ条件存在不全为零的非负数 $w_0,w_i^{\prime },i\in I$ ,使得

$$w_0\nabla f\left(\bar{x}\right)-\sum _{i\in I}{w}_i^{\prime }\nabla g_i\left(\bar{x}\right)=0.$$

显然 $w_0\ne 0$ ,否则 $\nabla g_i\left(\bar{x}\right)\left(i\in I\right)$ 线性相关,矛盾。 于是,令 $w_i=\frac{w_i^{\prime }}{w_0}\ge 0\left(i\in I\right)$ ,得

$$\nabla f\left(\bar{x}\right)-\sum _{i\in I}{w}_i\nabla g_i\left(\bar{x}\right)=0.$$

等式约束的最优性条件

曲面与曲线: 称点集 $C=\left\{x=x\left(t\right)\mid t_0\le t\le t_1\right\}$ 为曲面 $S=\{x\mid h\left(x\right)=0\}$上的一条曲线,如果对所有 $t\in \left[t_0,t_1\right]$ 均有 $h\left(x\left(t\right)\right)=0$ .如果导数 $x^{\prime }\left(t\right)=\frac{\mathrm{d}x\left(t\right)}{\mathrm{d}t}$ 存在,则称曲线是可微的. 此时的一阶导数 $x^{\prime }\left(t\right)$ 是曲线在点 $x\left(t\right)$ 处的切向量.
切平面: 曲面 $S$ 上在点 $x$ 处所有可微曲线的切向量组成的集合称为曲面 $S$ 在点 $x$ 的切平面,记为 $T\left(x\right)$ .
子空间: $H\left(x\right)\text{:=}\left\{d\mid \nabla h{\left(x\right)}^{T}d=0\right\}$ 其中 $\nabla h\left(x\right)=\left(\nabla h_1\left(x\right),\cdots ,\nabla h_l\left(x\right)\right)$
$\text{性质}$ :

1. 设 $\bar{x}$ 是约束集合 $S=\left\{x\in R^n\mid h\left(x\right)=0\right\}$ 上的点, $T\left(\bar{x}\right)$ 为 $S$ 在 $\bar{x}$ 处的切平面, $H\left(\bar{x}\right)$ 为相应的线性化可行方向集,则有$T\left(\bar{x}\right)\subseteq H\left(\bar{x}\right)$ ,即若向量 $d\in T\left(\bar{x}\right)$ ,则有 $\nabla h{\left(\bar{x}\right)}^{T}d=0$ .
2. 设 $\bar{x}\in S=\{x\mid h\left(x\right)=0\}$ 且 $\left\{\nabla h_1\left(\bar{x}\right),\cdots ,\nabla h_l\left(\bar{x}\right)\right\}$ 线性无关,则 $T\left(\bar{x}\right)=H\left(\bar{x}\right)$ .

---

Proof.
设 $d\in H\left(\bar{x}\right)$ ,考虑非线性方程组 $h\left(\bar{x}+td+\nabla h\left(\bar{x}\right)y\right)=0$ 其中 $t\in R^1,y\in R^l$ . 该方程组有解 $\left(y,t\right)=\left(0,0\right)$ .在 $t=0$ 处, $h$ 关于 $y$ 的Jacobi矩阵为 $\nabla h{\left(\bar{x}\right)}^T\nabla h\left(\bar{x}\right)$ 由隐函数定理,在 $t=0$ 的邻域,存在连续可微函数 $y=y\left(t\right)\left(y\left(0\right)=0\right)$ ,使 $h\left(\bar{x}+td+\nabla h\left(\bar{x}\right)y\left(t\right)\right)=0$ 成立. 令 $x\left(t\right)=\bar{x}+td+\nabla h\left(\bar{x}\right)y\left(t\right)$ ,则 $x\left(t\right)$ 为曲面 $S$ 上过 $x\left(0\right)$ 的一条曲线。在点 $x\left(0\right)=\bar{x}$ ,切向量为 $x^{\prime }\left(0\right)=d+\nabla h\left(\bar{x}\right)y^{\prime }\left(0\right)$ 又 $\nabla h{\left(\overline{x}\right)}^{T}d+\nabla h{\left(\overline{x}\right)}^T\nabla h\left(\overline{x}\right)y^{\prime }\left(0\right)=0$ 而 $d\in H\left(\bar{x}\right)\Rightarrow \nabla h{\left(\bar{x}\right)}^{T}d=0$ ,又 $\because \left\{\nabla h_1\left(\bar{x}\right),\cdots ,\nabla h_l\left(\bar{x}\right)\right\}$ 线性无关 $\therefore \nabla h{\left(\bar{x}\right)}^T\nabla h\left(\bar{x}\right)$ 可逆, $\Rightarrow y^{\prime }\left(0\right)=0\Rightarrow x^{\prime }\left(0\right)=d\Rightarrow d\in T\left(\bar{x}\right)$ .

---

• 几何最优性条件
  设 $\bar{x}\in S,f\left(x\right)$ 和 $g_i\left(x\right)\left(i\in I\right)$ 在 $\bar{x}$ 处可微, $g_i\left(x\right)\left(i\notin I\right)$ 在 $\bar{x}$ 处连续, $h_j\left(j=1,2,\cdots ,l\right)$ 在 $\bar{x}$ 处连续可微,且 $\left\{\nabla h_1\left(\bar{x}\right),\cdots ,\nabla h_l\left(\bar{x}\right)\right\}$ 线性无关。如果 $\bar{x}$ 是问题 $\left(NP\right)$ 的局部最优解,则在 $\bar{x}$ 处,有

$$F_0\cap G_0\cap H_0=\varnothing ,$$

其中

$$\begin{array}{rl}{F}_0& =\left\{d\mid \nabla f{\left(\bar{x}\right)}^{T}d<0\right\}\\ G_0& =\left\{d\mid \nabla g_i{\left(\bar{x}\right)}^{T}d>0,i\in I\right\}\\ H_0& =\left\{d\mid \nabla h_j{\left(\bar{x}\right)}^{T}d=0,j=1,2,\cdots ,l\right\}.\end{array}$$

• KKT条件
  考虑问题 $\{\begin{array}{l}\min f\left(x\right)\\ \text{ s.t. }{g}_i\left(x\right)\ge 0,i=1,\cdots ,m\\ h_j\left(x\right)=0,j=1,\cdots ,l\end{array}$

设 $\bar{x}$ 为可行点, $I=\left\{i\mid g_i\left(\bar{x}\right)=0\right\}$ . $f,g_i\left(i\in I\right)$ 在 $\bar{x}$ 处可微, $g_i\left(i\notin I\right)$ 在 $\bar{x}$ 连续, $h_j\left(j=1,\cdots ,l\right)$ 在 $\bar{x}$ 连续可微,向量集$\left\{\nabla g_i\left(\bar{x}\right),\nabla h_j\left(\bar{x}\right)\mid i\in I,j=1,\cdots ,l\right\}$ 线性无关（即LICQ成立）,若 $\bar{x}$ 是局部最优解,则存在数 $w_i,i\in I$ 和 $v_j\left(j=1,\cdots ,l\right)$ ,使得

$$\begin{array}{rl}\nabla f\left(\bar{x}\right)-\sum _{i\in I}{w}_i& \nabla g_i\left(\bar{x}\right)-\sum _{j=1}^l{v}_j\nabla h_j\left(\bar{x}\right)=0.\\ & w_i\ge 0\left(i\in I\right).\end{array}$$

• 拉格朗日函数
  Lagrange函数定义为

$$\begin{array}{rl}L\left(x,w,v\right)& =f\left(x\right)-\sum _{i=1}^m{w}_i{g}_i\left(x\right)-\sum _{j=1}^l{v}_j{h}_j\left(x\right)\\ & =f\left(x\right)-w^{T}g\left(x\right)-v^{T}h\left(x\right)\end{array}$$

其中 $w={\left(w_1,w_2,\cdots ,w_m\right)}^T\in R_{+}^m,v={\left(v_1,v_2,\cdots ,v_l\right)}^T\in R^l$ 称为Lagrange乘子.
于是, KKT条件可以改写为:

$$\{\begin{array}{ll}{\nabla }_{x}L\left(x,w,v\right)& =0\\ w_i{g}_i\left(x\right)& =0,i=1,2,\cdots ,m\\ g_i\left(x\right)& \ge 0,i=1,2,\cdots ,m\\ h_j\left(x\right)& =0,j=1,2,\cdots ,l\\ w_i& \ge 0,i=1,2,\cdots ,m\end{array}$$

凸优化问题中的KKT条件

凸优化模型

$$\begin{array}{rl}& \min f\left(x\right)\\ & s.t.x\in \Omega \text{:=}\{x\in R^n\left|\begin{array}{l}{g}_i\left(x\right)\ge 0,i=1,\cdots ,m\\ h_j\left(x\right)=0,j=1,\cdots ,l\end{array}\right\}\end{array}$$

若 $f\left(x\right)$ 是凸函数, $g_i\left(x\right)\left(i=1,\cdots ,m\right)$ 是凹函数, $h_i\left(x\right)\left(j=1,\cdots ,l\right)$ 是线性函数,则原问题为凸规划.

性质

• 凸优化的任一局部最优解为全局最优解

---

Proof.
设 $x^{\ast }$ 为凸优化局部最优解,则存在 $\delta >0$ ,对任意 $x\in N\left(x^{\ast },\delta \right)\cap \Omega$ 都有 $f\left(x^{\ast }\right)\le f\left(x\right)$ .
反证法. 假设 $x^{\ast }$ 不是全局最优解,则存在 $\bar{x}\in \Omega$ ,使得 $f\left(\bar{x}\right)<f\left(x^{\ast }\right)$ 考虑线段 $\left[\bar{x},x^{\ast }\right]$ 上一点 $y\text{:=}\lambda \bar{x}+\left(1-\lambda \right)x^{\ast },\lambda \in \left(0,1\right)$ ,由凸函数定义: $f\left(y\right)\le \lambda f\left(\bar{x}\right)+\left(1-\lambda \right)f\left(x^{\ast }\right)<\lambda f\left(x^{\ast }\right)+\left(1-\lambda \right)f\left(x^{\ast }\right)=f\left(x^{\ast }\right)$ 当 $\lambda$ 充分小时, $y\in N\left(x^{\ast },\delta \right)\cap \Omega$ 且 $f\left(y\right)<f\left(x^{\ast }\right)$ , 这与 $x^{\ast }$ 为局部最优解矛盾. 证毕

---

• 于是, 凸优化的最优解集为凸集
• 由严格凸的定义知, 严格凸函数若最优解存在则唯一
• 凸优化的全局最优解与稳定点等价

---

Def.
称 $x^{\ast }$ 为约束优化问题 $\min \{f\left(x\right):x\in \Omega \}$ 的稳定点,若满足 $⟨\nabla f\left(x^{\ast }\right),x-x^{\ast }⟩\ge 0,\forall x\in \Omega$ .
Proof.
$\Leftarrow$ 若 $x^{\ast }$ 为稳定点,即对任意 $x\in \Omega ,⟨\nabla f\left(x^{\ast }\right),x-x^{\ast }⟩\ge 0$ .利用凸函数的性质得

$$f\left(x\right)\ge f\left(x^{\ast }\right)+⟨\nabla f\left(x^{\ast }\right),x-x^{\ast }⟩\ge f\left(x^{\ast }\right)$$

因而 $x^{\ast }$ 为全局最优解.
$\Rightarrow$ 设 $x^{\ast }$ 为凸优化问题的全局最优解，由一阶最优性条件可知，在 $x^{\ast }$ 处不存在可行且使得目标函数下降的方向。注意到,由 $\Omega$ 的凸性可知 $\forall x\in \Omega ,\forall \lambda \in \left(0,1\right)$ ,

$$x^{\ast }+\lambda \left(x-x^{\ast }\right)=\lambda x+\left(1-\lambda \right)x^{\ast }\in \Omega$$

因此, $x-x^{\ast }$ 是 $x^{\ast }$ 处的可行方向. 从而 $⟨\nabla f\left(x^{\ast }\right),x-x^{\ast }⟩\ge 0,\forall x\in \Omega$ ,即 $x^{\ast }$ 为稳定点. 证毕 (注: 该性质对任意解集为非空闭凸集的优化模型均成立)

---

• 若( $x^{\ast }$ , ${\lambda }^{\ast }$ , ${\mu }^{\ast }$ )是凸优化的KKT点对, 则( $x^{\ast }$ , ${\lambda }^{\ast }$ , ${\mu }^{\ast }$ )为Lagrange函数的鞍点; 若( $x^{\ast }$ , ${\lambda }^{\ast }$ , ${\mu }^{\ast }$ )是优化问题Lagrange函数的鞍点,则( $x^{\ast }$ , ${\lambda }^{\ast }$ , ${\mu }^{\ast }$ )为KKT点对

---

Def.
称 $\left(x^{\ast },{\lambda }^{\ast },{\mu }^{\ast }\right)\in {\mathbb{R}}^n\times {\mathbb{R}}^{|\mathcal{E}|}\times {\mathbb{R}}_{+}^{|I|}$ 为约束优化问题

$$\underset{x}{\min }\left\{f\left(x\right):h_i\left(x\right)=0,i\in \mathcal{E};g_i\left(x\right)\ge 0,i\in I\right\}$$

的Lagrange函数 $L\left(x,\lambda ,\mu \right)$ 的鞍点,若 $\forall \left(x,\lambda ,\mu \right)\in {\mathbb{R}}^n\times {\mathbb{R}}^{|\mathcal{E}|}\times {\mathbb{R}}_{+}^{|I|}$ 有

$$L\left(x^{\ast },\lambda ,\mu \right)\le L\left(x^{\ast },{\lambda }^{\ast },{\mu }^{\ast }\right)\le L\left(x,{\lambda }^{\ast },{\mu }^{\ast }\right).$$

Proof.
结论1: 先证 $x^{\ast }\in \underset{x\in {\mathbb{R}}^n}{\mathrm{argmin}}L\left(x,{\lambda }^{\ast },{\mu }^{\ast }\right)$ 由 $L\left(x,{\lambda }^{\ast },{\mu }^{\ast }\right)=f\left(x\right)-\sum _{i\in \mathcal{E}}{\lambda }_i^{\ast }{h}_i\left(x\right)-\sum _{i\in I}{\mu }_i^{\ast }{g}_i\left(x\right)$ 关于 $x\in {\mathbb{R}}^n$ 为凸函数

$$L\left(x,{\lambda }^{\ast },{\mu }^{\ast }\right)\ge L\left(x^{\ast },{\lambda }^{\ast },{\mu }^{\ast }\right)+{\left(x-x^{\ast }\right)}^T{V}_{x}L\left(x^{\ast },{\lambda }^{\ast },{\mu }^{\ast }\right)=L\left(x^{\ast },{\lambda }^{\ast },{\mu }^{\ast }\right)$$

再证 $({\lambda }^{\ast },{\mu }^{\ast })\in \underset{\lambda \in {\mathbb{R}}^{|\epsilon |},\mu \in {\mathbb{R}}_{+}^{|I|}}{\mathrm{argmin}}L(x^{\ast },\lambda ,\mu )$ .

$$\begin{array}{rl}& L\left(x^{\ast },\lambda ,\mu \right)-L\left(x^{\ast },{\lambda }^{\ast },{\mu }^{\ast }\right)\\ & =-\sum _{i\in \epsilon }{\lambda }_i{h}_i\left(x^{\ast }\right)-\sum _{i\in I}{\mu }_i{g}_i\left(x^{\ast }\right)+\sum _{i\in \epsilon }{\lambda }_i^{\ast }{h}_i\left(x^{\ast }\right)+\sum _{i\in I}{\mu }_i^{\ast }{g}_i\left(x^{\ast }\right)\\ & =-\sum {\mu }_i{g}_i\left(x^{\ast }\right)\le 0\text{ 对任意 }\lambda \in {\mathbb{R}}^{|\mathcal{E}|},\mu \in {\mathbb{R}}_{+}^{|I|}\end{array}$$

结论2: 由 $x^{\ast }\in \underset{x\in {\mathbb{R}}^n}{\mathrm{argmin}}L\left(x,{\lambda }^{\ast },{\mu }^{\ast }\right)\Rightarrow {\nabla }_{x}L\left(x^{\ast },{\lambda }^{\ast },{\mu }^{\ast }\right)=0$ 由

$$\left({\lambda }^{\ast },{\mu }^{\ast }\right)\in \underset{\lambda \in {\mathbb{R}}^{|\mathcal{E}|},\mu \in {\mathbb{R}}_{+}^{|I|}}{\mathrm{argmax}}L\left(x^{\ast },\lambda ,\mu \right)=f\left(x^{\ast }\right)-\sum _{i\in \mathcal{E}}{\lambda }_i{h}_i\left(x^{\ast }\right)-\sum _{i\in I}{\mu }_i{g}_i\left(x^{\ast }\right)$$

知: $h_i\left(x^{\ast }\right)=0,i\in \mathcal{E};g_i\left(x^{\ast }\right)\ge 0,{\mu }_i^{\ast }\ge 0,{\mu }_i^{\ast }{g}_i\left(x^{\ast }\right)=0,i\in I,$ 因此, $\left(x^{\ast },{\lambda }^{\ast },{\mu }^{\ast }\right)$ 为KKT点对 (注意：该定理无需问题为凸优化)

对偶问题与对偶理论

原问题与对偶问题

原始优化问题

$$\begin{array}{rl}& \min f\left(x\right)\\ & \text{s.t.}{g}_i\left(x\right)\ge 0,i=1,\cdots ,m\\ & h_j\left(x\right)=0,j=1,\cdots ,l\\ & x\in D\end{array}$$

Lagrange对偶问题

$$\begin{array}{rl}& \max \theta \left(w,v\right)\\ & \text{s.t.}w\ge 0\end{array}$$

其中

$$\begin{array}{rl}\theta \left(w,v\right)& =\inf \left\{f\left(x\right)-\sum _{i=1}^m{w}_i{g}_i\left(x\right)-\sum _{j=1}^l{v}_j{h}_j\left(x\right)|x\in D\right\}\\ & =inf\{L(x;w,v)|x\in D\}\end{array}$$

对偶问题一定为凸规划

弱对偶定理

设 $x$ 和 $\left(w,v\right)$ 分别是原问题和对偶问题的可行解,则$f\left(x\right)\ge \theta \left(w,v\right)$

---

Proof.
$\because x$ 和 $\left(w,v\right)$ 是可行解,
$\therefore g\left(x\right)\ge 0,h\left(x\right)=0,w\ge 0$
$\begin{array}{rl}\therefore \theta \left(w,v\right)& =\underset{x^{\prime }}{\inf }\left\{f\left(x^{\prime }\right)-w^{T}g\left(x^{\prime }\right)-v^{T}h\left(x^{\prime }\right)\mid x^{\prime }\in D\right\}\\ & \le f\left(x\right)-w^{T}g\left(x\right)-v^{T}h\left(x\right)\\ & \le f(x)\end{array}$

---

强对偶定理

• 对偶间隙: $\delta =\underset{x\in D}{\inf }\underset{w\ge 0}{\sup }L(x;w,v)-\underset{w\ge 0}{\sup }\underset{x\in D}{\inf }L(x;w,v)$
• 设 $\left(x^{\ast },w^{\ast },v^{\ast }\right)$ 为优化问题(P)的Lagrange函数的鞍点,则 $x^{\ast }$与 $\left(w^{\ast },v^{\ast }\right)$ 分别是原问题与对偶问题的最优解且对偶间隙为零.

---

Proof.
由 $\left({\mathbf{w}}^{\ast },{\mathbf{v}}^{\ast }\right)\in \underset{w\in {\mathbb{R}}_{+}^{|I|},v\in {\mathbb{R}}^{|\epsilon |}}{\mathrm{argmax}}L\left(x^{\ast },\mathbf{w},\mathbf{v}\right)$ 可得: $h_i\left(x^{\ast }\right)=0,i\in \mathcal{E};$ $\begin{array}{c}{w}_i^{\ast }\ge 0,g_i\left(x^{\ast }\right)\ge 0,w_i^{\ast }{g}_i\left(x^{\ast }\right)=0,i\in I\end{array}$ 再结合 $x^{\ast }\in \underset{x\in {\mathbb{R}}^n}{\mathrm{argmin}}L(x;w^{\ast },v^{\ast })$
于是对原问题的任一可行解 $x$ 有 $\begin{array}{c}f\left(x\right)\ge L\left(x,{\mathbf{w}}^{\ast },{\mathbf{v}}^{\ast }\right)\ge L\left(x^{\ast },{\mathbf{w}}^{\ast },{\mathbf{v}}^{\ast }\right)=f\left(x^{\ast }\right)\end{array}$
$x^{\ast }\in \underset{x\in {\mathbb{R}}^n}{\mathrm{argmin}}L\left(x,{\mathbf{w}}^{\ast },{\mathbf{v}}^{\ast }\right)\Rightarrow \theta \left(w^{\ast },v^{\ast }\right)=L\left(x^{\ast },{\mathbf{w}}^{\ast },{\mathbf{v}}^{\ast }\right)$ 已证 $L\left(x^{\ast },{\mathbf{w}}^{\ast },{\mathbf{v}}^{\ast }\right)$ 为原问题的最优值 $f\left(x^{\ast }\right)$ ,由弱对偶定理可知: 对对偶问题的任一可行解 $\left(w,v\right)$ ,有 $\theta \left(w,v\right)\le L\left(x^{\ast },w^{\ast },v^{\ast }\right)=\theta \left(w^{\ast },v^{\ast }\right)$ 则对偶问题的最优解为 $\left(w^{\ast },v^{\ast }\right)$ ,且 $f\left(x^{\ast }\right)=\theta \left(w^{\ast },v^{\ast }\right)$ .

---