$/quad$牛頓法（Newton method）和擬牛頓法（quasi Newton method）是求解無(wú)約束最優(yōu)化問(wèn)題的常用方法，有收斂速度快的優(yōu)點(diǎn)。

1. 牛頓法

考慮無(wú)約束最優(yōu)化問(wèn)題 minx∈Rnf(x) $$min_{x/in R^n} f(x)$$ 其中x?$x^*$為目標(biāo)函數(shù)極小點(diǎn)。 假設(shè)f(x)$f(x)$有二階連續(xù)偏導(dǎo)數(shù)，若第k次迭代值為x(k)$x^{(k)}$,則可將f(x)$f(x)$在x(k)$x^{(k)}$附近進(jìn)行二階泰勒展開(kāi)： f(x)=f(x(k))+gTk(x?x(k))+12(x?x(k))TH(x(k))(x?x(k)) $$f(x)=f(x^{(k)})+g_k^T(x-x^{(k)})+/frac{1}{2}(x-x^{(k)})^TH(x^{(k)})(x-x^{(k)})$$ 這里，gk=g(x(k))=▽f(x(k))$g_k=g(x^{(k)})=/bigtriangledown f(x^{(k)})$是f(x)$f(x)$的梯度向量在點(diǎn)x(k)$x^{(k)}$的值，H(x(k))$H(x^{(k)})$是f(x)$f(x)$的海塞矩陣 H(x)=[?2f?xi?xj]n×n $$H(x)=[/frac{/partial^2f}{/partial x_i/partial x_j}]_{n/times n}$$ 在點(diǎn)x(k)的值。$x^{(k)}的值。$當(dāng)H(x(k))$H(x^{(k)})$是正定矩陣是，函數(shù)f(x)$f(x)$的極值為極小值。 假設(shè)x(k)$x^{(k)}$滿足： ▽f(x(k+1))=0 $$/bigtriangledown f(x^{(k+1)})=0$$ 對(duì)f(x)$f(x)$求導(dǎo)，得 ▽f(x)=gk+Hk(x?x(k)) $$/bigtriangledown f(x) = g_k+H_k(x-x^{(k)})$$ 其中Hk=H(x(k))$H_k=H(x^{(k)})$,則 gk+Hk(x(k+1)?x(k))=0 $$g_k+H_k(x^{(k+1)}-x^{(k)})=0$$ 因此，x(k+1)=x(k)?H?1kgk$x^{(k+1)}=x^{(k)}-H_k^{-1}g_k$ (**), 或者x(k+1)=x(k)+pk$x^{(k+1)}=x^{(k)}+p_k$,其中，Hkpk=?gk$H_kp_k=-g_k$ 式（**）作為迭代公式的算法就是牛頓法。 牛頓法： 輸入：目標(biāo)函數(shù)f(x),梯度g(x)=▽f(x),海塞矩陣H(x),精讀要求?;$f(x),梯度g(x)=/bigtriangledown f(x), 海塞矩陣H(x),精讀要求/epsilon;$ 輸出：f(x)的極小點(diǎn)x?.$f(x)的極小點(diǎn)x^*.$ （1）取初始點(diǎn)x(0)$x^{(0)}$,置k=0，$k=0，$ （2）計(jì)算gk=g(x(k))$g_k=g(x^{(k)})$, （3）若||gk||<?$||g_k||/lt /epsilon$,則停止計(jì)算，得近似解x?=x(k)$x^*=x^{(k)}$, （4）計(jì)算Hk=H(x(k)),并求pk$H_k=H(x^{(k)}),并求p_k$ Hkpk=?gk $$H_kp_k=-g_k$$ （5）置x(k+1)=x(k)+pk$x^(k+1)=x^{(k)}+p_k$， （6）置k=k+1$k=k+1$,轉(zhuǎn)至（2）。 步驟（4）要求H?1k$H_k^{-1}$，計(jì)算復(fù)雜，所以有其他改進(jìn)的方法，比如擬牛頓法等。

待續(xù)……