《畢業(yè)設(shè)計論文 外文文獻翻譯 數(shù)學專業(yè)》由會員分享，可在線閱讀，更多相關(guān)《畢業(yè)設(shè)計論文 外文文獻翻譯 數(shù)學專業(yè)（14頁珍藏版）》請在裝配圖網(wǎng)上搜索。
1、
重 慶 理 工 大 學
文 獻 翻 譯
二級學院 數(shù)學與統(tǒng)計學院
譯文：
摘自：The Newton Raphson Algorithm for FunctionOptimization
Kevin Quinn
Assistant Professor
Department of Political Science and
The C
2、enter for Statistics and the Social Sciences
Box 354322, Padelford Hall
University of Washington
Seattle, WA 98195-4322
October 25, 2001
一、引言
通過這個課程的學習我們將有興趣計算最大似然估計（極大似然估計）。例如我們常常觀察到的復雜的非線性函數(shù)的數(shù)據(jù)。因此，通過我們的計算封閉形式的去表達這極大似然估計的形式一般是不會存在模型的
牛頓拉夫森算法是一個迭代的過程，可用于計算出極大似然估計。其背后的算法的基本思想的內(nèi)容。首先，圍繞一些初步的參數(shù)
3、值構(gòu)造一個二次近似逼近的有利函數(shù)（希望能接近最大似然估計）。其次是，調(diào)整參數(shù)值讓其最大限度地提高二次近似。此過程再不斷的重復進行，直到參數(shù)值穩(wěn)定。
這就說明開始容易想象出一個函數(shù)遇到最大化的一個變量。在這種情況下開發(fā)，我們轉(zhuǎn)而更為一般的情況下最大化的一個變量k的函數(shù) 。
二、牛頓拉夫森算法求變量1的函數(shù)的最大值
2、1泰勒系列的逼近問題
牛頓拉夫遜算法的第一部分的發(fā)展是設(shè)計一個近似函數(shù)表示似然函數(shù)就可以很容易的最大化的分析。要做到這一點，我們需要利用泰勒定理。
定理1（泰勒定理（1維））假設(shè)函數(shù)f次可微的開區(qū)間I上的，對于任意的一點到在I區(qū)間上存在的一點在到上例如：
4、
. (1)
他可以表示成為從到的方程的高階項從到更快于從到。這就意味著（最小值）
這被稱作一階泰勒的近似函數(shù)f在x上的，小的值可以構(gòu)建一個更準確的逼近函數(shù)：
請注意第一階泰勒的近似可以重寫為被稱為一個二階泰勒的近似函數(shù)f在上的值如：
從到.這凸顯一個事實，即一階泰勒的近似的線性函數(shù)在上的。同樣的，二階泰勒的近似值可以被改寫成為：
當，，且。這凸顯出的一個事實，即是二階泰勒近似值是在上的第二階多項式。
2、2查找到的其最大值的二階多項式
假設(shè)出我們想要找出的值能最大化的
首先，我們計算出的一階導數(shù)的函數(shù)為：
我們了
5、解到這，當?shù)闹凳菚r，其中函數(shù)的值達到最大，換句話說，我們都知道
求解我們發(fā)現(xiàn)。第二階的條件就是。這意味著
的值將是最大無論什么時候當.
2、3牛頓拉夫森的算法
假設(shè)我們想要找到的值當最大化的二次連續(xù)可微的函數(shù)的值。
記得
當，且。這就意味著：
一階條件的（記為）值能最大化就是是：
這就意味著。換而言之就是，
在的函數(shù)值能最大化的二階泰勒近似值為函數(shù)
考慮到這一點，我們可以指定用于一維的函數(shù)優(yōu)化問題的牛頓拉夫森算法。
算法2、1：牛頓拉夫森一維的（，，公差）
發(fā)表評論：找出求的值能最大化的函數(shù)：
當
Do
6、
回到
注意事項：注意牛頓拉夫森算法，不檢查的二階的必要條件為是最大化。這就意味著，如果你給一個錯的開始x的值的算法，你可能最終是最小的，而不是一個最大的。
2、4例如：計算二項式抽樣模型的極大似然估計
看到牛頓拉夫森算法的工程實踐中如何讓看一個簡單的示例，二項式抽樣與分析解的簡單的模型。
我們的對數(shù)似然函數(shù)是：
當為樣本容量時，就是成功的次數(shù)，是一個取得成功的概率。一階導數(shù)對數(shù)似然函數(shù)是：
二階導數(shù)對數(shù)似然函數(shù)就是：
解析，我們知道的最大似然估計是：。
舉一個例子，假設(shè)且。解析，我們知道的最大似然估計是。讓我們來看看如何在這種情況下解出牛
7、頓拉夫森算法。
我們首先設(shè)置公差級別。在這種情況下的，讓將它設(shè)置為0.01（在實踐中你可能想要的東西更接近0.00001）。下一步，我們初始猜測的最大似然估計（記為）。假設(shè)。的這是在絕對值大于0.01的公差。
因此我們設(shè)置為：
。
現(xiàn)在我們計算出，它仍然是在絕對值大于的公差。因此我們設(shè)置為：
是約等于是絕對值小于的公差，這樣我們就可以停止了。牛頓拉夫森算法返回pi的的值等于到接近0.3994，這是合理的分析值0.40。請注意，我們可以設(shè)置的容忍水平接近的牛頓拉夫森過程更準確（機器精密度范圍內(nèi)）。
三、牛頓拉夫森算法求最大的變量的函數(shù)
3、1泰勒級數(shù)逼近問題維度
8、
考慮函數(shù)至少有兩次的連續(xù)可微。假設(shè)且。然后給出一階泰勒近似值在函數(shù)上的一個被寫為：
給出二階泰勒近似值在函數(shù)上的一個被寫為：
當是梯度（一階導數(shù)的向量）的函數(shù)在上時，且是 Hessian矩陣（第二衍生矩陣）在函數(shù)屬于上時。
3、2找到最大值的變量的二階多項式
考慮
當是一個標量，和是關(guān)于K-向量，且是一個的對稱矩陣，負正定矩陣。這的梯度在上表示為：
我們知道，由于最大化的值滿足能最大化的梯度將是一個零矢量，
求解 我們找出結(jié)果如：
由于被認為是負定的，而且我們知道這就是最大的。
3、
9、3在維度的牛頓拉夫森算法
假設(shè)我們要找出的最大限度地提高二次連續(xù)可微函數(shù)。
記得
當且。請注意矩陣將是對稱的，這就意味著是：
再一次，最大值的一階條件就是：
這就意味著：
換句話說就是，向量能最大化的在的二階泰勒近似值為函數(shù)：
考慮到這一點，我們就可以指定的k維函數(shù)優(yōu)化問題的牛頓拉夫森算法。
算法研究3、1：牛頓拉夫森算法的KD（，，公差）
發(fā)表評論：求關(guān)于的值的的最大函數(shù)。
當
Do
回到（）。
譯文：
摘自： The Ne
10、wton Raphson Algorithm for FunctionOptimization
Kevin Quinn
Assistant Professor
Department of Political Science and
The Center for Statistics and the Social Sciences
Box 354322, Padelford Hall
University of Washington
Seattle, WA 98195-4322
October 25, 2001
1 Introduction
T
11、hroughout this course we will be interested in calculating maximum likelihood estimate(MLEs). Such estimates are often extremely complicated nonlinear functions of the observed data. As a result, closed form expressions for the MLEs will generally not exist for the models we are working with.
Th
12、e Newton Raphson algorithm is an iterative procedure that can be used to calculate MLEs. The basic idea behind the algorithm is the following. First, construct a quadratic approximation to the function of interest around some initial parameter value (hopefully close to the MLE). Next, adjust the par
13、ameter value to that which maximizes the quadratic approximation. This procedure is iterated until the parameter values stabilize.
These notes begin with the easy to visualize case of maximizing a function of one variable. After this case is developed, we turn to the more general case of maximiz
14、ing a function of variables.
2 The Newton Raphson Algorithm for Finding the Maximum of a Function of 1 Variable
2.1 Taylor Series Approximations
The first part of developing the Newton Raphson algorithm is to devise a way to approximate the likelihood function with a function that can b
15、e easily maximized analytically. To do this we need to make use of Taylor’s Theorem.
Theorem 1 (Taylor’s Theorem (1 Dimension)). Suppose the function f is times differentiable on an open interval I. For any points and in I there exists a point between and such that
. (1)
It can be sho
16、wn that as goes to the higher order terms in equation go to 0 much faster than goes to . This means that (for small values of )
This is referred to as a first order Taylor approximation of f at . A more accurate approximation to can be constructed for small values of as:
This is known
17、as a second order Taylor approximation of f at Note that the first order Taylor approximation can be rewritten as:
where and . This highlights the fact that the first order Taylor approximation is a linear function in . Similarly, the second order Taylor approximation can be rewritten as:
W
18、here , and . This highlights the fact that the second order Taylor approximation is a second order polynomial in
2.2 Finding the Maximum of a Second Order Polynomial
Suppose we want to find the value of that maximizes
First, we calculate the first derivative of :
We know that , where
19、 is the value of at which f attains its maximum. In other words, we know that
Solving for we find that . The second order condition is . This implies that will be a maximum whenever .
2.3 The Newton Raphson Algorithm
Suppose we want to find the value of that maximizes some twice continu
20、ously differentiable function .
Recall
where , , and . This implies
.
The first order condition for the value of (denoted ) that maximizes is
Which implies . In other words, the value that maximizes the second order Taylor approximation to at is
With this in mind
21、we can specify the Newton Raphson algorithm for dimensional function optimization.
Algorithm 2.1: NewtonRaphson1D(,,tolerance)
comment: Find the value of that maximizes
While
do
return
Caution: Note that the Newton Raphson Algorithm doesn’t check the second order conditions nece
22、ssary for to be a maximizer. This means that if you give the algorithm a bad starting value for you may end up with a min rather than a max.
2.4 Example: Calculating the MLE of a Binomial Sampling Model
To see how the Newton Raphson algorithm works in practice lets look at a simple example with
23、an analytical solution– a simple model of binomial sampling.
Our log-likelihood function is:
where is the sample size, is the number of successes, and is the probability of a success.The first derivative of the log-likelihood function is
and the second derivative of the log-likelihood func
24、tion is
Analytically, we know that the MLE is .
For the sake of example, suppose and . Analytically, we know that the MLE is Let’s see how the Newton Raphson algorithm works in this situation.
We begin by setting a tolerance level. In this case, let’s set it to (In practice you probably want
25、 something closer to ). Next we make an initial guess (denoted ) as to the MLE. Suppose . which is larger in absolute value than our tolerance of . Thus we set
.
Now we calculate which is still larger in absolute value than our tolerance of . Thus we set
is approximately equal to which is s
26、maller in absolute value than our tolerance of so we can stop. The Newton Raphson algorithm here returns a value of pi equal to which is reasonably close to the analytical value of . Note we can make the Newton Raphson procedure more accurate (within machine precision) by setting the tolerance lev
27、el closer to .
3 The Newton Raphson Algorithm for Finding the
Maximum of a Function of Variables
3.1 Taylor Series Approximations in Dimensions
Consider a function that is at least twice continuously differentiable. Suppose and . Then the first order Taylor approximation to at is given
28、by
and the second order Taylor approximation to f at is given by
where is the gradient (vector of first derivatives) at , and is the Hessian (matrix of second derivatives) of at .
3.2 Finding the Maximum of a Second Order Polynomial in
Variables
Consider
where is a scalar, and
29、 are k-vectors, and is a symmetric, negative definite matrix. The gradient of at is
Since the gradient at the value that maximizes will be a vector of zeros we know that the maximizer satisfies
Solving for we find that
Since is assumed to be negative definite we know that this is a
30、maximum.
3.3 The Newton Raphson Algorithm in k Dimensions
Suppose we want to find the that maximizes the twice continuously differentiable function
Recall
where and . Note that will be symmetric. This implies
Once again, the first order condition for a maximum is
which implies that
31、
In other words, the vector that maximizes the second order Taylor approximation to at is
With this in mind we can specify the Newton Raphson algorithm for k-dimensional function optimization.
Algorithm 3.1: NewtonRaphsonKD
comment: Find the value of that maximizes
While
do
Return()
畢業(yè)設(shè)計論文 外文文獻翻譯 數(shù)學專業(yè)
