引言
本节将介绍共轭梯度法,并重点介绍共轭方向法的逻辑与几何意义。
背景:共轭梯度法
关于最小化二次目标函数: min f ( x ) = min 1 2 x T Q x + C T x \begin{aligned}\min f(x) = \min \frac{1}{2} x^T \mathcal Q x + \mathcal C^T x\end{aligned} minf(x)=min21xTQx+CTx,其中 Q ∈ R n × n ; Q ≻ 0 \mathcal Q \in \mathbb R^{n \times n};\mathcal Q \succ 0 Q∈Rn×n;Q≻0,且 C ∈ R n \mathcal C \in \mathbb R^n C∈Rn。很明显:由于 Q \mathcal Q Q是正定矩阵,那么该函数是凸二次函数。
关于该函数的最优解:令
∇
f
(
x
)
≜
0
\nabla f(x) \triangleq 0
∇f(x)≜0,有:凸函数的
局部最优解(极值点)也是它的
全局最优解。
∇
f
(
x
)
=
Q
x
+
C
≜
0
\nabla f(x) = \mathcal Q x + \mathcal C \triangleq 0
∇f(x)=Qx+C≜0
可以看出:
Q
x
+
C
=
0
\mathcal Q x + \mathcal C = 0
Qx+C=0是一个包含
n
n
n个方程的线性方程组。
- 如果 n n n的规模较小时,关于解方程组,可以使用其他工具进行解决。例如:高斯消去法;
- 相反,当 n n n的规模较大时,对应的增广矩阵规模同样很大,使用高斯消去法解方程组的成本较高。
而共轭梯度法初始就是针对方程组的一种迭代求解方法。随着最优化问题的推广,关于目标函数
f
(
x
)
f(x)
f(x)也不仅仅局限在二次函数。对于这类
min
f
(
x
)
\min f(x)
minf(x)的方法也被称作非线性共轭梯度法。对于上述方程组问题的迭代求解方法也被称作
线性共轭梯度法。
线性共轭梯度法
关于上述优化问题: min f ( x ) = 1 2 x T Q x + C T x ; Q ≻ 0 \begin{aligned}\min f(x) = \frac{1}{2} x^T \mathcal Q x + \mathcal C^T x;\mathcal Q \succ 0\end{aligned} minf(x)=21xTQx+CTx;Q≻0
- 假设正定矩阵
Q
\mathcal Q
Q是一个对角矩阵
B
=
(
b
1
b
2
⋱
b
n
)
n
×
n
\mathcal B = \begin{pmatrix} b_1 & \quad & \quad & \quad \\ \quad & b_2 & \quad & \quad\\ \quad & \quad & \ddots & \quad \\ \quad & \quad & \quad & b_n \end{pmatrix}_{n \times n}
B=
b1b2⋱bn
n×n,那么此时可以发现:
f
(
x
)
=
1
2
x
T
B
x
+
C
T
x
\begin{aligned}f(x) = \frac{1}{2}x^T \mathcal B x + \mathcal C^T x \end{aligned}
f(x)=21xTBx+CTx中的二次项部分仅包含
x
x
x内各分量的平方项,而不包含各分量的交叉项;
以
n = 2 n=2 n=2为例,对应目标函数图像以及在
x 1 , x 2 x_1,x_2 x1,x2方向上的投影
(等值线)示例如下。
很明显,可以看出:描述等值线的椭圆,其长轴与短轴分别与坐标轴平行。如果通过迭代的方式进行求解,可以根据无约束优化问题——常用求解方法(上)中介绍的坐标轴交替下降法进行求解。图像表示如下:由于更新方向被确定
——与坐标轴方向平行。因此仅需要计算各维度达到最小步长即可。因而仅需要
2 2 2步就可以找到最优解。
同理,如果是 x ∈ R n x \in \mathbb R^n x∈Rn,需要将所有的轴均迭代一遍即可找到最优解。 - 如果
Q
\mathcal Q
Q是一个一般形式的正定矩阵:
Q
=
(
q
11
q
12
⋯
q
1
n
q
21
q
22
⋯
q
2
n
⋮
⋮
⋱
⋮
q
n
1
q
n
2
⋯
q
n
n
)
n
×
n
;
Q
≻
0
\mathcal Q = \begin{pmatrix} q_{11} & q_{12} & \cdots & q_{1n} \\ q_{21} & q_{22} & \cdots & q_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ q_{n1} & q_{n2} & \cdots & q_{nn} \end{pmatrix}_{n \times n};\mathcal Q \succ 0
Q=
q11q21⋮qn1q12q22⋮qn2⋯⋯⋱⋯q1nq2n⋮qnn
n×n;Q≻0。这里依然以
n
=
2
n=2
n=2为例,对应的目标函数
f
(
x
)
f(x)
f(x)在决策变量
x
x
x各分量的等值线示例如下:
由于交叉项
q m n ( m ≠ n ) q_{mn}(m \neq n) qmn(m=n)的存在,对应椭圆图像的长轴与短轴不再与坐标轴平行。
针对这种一般情况的二次型函数 min f ( x ) = 1 2 x T Q x + C T x \begin{aligned}\min f(x) = \frac{1}{2} x^T \mathcal Q x + \mathcal C^T x\end{aligned} minf(x)=21xTQx+CTx,可以通过二次型的线性替换,从而将函数转化为标准型函数:其中
D \mathcal D D是由
Q \mathcal Q Q特征值组成的
对角阵;而
P \mathcal P P则表示由特征值对应特征向量组成的
正交阵。
Q = P T D P D = ( λ 1 λ 2 ⋱ λ n ) n × n \mathcal Q = \mathcal P^T \mathcal D \mathcal P \quad \mathcal D = \begin{pmatrix} \lambda_1 & \quad & \quad & \\ \quad & \lambda_2 &\quad & \\ \quad & \quad & \ddots & \\ \quad & \quad & \quad & \lambda_n \end{pmatrix}_{n \times n} Q=PTDPD= λ1λ2⋱λn n×n
替换后的函数 f ( x ) f(x) f(x)可表示为:记
x ^ = P x \hat {x} = \mathcal P x x^=Px反之
x = P T x ^ x = \mathcal P^T \hat x x=PTx^。
f ( x ) = 1 2 x T Q x + C T x = 1 2 x T P T D P x + C T x = 1 2 ( P x ) T D ( P x ) + C T x = 1 2 [ x ^ ] T D x ^ + C T ( P T x ^ ) = 1 2 [ x ^ ] T D x ^ + ( P C ) T x ^ = f ^ ( x ^ ) \begin{aligned} f(x) & = \frac{1}{2} x^T \mathcal Q x + \mathcal C^T x \\ & = \frac{1}{2} x^T \mathcal P^T \mathcal D \mathcal P x + \mathcal C^T x \\ & = \frac{1}{2}(\mathcal P x)^T \mathcal D (\mathcal P x) + \mathcal C^T x \\ & = \frac{1}{2} [\hat x]^T \mathcal D \hat {x} +\mathcal C^T (\mathcal P^T \hat x )\\ & = \frac{1}{2} [\hat x]^T \mathcal D \hat {x} + (\mathcal P \mathcal C)^T \hat x \\ & = \hat {f}(\hat x) \end{aligned} f(x)=21xTQx+CTx=21xTPTDPx+CTx=21(Px)TD(Px)+CTx=21[x^]TDx^+CT(PTx^)=21[x^]TDx^+(PC)Tx^=f^(x^)
此时,该公式又变回了第一类标准型。同样可以通过坐标轴交替下降法对新目标函数 f ^ ( x ^ ) \hat f(\hat x) f^(x^)进行求解。如果找到了关于 x ^ \hat x x^的最优解,可以通过 x = P T x ^ x = \mathcal P^T \hat x x=PTx^找到 x x x的最优解。
而线性共轭梯度法是用来针对线性方程组
∇
f
(
x
)
=
Q
x
+
C
≜
0
\nabla f(x) = \mathcal Q x + \mathcal C \triangleq 0
∇f(x)=Qx+C≜0的求解问题。如果针对上述逻辑,必然需要先将正交矩阵
P
\mathcal P
P求解出来。但相反,由于
P
\mathcal P
P是由特征值对应特征向量组成的正交矩阵,而求解特征向量依然要解方程组
Q
x
+
C
≜
0
\mathcal Q x + \mathcal C \triangleq 0
Qx+C≜0。很明显,这形成了一个
闭环:想要通过
P
\mathcal P
P求解方程组,而
P
\mathcal P
P自身也要通过求解方程组来获取。
而共轭梯度法的思路是:想要通过获取一系列的
n
n
n维向量:
d
0
,
d
1
,
⋯
,
d
n
−
1
∈
R
n
d_0,d_1,\cdots,d_{n-1} \in \mathbb R^n
d0,d1,⋯,dn−1∈Rn,其组成的矩阵
S
=
(
d
0
,
d
1
,
⋯
,
d
n
−
1
)
n
×
n
\mathcal S = (d_0,d_1,\cdots,d_{n-1})_{n \times n}
S=(d0,d1,⋯,dn−1)n×n,使其替代上面描述的正交矩阵
P
n
×
n
\mathcal P_{n \times n}
Pn×n,从而帮助
Q
\mathcal Q
Q完成对角化:
Q
=
S
T
D
S
\mathcal Q = \mathcal S^T \mathcal D \mathcal S
Q=STDS
从而通过上述思路,求解最优解:
x
=
S
T
x
^
x = \mathcal S^T \hat {x}
x=STx^。
关于向量组: d 0 , d 1 , ⋯ , d n − 1 d_0,d_1,\cdots,d_{n-1} d0,d1,⋯,dn−1,向量之间的关系被定义为共轭关系。
共轭方向
共轭方向的定义表示为:考虑正定矩阵
Q
\mathcal Q
Q以及非零向量
d
i
,
d
j
(
i
≠
j
)
d_i,d_j(i \neq j)
di,dj(i=j),若满足:
(
d
i
)
T
Q
d
j
=
0
(d_i)^T \mathcal Q d_j = 0
(di)TQdj=0
则称向量
d
i
,
d
j
d_i,d_j
di,dj关于矩阵
Q
\mathcal Q
Q共轭。如果向量组
D
=
{
d
0
,
d
1
,
⋯
,
d
k
}
\mathcal D = \{d_0,d_1,\cdots,d_k\}
D={d0,d1,⋯,dk}关于矩阵
Q
\mathcal Q
Q共轭,即向量之间两两共轭:
∀
d
i
,
d
j
∈
D
;
i
≠
j
⇒
(
d
i
)
T
Q
d
j
=
0
\forall d_i,d_j \in \mathcal D;i \neq j \Rightarrow (d_i)^T \mathcal Q d_j = 0
∀di,dj∈D;i=j⇒(di)TQdj=0
共轭VS正交
根据上述共轭梯度法的思路,以及共轭方向定义的描述,观察:共轭与正交之间的关系。
-
如果向量组 D { d 0 , d 1 , ⋯ , d k } \mathcal D \{d_0,d_1,\cdots,d_k\} D{d0,d1,⋯,dk}关于单位矩阵 I \mathcal I I共轭:此时向量 d i , d j ∈ D d_i,d_j \in \mathcal D di,dj∈D之间的共轭关系退化为正交关系:
∀ d i , d j ∈ D , i ≠ j ( d i ) T I d j = 0 ⇒ ( d i ) T d j = 0 \forall d_i,d_j \in \mathcal D,i \neq j \quad (d_i)^T \mathcal Id_j = 0 \Rightarrow (d_i)^T d_j = 0 ∀di,dj∈D,i=j(di)TIdj=0⇒(di)Tdj=0 -
如果向量组 D { d 0 , d 1 , ⋯ , d k } \mathcal D \{d_0,d_1,\cdots,d_k\} D{d0,d1,⋯,dk}关于正定矩阵 Q \mathcal Q Q共轭:令 Q = M T Λ M \mathcal Q = \mathcal M^T \Lambda \mathcal M Q=MTΛM,并令 Λ = λ 2 \Lambda = \lambda^2 Λ=λ2,有:
-
由于
M \mathcal M M是正交矩阵:
M M T = I \mathcal M \mathcal M^T = \mathcal I MMT=I,因而可以在展开过程中插入一个
M M T \mathcal M \mathcal M^T MMT。 -
令
P = M T λ M \mathcal P = \mathcal M^T \lambda \mathcal M P=MTλM
Q = M T Λ M = M T λ 2 M = ( M T λ M ) ( M T λ M ) = ( M T λ M ) 2 = P 2 \begin{aligned} \mathcal Q & = \mathcal M^T \Lambda \mathcal M \\ & = \mathcal M^T \lambda^2 \mathcal M \\ & = (\mathcal M^T\lambda \mathcal M) (\mathcal M^T \lambda \mathcal M) \\ & = (\mathcal M^T \lambda \mathcal M)^2 \\ & = \mathcal P^2 \end{aligned} Q=MTΛM=MTλ2M=(MTλM)(MTλM)=(MTλM)2=P2
从而将 Q \mathcal Q Q分解成 P 2 \mathcal P^2 P2的形式。并且 P = M T λ M \mathcal P = \mathcal M^T \lambda \mathcal M P=MTλM也是一个正定矩阵: P 2 = P ⋅ P = P T P \mathcal P^2 = \mathcal P \cdot \mathcal P = \mathcal P^T \mathcal P P2=P⋅P=PTP。
关于向量 d i , d j d_i,d_j di,dj共轭: ( d i ) T Q d j = 0 (d_i)^T \mathcal Q d_j = 0 (di)TQdj=0可表示为:
( d i ) T Q d j = ( d i ) T P 2 d j = ( d i ) T P T P d j = ( P d i ) T ( P d j ) = 0 \begin{aligned} (d_i)^T \mathcal Q d_j & = (d_i)^T \mathcal P^2 d_j \\ & = (d_i)^T \mathcal P^T \mathcal P d_j \\ & = (\mathcal P d_i)^T (\mathcal P d_j) = 0 \end{aligned} (di)TQdj=(di)TP2dj=(di)TPTPdj=(Pdi)T(Pdj)=0
也就是说:向量 d i , d j d_i,d_j di,dj经过正交矩阵 P \mathcal P P的投影结果: P d i , P d j \mathcal Pd_i,\mathcal Pd_j Pdi,Pdj之间是正交关系。关于
向量投影的描述详见
主成分分析(最大投影方差) -
-
根据正交的性质,两两正交的向量组,其内部向量必然线性无关;两两共轭的向量组,其内部向量同样线性无关。由于决策变量 x ∈ R n x \in \mathbb R^n x∈Rn,因而对应的两两共轭向量组内最多包含 n n n个两两共轭的向量。
再多一个,必然出现
向量之间不共轭的情况。
共轭方向法
依然针对凸二次函数的优化问题: min f ( x ) = 1 2 x T Q x + C T x , Q ≻ 0 \begin{aligned}\min f(x) = \frac{1}{2} x^T \mathcal Q x + \mathcal C^T x,\mathcal Q \succ 0 \end{aligned} minf(x)=21xTQx+CTx,Q≻0,通过迭代的方式求解 x x x的最优解:
- 给定:初始点
x
0
x_0
x0以及一组关于
Q
\mathcal Q
Q的共轭方向
d
0
,
d
1
,
⋯
,
d
n
−
1
d_0,d_1,\cdots,d_{n-1}
d0,d1,⋯,dn−1,令:
与
坐标轴交替下降法的思路如出一辙,只不过方向选择由原来
两两正交的坐标轴作为方向替换为
两两共轭的向量作为方向。
x k + 1 = x k + α k ⋅ d k x_{k+1} = x_k + \alpha_k \cdot d_k xk+1=xk+αk⋅dk - 其中
α
k
\alpha_k
αk满足:
即当前迭代步骤的
最优解,之所以选择最优解,因为该函数是
凸函数,对应的最优解必然是全局最优解。
α k = arg min α ϕ ( α ) = arg min α f ( x k + α ⋅ d k ) \alpha_k = \mathop{\arg\min}\limits_{\alpha} \phi(\alpha) = \mathop{\arg\min}\limits_{\alpha} f(x_k + \alpha \cdot d_k) αk=αargminϕ(α)=αargminf(xk+α⋅dk)
计算 ∇ ϕ ( α k ) ≜ 0 \nabla \phi(\alpha_k) \triangleq 0 ∇ϕ(αk)≜0,有:
∇ ϕ ( α k ) = ∇ f ( x k + α k ⋅ d k ) T d k = [ Q ( x k + α k ⋅ d k ) + C ] T d k = ( Q x k + C ) T d k + α k ( d k ) T Q d k ≜ 0 \begin{aligned} \nabla \phi(\alpha_k) & = \nabla f(x_k + \alpha_k \cdot d_k)^T d_k \\ & = [\mathcal Q(x_k + \alpha_k \cdot d_k) + \mathcal C]^T d_k \\ & = (\mathcal Q x_k + \mathcal C)^T d_k + \alpha_k (d_k)^T \mathcal Q d_k \triangleq 0 \\ \end{aligned} ∇ϕ(αk)=∇f(xk+αk⋅dk)Tdk=[Q(xk+αk⋅dk)+C]Tdk=(Qxk+C)Tdk+αk(dk)TQdk≜0
最终有:
α k = − ( Q x k + C ) T d k ( d k ) T Q d k = − [ ∇ f ( x k ) ] T d k ( d k ) T Q d k \alpha_k = -\frac{(\mathcal Q x_k + \mathcal C)^T d_k}{(d_k)^T \mathcal Q d_k} = -\frac{[\nabla f(x_k)]^T d_k}{(d_k)^T \mathcal Q d_k} αk=−(dk)TQdk(Qxk+C)Tdk=−(dk)TQdk[∇f(xk)]Tdk
整个的算法过程并不麻烦,但需要一个前提:将共轭方向
d
0
,
d
1
,
⋯
,
d
n
−
1
d_0,d_1,\cdots,d_{n-1}
d0,d1,⋯,dn−1提前给出。因而不同共轭方向的选择方式对应其相应的共轭方向法。与牛顿法的描述相似:针对
Hessian Matrix
\text{Hessian Matrix}
Hessian Matrix可能不是正定矩阵的一类情况,分为
修正法,
SR-1,DFP,BFGS
\text{SR-1,DFP,BFGS}
SR-1,DFP,BFGS等等方法;同理,共轭方向法为一类方法,而共轭梯度法只是其中一种方法。
共轭方向法的几何解释
观察关于初始点
x
0
x_0
x0的第一次迭代:
x
0
⇒
x
1
x_0 \Rightarrow x_1
x0⇒x1:
x
1
=
x
0
+
∑
i
=
0
n
−
1
α
i
⋅
d
i
x_1 = x_0 + \sum_{i=0}^{n-1} \alpha_i \cdot d_i
x1=x0+i=0∑n−1αi⋅di
如果将
n
n
n个共轭方向组成矩阵,记作
S
=
(
d
0
,
d
1
,
⋯
,
d
n
−
1
)
n
×
n
\mathcal S = (d_0,d_1,\cdots,d_{n-1})_{n \times n}
S=(d0,d1,⋯,dn−1)n×n,由于共轭方向两两线性无关,因而
S
\mathcal S
S必然是可逆矩阵。该矩阵存在如下性质:
- 关于
S
T
Q
S
=
[
(
d
0
)
T
⋮
(
d
n
−
1
)
T
]
Q
(
d
0
,
⋯
,
d
n
−
1
)
=
[
(
d
i
)
T
Q
d
j
]
n
×
n
\mathcal S^T \mathcal Q \mathcal S = \begin{bmatrix} (d_0)^T \\ \vdots \\ (d_{n-1})^T \end{bmatrix} \mathcal Q (d_0,\cdots,d_{n-1}) = [(d_i)^T \mathcal Q d_j]_{n \times n}
STQS=
(d0)T⋮(dn−1)T
Q(d0,⋯,dn−1)=[(di)TQdj]n×n,根据共轭方向的定义,当
i
≠
j
i \neq j
i=j时,必然有:
(
d
i
)
T
Q
d
j
=
0
(d_i)^T \mathcal Q d_j = 0
(di)TQdj=0;相反,当
i
=
j
i = j
i=j时,由于
Q
\mathcal Q
Q是正定矩阵,因而
(
d
i
)
T
Q
d
j
>
0
(d_i)^T \mathcal Q d_j >0
(di)TQdj>0恒成立。从而
S
T
Q
S
\mathcal S^T \mathcal Q \mathcal S
STQS不仅是一个正定矩阵,甚至是一个对角阵。
从而达到利用
S \mathcal S S对
Q \mathcal Q Q进行
对角化的目的。
- 由于
S
\mathcal S
S可逆,根据逆矩阵的性质,必然有:
S
−
1
S
=
S
−
1
(
d
0
,
d
1
,
⋯
,
d
n
−
1
)
=
I
\mathcal S^{-1} \mathcal S = \mathcal S^{-1}(d_0,d_1,\cdots,d_{n-1}) = \mathcal I
S−1S=S−1(d0,d1,⋯,dn−1)=I(单位矩阵)。将该式展开,有:
I = S − 1 ( d 0 , d 1 , ⋯ , d n − 1 ) = ( S − 1 d 0 , S − 1 d 1 ⋯ S − 1 d n − 1 ) \begin{aligned} \mathcal I & = \mathcal S^{-1}(d_0,d_1,\cdots,d_{n-1}) \\ & = (\mathcal S^{-1} d_0,\mathcal S^{-1} d_1 \cdots \mathcal S^{-1} d_{n-1}) \end{aligned} I=S−1(d0,d1,⋯,dn−1)=(S−1d0,S−1d1⋯S−1dn−1)
其中展开后矩阵中的元素 S − 1 d i ( i = 0 , 1 , 2 , ⋯ , n − 1 ) \mathcal S^{-1} d_i(i=0,1,2,\cdots,n-1) S−1di(i=0,1,2,⋯,n−1)表示单位坐标向量 e i + 1 = ( 0 , 0 , ⋯ , 1 ⏟ i + 1 , ⋯ , 0 ) T e_{i+1} = (0,0,\cdots,\underbrace{1}_{i+1},\cdots,0)^T ei+1=(0,0,⋯,i+1 1,⋯,0)T
如果将决策变量
x
=
S
⋅
x
^
x = \mathcal S \cdot \hat {x}
x=S⋅x^或者
x
^
=
S
−
1
x
\hat x = \mathcal S^{-1} x
x^=S−1x,从而原始目标函数
f
(
x
)
=
1
2
x
T
Q
x
+
C
T
x
\begin{aligned}f(x) = \frac{1}{2} x^T \mathcal Q x + \mathcal C^T x\end{aligned}
f(x)=21xTQx+CTx可替换为一个新函数
f
^
(
x
^
)
\hat f(\hat {x})
f^(x^):
f
^
(
x
^
)
=
1
2
[
x
^
]
T
S
T
Q
S
⏟
对角阵
⋅
x
^
+
(
S
T
C
)
T
x
^
\hat f(\hat {x}) = \frac{1}{2} [\hat x]^T \underbrace{\mathcal S^T \mathcal Q \mathcal S}_{对角阵} \cdot \hat {x} + (\mathcal S^T \mathcal C)^T \hat {x}
f^(x^)=21[x^]T对角阵
STQS⋅x^+(STC)Tx^
此时的新函数中仅包含关于
x
^
i
(
i
=
1
,
2
,
⋯
,
n
)
\hat {x}_i(i=1,2,\cdots,n)
x^i(i=1,2,⋯,n)的平方项,而没有交叉项。从而新函数
f
^
(
x
^
)
\hat f(\hat x)
f^(x^)在
x
^
\hat x
x^特征空间中的等值线依然是一个椭圆/椭球/超椭球,其长轴与短轴同样与坐标轴平行。
回归第一次迭代:
x
0
+
∑
i
=
0
n
−
1
α
i
⋅
d
i
x_0 + \sum_{i=0}^{n-1} \alpha_i \cdot d_i
x0+∑i=0n−1αi⋅di,这明显是一个在原始特征空间
x
x
x上的操作。如果该操作映射在
x
^
\hat x
x^的特征空间中会变成什么样的效果
?
?
?只需要将
x
x
x特征空间中的正交向量乘以
S
−
1
\mathcal S^{-1}
S−1即可得到对应
x
^
\hat x
x^特征空间的正交向量。
S
−
1
x
0
+
α
0
S
−
1
d
0
+
α
1
S
−
1
d
1
+
⋯
+
α
n
−
1
S
−
1
d
n
−
1
\mathcal S^{-1}x_0 + \alpha_0 \mathcal S^{-1}d_0 + \alpha_1 \mathcal S^{-1} d_1 + \cdots + \alpha_{n-1} \mathcal S^{-1} d_{n-1}
S−1x0+α0S−1d0+α1S−1d1+⋯+αn−1S−1dn−1
由于
e
i
+
1
=
S
−
1
d
i
(
i
=
1
,
2
,
⋯
,
n
−
1
)
e_{i+1} = \mathcal S^{-1} d_i(i=1,2,\cdots,n-1)
ei+1=S−1di(i=1,2,⋯,n−1),整理有:很明显,在
x
^
\hat x
x^的特征空间中,相当于
坐标轴交替下降法,沿着坐标轴进行搜索。
S
−
1
x
0
+
α
0
e
1
+
α
1
e
2
+
⋯
+
α
n
−
1
e
n
\mathcal S^{-1}x_0 + \alpha_0 e_1 + \alpha_1 e_2 + \cdots + \alpha_{n-1} e_{n}
S−1x0+α0e1+α1e2+⋯+αn−1en
下一节将继续介绍共轭方向法。
0
:
37
:
14
/
1
:
26
:
29
0:37:14/1:26:29
0:37:14/1:26:29文章来源:https://www.toymoban.com/news/detail-705341.html
Reference
\text{Reference}
Reference:
最优化理论与方法-第七讲-无约束优化问题(三)文章来源地址https://www.toymoban.com/news/detail-705341.html
到了这里,关于机器学习笔记之最优化理论与方法(十)无约束优化问题——共轭梯度法背景介绍的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!