Optimal Algorithm

Definition

Lipschitz Continuous

F be an m-vector of functions of x ∈ E n . F is Lipschitz continuous on an open set S⊂En ifthereisaconstant 0<L<∞ such that F(x)−F(y) ≤Lx−y for all x, y ∈ S .
符合利普希茨條件的函數一致連續,也連續,但不一定可微分

Newton's Method

(Theorm) Quadratic Convergence

Let f be a real-valued function of n variables defined on an open convex set S . Assume that ∇ 2 f is Lipschitz continuous on S, that is, ∇2f (x) − ∇2f (y) ≤ L ∥x − y∥
for all x, y ∈ S and for some constant L < ∞. Consider the sequence { xk } generated by xk+1 =xk −[∇2f(xk)]−1∇f(xk).
Let x∗ be a minimizer of f (x) in S and assume that ∇2f (x∗) is positive definite. If ∥x0 − x∗∥ is sufficiently small, then { xk } converges quadratically to x∗ .

(Theorm) Superlinear Convergence

Let f be a real-valued function of n variables defined on an open convex set S. Assume that ∇2f is Lipschitz continuous on S, that is,
∇2f (x) − ∇2f (y) ≤ L ∥x − y∥
for all x, y ∈ S and for some constant L < ∞. Consider the sequence { xk } generated by xk+1 =xk +pk.

(Algorithm) Newton Method with Line Search

  1. Specify some initial guess of the solution x0, and specify a convergence tolerance ε.
  2. For k = 0,1,…
    • If ∥∇f (xk)∥ < ε, stop.
    • Compute a modified factorization of the Hessian: ∇2f (xk) + E = LDLT and solve (LDLT)p = −∇f(xk) for the search direction pk . (E will be zero if ∇ 2 f (xk ) is “sufficiently” positive definite.)
    • Perform a line search to determine xk+1 =xk +αkpk, the new estimate of the solution.

Guaranteeing Converge

Line Search Method

Trust-Region Methods

廣告

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com 標誌

您的留言將使用 WordPress.com 帳號。 登出 /  變更 )

Google+ photo

您的留言將使用 Google+ 帳號。 登出 /  變更 )

Twitter picture

您的留言將使用 Twitter 帳號。 登出 /  變更 )

Facebook照片

您的留言將使用 Facebook 帳號。 登出 /  變更 )

連結到 %s

在 WordPress.com 建立免費網站或網誌.

向上 ↑

%d 位部落客按了讚: