Newto

Newto

• Newton-Raphson
  • 一阶形式
    • 推导过程
  • 二阶形式
    • 推导过程
• Convex Function
  • Quadratic Program

1. Newton-Raphson

解决 f(x)=0 $f(x)=0$问题的逼近方式

一阶形式

xnew=xold−f(x)f′(x)f′(x)=∂f(x)∂x $$x^{new} = x^{old}-frac{f(x)}{f'(x)}\ f'(x) = frac{partial f(x)}{partial x}$$

推导过程

1级泰勒展开：

f(x+Δx)=f(x)+Δxf′(x) $$f(x+Delta x) = f(x)+Delta xf'(x)$$
令 f(x+Δx)≈0 $f(x+Delta x) approx 0$ Δx $Delta x$是x使得f(x)趋近于0的方向。那么
f(x)+Δxf′(x)=0→Δx=−f(x)f′(x) $$f(x)+Delta xf'(x) = 0\ to Delta x = -frac{f(x)}{f'(x)}$$

二阶形式

xnew=xold−∇−2f(xold)×∇f(xold) $$x^{new} = x^{old} - nabla^{-2}f (x^{old})timesnabla f (x^{old})\ $$
矩阵形式
xnew=xold−H−1∇f(xold)H=∇2f $$x^{new} = x^{old} - H^{-1}nabla f(x^{old})\ H = nabla^2f$$
H是Hessian Matrix.

推导过程

泰勒二级展开

f(X+ΔX)=f(X)+∇Tf(X)×ΔX+12(ΔX)T×∇2f(X)×ΔX $$f(X+Delta X)=f(X) + nabla ^Tf(X)times Delta X+frac{1}{2}(Delta X)^Ttimes nabla ^2f(X)times Delta X$$
令 f(X+ΔX)=0→ $f(X+Delta X) = 0 to$
ΔX=−(∇2f(X))−1×∇f(X) $$Delta X = -(nabla^2f(X))^{-1}times nabla f(X)$$
ΔX $Delta X$是X逼近解的方向。

Convex Function

Quadratic Program

F=xTAx+bTx+cxmax=−0.5A−1b $$F = x^TAx +b^Tx + c\ x_{max} = -0.5A^{-1}b$$