ADMM算法

算法迭代过程

1. 典型优化问题形式

x_{1}, x_{2} min f_{1} (x_{1}) + f_{2} (x_{2}) s . t . A_{1} x_{1} + A_{2} x_{2} = b (1)

2. 迭代过程

增广拉格朗日函数

L_{p} (x_{1}, x_{2}, y) = f_{1} (x_{1}) + f_{2} (x_{2}) + y^{T} (A_{1} x_{1} + A_{2} x_{2} - b) + \frac{ρ}{2} ∥ A_{1} x_{1} + A_{2} x_{2} - b ∥_{2}^{2} . (2)

ADMM迭代

x_{1}^{k + 1} = ar g x_{1} min L_{ρ} (x_{1}, x_{2}^{k}, y^{k}), (3) x_{2}^{k + 1} = ar g x_{2} min L_{ρ} (x_{1}^{k + 1}, x_{2}, y^{k}), (4) y^{k + 1} = y^{k} + τ ρ (A_{1} x_{1}^{k + 1} + A_{2} x_{2}^{k + 1} - b) . (5)

其中 $τ$ 为步长, 通常取 $(0, \frac{1 + 5}{2})$

3. 收敛准则

全局最优性条件:

0 \in \partial_{x_{1}} L (x_{1}^{*}, x_{2}^{*}, y^{*}) 0 \in \partial_{x_{2}} L (x_{1}^{*}, x_{2}^{*}, y^{*}) A_{1} x_{1}^{*} + A_{2} x_{2}^{*} = \partial f_{1} (x_{1}^{*}) + A_{1}^{T} y^{*}, (6 a) = \partial f_{2} (x_{2}^{*}) + A_{2}^{T} y^{*}, (6 b) = b (6 c)

单步迭代最优性条件:
由 $x_{2}$ 的更新:

x_{2}^{k} = ar g x min {f_{2} (x) + \frac{ρ}{2} A_{1} x_{1}^{k} + A_{2} x - b + \frac{y ^{k - 1}}{ρ}^{2}}, \Rightarrow 0 \in \partial f_{2} (x_{2}^{k}) + A_{2}^{T} [y^{k - 1} + ρ (A_{1} x_{1}^{k} + A_{2} x_{2}^{k} - b)]

由 $x_{1}$ 的更新:

x_{1}^{k} = ar g x min {f_{1} (x) + \frac{ρ}{2} A_{1} x + A_{2} x_{2}^{k - 1} - b + \frac{y ^{k - 1}}{ρ}^{2}}, \Rightarrow 0 \in \partial f_{1} (x_{1}^{k}) + A_{1}^{T} [ρ (A_{1} x_{1}^{k} + A_{2} x_{2}^{k - 1} - b) + y^{k - 1}] .

算法收敛理论

基本假设

$f_{1}, f_{2}$ 适当闭凸函数,ADMM 子问题 $(3), (4)$ 有唯一解;
原问题 $(1)$ 最优解集非空, 且Slater条件成立, 即: $\exists (x_{1}, x_{2}) \in int (dom f_{1} \times dom f_{2}) 使得 A_{1} x_{1} + A_{2} x_{2} = b .$

收敛性

若基本假设成立且 $A_{1}, A_{2}$ 列满秩,取 $τ \in (0, \frac{1 + 5}{2})$ ,则ADMM 算法产生的迭代点列 ${(x_{1}^{k}, x_{2}^{k}, y^{k})}$ 收敛到原问题 $(1)$ 的一个KKT点对.
分析:

证明点列收敛: 即 $(x_{1}^{k} - x_{1}^{*}, x_{2}^{k} - x_{2}^{*}, y^{k} - y^{*}) \to 0$
证明原始可行性: 即 $A_{1} (x_{1}^{k} - x_{1}^{*}) + A_{2} (x_{2}^{k} - x_{2}^{*}) \to 0$
证明对偶可行性(KKT条件): 即 $\exists u^{k} \in \partial f_{1} (x_{1}^{k}), v^{k} \in \partial f_{2} (x_{2}^{k})$ 使得, $u^{k} \to - A_{1}^{T} y^{*}, v^{k} \to - A_{2}^{T} y^{*}$

Proof.

u^{k} v^{k} Ψ_{k} Φ_{k} (e_{1}^{k}, e_{2}^{k}, e_{y}^{k}) = def (x_{1}^{k}, x_{2}^{k}, y^{k}) - (x_{1}^{*}, x_{2}^{*}, y^{*}), = - A_{1}^{T} [y^{k} + (1 - τ) ρ (A_{1} e_{1}^{k} + A_{2} e_{2}^{k}) + ρ A_{2} (x_{2}^{k - 1} - x_{2}^{k})], = - A_{2}^{T} [y^{k} + (1 - τ) ρ (A_{1} e_{1}^{k} + A_{2} e_{2}^{k})], = \frac{1}{τ ρ} e_{y}^{k}^{2} + ρ A_{2} e_{2}^{k}^{2}, = Ψ_{k} + max (1 - τ, 1 - τ^{- 1}) ρ A_{1} e_{1}^{k} + A_{2} e_{2}^{k}^{2} .

其中 $(x_{1}^{*}, x_{2}^{*}, y^{*})$ 是一个KKT点对,即其满足:

0 \in \partial_{x_{1}} L (x_{1}^{*}, x_{2}^{*}, y^{*}) 0 \in \partial_{x_{2}} L (x_{1}^{*}, x_{2}^{*}, y^{*}) A_{1} x_{1}^{*} + A_{2} x_{2}^{*} = \partial f_{1} (x_{1}^{*}) + A_{1}^{T} y^{*}, (6 a) = \partial f_{2} (x_{2}^{*}) + A_{2}^{T} y^{*}, (6 b) = b (6 c)

先证明: 设 ${(x_{1}^{k}, x_{2}^{k}, y^{k})}$ 为ADMM产生一个迭代序列,则 $\forall k \geq 1$ 有 $u^{k} \in \partial f_{1} (x_{1}^{k}), v^{k} \in \partial f_{2} (x_{2}^{k})$ 和

Φ_{k} - Φ_{k + 1} \geq min (τ, 1 + τ - τ^{2}) ρ A_{2} (x_{2}^{k} - x_{2}^{k + 1})^{2} + min (1, 1 + τ^{- 1} - τ) ρ A_{1} e_{1}^{k + 1} + A_{2} e_{2}^{k + 1}^{2} . (9)

Proof.

先证 $u^{k + 1} \in \partial f_{1} (x_{1}^{k + 1})$ : 对 $x_{1}^{k + 1}$ ,由子问题(3)的最优性条件可知, $0 \in \partial f_{1} (x_{1}^{k + 1}) + A_{1}^{T} y^{k} + ρ A_{1}^{T} (A_{1} x_{1}^{k + 1} + A_{2} x_{2}^{k} - b) .$ 将 $y^{k} = y^{k + 1} - τ ρ (A_{1} x_{1}^{k + 1} + A_{2} x_{2}^{k + 1} - b)$ 代入前式得, $- A_{1}^{T} (y^{k + 1} + (1 - τ) ρ (A_{1} x_{1}^{k + 1} + A_{2} x_{2}^{k + 1} - b) + ρ A_{2} (x_{2}^{k} - x_{2}^{k + 1})) \in \partial f_{1} (x_{1}^{k + 1}) .$ 根据 $u^{k + 1}$ 的定义以及 $b = A_{1} x_{1}^{*} + A_{2} x_{2}^{*}$ 可知: $u^{k + 1} \in \partial f_{1} (x_{1}^{k + 1})$ .
再证 $v^{k + 1} \in \partial f_{2} (x_{2}^{k + 1})$ : 对 $x_{2}^{k + 1}$ ,由子问题 (4) 的最优性条件可知, $0 \in \partial f_{2} (x_{2}^{k + 1}) + A_{2}^{T} y^{k} + ρ A_{2}^{T} (A_{1} x_{1}^{k + 1} + A_{2} x_{2}^{k + 1} - b),$ 又由 $y^{k} = y^{k + 1} - τ ρ (A_{1} x_{1}^{k + 1} + A_{2} x_{2}^{k + 1} - b)$ 知 $- A_{2}^{T} (y^{k + 1} + (1 - τ) ρ (A_{1} x_{1}^{k + 1} + A_{2} x_{2}^{k + 1} - b)) \in \partial f_{2} (x_{2}^{k + 1}) .$ 根据 $v^{k + 1}$ 的定义以及 $b = A_{1} x_{1}^{*} + A_{2} x_{2}^{*}, v^{k + 1} \in \partial f_{2} (x_{2}^{k + 1})$ . 故第一个命题得证.
然后证明 ${Φ_{k}}$ 的下降性. 由第一个命题结论, 以及 $x^{*}$ 是KKT点有以下四式成立:

u^{k + 1} - A_{1}^{T} y^{*} v^{k + 1} - A_{2}^{T} y^{*} \in \partial f_{1} (x_{1}^{k + 1}) \in \partial f_{1} (x_{1}^{*}) \in \partial f_{2} (x_{2}^{k + 1}) \in \partial f_{2} (x_{2}^{*})

由于 $f_{1}, f_{2}$ 是凸函数, 于是他们的次微分算子具有单调性, 即若有 $u \in \partial f (x), v \in \partial f (x)$ 则有 $⟨ u - v, x - y ⟩ \geq 0$ 因此:

⟨ u^{k + 1} + A_{1}^{T} y^{*}, x_{1}^{k + 1} - x_{1}^{*} ⟩ \geq 0 ⟨ v^{k + 1} + A_{2}^{T} y^{*}, x_{2}^{k + 1} - x_{2}^{*} ⟩ \geq 0.

将 $u^{k + 1}, v^{k + 1}, e_{y}^{k + 1}$ 的定义代入,得到

⟨ A_{1}^{T} (- e_{y}^{k + 1} - (1 - τ) ρ (A_{1} e_{1}^{k + 1} + A_{2} e_{2}^{k + 1}) - ρ A_{2} (x_{2}^{k} - x_{2}^{k + 1})), e_{1}^{k + 1} ⟩ \geq 0, ⟨ A_{2}^{T} (- e_{y}^{k + 1} - (1 - τ) ρ (A_{1} e_{1}^{k + 1} + A_{2} e_{2}^{k + 1}), e_{2}^{k + 1}) ⟩ \geq 0.

再由等式 $⟨ A^{T} x, y ⟩ = ⟨ x, A y ⟩$ 知:

⟨ - e_{y}^{k + 1} - (1 - τ) ρ (A_{1} e_{1}^{k + 1} + A_{2} e_{2}^{k + 1}) - ρ A_{2} (x_{2}^{k} - x_{2}^{k + 1}), A_{1} e_{1}^{k + 1} ⟩ \geq 0, ⟨ - e_{y}^{k + 1} - (1 - τ) ρ (A_{1} e_{1}^{k + 1} + A_{2} e_{2}^{k + 1}), A_{2} e_{2}^{k + 1} ⟩ \geq 0.

上面两式相加得到:

⟨ e_{y}^{k + 1}, - (A_{1} e_{1}^{k + 1} + A_{2} e_{2}^{k + 1}) ⟩ - (1 - τ) ρ A_{1} e_{1}^{k + 1} + A_{2} e_{2}^{k + 1}^{2} + ρ ⟨ - A_{2} (x_{2}^{k} - x_{2}^{k + 1}), A_{1} e_{1}^{k + 1} ⟩ \geq 0

由 $y^{k + 1}$ 的定义知有恒等式:

A_{1} e_{1}^{k + 1} + A_{2} e_{2}^{k + 1} = A_{1} x_{1}^{k + 1} + A_{2} x_{2}^{k + 1} - b = (τ ρ)^{- 1} (y^{k + 1} - y^{k}) = (τ ρ)^{- 1} (e_{y}^{k + 1} - e_{y}^{k})

代入上不等式可得:

\frac{1}{τ ρ} ⟨ e_{y}^{k + 1}, e_{y}^{k} - e_{y}^{k + 1} ⟩ - (1 - τ) ρ A_{1} x_{1}^{k + 1} + A_{2} x_{2}^{k + 1} - b^{2} + ρ ⟨ A_{2} (x_{2}^{k + 1} - x_{2}^{k}), A_{1} x_{1}^{k + 1} + A_{2} x_{2}^{k + 1} - b ⟩ - ρ ⟨ A_{2} (x_{2}^{k + 1} - x_{2}^{k}), A_{2} e_{2}^{k + 1} ⟩ \geq 0. (7)

接下来, 估计 $ρ ⟨ A_{2} (x_{2}^{k + 1} - x_{2}^{k}), A_{1} x_{1}^{k + 1} + A_{2} x_{2}^{k + 1} - b ⟩ .$ 的上界. 引入新符号:

ν^{k + 1} M^{k + 1} := y^{k + 1} + (1 - τ) ρ (A_{1} x_{1}^{k + 1} + A_{2} x_{2}^{k + 1} - b), := (1 - τ) ρ ⟨ A_{2} (x_{2}^{k + 1} - x_{2}^{k}), A_{1} x_{1}^{k} + A_{2} x_{2}^{k} - b ⟩,

由 $v^{k}$ 的定义知: $- A_{2}^{T} ν^{k + 1} \in \partial f_{2} (x_{2}^{k + 1}), - A_{2}^{T} ν^{k} \in \partial f_{2} (x_{2}^{k})$ . 因 $f_{2}$ 凸,由其次微分算子的单调性知:

⟨ - A_{2}^{T} (ν^{k + 1} - ν^{k}), x_{2}^{k + 1} - x_{2}^{k} ⟩ \geq 0.

即:

⟨ ν^{k + 1} - ν^{k}, A_{2} (x_{2}^{k + 1} - x_{2}^{k}) ⟩ \leq 0.

从而有

ρ ⟨ A_{2} (x_{2}^{k + 1} - x_{2}^{k}), A_{1} x_{1}^{k + 1} + A_{2} x_{2}^{k + 1} - b ⟩ = (1 - τ) ρ ⟨ A_{2} (x_{2}^{k + 1} - x_{2}^{k}), A_{1} x_{1}^{k + 1} + A_{2} x_{2}^{k + 1} - b ⟩ + ⟨ A_{2} (x_{2}^{k + 1} - x_{2}^{k}), y^{k + 1} - y^{k} ⟩ = M^{k + 1} + ⟨ ν^{k + 1} - ν^{k}, A_{2} (x_{2}^{k + 1} - x_{2}^{k}) ⟩ \leq M^{k + 1} .

因此, 不等式 $(7)$ 可以放缩成:

\frac{1}{τ ρ} ⟨ e_{y}^{k + 1}, e_{y}^{k} - e_{y}^{k + 1} ⟩ - (1 - τ) ρ A_{1} x_{1}^{k + 1} + A_{2} x_{2}^{k + 1} - b^{2} + M^{k + 1} - ρ ⟨ A_{2} (x_{2}^{k + 1} - x_{2}^{k}), A_{2} e_{2}^{k + 1} ⟩ \geq 0.

利用恒等式 $⟨ a, b ⟩ = \frac{1}{2} (∥ a + b ∥^{2} - ∥ a ∥^{2} - ∥ b ∥^{2}),$ 可得:

2 ⟨ e_{y}^{k + 1}, e_{y}^{k} - e_{y}^{k + 1} ⟩ = e_{y}^{k}^{2} - e_{y}^{k + 1}^{2} - e_{y}^{k} - e_{y}^{k + 1}^{2} = e_{y}^{k}^{2} - e_{y}^{k + 1}^{2} - (τ ρ)^{2} A_{1} x_{1}^{k + 1} + A_{2} x_{2}^{k + 1} - b^{2} 2 ⟨ A_{2} (x_{2}^{k + 1} - x_{2}^{k}), A_{2} e_{2}^{k + 1} ⟩ = A_{2} (x_{2}^{k + 1} - x_{2}^{k})^{2} + A_{2} e_{2}^{k + 1}^{2} - A_{2} e_{2}^{k}^{2}

从而:

\frac{1}{τ ρ} (e_{y}^{k}^{2} - e_{y}^{k + 1}^{2}) - (2 - τ) ρ A_{1} x_{1}^{k + 1} + A_{2} x_{2}^{k + 1} - b^{2} + 2 M^{k + 1} - ρ A_{2} (x_{2}^{k + 1} - x_{2}^{k})^{2} - ρ A_{2} e_{2}^{k + 1}^{2} + ρ A_{2} e_{2}^{k}^{2} \geq 0. (8)

将目标不等式按照定义展开得:

\frac{1}{τ ρ} (∥ e_{y}^{k} - e_{y}^{k + 1} ∥) - (max (1 - τ, 1 - τ^{- 1}) + min (1, 1 + τ^{- 1} - τ)) ρ A_{1} x_{1}^{k + 1} + A_{2} x_{2}^{k + 1} - b^{2} - min (τ, 1 + τ - τ^{2}) ρ A_{2} (x_{2}^{k + 1} - x_{2}^{k})^{2} - ρ A_{2} e_{2}^{k + 1}^{2} + ρ A_{2} e_{2}^{k}^{2} + max (1 - τ, 1 - τ^{- 1}) ρ A_{1} x_{1}^{k} + A_{2} x_{2}^{k} - b^{2} \geq 0

除了 $M^{k + 1}$ 中的项,其余项均出现在 $(8)$ 中
下面分两种情形讨论:

$τ \in (0, 1]$ : 此时 $1 - τ \geq 0$ ,根据基本不等式

\frac{2}{( 1 - τ ) ρ} M^{k + 1} = 2 ⟨ A_{2} (x_{2}^{k + 1} - x_{2}^{k}), A_{1} x_{1}^{k} + A_{2} x_{2}^{k} - b ⟩ \leq A_{2} (x_{2}^{k + 1} - x_{2}^{k})^{2} + A_{1} x_{1}^{k} + A_{2} x_{2}^{k} - b^{2} .

代入 $(8)$ 得:

\frac{1}{τ ρ} e_{y}^{k}^{2} + ρ A_{2} e_{2}^{k}^{2} + (1 - τ) ρ A_{1} e_{1}^{k} + A_{2} e_{2}^{k}^{2} - [\frac{1}{τ ρ} e_{y}^{k + 1}^{2} + ρ A_{2} e_{2}^{k + 1}^{2} + (1 - τ) ρ A_{1} e_{1}^{k + 1} + A_{2} e_{2}^{k + 1}^{2}] \geq ρ A_{1} x_{1}^{k + 1} + A_{2} x_{2}^{k + 1} - b^{2} + τ ρ A_{2} (x_{2}^{k + 1} - x_{2}^{k})^{2} .

$τ > 1$ : 此时 $1 - τ < 0$ ,根据基本不等式

- 2 ⟨ A_{2} (x_{2}^{k + 1} - x_{2}^{k}), A_{1} x_{1}^{k} + A_{2} x_{2}^{k} - b ⟩ \leq τ A_{2} (x_{2}^{k + 1} - x_{2}^{k})^{2} + \frac{1}{τ} A_{1} x_{1}^{k} + A_{2} x_{2}^{k} - b^{2} .

同样代入不等式 $(8)$ 可以得到

\frac{1}{τ ρ} e_{y}^{k}^{2} + ρ A_{2} e_{2}^{k}^{2} + (1 - \frac{1}{τ}) ρ A_{1} e_{1}^{k} + A_{2} e_{2}^{k}^{2} - [\frac{1}{τ ρ} e_{y}^{k + 1}^{2} + ρ A_{2} e_{2}^{k + 1}^{2} + (1 - \frac{1}{τ}) ρ A_{1} e_{1}^{k + 1} + A_{2} e_{2}^{k + 1}^{2}] \geq (1 + \frac{1}{τ} - τ) ρ A_{1} x_{1}^{k + 1} + A_{2} x_{2}^{k + 1} - b^{2} + (1 + τ - τ^{2}) ρ A_{2} (x_{2}^{k + 1} - x_{2}^{k})^{2} .

综合两种情况知,原命题得证.

再证明全序列收敛到一个KKT点
由 ${Φ_{k}}$ 序列下降性可知 ${Φ_{k}}$ 是有界序列,结合 $Φ_{k}$ 的定义式

Φ_{k} = \frac{1}{τ ρ} e_{y}^{k}^{2} + ρ A_{2} e_{2}^{k}^{2} + max (1 - τ, 1 - τ^{- 1}) ρ A_{1} e_{1}^{k} + A_{2} e_{2}^{k}^{2}

可知 $e_{y}^{k}, A_{2} e_{2}^{k}, A_{1} e_{1}^{k} + A_{2} e_{2}^{k}$ 均有界. 根据三角不等式 $A_{1} e_{1}^{k} \leq A_{1} e_{1}^{k} + A_{2} e_{2}^{k} + A_{2} e_{2}^{k},$ 可推出 ${A_{1} e_{1}^{k}}$ 也是有界序列.
由于 $A_{1}, A_{2}$ 是列满秩矩阵, 于是 $A_{1}^{T} A_{1} ≻ 0, A_{2}^{T} A_{2} ≻ 0$ ,即 $λ_{m i n} (A_{1}^{T} A_{1}) > 0, λ_{m i n} (A_{2}^{T} A_{2}) > 0$ . 结合

λ_{m i n} (A_{1}^{T} A_{1}) e_{1}^{k}^{2} \leq A_{1} e_{1}^{k}^{2}, λ_{m i n} (A_{2}^{T} A_{2}) e_{2}^{k}^{2} \leq A_{2} e_{2}^{k}^{2}

可得 ${(x_{1}^{k} - x_{1}^{*}, x_{2}^{k} - x_{2}^{*})}$ 有界. 再由 $e_{y}^{k} = y^{k} - y^{*}$ 有界,可知 ${(x_{1}^{k}, x_{2}^{k}, y^{k})}$ 是有界序列. 考虑到 ${Φ_{k}}$ 序列下降性以及 ${Φ_{k}}$ 有界,可知:

k = 0 \sum \infty A_{1} e_{1}^{k} + A_{2} e_{2}^{k}^{2} < \infty, k = 0 \sum \infty A_{2} (x_{2}^{k + 1} - x_{2}^{k})^{2} < \infty

这表明

A_{1} e_{1}^{k} + A_{2} e_{2}^{k} = A_{1} x_{1}^{k} + A_{2} x_{2}^{k} - b \to 0, A_{2} (x_{2}^{k + 1} - x_{2}^{k}) \to 0. (10)

由于 ${(x_{1}^{k}, x_{2}^{k}, y^{k})}$ 是有界序列，因此存在一个收敛子列，设 $(x_{1}^{k_{j}}, x_{2}^{k_{j}}, y^{k_{j}}) \to (x_{1}^{\infty}, x_{2}^{\infty}, y^{\infty})$ . 由 ${u^{k}}$ 与 ${v^{k}}$ 的定义式

u^{k} v^{k} = - A_{1}^{⊤} [y^{k} + (1 - τ) ρ (A_{1} e_{1}^{k} + A_{2} e_{2}^{k}) + ρ A_{2} (x_{2}^{k - 1} - x_{2}^{k})], = - A_{2}^{⊤} [y^{k} + (1 - τ) ρ (A_{1} e_{1}^{k} + A_{2} e_{2}^{k})]

再由结论 $(10)$ 可知 ${u^{k}}$ 与 ${v^{k}}$ 相应的子列也收敛。从而

u^{\infty} = def j \to \infty lim u^{k_{j}} = - A_{1}^{⊤} y^{\infty}, v^{\infty} = j \to \infty lim v^{k_{j}} = - A_{2}^{⊤} y^{\infty} .

由 $u^{k} \in \partial f_{1} (x_{1}^{k}), v^{k} \in \partial f_{2} (x_{2}^{k})$ 知，由次梯度映射的图像是闭集可知

- A_{1}^{⊤} y^{\infty} \in \partial f_{1} (x_{1}^{\infty}), - A_{2}^{⊤} y^{\infty} \in \partial f_{2} (x_{2}^{\infty}) .

由 $(10)$ 可知 $lim_{j \to \infty} ∥ A_{1} x_{1}^{k_{j}} + A_{2} x_{2}^{k_{j}} - b ∥ = ∥ A_{1} x_{1}^{\infty} + A_{2} x_{2}^{\infty} - b ∥ = 0.$ 这表明 $((x_{1}^{\infty}, x_{2}^{\infty}, y^{\infty})$ 是原问题的一个 KKT 对。因此上述分析中的 $(x_{1}^{*}, x_{2}^{*}, y^{*})$ 均可替换为 $(x_{1}^{\infty}, x_{2}^{\infty}, y^{\infty})$ . 注意到 ${Φ_{k}}$ 是单调下降的，并且对子列 ${Φ_{k_{j}}}$ 有

j \to \infty lim Φ_{k_{j}} = j \to \infty lim (\frac{1}{τ ρ} ∥ e_{y}^{k_{j}} ∥^{2} + ρ ∥ A_{2} e_{2}^{k_{j}} ∥^{2} + max {1 - τ, 1 - \frac{1}{τ}} ρ ∥ A_{1} e_{1}^{k_{j}} + A_{2} e_{2}^{k_{j}} ∥^{2}) = 0.

进一步由 $(10)$ 知:

0 \leq k \to \infty lim sup ∥ A_{1} e_{1}^{k} ∥ \leq k \to \infty lim (∥ A_{2} e_{2}^{k} ∥ + ∥ A_{1} e_{1}^{k} + A_{2} e_{2}^{k} ∥) = 0.

注意到 $A_{1}^{⊤} A_{1} > 0 ， A_{2}^{⊤} A_{2} > 0$ ，再运用:

λ_{m i n} (A_{1}^{T} A_{1}) e_{1}^{k}^{2} \leq A_{1} e_{1}^{k}^{2}, λ_{m i n} (A_{2}^{T} A_{2}) e_{2}^{k}^{2} \leq A_{2} e_{2}^{k}^{2}

故全序列 ${(x_{1}^{k}, x_{2}^{k}, y^{k})}$ 收敛到KKT点 $(x_{1}^{\infty}, x_{2}^{\infty}, y^{\infty})$ 。

👨‍💻Zhenry's Notebook Set

Explorer

7.20最优化