机器学习笔记之最优化理论与方法(十)无约束优化问题——共轭梯度法背景介绍

这篇具有很好参考价值的文章主要介绍了机器学习笔记之最优化理论与方法(十)无约束优化问题——共轭梯度法背景介绍。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

引言

本节将介绍共轭梯度法,并重点介绍共轭方向法的逻辑与几何意义。

背景:共轭梯度法

关于最小化二次目标函数: 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 QRn×n;Q0,且 C ∈ R n \mathcal C \in \mathbb R^n CRn。很明显:由于 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+C0
可以看出: 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;Q0

  • 假设正定矩阵 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= b1b2bn 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 xRn,需要将所有的轴均迭代一遍即可找到最优解。
  • 如果 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= q11q21qn1q12q22qn2q1nq2nqnn n×n;Q0。这里依然以 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+C0的求解问题。如果针对上述逻辑,必然需要先将正交矩阵 P \mathcal P P求解出来。但相反,由于 P \mathcal P P是由特征值对应特征向量组成的正交矩阵,而求解特征向量依然要解方程组 Q x + C ≜ 0 \mathcal Q x + \mathcal C \triangleq 0 Qx+C0
很明显,这形成了一个闭环:想要通过 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,,dn1Rn,其组成的矩阵 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,,dn1)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,,dn1,向量之间的关系被定义为共轭关系

共轭方向

共轭方向的定义表示为:考虑正定矩阵 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,djD;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,djD之间的共轭关系退化为正交关系
    ∀ 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,djD,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=PP=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 xRn,因而对应的两两共轭向量组内最多包含 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,Q0,通过迭代的方式求解 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,,dn1,令:
    坐标轴交替下降法的思路如出一辙,只不过方向选择由原来两两正交的坐标轴作为方向替换为两两共轭的向量作为方向
    x k + 1 = x k + α k ⋅ d k x_{k+1} = x_k + \alpha_k \cdot d_k xk+1=xk+αkdk
  • 其中 α 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+αkdk)Tdk=[Q(xk+αkdk)+C]Tdk=(Qxk+C)Tdk+αk(dk)TQdk0
    最终有:
    α 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,,dn1提前给出。因而不同共轭方向的选择方式对应其相应的共轭方向法。
与牛顿法的描述相似:针对 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 x0x1
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=0n1αidi
如果将 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,,dn1)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(dn1)T Q(d0,,dn1)=[(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 S1S=S1(d0,d1,,dn1)=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=S1(d0,d1,,dn1)=(S1d0,S1d1S1dn1)
    其中展开后矩阵中的元素 S − 1 d i ( i = 0 , 1 , 2 , ⋯   , n − 1 ) \mathcal S^{-1} d_i(i=0,1,2,\cdots,n-1) S1di(i=0,1,2,,n1)表示单位坐标向量 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=Sx^或者 x ^ = S − 1 x \hat x = \mathcal S^{-1} x x^=S1x,从而原始目标函数 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对角阵 STQSx^+(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=0n1αidi,这明显是一个在原始特征空间 x x x上的操作。如果该操作映射在 x ^ \hat x x^的特征空间中会变成什么样的效果 ? ? ?
只需要将 x x x特征空间中的正交向量乘以 S − 1 \mathcal S^{-1} S1即可得到对应 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} S1x0+α0S1d0+α1S1d1++αn1S1dn1
由于 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=S1di(i=1,2,,n1),整理有:
很明显,在 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} S1x0+α0e1+α1e2++αn1en

下一节将继续介绍共轭方向法
0 : 37 : 14 / 1 : 26 : 29 0:37:14/1:26:29 0:37:14/1:26:29

Reference \text{Reference} Reference
最优化理论与方法-第七讲-无约束优化问题(三)文章来源地址https://www.toymoban.com/news/detail-705341.html

到了这里,关于机器学习笔记之最优化理论与方法(十)无约束优化问题——共轭梯度法背景介绍的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 机器学习笔记之最优化理论与方法(二)凸集的简单认识(上)

    本节将介绍关于 凸集 的基本信息,包括 概念 、 基本性质 以及常见凸集。 在 最优化问题 范畴中, 凸优化问题 是一类常见的、并且 性质优秀 的优化问题。一些情况下可以通过 凸优化问题 来解决 非凸优化问题 。 而 凸集合与凸函数 决定了该优化问题是 凸优化问题 。具体

    2024年02月10日
    浏览(38)
  • 无约束最优化方法

    求解无约束最优化的基本思路 给定初始点 x 0 ∈ R n , k = 0 x_0in mathbb{R}^n,k=0 x 0 ​ ∈ R n , k = 0 判断当前解是否满足终止准则,若满足则停止迭代,若不满足则转3. 确定 f ( x ) f(x) f ( x ) 在 x k x_k x k ​ 点的下降方向 确定步长 λ k lambda_k λ k ​ ,使 f ( x k + λ k d k ) f(x_k+lambda_

    2023年04月08日
    浏览(96)
  • 最优化理论笔记及期末复习(《数值最优化》——高立)

    8.3.1实验内容 利用Matlab编程,实现采用简单Armijo非精确线搜索求步长的三种方法:负梯度法、BFGS法及FR共轭梯度法,并求解如下无约束优化问题: m i n f ( x ) = 10 ( x 1 3 − x 2 ) 2 + ( x 1 − 1 ) 2 min f(x) =10(x_1^3-x_2)^2+(x_1-1)^2 m i n f ( x ) = 1 0 ( x 1 3 ​ − x 2 ​ ) 2 + ( x 1 ​ − 1 ) 2 通过

    2024年02月02日
    浏览(41)
  • (最优化理论与方法)第一章最优化简介-第二节:最优化典型实例之稀疏优化和低秩矩阵恢复

    考虑下面线性方程组的求解问题,其中 x ∈ R n , b ∈ R m xin R^{n},bin R^{m} x ∈ R n , b ∈ R m ,矩阵 A ∈ R m × n Ain R^{m×n} A ∈ R m × n ,且向量 b b b 的维数远小于向量 x x x 的维数,也即 m m m n n n A x = b Ax=b A x = b 在相关问题中,当我们建立这样的模型后,常常希望 解出向量

    2024年02月08日
    浏览(44)
  • 25.9 matlab里面的10中优化方法介绍—— 惩罚函数法求约束最优化问题(matlab程序)

    1. 简述          一、算法原理 1、问题引入 之前我们了解过的算法大部分都是无约束优化问题,其算法有:黄金分割法,牛顿法,拟牛顿法,共轭梯度法,单纯性法等。但在实际工程问题中,大多数优化问题都属于有约束优化问题。惩罚函数法就可以将约束优化问题转化为

    2024年02月15日
    浏览(33)
  • 最优化:建模、算法与理论(最优性理论2

    考虑优化问题 min ⁡ x ∈ R n 1 2 ∣ ∣ x − y ∣ ∣ 2 2 , s . t . A x = b min_{x{in}R^n}frac{1}{2}||x-y||_2^2,\\\\ s.t.{quad}Ax=b x ∈ R n min ​ 2 1 ​ ∣∣ x − y ∣ ∣ 2 2 ​ , s . t . A x = b 其中 A ∈ R m × n , b ∈ R m , y ∈ R n A{in}R^{m times n},b{in}R^m,y{in}R^n A ∈ R m × n , b ∈ R m , y ∈ R n 为给定的矩阵

    2024年02月07日
    浏览(43)
  • 【机器学习】最大熵模型【下】最大熵模型学习的最优化算法

    有任何的书写错误、排版错误、概念错误等,希望大家包含指正。 由于字数限制,分成两篇博客。 【机器学习】最大熵模型【上】最大熵模型概述与约束最优化问题 【机器学习】最大熵模型【下】最大熵模型学习的最优化算法 这里的最优化算法就是用于训练最大熵模型参数

    2023年04月15日
    浏览(51)
  • 最优化学习笔记——第三章

    非线性规划比线性规划更困难,没有统一的数学模型,有自己特定的适用范围,目前还没有通用于所有问题的非线性规划问题的算法 满足以上条件的解释可行解,所有解为可行域,如果可行域=R n ,则为无约束问题,否则为有约束问题 如果所有的约束与目标函数都是凸函数,

    2024年02月03日
    浏览(77)
  • 最优化:建模、算法与理论(优化建模)

    目前在学习 最优化:建模、算法与理论这本书,来此记录一下,顺便做一些笔记,在其中我也会加一些自己的理解,尽量写的不会那么的条条框框(当然最基础的还是要有) 本章将从常用的建模技巧开始,接着介绍统计学、信号处理、图像处理以及机器学习中常见的优化模

    2024年02月10日
    浏览(187)
  • 最优化:建模、算法与理论(典型优化问题

    4.1.1 基本形式和应用背景 再次说明一下,其实这本书很多的内容之前肯定大家都学过,但是我觉得这本书和我们之前学的东西的出发角度不一样,他更偏向数学,也多一个角度让我们去理解 线性规划问题的一般形式如下: min ⁡ x ∈ R n c T x s . t . A x = b G x ≤ e (4.1.1) min_{x{

    2024年02月09日
    浏览(246)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包