海口小微企业网站建设,阜阳万维网站建设,丹东做网站的公司,怎么样用ppt做网站机器学习笔记之最优化理论与方法——共轭梯度法背景介绍 引言背景#xff1a;共轭梯度法线性共轭梯度法共轭方向共轭VS正交共轭方向法共轭方向法的几何解释 引言
本节将介绍共轭梯度法#xff0c;并重点介绍共轭方向法的逻辑与几何意义。
背景#xff1a;共轭梯度法
关于… 机器学习笔记之最优化理论与方法——共轭梯度法背景介绍 引言背景共轭梯度法线性共轭梯度法共轭方向共轭VS正交共轭方向法共轭方向法的几何解释 引言
本节将介绍共轭梯度法并重点介绍共轭方向法的逻辑与几何意义。
背景共轭梯度法
关于最小化二次目标函数 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)min21xTQxCTx其中 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)QxC≜0 可以看出 Q x C 0 \mathcal Q x \mathcal C 0 QxC0是一个包含 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)21xTQxCTx;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)21xTBxCTx中的二次项部分仅包含 x x x内各分量的平方项而不包含各分量的交叉项 以 n 2 n2 n2为例对应目标函数图像以及在 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 n2 n2为例对应的目标函数 f ( x ) f(x) f(x)在决策变量 x x x各分量的等值线示例如下 由于交叉项 q m n ( m ≠ n ) q_{mn}(m \neq n) qmn(mn)的存在对应椭圆图像的长轴与短轴不再与坐标轴平行。 针对这种一般情况的二次型函数 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)21xTQxCTx可以通过二次型的线性替换从而将函数转化为标准型函数 其中 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} QPTDPD λ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 xPTx^。 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)21xTQxCTx21xTPTDPxCTx21(Px)TD(Px)CTx21[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 xPTx^找到 x x x的最优解。
而线性共轭梯度法是用来针对线性方程组 ∇ f ( x ) Q x C ≜ 0 \nabla f(x) \mathcal Q x \mathcal C \triangleq 0 ∇f(x)QxC≜0的求解问题。如果针对上述逻辑必然需要先将正交矩阵 P \mathcal P P求解出来。但相反由于 P \mathcal P P是由特征值对应特征向量组成的正交矩阵而求解特征向量依然要解方程组 Q x C ≜ 0 \mathcal Q x \mathcal C \triangleq 0 QxC≜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 QSTDS 从而通过上述思路求解最优解 x S T x ^ x \mathcal S^T \hat {x} xSTx^。
关于向量组 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(ij)若满足 ( d i ) T Q d j 0 (d_i)^T \mathcal Q d_j 0 (di)TQdj0 则称向量 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;ij⇒(di)TQdj0
共轭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,ij(di)TIdj0⇒(di)Tdj0 如果向量组 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 QMTΛM并令 Λ λ 2 \Lambda \lambda^2 Λλ2有 由于 M \mathcal M M是正交矩阵: M M T I \mathcal M \mathcal M^T \mathcal I MMTI,因而可以在展开过程中插入一个 M M T \mathcal M \mathcal M^T MMT。令 P M T λ M \mathcal P \mathcal M^T \lambda \mathcal M PMTλ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} QMTΛMMTλ2M(MTλM)(MTλM)(MTλM)2P2 从而将 Q \mathcal Q Q分解成 P 2 \mathcal P^2 P2的形式。并且 P M T λ M \mathcal P \mathcal M^T \lambda \mathcal M PMTλM也是一个正定矩阵 P 2 P ⋅ P P T P \mathcal P^2 \mathcal P \cdot \mathcal P \mathcal P^T \mathcal P P2P⋅PPTP。 关于向量 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)TQdj0可表示为 ( 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)21xTQxCTx,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_{k1} x_k \alpha_k \cdot d_k xk1xkα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 ( x k ) T Q d k ≜ 0 \begin{aligned} \nabla \phi(\alpha_k) 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 (x_k)^T \mathcal Q d_k \triangleq 0 \\ \end{aligned} ∇ϕ(αk)f(xkαk⋅dk)Tdk[Q(xkαk⋅dk)C]Tdk(QxkC)Tdkαk(xk)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(QxkC)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_{i0}^{n-1} \alpha_i \cdot d_i x1x0i0∑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 ij时必然有 ( d i ) T Q d j 0 (d_i)^T \mathcal Q d_j 0 (di)TQdj0相反当 i j i j ij时由于 Q \mathcal Q Q是正定矩阵因而 ( d i ) T Q d j 0 (d_i)^T \mathcal Q d_j 0 (di)TQdj0恒成立。从而 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−1SS−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} IS−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(i0,1,2,\cdots,n-1) S−1di(i0,1,2,⋯,n−1)表示单位坐标向量 e i 1 ( 0 , 0 , ⋯ , 1 ⏟ i 1 , ⋯ , 0 ) T e_{i1} (0,0,\cdots,\underbrace{1}_{i1},\cdots,0)^T ei1(0,0,⋯,i1 1,⋯,0)T
如果将决策变量 x S ⋅ x ^ x \mathcal S \cdot \hat {x} xS⋅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)21xTQxCTx可替换为一个新函数 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(i1,2,\cdots,n) x^i(i1,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_{i0}^{n-1} \alpha_i \cdot d_i x0∑i0n−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_{i1} \mathcal S^{-1} d_i(i1,2,\cdots,n-1) ei1S−1di(i1,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 Reference \text{Reference} Reference 最优化理论与方法-第七讲-无约束优化问题三
