线性等式约束问题的投影方法
1 回顾最速下降法
无约束最优化问题:
(
P
)
min
f
(
x
)
s.t.
x
∈
R
n
\begin{aligned} (P) ~ ~ ~ \min &~ ~ ~ f(x)\\ \text{s.t.} &~ ~ ~x ∈ R^n \end{aligned}
(P) mins.t. f(x) x∈Rn
其中
f
(
x
)
f(x)
f(x)是可微的。在
x
=
x
ˉ
x =\bar{x}
x=xˉ处，
f
(
x
)
f(x)
f(x)可以通过线性展开逼近
f
(
x
ˉ
+
d
)
≈
f
(
x
ˉ
)
+
∇
f
(
x
ˉ
)
T
d
f(\bar{x} + d) ≈ f(\bar{x}) + ∇f(\bar{x})^T d
f(xˉ+d)≈f(xˉ)+∇f(xˉ)Td
为了使d小。这就导致了d的选择，由方向查找问题所决定的:
m
i
n
i
m
i
z
e
∇
f
(
x
ˉ
)
T
d
s
.
t
.
∥
d
∥
≤
1
,
minimize~~~ ∇f(\bar{x})^T d\\ s.t. ~~\|d\| ≤ 1,
minimize ∇f(xˉ)Tds.t. ∥d∥≤1,
等于:
m
i
n
i
m
i
z
e
∇
f
(
x
ˉ
)
T
d
s
.
t
.
d
T
I
d
≤
1.
minimize~~~ ∇f(\bar{x})^T d\\ s.t.~ ~~d^T Id ≤ 1.
minimize ∇f(xˉ)Tds.t. dTId≤1.
这个方向查找问题的解决方法为:
d
ˉ
=
−
∇
f
(
x
ˉ
)
∥
∇
f
(
x
ˉ
)
∥
\bar{d}=\frac{-∇f(\bar{x})}{\|∇f(\bar{x})\|}
dˉ=∥∇f(xˉ)∥−∇f(xˉ)
因为我们选择了下一步
x
′
=
x
ˉ
+
α
d
ˉ
x' = \bar{x} + α\bar{d}
x′=xˉ+αdˉ
对于一些步长尺寸
α
α
α的选择，那么我们可以简单地将
d
ˉ
\bar{d}
dˉ方向重新缩放为:
d
ˉ
=
−
∇
f
(
x
ˉ
)
\bar{d} = −∇f(\bar{x})
dˉ=−∇f(xˉ)
也就是说，最速下降法方向就是f(x)在
x
=
x
ˉ
x =\bar{x}
x=xˉ处的梯度的负值。
2 等式限制问题
现在考虑稍微复杂一点的问题
(
P
)
min
f
(
x
)
s.t.
A
x
=
b
x
∈
R
n
\begin{aligned} (P) ~ ~ ~ \min &~ ~ ~ f(x)\\\text{s.t.} &~ ~ ~ Ax = b\\ &~ ~ ~x ∈ R^n \end{aligned}
(P) mins.t. f(x) Ax=b x∈Rn
其中f(x)是可微的。这个问题的KKT条件如下:
A
x
ˉ
=
b
∇
f
(
x
ˉ
)
+
A
T
π
ˉ
=
0.
A\bar{x}= b \\∇f(\bar{x}) +A^T\bar{π} = 0.
Axˉ=b∇f(xˉ)+ATπˉ=0.
我们希望找到KKT点。
假设我们在点
x
=
x
ˉ
x =\bar{x}
x=xˉ，其中
A
x
ˉ
=
b
A\bar{x}= b
Axˉ=b，即
x
ˉ
\bar{x}
xˉ是一个可行点。我们有
f
(
x
ˉ
+
d
)
≈
f
(
x
ˉ
)
+
∇
f
(
x
ˉ
)
T
d
f(\bar{x} + d) ≈ f(\bar{x}) + ∇f(\bar{x})^T d
f(xˉ+d)≈f(xˉ)+∇f(xˉ)Td
使d小。为了选择
d
ˉ
\bar{d}
dˉ方向并计算下一个点
x
′
=
x
ˉ
+
α
d
ˉ
x' = \bar{x} + α\bar{d}
x′=xˉ+αdˉ
对于某些步长
α
α
α，我们将解决以下方向查找问题:
min
f
(
x
ˉ
)
+
∇
f
(
x
ˉ
)
T
(
x
−
x
ˉ
)
s.t.
A
x
=
b
∥
x
−
x
ˉ
∥
≤
1
\begin{aligned} ~ ~ ~ \min &~ ~ ~ f(\bar{x}) + ∇f(\bar{x})^T (x-\bar{x})\\\text{s.t.} &~ ~ ~ Ax = b\\ &~ ~ ~\|x-\bar{x}\|\leq1 \end{aligned}
mins.t. f(xˉ)+∇f(xˉ)T(x−xˉ) Ax=b ∥x−xˉ∥≤1
或者相等地设
d
=
x
−
x
ˉ
d = x-\bar{x}
d=x−xˉ
min
∇
f
(
x
ˉ
)
T
d
s.t.
A
d
=
0
d
T
I
d
≤
1
\begin{aligned} ~ ~ ~ \min &~ ~ ~ ∇f(\bar{x})^T d\\\text{s.t.} &~ ~ ~ Ad = 0\\ &~ ~ ~d^T Id ≤ 1\end{aligned}
mins.t. ∇f(xˉ)Td Ad=0 dTId≤1
请注意，
A
d
=
0
Ad = 0
Ad=0确保
A
(
x
ˉ
+
α
d
)
=
A
x
ˉ
=
b
A(\bar{x} + α{d}) = A\bar{x} = b
A(xˉ+αd)=Axˉ=b,对于任何
α
α
α而言。还要注意，约束“
d
T
I
d
≤
1
d^T Id ≤ 1
dTId≤1”表示
d
d
d必须位于欧几里得单位球
B
B
B中，定义为:
B
=
{
d
∈
R
n
∣
d
T
I
d
≤
1
}
.
B = \{d ∈ R^n | d^T Id ≤ 1\}.
B={d∈Rn∣dTId≤1}.
然而，欧几里得球只是一个度规，我们可以更一般化，选择将
d
d
d限制在一个椭球内
E
Q
=
{
d
∈
R
n
∣
d
T
Q
d
≤
1
}
.
E_Q = \{d ∈ R^n | d^T Qd ≤ 1\}.
EQ={d∈Rn∣dTQd≤1}.
其中Q是给定的对称正定矩阵。这导致了更普遍的方向查找问题:
min
∇
f
(
x
ˉ
)
T
d
s.t.
A
d
=
0
d
T
Q
d
≤
1
\begin{aligned} ~ ~ ~ \min &~ ~ ~ ∇f(\bar{x})^T d\\\text{s.t.} &~ ~ ~ Ad = 0\\ &~ ~ ~ d^T Qd ≤ 1\end{aligned}
mins.t. ∇f(xˉ)Td Ad=0 dTQd≤1
投 影 最 速 下 降 算 法 为 : \large\color{#70f3ff}{\boxed{\color{brown}{投影最速下降算法为:} }} 投影最速下降算法为:
- 第一步： x ˉ \bar{x} xˉ满足 A x ˉ = b A\bar{x}= b Axˉ=b计算 ∇ f ( x ˉ ) ∇f(\bar{x}) ∇f(xˉ)
- 第二步：解决方向查找问题(DFP):
DFP:
d
ˉ
=
a
r
g
m
i
n
i
m
u
m
∇
f
(
x
ˉ
)
T
d
s.t.
A
d
=
0
d
T
Q
d
≤
1
\begin{aligned} ~ ~ ~ \bar{d}=arg~ minimum& ~ ~ ~ ∇f(\bar{x})^T d\\\text{s.t.} &~ ~ ~ Ad = 0\\ &~ ~ ~ d^T Qd ≤ 1\end{aligned}
dˉ=arg minimums.t. ∇f(xˉ)Td Ad=0 dTQd≤1
若
∇
f
(
x
ˉ
)
T
d
=
0
∇f(\bar{x})^T d= 0
∇f(xˉ)Td=0，则停止。在这种情况下，
x
ˉ
\bar{x}
xˉ是一个KKT点。
- 第三步：步长 α ˉ \bar{α} αˉ通过精确或不精确的直线搜索获得，求出$\min_\alpha ~f(\bar{x} + α\bar{d}) $。
- 第四步： x ˉ = x ˉ + α ˉ d ˉ \bar{x} = \bar{x} + \bar{α}\bar{d} xˉ=xˉ+αˉdˉ,返回第一步。
注意，如果 Q = I Q = I Q=I和等式约束 A x = b Ax = b Ax=b不存在，那么这个算法就是最速下降算法。
3投影最速下降方向 d ˉ \bar{d} dˉ的性质
注意，DFP是一个凸程序，
d
=
0
d = 0
d=0是Slater点。因此，Karush-Kuhn-Tucker条件是DFP最优性的充分必要条件。这些条件是:
A
d
ˉ
=
0
d
ˉ
T
Q
d
ˉ
≤
1
∇
f
(
x
ˉ
)
+
A
T
π
ˉ
+
2
β
ˉ
Q
d
ˉ
=
0
β
ˉ
≥
0
β
ˉ
(
1
−
d
ˉ
T
Q
d
ˉ
)
=
0
(1)
\begin{aligned} A\bar{d}=0 \\ \bar{d}^T Q\bar{d} ≤ 1\\ ∇f(\bar{x}) +A^T\bar{π} + 2 \bar{\beta}Q\bar{d} = 0\\ \bar{\beta} \geq0\\ \bar{\beta}(1-\bar{d}^T Q\bar{d})=0 \end{aligned}\tag1
Adˉ=0dˉTQdˉ≤1∇f(xˉ)+ATπˉ+2βˉQdˉ=0βˉ≥0βˉ(1−dˉTQdˉ)=0(1)
结果是，解这些方程非常容易。(我们将很快看到这个。)让
d
ˉ
\bar{d}
dˉ用乘数$ \bar{\beta},\bar{π}$ 求解(1式。
命 题 1 \large\color{magenta}{\boxed{\color{brown}{命题1} }} 命题1 x ˉ \bar{x} xˉ是P的Karush-Kuhn-Tucker点充分必要条件是 ∇ f ( x ˉ ) T d ˉ = 0 ∇f(\bar{x})^T \bar{d}=0 ∇f(xˉ)Tdˉ=0.
命 题 2 \large\color{magenta}{\boxed{\color{brown}{命题2} }} 命题2 x ˉ \bar{x} xˉ是P的Karush-Kuhn-Tucker点充分必要条件是 β ˉ = 0 \bar{\beta} =0 βˉ=0.
命 题 3 \large\color{magenta}{\boxed{\color{brown}{命题3} }} 命题3如果 x ˉ \bar{x} xˉ不是P的Karush-Kuhn-Tucker点，那么 d ˉ \bar{d} dˉ就是一个下降方向。
命 题 4 \large\color{magenta}{\boxed{\color{brown}{命题4} }} 命题4投影最速下降算法与最速下降算法具有相同的收敛性质和线性收敛性。在与最速下降算法相同的条件下，迭代收敛到一个Karush-Kuhn-Tucker点，并且收敛速率是线性的，与最速下降算法相同，其收敛常数是根据特征值且有界的。
4 解决方向查找问题(DFP)
D F P 的 求 解 方 法 1 : 求 解 线 性 方 程 组 \large\color{#70f3ff}{\boxed{\color{brown}{DFP的求解方法1:求解线性方程组} }} DFP的求解方法1:求解线性方程组
创建线性方程组:
Q
d
~
+
A
T
π
~
=
−
∇
f
(
x
ˉ
)
A
d
~
=
0
(2)
\begin{aligned} Q\widetilde{d} +A^T\widetilde{π} = -∇f(\bar{x}) \\ A\widetilde{d} =0 \\ \end{aligned}\tag2
Qd
+ATπ
=−∇f(xˉ)Ad
=0(2)
解决线性方程
(
d
~
,
π
~
)
(\widetilde{d} ,\widetilde{π})
(d
,π
)通过任何方法处理。
如果
Q
d
~
=
0
Q\widetilde{d}=0
Qd
=0,然后
A
T
π
~
+
∇
f
(
x
ˉ
)
=
0
A^T\widetilde{π}+∇f(\bar{x}) = 0
ATπ
+∇f(xˉ)=0
所以
x
ˉ
\bar{x}
xˉ是P的Karush-Kuhn-Tucker点。
如果
Q
d
~
≠
0
Q\widetilde{d}\neq 0
Qd
=0,然后按照如下方法重新调节该方程:
d
ˉ
=
d
~
d
~
T
Q
d
~
\bar{d} = \frac{\widetilde{d}}{\sqrt{\widetilde{d}^T Q\widetilde{d}}}
dˉ=d
TQd
d
π ˉ = π ~ \bar{π}=\widetilde{π} πˉ=π
β ˉ = 1 2 d ~ T Q d ~ \bar{\beta} = \frac{1}{2\sqrt{\widetilde{d}^T Q\widetilde{d}}} βˉ=2d TQd 1
命 题 5 \large\color{magenta}{\boxed{\color{brown}{命题5} }} 命题5$\bar{d} ,\bar{π},\bar{\beta} $定义如上满足公式（1）。
注意，由于我们使用的是线搜索，所以在实践中重新调节步骤是不必要的。
D F P 的 求 解 方 法 2 : 公 式 \large\color{#70f3ff}{\boxed{\color{brown}{DFP的求解方法2:公式} }} DFP的求解方法2:公式
令
P
=
[
Q
−
1
−
Q
−
1
A
T
(
A
Q
−
1
A
T
)
−
1
A
Q
−
1
]
P = [Q^{−1} − Q^{−1}A^T (AQ^{−1}A^T )^{−1}AQ^{−1}]
P=[Q−1−Q−1AT(AQ−1AT)−1AQ−1]
β ˉ = ( ∇ f ( x ˉ ) ) T P ( ∇ f ( x ˉ ) ) 2 \bar{\beta} = \frac{\sqrt{(∇f(\bar{x}))^T P(∇f(\bar{x}))}}{2} βˉ=2(∇f(xˉ))TP(∇f(xˉ))
π ˉ = − ( A Q − 1 A T ) − 1 A Q − 1 ( ∇ f ( x ˉ ) ) \bar{π}=-(AQ^{−1}A^T )^{−1}AQ^{−1}(∇f(\bar{x})) πˉ=−(AQ−1AT)−1AQ−1(∇f(xˉ))
如果
β
ˉ
>
0
\bar{\beta}>0
βˉ>0,让
d
ˉ
=
−
P
(
∇
f
(
x
ˉ
)
)
(
∇
f
(
x
ˉ
)
)
T
P
(
∇
f
(
x
ˉ
)
)
\bar{d} = \frac{-P(∇f(\bar{x}))}{\sqrt{(∇f(\bar{x}))^T P(∇f(\bar{x}))}}
dˉ=(∇f(xˉ))TP(∇f(xˉ))
−P(∇f(xˉ))
如果
β
ˉ
=
0
\bar{\beta}=0
βˉ=0,让
d
ˉ
=
0
\bar{d}=0
dˉ=0
命 题 6 \large\color{magenta}{\boxed{\color{brown}{命题6} }} 命题6 P P P是对称的正半定的。因此 β ˉ ≥ 0 \bar{\beta}≥0 βˉ≥0
命 题 7 \large\color{magenta}{\boxed{\color{brown}{命题7} }} 命题7$\bar{d} ,\bar{π},\bar{\beta} $定义如上满足公式（1）。
5 牛顿法的修正在线性等式约束
这里我们考虑以下问题:
(
P
:
)
minimize
x
f
(
x
)
s.t.
A
x
=
b
x
∈
R
n
\begin{aligned} (P:) ~ ~ ~ \text{minimize}_x &~ ~ ~ f(x)\\\text{s.t.} &~ ~ ~ Ax = b\\ &~ ~ ~x ∈ R^n \end{aligned}
(P:) minimizexs.t. f(x) Ax=b x∈Rn
正如在牛顿法的常规版本中，我们用
f
(
x
)
f(x)
f(x)在
x
=
x
ˉ
x =\bar{x}
x=xˉ处的二次展开来近似目标。
(
P
:
)
minimize
x
h
(
x
)
=
f
(
x
ˉ
)
+
∇
f
(
x
ˉ
)
T
(
x
−
x
ˉ
)
+
1
2
(
x
−
x
ˉ
)
T
H
(
x
ˉ
)
(
x
−
x
ˉ
)
s.t.
A
x
=
b
x
∈
R
n
\begin{aligned} (P:) ~ ~ ~ \text{minimize}_x &~ ~ ~ h(x)=f(\bar{x})+∇f(\bar{x})^T(x-\bar{x})+\frac{1}{2}(x-\bar{x})^TH(\bar{x})(x-\bar{x}) \\\text{s.t.} &~ ~ ~ Ax = b\\ &~ ~ ~x ∈ R^n \end{aligned}
(P:) minimizexs.t. h(x)=f(xˉ)+∇f(xˉ)T(x−xˉ)+21(x−xˉ)TH(xˉ)(x−xˉ) Ax=b x∈Rn
现在我们利用KKT条件来解决这个问题，所以我们求解(x, u)的方程组:
A
x
=
b
∇
h
(
x
)
+
A
T
u
=
0.
Ax = b \\∇h(x) +A^T u = 0 .
Ax=b∇h(x)+ATu=0.
现在让我们代入这样一个事实:
∇
h
(
x
)
=
∇
f
(
x
ˉ
)
+
H
(
x
ˉ
)
(
x
−
x
ˉ
)
,
A
x
ˉ
=
b
∇h(x)=∇f(\bar{x})+H(\bar{x})(x-\bar{x}),A\bar{x}=b
∇h(x)=∇f(xˉ)+H(xˉ)(x−xˉ),Axˉ=b
把这个和
d
=
x
−
x
ˉ
d = x-\bar{x}
d=x−xˉ相加，我们就得到了这样一个方程:
A
d
=
0
H
(
x
ˉ
)
d
+
A
T
u
=
−
∇
f
(
x
ˉ
)
Ad = 0\\H(\bar{x})d+A^T u = -∇f(\bar{x})
Ad=0H(xˉ)d+ATu=−∇f(xˉ)
这个方程组的解
(
d
,
u
)
(d, u)
(d,u)得到
x
ˉ
\bar{x}
xˉ处的牛顿方向d。
注意，这个方程组实际上有一个封闭的解，如果我们想沿着这条路走的话。它是:
d
=
−
H
(
x
ˉ
)
−
1
∇
f
(
x
ˉ
)
+
H
(
x
ˉ
)
−
1
A
T
(
A
H
(
x
ˉ
)
−
1
A
T
)
−
1
A
H
(
x
ˉ
)
−
1
∇
f
(
x
ˉ
)
u
=
−
(
A
H
(
x
ˉ
)
−
1
A
T
)
−
1
A
H
(
x
ˉ
)
−
1
∇
f
(
x
ˉ
)
\begin{aligned} d &= -H(\bar{x})^{−1}∇f(\bar{x}) + H(\bar{x})^{−1}A^T (AH(\bar{x})^{−1}A^T )^{−1}AH(\bar{x})^{−1}∇f(\bar{x})\\ u&=- (AH(\bar{x})^{−1}A^T )^{−1}AH(\bar{x})^{−1}∇f(\bar{x}) \end{aligned}
du=−H(xˉ)−1∇f(xˉ)+H(xˉ)−1AT(AH(xˉ)−1AT)−1AH(xˉ)−1∇f(xˉ)=−(AH(xˉ)−1AT)−1AH(xˉ)−1∇f(xˉ)
这导致了线性约束问题的牛顿方法的以下版本.
线 性 约 束 问 题 的 牛 顿 法 : \large\color{#70f3ff}{\boxed{\color{brown}{线性约束问题的牛顿法:} }} 线性约束问题的牛顿法:
给定起始点$ x_0\in dom \ f,让Ax^0 = b,k=0 $，容许误差 $\epsilon >0 $,
-
第一步： x ˉ = x k \bar{x}=x^k xˉ=xk,解决 ( d ˉ , u ˉ ) (\bar{d}, \bar{u}) (dˉ,uˉ):
-
A d ˉ = 0 H ( x ˉ ) d ˉ + A T u ˉ = − ∇ f ( x ˉ ) (3) A\bar{d} = 0\\H(\bar{x})\bar{d}+A^T \bar{u} = -∇f(\bar{x})\tag3 Adˉ=0H(xˉ)dˉ+ATuˉ=−∇f(xˉ)(3)
-
如果 H ( x ˉ ) d ˉ = 0 H(\bar{x})\bar{d}= 0 H(xˉ)dˉ=0，则停止。
-
第二步：选择步长 α k = 1 α_k = 1 αk=1
-
第三步：迭代： x k + 1 = x ˉ + α k d ˉ , k = k + 1 x^{k+1} = \bar{x}+ α_k\bar{d}, k = k + 1 xk+1=xˉ+αkdˉ,k=k+1. 转到第一步。
请注意以下几点:
如果 H ( x ˉ ) d ˉ = 0 H(\bar{x})\bar{d}= 0 H(xˉ)dˉ=0，那么 x ˉ \bar{x} xˉ是一个KKT点。从步骤1注意， ∇ f ( x ˉ ) + A T u ˉ = 0 ∇f(\bar{x})+A^T \bar{u} = 0 ∇f(xˉ)+ATuˉ=0，这就是这个问题的KKT条件。
式(3)称为“正规方程”。它们是在假定 H ( x ˉ ) H(\bar{x}) H(xˉ)是正定的情况下推导出来的，但即使在 H ( x ˉ ) H(\bar{x}) H(xˉ)不是正定的情况下也可以使用。
如果 H ( x ˉ ) H(\bar{x}) H(xˉ)是正定，那么 d ˉ \bar{d} dˉ是一个下降方向。注意，在(3)得到 ∇ f ( x ˉ ) T d ˉ = − d ˉ T H ( x ˉ ) d ˉ < 0 ∇f(\bar{x})^T\bar{d}=-\bar{d}^TH(\bar{x})\bar{d}<0 ∇f(xˉ)Tdˉ=−dˉTH(xˉ)dˉ<0，因为 H ( x ˉ ) H(\bar{x}) H(xˉ)是正定的。
6 变度量法
在投影最速下降算法中，d方向必须在椭球面上
E
Q
=
{
d
∈
R
n
∣
d
T
Q
d
≤
1
}
.
E_Q = \{d ∈ R^n | d^T Qd ≤ 1\}.
EQ={d∈Rn∣dTQd≤1}.
其中
Q
Q
Q对于所有迭代都是固定的。在可变度量方法中，
Q
Q
Q在每次迭代中变化。变度量算法为:
- 第一步： x ˉ \bar{x} xˉ满足 A x ˉ = b A\bar{x}= b Axˉ=b计算 ∇ f ( x ˉ ) ∇f(\bar{x}) ∇f(xˉ)
- 第二步：选择一个正定对称矩阵 Q Q Q(或许 Q = Q ( x ˉ ) Q = Q(\bar{x}) Q=Q(xˉ)，即 Q Q Q的选择可能取决于当前点)。解决方向查找问题(DFP):
DFP:
d
ˉ
=
a
r
g
m
i
n
i
m
u
m
∇
f
(
x
ˉ
)
T
d
s.t.
A
d
=
0
d
T
Q
d
≤
1
\begin{aligned} ~ ~ ~ \bar{d}=arg~ minimum& ~ ~ ~ ∇f(\bar{x})^T d\\\text{s.t.} &~ ~ ~ Ad = 0\\ &~ ~ ~ d^T Qd ≤ 1\end{aligned}
dˉ=arg minimums.t. ∇f(xˉ)Td Ad=0 dTQd≤1
若
∇
f
(
x
ˉ
)
T
d
=
0
∇f(\bar{x})^T d= 0
∇f(xˉ)Td=0，则停止。在这种情况下，
x
ˉ
\bar{x}
xˉ是一个KKT点。
- 第三步：步长 α ˉ \bar{α} αˉ通过精确或不精确的直线搜索获得，求出$\min_\alpha ~f(\bar{x} + α\bar{d}) $。
- 第四步： x ˉ = x ˉ + α ˉ d ˉ \bar{x} = \bar{x} + \bar{α}\bar{d} xˉ=xˉ+αˉdˉ,返回第一步。
投影最速下降算法的所有性质在这里仍然成立。
在每次迭代中选择Q的一些策略是:
- Q = I Q=I Q=I
- Q Q Q是在所有迭代中保持不变的给定矩阵
- Q = H ( x ˉ ) Q = H(\bar{x}) Q=H(xˉ)其中 H ( x ) H(x) H(x)是 f ( x ) f(x) f(x)的Hessian。很容易证明，在这种情况下，变度量算法等价于线搜索的牛顿法，见下面的命题。
- Q = H ( x ˉ ) + δ I Q = H(\bar{x}) + δI Q=H(xˉ)+δI，在早期迭代中，选择了较大的 δ δ δ，但在后期迭代中，选择了较小的 δ δ δ。我们可以把这个策略看作是在早期迭代中近似投影下降下降算法，然后在后期迭代中近似牛顿法。
命 题 8 \large\color{magenta}{\boxed{\color{brown}{命题8} }} 命题8假设变度量算法中的 Q = H ( x ˉ ) Q = H(\bar{x}) Q=H(xˉ)。那么变度规法中的方向 d ˉ \bar{d} dˉ是一个正标量乘以牛顿方向。
证明：
d
ˉ
=
a
r
g
m
i
n
i
m
u
m
∇
f
(
x
ˉ
)
T
d
s.t.
A
d
=
0
d
T
H
(
x
ˉ
)
d
≤
1
\begin{aligned} ~ ~ ~ \bar{d}=arg~ minimum& ~ ~ ~ ∇f(\bar{x})^T d\\\text{s.t.} &~ ~ ~ Ad = 0\\ &~ ~ ~ d^T H(\bar{x})d ≤ 1\end{aligned}
dˉ=arg minimums.t. ∇f(xˉ)Td Ad=0 dTH(xˉ)d≤1
牛顿方向$\widetilde{d}
对
于
P
在
对于P在
对于P在\bar{x}$点是以下问题的解:
NDP:
d
^
=
a
r
g
m
i
n
i
m
u
m
∇
f
(
x
ˉ
)
T
d
+
1
2
d
T
H
(
x
ˉ
)
d
s.t.
A
d
=
0
\begin{aligned} ~ ~ ~ \hat{d}=arg~ minimum& ~ ~ ~ ∇f(\bar{x})^T d+\frac{1}{2}d^TH(\bar{x}){d}\\\text{s.t.} &~ ~ ~ Ad = 0\end{aligned}
d^=arg minimums.t. ∇f(xˉ)Td+21dTH(xˉ)d Ad=0
如果你写下Karush-Kuhn-Tucker条件这两个问题,然后可以很容易地验证
d
ˉ
=
γ
d
^
\bar{d}=\gamma \hat{d}
dˉ=γd^。
参考资料
MIT凸优化课程
Stephen Boyd的Convex Optimization
《凸优化》，Stephen Boyd等著，王书宁等译