考虑求解这个无约束优化问题：min x ∈ R n f ( x ) \min _{\boldsymbol{x} \in \mathbb{R}^{n}} f(\boldsymbol{x}) min x ∈ R n f ( x )
选取初始点 x 0 ∈ R n x^{0} \in \mathbb{R}^{n} x 0 ∈ R n x 1 , x 2 , ⋯ , x k x^{1}, x^{2}, \cdots, x^{k} x 1 , x 2 , ⋯ , x k { x k } \{\boldsymbol{x}^{k}\} { x k } x k \boldsymbol{x}^{k} x k { x k } \{\boldsymbol{x}^{k}\} { x k }
迭代的定义：x k x^{k} x k d k \boldsymbol{d}^{k} d k x = x k + α d k ( α > 0 ) \boldsymbol{x}=\boldsymbol{x}^{k}+\alpha \boldsymbol{d}^{k}(\alpha>0) x = x k + α d k ( α > 0 ) α k \alpha_{k} α k x k + 1 = x k + α k d k \boldsymbol{x}^{k+1}=\boldsymbol{x}^{k}+\alpha_{k} \boldsymbol{d}^{k} x k + 1 = x k + α k d k
通常希望： f ( x k + 1 ) ≤ f ( x k ) f(\boldsymbol{x}^{k+1}) \leq f(\boldsymbol{x}^{k}) f ( x k + 1 ) ≤ f ( x k )
d k \boldsymbol{d}^{k} d k 在点 x k x^{k} x k p k ≠ 0 p^{k} \neq 0 p k = 0 δ > 0 \delta>0 δ > 0 α ∈ ( 0 , δ ) \alpha \in(0, \delta) α ∈ ( 0 , δ ) f ( x k + α p k ) < f ( x k ) f(\boldsymbol{x}^{k}+\alpha \boldsymbol{p}^{k})<f(\boldsymbol{x}^{k}) f ( x k + α p k ) < f ( x k ) p k \boldsymbol{p}^{k} p k f ( x ) f(\boldsymbol{x}) f ( x ) x k \boldsymbol{x}^{k} x k
设函数 f : Ω ⊆ R n → R f: \Omega \subseteq \mathbb{R}^{n} \rightarrow \mathbb{R} f : Ω ⊆ R n → R x k \boldsymbol{x}^{k} x k p ∈ R n \boldsymbol{p} \in \mathbb{R}^{n} p ∈ R n n n n ∇ f ( x k ) T p < 0 \nabla f(\boldsymbol{x}^{k})^{\mathrm{T}} \boldsymbol{p}<0 ∇ f ( x k ) T p < 0 p p p f ( x ) f(x) f ( x ) x k x^{k} x k
α k \alpha_{k} α k 确定了搜索方向 d k \boldsymbol{d}^{k} d k α k \alpha_{k} α k
固定步长法：将步长 α k \alpha_{k} α k α k = 1 \alpha_{k}=1 α k = 1
可接受步长法：在能够保证目标函数值下降或整体下降的前提下，步长 α k \alpha_{k} α k
（精确）一维搜索或（精确）线搜索：沿搜索方向使目标函数值下降最多，即沿射线 x = x k + α d k ( α > 0 ) \boldsymbol{x}=\boldsymbol{x}^{k}+\alpha \boldsymbol{d}^{k}(\alpha>0) x = x k + α d k ( α > 0 ) f ( x k + α d k ) f(\boldsymbol{x}^{k}+\alpha \boldsymbol{d}^{k}) f ( x k + α d k )
具体而言，（精确）一维搜索或（精确）线搜索在确定步长 α k \alpha_{k} α k α k > 0 \alpha_{k}>0 α k > 0 f ( x k + α k d k ) = min α > 0 f ( x k + α d k ) f(\boldsymbol{x}^{k}+\alpha_{k} \boldsymbol{d}^{k})=\min _{\alpha>0} f(\boldsymbol{x}^{k}+\alpha \boldsymbol{d}^{k}) f ( x k + α k d k ) = min α > 0 f ( x k + α d k ) α k = arg min α > 0 f ( x k + α d k ) \alpha_{k}=\arg \min _{\alpha>0} f(\boldsymbol{x}^{k}+\alpha \boldsymbol{d}^{k}) α k = arg min α > 0 f ( x k + α d k ) min α > 0 f ( x k + α d k ) ⇔ min α > 0 f ( α ) \min _{\alpha>0} f(\boldsymbol{x}^{k}+\alpha \boldsymbol{d}^{k}) \Leftrightarrow \min _{\alpha>0} f(\alpha) min α > 0 f ( x k + α d k ) ⇔ min α > 0 f ( α )
给定初始点 x 0 \boldsymbol{x}^{0} x 0 k = 0 k=0 k = 0
确定 x k \boldsymbol{x}^{k} x k d k \boldsymbol{d}^{k} d k
确定步长 α k > 0 \alpha_{k}>0 α k > 0 f ( x k + α k d k ) ≤ f ( x k ) f(\boldsymbol{x}^{k}+\alpha_{k} \boldsymbol{d}^{k}) \leq f(\boldsymbol{x}^{k}) f ( x k + α k d k ) ≤ f ( x k )
令 x k + 1 = x k + α k d k \boldsymbol{x}^{k+1}=\boldsymbol{x}^{k}+\alpha_{k} \boldsymbol{d}^{k} x k + 1 = x k + α k d k
若 x k + 1 x^{k+1} x k + 1 k = k + 1 k=k+1 k = k + 1
收敛性
算法收敛：存在正整数 N N N x N = x ∗ \boldsymbol{x}^{N}=\boldsymbol{x}^{*} x N = x ∗ lim k → + ∞ x k = x ∗ \lim _{k \rightarrow+\infty} \boldsymbol{x}^{k}=\boldsymbol{x}^{*} lim k → + ∞ x k = x ∗
局部收敛：存在 x ∗ \boldsymbol{x}^{*} x ∗ N δ ( x ∗ ) N_{\delta}(\boldsymbol{x}^{*}) N δ ( x ∗ ) x 0 ∈ N δ ( x ∗ ) \boldsymbol{x}^{0} \in N_{\delta}(\boldsymbol{x}^{*}) x 0 ∈ N δ ( x ∗ ) { x k } \{x^{k}\} { x k } x ∗ x^{*} x ∗
全局收敛：在定义域内任取初值 x 0 \boldsymbol{x}^{0} x 0 { x k } \{\boldsymbol{x}^{k}\} { x k } x ∗ x^{*} x ∗
收敛速度
线性收敛：x ∗ \boldsymbol{x}^{*} x ∗ min f ( x ) \min f(\boldsymbol{x}) min f ( x ) x ∈ R n \boldsymbol{x} \in \mathbb{R}^{n} x ∈ R n A A A { x k } \{\boldsymbol{x}^{k}\} { x k } x ∗ \boldsymbol{x}^{*} x ∗ lim k → + ∞ x k = x ∗ \lim _{k \rightarrow+\infty} x^{k}=x^{*} lim k → + ∞ x k = x ∗ k k k β ∈ ( 0 , 1 ) \beta \in(0,1) β ∈ ( 0 , 1 ) k 0 k_{0} k 0 k ≥ k 0 k \geq k_{0} k ≥ k 0 ∥ x k + 1 − x ∗ ∥ 2 ≤ β ∥ x k − x ∗ ∥ 2 \|\boldsymbol{x}^{k+1}-\boldsymbol{x}^{*}\|_{2} \leq \beta\|\boldsymbol{x}^{k}-\boldsymbol{x}^{*}\|_{2} ∥ x k + 1 − x ∗ ∥ 2 ≤ β ∥ x k − x ∗ ∥ 2 { x k } \{\boldsymbol{x}^{k}\} { x k } A A A
不失一般性，可以假设上式对于任意 k ≥ 0 k \geq 0 k ≥ 0
∥ x k − x ∗ ∥ 2 ≤ β ∥ x k − 1 − x ∗ ∥ 2 ≤ β 2 ∥ x k − 2 − x ∗ ∥ 2 ≤ ⋯ ≤ β k ∥ x 0 − x ∗ ∥ 2 \|x^{k}-x^{*}\|_{2} \leq \beta\|x^{k-1}-x^{*}\|_{2}
\leq \beta^{2}\|x^{k-2}-x^{*}\|_{2}
\leq \cdots \leq \beta^{k}\|x^{0}-x^{*}\|_{2}
∥ x k − x ∗ ∥ 2 ≤ β ∥ x k − 1 − x ∗ ∥ 2 ≤ β 2 ∥ x k − 2 − x ∗ ∥ 2 ≤ ⋯ ≤ β k ∥ x 0 − x ∗ ∥ 2
即 lim k → + ∞ ∥ x k − x ∗ ∥ 2 = 0 \lim _{k \rightarrow+\infty}\|\boldsymbol{x}^{k}-\boldsymbol{x}^{*}\|_{2}=0 lim k → + ∞ ∥ x k − x ∗ ∥ 2 = 0 k → ∞ k \rightarrow \infty k → ∞ x k x^{k} x k x ∗ x^{*} x ∗ β \beta β
p 阶收敛：设由算法 A A A { x k } \{\boldsymbol{x}^{k}\} { x k } x ∗ \boldsymbol{x}^{*} x ∗ k k k β > 0 \beta>0 β > 0 p > 1 p>1 p > 1 k 0 k_{0} k 0 k ≥ k 0 k \geq k_{0} k ≥ k 0 ∥ x k + 1 − x ∗ ∥ 2 ≤ β ∥ x k − x ∗ ∥ 2 p \|\boldsymbol{x}^{k+1}-\boldsymbol{x}^{*}\|_{2} \leq \beta\|\boldsymbol{x}^{k}-\boldsymbol{x}^{*}\|_{2}^{p} ∥ x k + 1 − x ∗ ∥ 2 ≤ β ∥ x k − x ∗ ∥ 2 p { x k } \{\boldsymbol{x}^{k}\} { x k } { x k } \{\boldsymbol{x}^{k}\} { x k } A A A
当 1<p<2 时，则称序列 { x k } \{\boldsymbol{x}^{k}\} { x k }
当 p=2 时，则称序列 { x k } \{\boldsymbol{x}^{k}\} { x k }
该定义中，数值解与最优解间的差异性用范数 ∥ ⋅ ∥ 2 \|\cdot\|_{2} ∥ ⋅ ∥ 2 ∥ ⋅ ∥ 2 \|\cdot\|_{2} ∥ ⋅ ∥ 2
终止准则 { x k } \{\boldsymbol{x}^{k}\} { x k } x ∗ \boldsymbol{x}^{*} x ∗
若算法可以收敛，则当 ∥ x k − x ∗ ∥ 2 \|\boldsymbol{x}^{k}-\boldsymbol{x}^{*}\|_{2} ∥ x k − x ∗ ∥ 2 ∥ x k + 1 − x k ∥ 2 \|\boldsymbol{x}^{k+1}-\boldsymbol{x}^{k}\|_{2} ∥ x k + 1 − x k ∥ 2 ∥ x k + 1 − x k ∥ 2 ≤ ϵ 1 \|\boldsymbol{x}^{k+1}-\boldsymbol{x}^{k}\|_{2} \leq \epsilon_{1} ∥ x k + 1 − x k ∥ 2 ≤ ϵ 1 ∥ x k + 1 − x k ∥ 2 ≤ ϵ 1 ′ ∥ x k ∥ 2 \|\boldsymbol{x}^{k+1}-\boldsymbol{x}^{k}\|_{2} \leq \epsilon_{1}^{\prime}\|\boldsymbol{x}^{k}\|_{2} ∥ x k + 1 − x k ∥ 2 ≤ ϵ 1 ′ ∥ x k ∥ 2 ∣ f ( x k + 1 ) − f ( x k ) ∣ ≤ ϵ 2 |f(\boldsymbol{x}^{k+1})-f(\boldsymbol{x}^{k})| \leq \epsilon_{2} ∣ f ( x k + 1 ) − f ( x k ) ∣ ≤ ϵ 2 ∣ f ( x k + 1 ) − f ( x k ) ∣ ≤ ϵ 2 ′ ∣ f ( x k ) ∣ |f(\boldsymbol{x}^{k+1})-f(\boldsymbol{x}^{k})| \leq \epsilon_{2}^{\prime}|f(\boldsymbol{x}^{k})| ∣ f ( x k + 1 ) − f ( x k ) ∣ ≤ ϵ 2 ′ ∣ f ( x k ) ∣ ∥ ∇ f ( x k ) ∥ 2 ≤ ϵ 3 \|\nabla f(\boldsymbol{x}^{k})\|_{2} \leq \epsilon_{3} ∥ ∇ f ( x k ) ∥ 2 ≤ ϵ 3
若目标函数一维可导，通常采用解析法求解最优步长α k \alpha_{k} α k d f ( x ) d x = 0 \frac{d f(x)}{d x}=0 d x d f ( x ) = 0
在进行最优解的计算前，先要进行搜索区间的确定。
搜索区间：设 f ( x ) f(x) f ( x ) x ∗ = arg min x f ( x ) x^{*}=\arg \min _{x} f(x) x ∗ = arg min x f ( x ) [ a , b ] [a, b] [ a , b ] x ∗ ∈ ( a , b ) x^{*} \in(a, b) x ∗ ∈ ( a , b ) [ a , b ] [a, b] [ a , b ]
单谷函数：若 x ∗ x^{*} x ∗ f ( x ) f(x) f ( x ) [ a , x ∗ ] [a, x^{*}] [ a , x ∗ ] [ x ∗ , b ] [x^{*}, b] [ x ∗ , b ] f ( x ) f(x) f ( x ) [ a , b ] [a, b] [ a , b ]
方法1 ：f ( x ) f(x) f ( x )
任意选一个初始点 x 0 x_{0} x 0 Δ x \Delta x Δ x
若 f ′ ( x 0 ) < 0 f^{\prime}(x_{0})<0 f ′ ( x 0 ) < 0 x 0 x_{0} x 0 x 1 = x 0 + Δ x x_{1}=x_{0}+\Delta x x 1 = x 0 + Δ x
若 f ′ ( x 1 ) > 0 f^{\prime}(x_{1})>0 f ′ ( x 1 ) > 0 [ a , b ] = [ x 0 , x 1 ] [a, b]=[x_{0}, x_{1}] [ a , b ] = [ x 0 , x 1 ]
若 f ′ ( x 1 ) < 0 f^{\prime}(x_{1})<0 f ′ ( x 1 ) < 0 x 0 = x 1 x_{0}=x_{1} x 0 = x 1
若 f ′ ( x 0 ) > 0 f^{\prime}(x_{0})>0 f ′ ( x 0 ) > 0
方法2 （进退法）（无需计算导数）：x 1 x_{1} x 1 Δ x > 0 \Delta x>0 Δ x > 0
x 2 = x 1 + Δ x x_{2}=x_{1}+\Delta x x 2 = x 1 + Δ x f ( x 1 ) f(x_{1}) f ( x 1 ) f ( x 2 ) f(x_{2}) f ( x 2 ) f ( x 1 ) ≥ f ( x 2 ) f(x_{1}) \geq f(x_{2}) f ( x 1 ) ≥ f ( x 2 ) 令 Δ x = 2 Δ x ， x 3 = x 2 + Δ x \Delta x=2 \Delta x， x_{3}=x_{2}+\Delta x Δ x = 2 Δ x ， x 3 = x 2 + Δ x f ( x 3 ) f(x_{3}) f ( x 3 ) f ( x 2 ) ≤ f ( x 3 ) f(x_{2}) \leq f(x_{3}) f ( x 2 ) ≤ f ( x 3 ) [ x 1 , x 3 ] [x_{1}, x_{3}] [ x 1 , x 3 ] f ( x 2 ) > f ( x 3 ) f(x_{2})>f(x_{3}) f ( x 2 ) > f ( x 3 ) x 1 = x 2 ， x 2 = x 3 x_{1}=x_{2}， x_{2}=x_{3} x 1 = x 2 ， x 2 = x 3
令 x 3 = x 2 x_{3}=x_{2} x 3 = x 2 x 2 = x 1 x_{2}=x_{1} x 2 = x 1 Δ x = 2 Δ x \Delta x=2 \Delta x Δ x = 2 Δ x x 1 = x 2 − Δ x x_{1}=x_{2}-\Delta x x 1 = x 2 − Δ x f ( x 1 ) f(x_{1}) f ( x 1 ) f ( x 1 ) ≥ f ( x 2 ) f(x_{1}) \geq f(x_{2}) f ( x 1 ) ≥ f ( x 2 ) [ x 1 , x 3 ] [x_{1}, x_{3}] [ x 1 , x 3 ] f ( x 1 ) < f ( x 2 ) f(x_{1})<f(x_{2}) f ( x 1 ) < f ( x 2 )
得到初始搜索区间后，可以采用试探法或函数逼近法进一步求解最优步长。
基本思想：从一个包含极小点的初始区间 [ a , b ] [a, b] [ a , b ]
①二分法
基本思想：f ( x ) f(x) f ( x ) [ a k , b k ] [a_{k}, b_{k}] [ a k , b k ] f ′ ( a k ) < 0 f^{\prime}(a_{k})<0 f ′ ( a k ) < 0 f ′ ( b k ) > 0 f^{\prime}(b_{k})>0 f ′ ( b k ) > 0 c k = ( a k + b k ) 2 c_{k}=\frac{(a_{k}+b_{k})}{2} c k = 2 ( a k + b k ) f ′ ( c k ) = 0 f^{\prime}(c_{k})=0 f ′ ( c k ) = 0 c k c_{k} c k f ′ ( c k ) > 0 f^{\prime}(c_{k})>0 f ′ ( c k ) > 0 a k + 1 = a k , b k + 1 = c k a_{k+1}=a_{k}, b_{k+1}=c_{k} a k + 1 = a k , b k + 1 = c k f ′ ( c k ) < 0 f^{\prime}(c_{k})<0 f ′ ( c k ) < 0 a k + 1 = c k , b k + 1 = b k a_{k+1}=c_{k}, b_{k+1}=b_{k} a k + 1 = c k , b k + 1 = b k [ a , b ] [a, b] [ a , b ]
算法步骤：
给定初始区间 [ a 1 , b 1 ] [a_{1}, b_{1}] [ a 1 , b 1 ] f ′ ( a 1 ) < 0 , f ′ ( b 1 ) > 0 f^{\prime}(a_{1})<0, f^{\prime}(b_{1})>0 f ′ ( a 1 ) < 0 , f ′ ( b 1 ) > 0 ϵ > 0 \epsilon>0 ϵ > 0 k = 1 k=1 k = 1
若 ∣ b k − a k ∣ ≤ ϵ |b_{k}-a_{k}| \leq \epsilon ∣ b k − a k ∣ ≤ ϵ c k = a k + b k 2 c_{k}=\frac{a_{k}+b_{k}}{2} c k = 2 a k + b k
计算 f ′ ( c k ) f^{\prime}(c_{k}) f ′ ( c k ) f ′ ( c k ) = 0 f^{\prime}(c_{k})=0 f ′ ( c k ) = 0 x ∗ = c k x^{*}=c_{k} x ∗ = c k f ′ ( c k ) < 0 f^{\prime}(c_{k})<0 f ′ ( c k ) < 0 a k + 1 = c k , b k + 1 = b k a_{k+1}=c_{k}, b_{k+1}=b_{k} a k + 1 = c k , b k + 1 = b k f ′ ( c k ) > 0 f^{\prime}(c_{k})>0 f ′ ( c k ) > 0 a k + 1 = a k , b k + 1 = c k a_{k+1}=a_{k}, b_{k+1}=c_{k} a k + 1 = a k , b k + 1 = c k
令 k = k + 1 k=k+1 k = k + 1
适用条件：二分法适用于 f ( x ) f(x) f ( x )
优点：
每次以搜索区间的中点作为试探点，计算量小，算法简洁易于实现；
总能收敛到一个局部极小点。
缺点：
②黄金分割法
基本思想：[ a k , b k ] [a_{k}, b_{k}] [ a k , b k ] λ k \lambda_{k} λ k μ k \mu_{k} μ k
算法步骤：
设置初始区间 [ a 1 , b 1 ] [a_{1}, b_{1}] [ a 1 , b 1 ] ϵ > 0 \epsilon>0 ϵ > 0 λ 1 = a 1 + 0.382 ( b 1 − a 1 ) \lambda_{1}=a_{1}+0.382(b_{1}-a_{1}) λ 1 = a 1 + 0 . 3 8 2 ( b 1 − a 1 ) μ 1 = a 1 + 0.618 ( b 1 − a 1 ) \mu_{1}=a_{1}+0.618(b_{1}-a_{1}) μ 1 = a 1 + 0 . 6 1 8 ( b 1 − a 1 ) f ( λ 1 ) , f ( μ 1 ) f(\lambda_{1}), f(\mu_{1}) f ( λ 1 ) , f ( μ 1 ) k = 1 k=1 k = 1
若 ∣ b k − a k ∣ ≤ ϵ |b_{k}-a_{k}| \leq \epsilon ∣ b k − a k ∣ ≤ ϵ x ∗ = a k + b k 2 x^{*}=\frac{a_{k}+b_{k}}{2} x ∗ = 2 a k + b k f ( λ k ) > f ( μ k ) f(\lambda_{k})>f(\mu_{k}) f ( λ k ) > f ( μ k ) f ( λ k ) ≤ f ( μ k ) f(\lambda_{k}) \leq f(\mu_{k}) f ( λ k ) ≤ f ( μ k )
令 [ a k + 1 , b k + 1 ] = [ λ k , b k ] [a_{k+1}, b_{k+1}]=[\lambda_{k}, b_{k}] [ a k + 1 , b k + 1 ] = [ λ k , b k ] λ k + 1 = μ k \lambda_{k+1}=\mu_{k} λ k + 1 = μ k f ( λ k + 1 ) = f ( μ k ) f(\lambda_{k+1})=f(\mu_{k}) f ( λ k + 1 ) = f ( μ k ) μ k + 1 = a k + 1 + 0.618 ( b k + 1 − a k + 1 ) \mu_{k+1}=a_{k+1}+0.618(b_{k+1}-a_{k+1}) μ k + 1 = a k + 1 + 0 . 6 1 8 ( b k + 1 − a k + 1 ) f ( μ k + 1 ) f(\mu_{k+1}) f ( μ k + 1 )
令 [ a k + 1 , b k + 1 ] = [ a k , μ k ] [a_{k+1}, b_{k+1}]=[a_{k}, \mu_{k}] [ a k + 1 , b k + 1 ] = [ a k , μ k ] μ k + 1 = λ k \mu_{k+1}=\lambda_{k} μ k + 1 = λ k f ( μ k + 1 ) = f ( λ k ) f(\mu_{k+1})=f(\lambda_{k}) f ( μ k + 1 ) = f ( λ k ) λ k + 1 = a k + 1 + 0.382 ( b k + 1 − a k + 1 ) \lambda_{k+1}=a_{k+1}+0.382(b_{k+1}-a_{k+1}) λ k + 1 = a k + 1 + 0 . 3 8 2 ( b k + 1 − a k + 1 ) f ( λ k + 1 ) f(\lambda_{k+1}) f ( λ k + 1 )
令 k = k + 1 k=k+1 k = k + 1
适用条件：黄金分割法对函数的要求较低，函数可以不连续。因为该算法仅利用函数值而非函数的导数来缩小搜索区间。
优点：
对函数要求低，不要求函数可微，只需要计算函数值；
新区间里包含原来的试探点，且该试探点在下一步被利用 (即每次只需计算一个试探点)，计算量小；
试探点的计算公式一致。
收敛性：
补充：为什么采用0.618作为分割比？
记当前的搜索区间为 [ a k , b k ] [a_{k}, b_{k}] [ a k , b k ] λ k \lambda_{k} λ k μ k \mu_{k} μ k λ k < μ k \lambda_{k}<\mu_{k} λ k < μ k f ( λ k ) ≤ f ( μ k ) f(\lambda_{k}) \leq f(\mu_{k}) f ( λ k ) ≤ f ( μ k ) x ∗ ∈ [ a k , μ k ] x^{*} \in[a_{k}, \mu_{k}] x ∗ ∈ [ a k , μ k ] f ( λ k ) > f ( μ k ) f(\lambda_{k})>f(\mu_{k}) f ( λ k ) > f ( μ k ) x ∗ ∈ [ λ k , b k ] x^{*} \in[\lambda_{k}, b_{k}] x ∗ ∈ [ λ k , b k ] [ a k , μ k ] [a_{k}, \mu_{k}] [ a k , μ k ] [ λ k , b k ] [\lambda_{k}, b_{k}] [ λ k , b k ]
为了机会均等，我们选取对称的试点，即μ k − a k = b k − λ k \mu_{k}-a_{k}=b_{k}-\lambda_{k} μ k − a k = b k − λ k b k + 1 − a k + 1 = ρ ( b k − a k ) b_{k+1}-a_{k+1}=\rho(b_{k}-a_{k}) b k + 1 − a k + 1 = ρ ( b k − a k ) 0 < ρ < 1 0<\rho<1 0 < ρ < 1
分情况讨论：f ( λ k ) ≤ f ( μ k ) f(\lambda_{k}) \leq f(\mu_{k}) f ( λ k ) ≤ f ( μ k ) [ a k + 1 , b k + 1 ] = [ a k , μ k ] [a_{k+1}, b_{k+1}]=[a_{k}, \mu_{k}] [ a k + 1 , b k + 1 ] = [ a k , μ k ]
λ k = a k + ( 1 − ρ ) ( b k − a k ) , μ k = a k + ρ ( b k − a k ) \begin{aligned}
\lambda_{k} & =a_{k}+(1-\rho)(b_{k}-a_{k}), \\
\mu_{k} & =a_{k}+\rho(b_{k}-a_{k})
\end{aligned} λ k μ k = a k + ( 1 − ρ ) ( b k − a k ) , = a k + ρ ( b k − a k )
同理，当 f ( λ k ) > f ( μ k ) f(\lambda_{k})>f(\mu_{k}) f ( λ k ) > f ( μ k )
可见，一旦 0 < ρ < 1 0<\rho<1 0 < ρ < 1 λ k \lambda_{k} λ k μ k \mu_{k} μ k ρ \rho ρ
类似上一页的做法，再分情况讨论，发现f ( λ k ) ≤ f ( μ k ) f(\lambda_{k}) \leq f(\mu_{k}) f ( λ k ) ≤ f ( μ k ) [ a k + 1 , b k + 1 ] = [ a k , μ k ] [a_{k+1}, b_{k+1}]=[a_{k}, \mu_{k}] [ a k + 1 , b k + 1 ] = [ a k , μ k ] μ k + 1 = a k + 1 + ρ ( b k + 1 − a k + 1 ) = a k + ρ 2 ( b k − a k ) \mu_{k+1}=a_{k+1}+\rho(b_{k+1}-a_{k+1})=a_{k}+\rho^{2}(b_{k}-a_{k}) μ k + 1 = a k + 1 + ρ ( b k + 1 − a k + 1 ) = a k + ρ 2 ( b k − a k ) λ k = a k + ( 1 − ρ ) ( b k − a k ) \lambda_{k}=a_{k}+(1-\rho)(b_{k}-a_{k}) λ k = a k + ( 1 − ρ ) ( b k − a k ) ρ 2 = 1 − ρ \rho^{2}=1-\rho ρ 2 = 1 − ρ μ k + 1 = λ k \mu_{k+1}=\lambda_{k} μ k + 1 = λ k k + 1 k+1 k + 1 μ k + 1 \mu_{k+1} μ k + 1 f ( λ k ) > f ( μ k ) f(\lambda_{k})>f(\mu_{k}) f ( λ k ) > f ( μ k ) [ a k + 1 , b k + 1 ] = [ λ k , b k ] [a_{k+1}, b_{k+1}]=[\lambda_{k}, b_{k}] [ a k + 1 , b k + 1 ] = [ λ k , b k ] ρ 2 = 1 − ρ \rho^{2}=1-\rho ρ 2 = 1 − ρ λ k + 1 = μ k \lambda_{k+1}=\mu_{k} λ k + 1 = μ k k + 1 k+1 k + 1 λ k + 1 \lambda_{k+1} λ k + 1
解方程 ρ 2 = 1 − ρ \rho^{2}=1-\rho ρ 2 = 1 − ρ ρ > 0 \rho>0 ρ > 0 ρ = 5 − 1 2 ≈ 0.618 \rho=\frac{\sqrt{5}-1}{2} \approx 0.618 ρ = 2 5 − 1 ≈ 0 . 6 1 8 ρ = − 5 − 1 2 \rho=\frac{-\sqrt{5}-1}{2} ρ = 2 − 5 − 1
λ k = a k + 0.382 ( b k − a k ) , μ k = a k + 0.618 ( b k − a k ) 0 \begin{aligned}
\lambda_{k} & =a_{k}+0.382(b_{k}-a_{k}), \\
\mu_{k} & =a_{k}+0.618(b_{k}-a_{k})_{0}
\end{aligned} λ k μ k = a k + 0 . 3 8 2 ( b k − a k ) , = a k + 0 . 6 1 8 ( b k − a k ) 0
由于区间缩短率 ρ \rho ρ ρ 1 = 1 − ρ ρ \frac{\rho}{1}=\frac{1-\rho}{\rho} 1 ρ = ρ 1 − ρ
基本思想：
牛顿迭代公式：x k x^{k} x k f ( x ) f(x) f ( x ) x k x^{k} x k g k ( x ) = f ( x k ) + f ′ ( x k ) ( x − x k ) + 1 2 f ′ ′ ( x k ) ( x − x k ) 2 g_{k}(x)=f(x^{k})+f^{\prime}(x^{k})(x-x^{k})+\frac{1}{2} f^{\prime \prime}(x^{k})(x-x^{k})^{2} g k ( x ) = f ( x k ) + f ′ ( x k ) ( x − x k ) + 2 1 f ′ ′ ( x k ) ( x − x k ) 2 x x x g k ′ ( x ) = 0 g_{k}^{\prime}(x)=0 g k ′ ( x ) = 0 f ′ ( x k ) + f ′ ′ ( x k ) ( x − x k ) = 0 f^{\prime}(x^{k})+f^{\prime \prime}(x^{k})(x-x^{k})=0 f ′ ( x k ) + f ′ ′ ( x k ) ( x − x k ) = 0 x = x k − f ′ ( x k ) f ′ ′ ( x k ) x=x^{k}-\frac{f^{\prime}(x^{k})}{f^{\prime \prime}(x^{k})} x = x k − f ′ ′ ( x k ) f ′ ( x k ) x k + 1 = x k − f ′ ( x k ) f ′ ′ ( x k ) x^{k+1}=x^{k}-\frac{f^{\prime}(x^{k})}{f^{\prime \prime}(x^{k})} x k + 1 = x k − f ′ ′ ( x k ) f ′ ( x k )
算法步骤：
给定初始点 x 0 ∈ R x^{0} \in \mathbb{R} x 0 ∈ R 0 ≤ ϵ ≪ 1 0 \leq \epsilon \ll 1 0 ≤ ϵ ≪ 1 k = 0 k=0 k = 0
计算 f ′ ( x k ) f^{\prime}(x^{k}) f ′ ( x k ) ∣ f ′ ( x k ) ∣ ≤ ϵ |f^{\prime}(x^{k})| \leq \epsilon ∣ f ′ ( x k ) ∣ ≤ ϵ f ′ ′ ( x k ) f^{\prime \prime}(x^{k}) f ′ ′ ( x k ) x k + 1 = x k − f ′ ( x k ) f ′ ′ ( x k ) x^{k+1}=x^{k}-\frac{f^{\prime}(x^{k})}{f^{\prime \prime}(x^{k})} x k + 1 = x k − f ′ ′ ( x k ) f ′ ( x k )
令 k = k + 1 k=k+1 k = k + 1
适用条件：牛顿法适用于二阶连续可导函数求极值问题。
优点：
对于严格凸二次函数求极值，一步迭代即可找到最优解；
如果初始点距离极小点较近，算法会很快收敛于极小点。
缺点：
对初始点要求高，若初始点距离极小点太远，则迭代过程可能不收敛，也可能收敛到极大点，即牛顿法的收敛性依赖于初始点的选择；
对函数要求高，牛顿法适用于二阶连续可导函数求极值问题；
需计算二阶导数，计算复杂度高。
