【最优化期末复习】F

设 Q Q Q 是 n × n n\times n n×n 对称正定矩阵，若 n n n 维向量空间中非零向量 p ⃗ 0 , p ⃗ 1 , ⋯   , p ⃗ m \vec{p}_0,\vec{p}_1,\cdots,\vec{p}_m p ​0​,p ​1​,⋯,p ​m​ 满足： 对于任意的 i , j ∈ { 0 , 1 , 2 , ⋯   , m } ∧ i ≠ j i,j\in\{0,1,2,\cdots,m\}\wedge i\neq j i,j∈{0,1,2,⋯,m}∧i=j，如果： p ⃗ i   T Q p ⃗ j = 0 \vec{p}^{\rm \space T}_iQ\vec{p}_j=0 p ​i T​Qp ​j​=0，则称这些向量是 Q Q Q 的共轭向量。

当 Q = E Q=E Q=E 时，说明向量是正交的，由此可知，正交是一种特殊的共轭。

我对线性流形的概念，感觉跟生成子空间类似，不知道这种理解对不对。。。

初始点： x ⃗ 0 \vec{x}_0 x 0​

目标函数： f ( x ⃗ ) f(\vec{x}) f(x )

目标函数梯度： g ⃗ ( x ⃗ ) = ∇ f ( x ⃗ ) \vec{g}(\vec{x})=\nabla f(\vec{x}) g ​(x )=∇f(x )

初始方向： p ⃗ 0 = − g ⃗ 0 \vec{p}_0=-\vec{g}_0 p ​0​=−g ​0​

x ⃗ k + 1 = x ⃗ k + t k p ⃗ k \vec{x}_{k+1}=\vec{x}_k+t_k\vec{p}_k x k+1​=x k​+tk​p ​k​

p ⃗ k = − g ⃗ k + α k − 1 p ⃗ k − 1      ( k > 0 , k ∈ Z ) \vec{p}_k=-\vec{g}_k+\alpha_{k-1}\vec{p}_{k-1}\space\space\space\space(k>0,k\in Z) p ​k​=−g ​k​+αk−1​p ​k−1​    (k>0,k∈Z)

α k − 1 = ∣ ∣ g ⃗ k ∣ ∣ 2 ∣ ∣ g ⃗ k − 1 ∣ ∣ 2 \alpha_{k-1}=\frac{||\vec{g}_k||^2}{||\vec{g}_{k-1}||^2} αk−1​=∣∣g ​k−1​∣∣2∣∣g ​k​∣∣2​

对于正定二次函数，有： t k = g ⃗ k T g ⃗ k p ⃗ k T Q p ⃗ k t_k=\frac{\vec{g}_k^T\vec{g}_k}{\vec{p}^T_kQ\vec{p}_k} tk​=p ​kT​Qp ​k​g ​kT​g ​k​​

m i n x 1 2 + x 2 2 − x 1 2 x 2 {\rm min} x_1^2+x_2^2-x_1^2x_2 minx12​+x22​−x12​x2​，初始点 x 0 = [ 1 , 1 ] T x_0=[1,1]^{\rm T} x0​=[1,1]T，迭代两次求 x ⃗ 2 \vec{x}_2 x 2​。

解：令 f ( x ⃗ ) = x 1 2 + x 2 2 − x 1 2 x 2 f(\vec{x})=x_1^2+x_2^2-x_1^2x_2 f(x )=x12​+x22​−x12​x2​，则： g ⃗ ( x ⃗ ) = ∇ f ( x ⃗ ) = [ 2 x 1 − 2 x 1 x 2 , 2 x 2 − x 1 2 ] T \vec{g}(\vec{x})=\nabla f(\vec{x})=[2x_1-2x_1x_2,2x_2-x_1^2]^{\rm T} g ​(x )=∇f(x )=[2x1​−2x1​x2​,2x2​−x12​]T进而： g ⃗ 0 = ∇ f ( x ⃗ 0 ) = [ 0 , 1 ] T \vec{g}_0=\nabla f(\vec{x}_0)=[0,1]^{\rm T} g ​0​=∇f(x 0​)=[0,1]T. 取 p ⃗ 0 = − g ⃗ 0 \vec{p}_0=-\vec{g}_0 p ​0​=−g ​0​，有 x ⃗ 1 = x ⃗ 0 − t g ⃗ 0 = [ 1 , 1 − t ] T \vec{x}_1=\vec{x}_0-t\vec{g}_0=[1,1-t]^{\rm T} x 1​=x 0​−tg ​0​=[1,1−t]T f ( x ⃗ 1 ) = ϕ 1 ( t ) = 1 + ( 1 − t ) 2 − ( 1 − t ) = ( 1 − t ) 2 + t f(\vec{x}_1)=\phi_1(t)=1+(1-t)^2-(1-t)=(1-t)^2+t f(x 1​)=ϕ1​(t)=1+(1−t)2−(1−t)=(1−t)2+t ϕ 1 ′ ( t ) = − 2 ( 1 − t ) + 1 = 2 t − 1 \phi_1^\prime(t)=-2(1-t)+1=2t-1 ϕ1′​(t)=−2(1−t)+1=2t−1 令 ϕ 1 ′ ( t ) = 0 \phi_1^\prime(t)=0 ϕ1′​(t)=0，得： t = 1 2 t=\frac{1}{2} t=21​，所以： x 1 = [ 1 , 1 2 ] T x_1=[1,\frac{1}{2}]^{\rm T} x1​=[1,21​]T

进而： g ⃗ 1 = ∇ f ( x ⃗ 1 ) = [ 1 , 0 ] T \vec{g}_1=\nabla f(\vec{x}_1)=[1,0]^{\rm T} g ​1​=∇f(x 1​)=[1,0]T α 0 = ∣ ∣ g ⃗ 1 ∣ ∣ 2 ∣ ∣ g ⃗ 0 ∣ ∣ 2 = 1 \alpha_0=\frac{||\vec{g}_1||^2}{||\vec{g}_0||^2}=1 α0​=∣∣g ​0​∣∣2∣∣g ​1​∣∣2​=1 p ⃗ 1 = − g ⃗ 1 + α 0 p ⃗ 0 = − g ⃗ 1 − g ⃗ 0 = [ − 1 , − 1 ] T \vec{p}_1=-\vec{g}_1+\alpha_0\vec{p}_0=-\vec{g}_1-\vec{g}_0=[-1,-1]^{\rm T} p ​1​=−g ​1​+α0​p ​0​=−g ​1​−g ​0​=[−1,−1]T x ⃗ 2 = x ⃗ 1 + t p ⃗ 1 = [ 1 − t , 1 2 − t ] T \vec{x}_2=\vec{x}_1+t\vec{p}_1=[1-t,\frac{1}{2}-t]^{\rm T} x 2​=x 1​+tp ​1​=[1−t,21​−t]T f ( x ⃗ 2 ) = ϕ 2 ( t ) = ( 1 − t ) 2 + ( 1 2 − t ) 2 − ( 1 − t ) 2 ( 1 2 − t ) f(\vec{x}_2)=\phi_2(t)=(1-t)^2+(\frac{1}{2}-t)^2-(1-t)^2(\frac{1}{2}-t) f(x 2​)=ϕ2​(t)=(1−t)2+(21​−t)2−(1−t)2(21​−t) ϕ 2 ′ ( t ) = 3 t 2 − t − 1 \phi_2^\prime(t)=3t^2-t-1 ϕ2′​(t)=3t2−t−1令 ϕ 2 ′ ( t ) = 0 \phi_2^\prime(t)=0 ϕ2′​(t)=0，得： t = 1 + 13 6 t=\frac{1+\sqrt{13}}{6} t=61+13 ​​，于是： x ⃗ 2 = [ 5 − 13 6 , 2 − 13 6 ] T \vec{x}_2=[\frac{5-\sqrt{13}}{6},\frac{2-\sqrt{13}}{6}]^{\rm T} x 2​=[65−13 ​​,62−13 ​​]T