Solving Nonlinear Equations
Bisection Algorithm
The goal is to find a root x0∈[a,b]such that f(x0)=0
First we must check that sign(f(a))≠sign(f(b))
- Let c=a+b/2.
- If f(c)=0, stop and return c.
- If sign(f(a))≠sign(f(c), then set b←c. Else if sign(f(b))≠sign(f(c)), then set a←c
- Goto the beginning and repeat until convergence (see below).
这种方法的优点是简单直观，不需要对f了解太多复杂信息只需对取值做出判断即可；缺点是只在一维上可行，而且是线性的，收敛速度慢。而且对于复杂函数, a和b的取值需要摸索（f(a)和f(b)正负号不同，对于如反比例函数，即使f(a)和f(b)正负号不同，也没有根）。
对于这种方法的收敛程度，可以通过|b−a|<ε 或者|f(b)−f(a)|<ε来衡量
Example: Quantiles
二分法应用实例：求累积分布函数的分位数：定义F(x)为累积分布函数，p为概率值，求x使得F(x)=p
只要求x满足g(x)=0即可
Rates of Convergence
评估和比较算法时可以比较他们收敛到一定范围的速度。有三种类型的收敛速率从慢到快依次是：
linear(线性）、superlinear（超线性）、quadratic（二次）
收敛速率很大程度上由算法对x更新过程中对f函数本身信息的利用程度决定。比如二分法在x更新过程中就没怎么利用到f，所以收敛速度慢。
Algorithms that require more information about f, such as derivative information（微分信息）, typically converge more quickly. There is no free lunch!
Linear convergence
假设有一个序列{xn}， xn→x∞ in Rk. 我们定义线性收敛：如果存在 r∈(0,1)，使得：
其中n足够大
Example
举例一个简单的序列：
这个序列线性收敛于1，因为
这里的r是在(0,1)内的
Superlinear Convergence
我们把超线性收敛定义为：
举例如：
超线性收敛于1。
Quadratic Convergence
二次收敛是收敛最快的。定义为：存在常数M：0<M<∞，使得
当n足够大。
Functional iteration函数迭代法
The Shrinking Lemma
收缩引理定义了在什么情况下函数迭代(functional iteration)最终会收敛于一定值上。
在数学中，函数的不动点（Fixed point, or shortened to fixpoint, also knowns as invariant point），指的是在函数定义域内的某一个值，经过函数映射后的值还是其本身。
令M是一个封闭的向量空间，f:M→M是一个映射。假设存在一个K，0<K<1，对于任意的x,y∈M，若有：
则存在一唯一的定点x0，x0∈M f(x0)=x0，x0为f唯一的不动点。
证明如下：
shrink.jpg
这里最后一个式子应用了之前的假设前提。达到不动点后，每次迭代映射后的值都是x0本身。
conclude.jpg
同样，唯一性也得到了证明
Convergence Rates for Shrinking Maps
假设有个函数g满足条件：
对于某个常数0<K<1，任意x,y∈I成立。因此, 函数g有个不定点x∞。 假定：0<|g′(x∞)|<1，即g在x∞处可微。那么xn→x∞为线性收敛。
证明：
因为0<K<1，因此是线性收敛
Newton’s Method
最优化的牛顿迭代法就是通过函数迭代求得f最终收敛的根。假设根为x∞，xn为初始点，由中值定理，存在一个点xn<z<x∞使得：
也就是：
但是x∞和z都是未知的，我们分别用xn+1和xn代替，就得到了牛顿法的迭代更新公式
Proof of Newton’s Method
proof_Newton.jpg
Convergence Rate of Newton’s Method
牛顿法的核心思想是对函数进行泰勒展开
参考：https://blog.csdn.net/michaelhan3/article/details/82350047
收敛速率为二次收敛级，速度很快，但是每轮需要计算f‘，这使得计算复杂。这种方法只能是趋近于要求的根的邻近，邻域的大小是未知的。
正因为其速度太快，也不能保证每次迭代都是一种“提升”，甚至可能越过了我们希望到达的界限。
Newton’s Method for Maximum Likelihood Estimation
最大似然估计(MLE)需要求解参数向量θ，在某概率分布下生成观测数据的概率，表达式一般取对数为l(θ)。很多情况下就是为了求ℓ′(θ)=0
假设θ是k x 1的向量，用牛顿法（二阶泰勒展开），得：
其中ℓ′′是对数似然函数的hessian矩阵，详细参考：https://blog.csdn.net/guoyunfei20/article/details/78246699?depth_1-utm_source=distribute.pc_relevant.none-task-blog-BlogCommendFromBaidu-2&utm_source=distribute.pc_relevant.none-task-blog-BlogCommendFromBaidu-2
为了回避求矩阵的逆，写成下式：
Example: Estimating a Poisson Mean
假设数据服从泊松分布：x1,x2,…,xn∼Poisson(μ)，我们想用最大似然法求解μ，得出的对数似然函数为：
求导：
令导数等于零，明显地u_hat等于x_bar，我们对ℓ′(μ)可视化，看看牛顿法是怎么让这个函数逼近零的：
set.seed(2017-08-09)
x <- rpois(100, 5)
xbar <- mean(x)
n <- length(x)
score <- function(mu) {
n * xbar / mu - n
}
curve(score, .3, 10, xlab = expression(mu), ylab = expression(score(mu)))
abline(h = 0, lty = 3)
likelihood_Newton.jpg
可以看到导函数随u的变化趋势，这种平滑曲线最适合牛顿法不过了，不过为了使一阶导等于零，我们还需要二阶导的信息：
因此牛顿法的参数迭代表达式为：
在R里面实现牛顿法，需要迭代器：这里iterate的参数f是函数，n是迭代次数
Funcall <- function(f, ...) f(...)
Iterate <- function(f, n = 1) {
function(x) {
Reduce(Funcall, rep.int(list(f), n), x, right = TRUE)#表示从向量的右侧开始，依次向左侧取出元素，传递给函数；
}
}
#Reduce()函数对一个向量循环执行函数（该函数有两个参数）
现在我们尝试迭代次数为一，测试一下：
single_iteration <- function(x) {
2 * x - x^2 / xbar
}
g <- function(x0, n) {
giter <- Iterate(single_iteration, n)
giter(x0)
}
为了更好地可视化迭代的效果，我们把每次的迭代n向量化（方便作为横坐标）：
g <- Vectorize(g, "n")
#设置初始值为u0=10，迭代7次
par(mar = c(5, 5, 4, 1))
curve(score, .35, 10, xlab = expression(mu), ylab = expression(score(mu)), cex.axis = 0.8)
abline(h = 0, lty = 3)
iterates <- g(10, 1:7) ## Generate values for 7 functional iterations with a starting value of 10.
abline(v = c(10, iterates), lty = 2)
axis(3, c(10, iterates), labels = c(0, 1:7), cex = 2, cex.axis = 0.8)
mtext("Iteration #", at = 2, line = 2.5)
详细的理解还可以参考：
机器学习优化算法中梯度下降,牛顿法和拟牛顿法的优缺点详细介绍：http://m.elecfans.com/article/722244.html
参考教材：Advanced Statistical Computing
网友评论