優(yōu)化與求解非線性方程組（單變量問(wèn)題）

求函數(shù)極值的問(wèn)題通常被化簡(jiǎn)為求解導(dǎo)數(shù)為0的點(diǎn)的問(wèn)題。所以優(yōu)化問(wèn)題通常與解非線性方程組聯(lián)系起來(lái)。在前面寫(xiě)點(diǎn)估計(jì)中的mle時(shí)，我們介紹了R中求解方程極值的函數(shù)nlm（），optim().

我們以一元函數(shù)f(x)=ln(x)/(1+x)為例求解函數(shù)的極值。

    f<-function(x) -log(x)/(1+x)      #（1）  
    optimize(f,c(0,10)) #求解（0,10）上的最小值，對(duì)于一元函數(shù)區(qū)間的確定，我們通?？梢援?huà)圖來(lái)做初步判斷 

對(duì)于多元函數(shù)：

    f <- function(x) sum((x-1:length(x))^2)  
    nlm(f, c(10,10))#這里需要給出迭代的初值  
    optim(c(10,10),f) 

由于nlm，optim，的默認(rèn)迭代方法不同，得出的結(jié)果精度也會(huì)有區(qū)別。運(yùn)行上面的代碼，我們可以看到nlm給出的最小值點(diǎn)為（1,2），而optim給出的是(1.000348, 2.001812)。

我們也可以通過(guò)求解函數(shù)的導(dǎo)數(shù)為0的點(diǎn)求解函數(shù)的極值。還是以1式為例。運(yùn)行下面的代碼：

D(expression(log(x)/(1+x)),"x")

結(jié)果為：1/x/(1 + x) - log(x)/(1 + x)^2。                        （2）

對(duì)于這樣的方程，我們通常是沒(méi)有好的辦法讓R給出解析解的。我們可以使用一些數(shù)值辦法來(lái)求解方程（2）的數(shù)值解。常用的辦法有：二分法，newton法，fisher得分法，不動(dòng)點(diǎn)迭代法。下面我們來(lái)簡(jiǎn)單介紹算法的思想與R的實(shí)現(xiàn)代碼。

一、二分法
   二分法的思想十分簡(jiǎn)單，利用的就是函數(shù)的中值定理，局限也十分明顯，只能求解出一個(gè)根而且速度較慢。所以函數(shù)的單調(diào)性，作圖都是解決第一個(gè)局限的辦法。

給出方程（1）的極小值利用二分法的求解程序：

    fzero<-function(f,a,b,eps=1e-6){  
      if(f(a)*f(b)>0)  
        list(fail="failed")  
      else{  
        repeat{  
          x<-(a+b)/2       
          if(f(a)*f(x)<0) b<-x else a<-x  
          if(abs(b-a)<eps) break  
        }  
        list(root=(a+b)/2,fun=f(x))  
      }  
    }  
    fd<-function(x)    1/x/(1 + x) - log(x)/(1 + x)^2  
    fzero(fd,0,10) 

注：跟蹤導(dǎo)函數(shù)值為0來(lái)檢測(cè)收斂情況是誘人的，但是存在不穩(wěn)定性，利用絕對(duì)收斂準(zhǔn)則解決了這一問(wèn)題（當(dāng)然用相對(duì)收斂準(zhǔn)則也是可以的）

二、Newton法

Newton-rapshon迭代是一種快速求根方法。主要利用泰勒級(jí)數(shù)展開(kāi)來(lái)解決問(wèn)題。

利用0=g’(x)=g’(x(t))+g’’(x(t))(x-x(t))（后面的等式是近似成立）來(lái)近似g’(x)。解上述的這個(gè)方程，我們可以得到一個(gè)很好的線性近似，迭代方程為：

X(t+1)=x(t)+g’(x(t))/g’’(x(t))

收斂條件依然使用絕對(duì)收斂。對(duì)于方程（1），有：

> D(expression(log(x)/(1+x)),"x")

1/x/(1 + x) - log(x)/(1 + x)^2

> D(expression(1/x/(1 + x) - log(x)/(1 + x)^2),"x")

-(1/x^2/(1 + x) + 1/x/(1 + x)^2 + (1/x/(1 + x)^2 - log(x) * (2 * (1+ x))/((1 + x)^2)^2))

問(wèn)題的newton增量為：h(t)=((x(t)+1)(1+1/x(t)-logx(t))/(3+4/x(t)+1/(x(t))^2-2logx(t))

給出方程（1）的極小值利用newton法的求解程序：

三、Fisher得分法

我們知道fisher信息量是對(duì)數(shù)似然函數(shù)的二階導(dǎo)數(shù)的期望的相反數(shù)。所以在求解g對(duì)應(yīng)著的mle優(yōu)化時(shí)，使用fisher信息量替換是合理的。這里不再給出程序。

四、切線法

在牛頓法的基礎(chǔ)上，我們把導(dǎo)數(shù)改為曲線上兩點(diǎn)的連線的斜率顯然也十分的合理。這便是切線法的基本想法。我們還是給出上面例子的R程序：

f0<-function(x){  
1/x/(1 + x) - log(x)/(1 + x)^2  
}  
ftwo<-function(f0,a,b,eps=1e-3){  
c<-b-f0(b)*(b-a)/(f0(b)-f0(a))  
if(abs(c-b)<eps){  
return(c)  
}  
else{  
ftwo(f0,b,c)  
}  
}

五、不動(dòng)點(diǎn)迭代法

除去二分法外，我們所討論的都是不動(dòng)點(diǎn)迭代的特例。這里只是簡(jiǎn)要敘述一下不動(dòng)點(diǎn)迭代法的原理，并以開(kāi)篇的例子給出R程序。

不動(dòng)點(diǎn)定理是一個(gè)結(jié)果表示函數(shù)F在某種特定情況下，至少有一個(gè)不動(dòng)點(diǎn)存在，即至少有一個(gè)點(diǎn)x能令函數(shù)F(x)=x。在數(shù)學(xué)中有很多定理能保證函數(shù)在一定的條件下必定有一個(gè)或更多的不動(dòng)點(diǎn)，而在這些最基本的定性結(jié)果當(dāng)中存在不動(dòng)點(diǎn)及其定理被應(yīng)用的結(jié)果具有非常普遍的價(jià)值。

    ffour<-function(f0,a,eps=1e-6){  
    repeat{  
    b<-4*f0(a)+a  
    if(abs(b-a)<eps){  
    return(b)  
    break}  
    else a<-b  
    }  
    }  

         這里還想說(shuō)一點(diǎn)的就是關(guān)于不動(dòng)點(diǎn)迭代的條件（百度一下，你就知道），如果不滿足的話，需要對(duì)導(dǎo)函數(shù)前乘上一個(gè)系數(shù)加以調(diào)整，本例中的4*f0(a)+a正是調(diào)整刻度的結(jié)果。

<pre class="plain" name="code"></pre>  
<pre></pre>  
<pre></pre>  
<pre></pre>  
<pre></pre>  
<pre></pre>