最優化算法-牛頓法

/*****************************************
 * FileName  : newton_search.go
 * Author    : fredric
 * Date      : 2017.09.01
 * Note      : 牛頓搜索算法
 * History   :
*****************************************/
package search

import(
    "fmt"
    "math"
)



/*
* 根據泰勒公式，若f(x)在x0點存在高階導數，則（此處取二階余子項）
* f(x) = f(x0) + f'(x0)(x - x0) + 1／2 * f''(x0) * (x - x0)
* 此時求解極值的方式轉換為求解該泰勒公式的一階導數何時為0
* 令x = x0 - f'(x0)/f''(x0)
* 此時有x,x0進行迭代，直到xk+1 - xk小于一個閾值

* 迭代的思路：
* 相當于在函數上對xk做一個切線，取這個切線然后取這個切線與x軸的交點，作為xk + 1
* 由于切線是根據函數的導數所做，相當于根據函數的遞增或遞減趨勢來取下一個x k + 1
* 最終的值計算導數的值是否趨向于0
* 因此牛頓方法也應是只針對單峰的函數
*/
func DoNewtonSearch() {
    //計算f(x) = 1/2 * x^2 + sinx
    //f'(x) = x -cosx
    //f''(x) = 1 + sinx

    x0 := 0.5
    x1 := 1.0
    delta := 0.000005

    for math.Abs(x1 - x0) > delta {

        x0 = x1

        x1 = x0 - (x0 - math.Cos(x0))/(1 + math.Sin(x0))
    }

    fmt.Printf("x0 = %f, x1 = %f\n", x0, x1)

}