# Eigenvalue Decomposition-Based Modified Newton Algorithm

Authors: Wen-jun Wang; Ju-bo Zhu; Xiao-jun Duan
Journal: Mathematical Problems in Engineering
 (2013)

---

## Abstract

When the Hessian matrix is not positive, the Newton direction may not be the descending direction. A new method named eigenvalue decomposition-based modified Newton algorithm is presented, which first takes the eigenvalue decomposition of the Hessian matrix, then replaces the negative eigenvalues with their absolute values, and finally reconstructs the Hessian matrix and modifies the searching direction. The new searching direction is always the descending direction. The convergence of the algorithm is proven and the conclusion on convergence rate is presented qualitatively. Finally, a numerical experiment is given for comparing the convergence domains of the modified algorithm and the classical algorithm.


---

## Body

## 1.  Introduction

Newton algorithm (also known as Newton’s method) is commonly used in numerical analysis, especially in nonlinear optimization [1]. But, in the definition domain of the object function, the method requires that (1) object function f(x) is twice differentiable, (2) the Hessian matrix must be positive, and (3) the initial solution x0 should be near the extreme point xk [2]. If there is a point in the definition domain whose Hessian matrix is not positive, then the Newton direction of this point is not the descending direction. So the classical algorithm may not be convergent in the definition domain.There are several improved forms of the classical Newton algorithm on the above problem: (1) combining Newton direction with the steepest descent direction [3]; (2) combining Newton direction with the negative curvature direction [4]; (3) adding a diagonal matrix vkI to the Hessian matrix so that the sum matrix is positive, where vk is a positive number bigger than the absolutely value of the smallest eigenvalue [5]. This paper presents a new algorithm to handle the “nonpositive problem.”


## 2. Newton Algorithm

We discuss the extreme value problems of multi-function. Suppose object functionf(x) is a twice differentiable function, and the extreme value problem of f(x) is
(1)minxf(x).If the Hessian matrix off(x) is positive, the Taylor expansion to the second order of f(x) is:
(2)f(x)≈f(xk)+∇f(xk)(x-xk)+12(x-xk)T∇2f(xk)(x-xk).As we know,∇xf(x)=0 is the necessary condition, so the derivative form of (2) is
(3)∇xf(x)=0+∇f(xk)+(x-xk)T∇2f(xk)=0.Equation (3) is usually called Newton's equation. When matrix ∇2f(xk) is positive, and the inverse matrix [∇2f(xk)]-1 exists, we can get an iterative equation as follows:
(4)x=xk+[∇2f(xk)]-1[-∇f(xk)].Equation (4) is usually called Newton iterative algorithm format, where -∇f(xk) is called negative gradient direction, and [∇2f(xk)]-1[-∇f(xk)] is called Newton direction.Next, we must give a proper step length to ensure the value of function declining. A well-known algorithm is “Damped Newton Algorithm,” which gets the step length by solving the following optimization problem:(5)α=argminα{xk+α[∇2f(xk)]-1[-∇f(xk)]}.


## 3. Modified Newton Algorithm Based on Eigenvalue Decomposition

### 3.1. Modified Algorithm

First, take eigenvalue decomposition on the Hessian matrix[∇2f(xk)]-1:
(6)[∇2f(xk)]-1=UΣUH,
where U is a unitary matrix; Σ is a diagonal matrix. Because matrix [∇2f(xk)]-1 is not positive, there must be a few negative eigenvalues in Σ. We replace the negative eigenvalues with their absolutely values, so the modified searching direction is:
(7)dk=U|Σ|UH[-∇f(xk)].The inner product of the negative gradient direction withdk is always positive, because the right part of the next equation is a quadratic form [6]:
(8)〈[-∇f(xk)],U|Σ|UH[-∇f(xk)]〉=[-∇f(xk)]TU|Σ|UH[-∇f(xk)]>0.
Equation (8) shows that the angle between the negative gradient direction and dk is less than 90°, so the new direction dk is always a descent direction. Then we can get the similar iterative equation by replacing the Newton direction with dk, that is,
(9)x=xk+αdk,
where α is the step length obtained by solving optimization problem (5).


### 3.2. Convergence Conclusion

We prove that the modified Newton algorithm based on eigenvalue decomposition is convergent. First, we talk about Wolfe-Powell condition [7].If step lengthαk>0 satisfies the two following equations:
(10)f(xk+αkdk)-f(xk)≤ραk∇f(xk)Tdk,∇f(xk+αkdk)Tdk≥σ∇f(xk)Tdk.Equation (10) is named Wolfe-Powell condition, where ρ∈(0,1) and σ∈(ρ,1).Theorem 1.
Letf be a continuously differentiable function, and let α^ be defined by
(11)α^=min{(xk)Tα≥0∣f(xk+αdk)=f(xk)+αρ∇f(xk)Tdk},
where α^ has a bound. Then there must be a finite interval (a,b)⊆[0,α^], for all αk∈(a,b), the Wolfe-Powell conditions are right.Proof.
Letϕ(t)≜f(xk+tdk), as α^>0 and satisfies the following equation:
(12)ϕ(α)≜ϕ(0)+α^ρϕ′(0).
Then
(13)ϕ(α)<ϕ(0)+α^ρϕ′(0)∀α∈(0,α^).
According to the Mean Value Theorem, there must be α-∈(0,α^) satisfies the following equation:
(14)ϕ(α^)-ϕ(0)α^<ϕ′(α-)<0.
Notice ρϕ′(0)=ϕ′(α-), and ρ<σ, so we can get:
(15)ϕ′(α-)>σϕ′(0).
Notice ϕ is a continuously differentiable operator, so there is an open set (a,b) satisfies (a,b)⊂(0,α^), where α-∈(a,b). For any αk when αk∈(a,b), the following equations are right:
(16)(1)ϕ(αk)≤ϕ(0)+αkϕ′(0),(2)ϕ′(αk)≥σϕ′(0).
Finally, we can get the Wolfe-Powell condition.Theorem 2.
Letf:Rn→R be a continuously differentiable function, so f has lower bounded in Rn; ∇f is uniformly continuous on O, which contains a horizontal set Levα0:={x∈Rn∣f(x)≤α0}, where α0=f(x0) and x0∈Rn. If dk satisfy the following conditions: θk≤π/2-μ, where θk stands for the angle between -∇f(xk) and dk, and μ∈(0,π/2) is a constant, then there must be a k satisfying ∇f(xk)=0 or ∇f(xk)→0 by Wolfe-Powell conditions.Proof.
We proof the theorem by contradiction. Suppose∇f(xk)≠0 or ∇f(xk)↛0 for all k, and there is a set {ki} and a constant ε>0 satisfy ∥∇f(xki)∥≥ε for all i. Because dk satisfies the angle condition θk≤π/2-μ, so
(17)∇f(xk)Tdk=-∥∇f(xk)∥∥dk∥cosθk≤-∥∇f(xk)∥∥dk∥sinμ<0.
Equation (17) shows that dk is a descending direction, so {f(xk)} is a decreasing sequence. Suppose the limit of {f(xk)} is ξ, and ξ>-∞. That is f(xk)→ξ, so f(xk)-f(xk+1)→0, take the Wolfe-Powell condition (16)(1) on index ki,
(18)f(xki)-f(xki+1)≥-ραki∇f(xki)Tdki≥∥∇f(xki)∥∥αkidki∥cosθki≥εsinμ∥αkidki∥.
It is easy to get ∥αkidki∥→0, again by the Wolfe-Powell condition (16)(2),
(19)[∇f(xki+1)-∇f(xki)]Tdki≥-(1-σ)∇f(xki)Tdki.
Further
(20)∥∇f(xki+1)-∇f(xki)∥≥ε(1-σ)sinμ.
Because of∥xki+1-xki∥=∥αkidki∥→0, (20) is in contradiction with the assumption that ∇f is uniformly continuous on Levα0. The contradiction suggests that ∇f(xk)→0.


## 3.1. Modified Algorithm

First, take eigenvalue decomposition on the Hessian matrix[∇2f(xk)]-1:
(6)[∇2f(xk)]-1=UΣUH,
where U is a unitary matrix; Σ is a diagonal matrix. Because matrix [∇2f(xk)]-1 is not positive, there must be a few negative eigenvalues in Σ. We replace the negative eigenvalues with their absolutely values, so the modified searching direction is:
(7)dk=U|Σ|UH[-∇f(xk)].The inner product of the negative gradient direction withdk is always positive, because the right part of the next equation is a quadratic form [6]:
(8)〈[-∇f(xk)],U|Σ|UH[-∇f(xk)]〉=[-∇f(xk)]TU|Σ|UH[-∇f(xk)]>0.
Equation (8) shows that the angle between the negative gradient direction and dk is less than 90°, so the new direction dk is always a descent direction. Then we can get the similar iterative equation by replacing the Newton direction with dk, that is,
(9)x=xk+αdk,
where α is the step length obtained by solving optimization problem (5).


## 3.2. Convergence Conclusion

We prove that the modified Newton algorithm based on eigenvalue decomposition is convergent. First, we talk about Wolfe-Powell condition [7].If step lengthαk>0 satisfies the two following equations:
(10)f(xk+αkdk)-f(xk)≤ραk∇f(xk)Tdk,∇f(xk+αkdk)Tdk≥σ∇f(xk)Tdk.Equation (10) is named Wolfe-Powell condition, where ρ∈(0,1) and σ∈(ρ,1).Theorem 1.
Letf be a continuously differentiable function, and let α^ be defined by
(11)α^=min{(xk)Tα≥0∣f(xk+αdk)=f(xk)+αρ∇f(xk)Tdk},
where α^ has a bound. Then there must be a finite interval (a,b)⊆[0,α^], for all αk∈(a,b), the Wolfe-Powell conditions are right.Proof.
Letϕ(t)≜f(xk+tdk), as α^>0 and satisfies the following equation:
(12)ϕ(α)≜ϕ(0)+α^ρϕ′(0).
Then
(13)ϕ(α)<ϕ(0)+α^ρϕ′(0)∀α∈(0,α^).
According to the Mean Value Theorem, there must be α-∈(0,α^) satisfies the following equation:
(14)ϕ(α^)-ϕ(0)α^<ϕ′(α-)<0.
Notice ρϕ′(0)=ϕ′(α-), and ρ<σ, so we can get:
(15)ϕ′(α-)>σϕ′(0).
Notice ϕ is a continuously differentiable operator, so there is an open set (a,b) satisfies (a,b)⊂(0,α^), where α-∈(a,b). For any αk when αk∈(a,b), the following equations are right:
(16)(1)ϕ(αk)≤ϕ(0)+αkϕ′(0),(2)ϕ′(αk)≥σϕ′(0).
Finally, we can get the Wolfe-Powell condition.Theorem 2.
Letf:Rn→R be a continuously differentiable function, so f has lower bounded in Rn; ∇f is uniformly continuous on O, which contains a horizontal set Levα0:={x∈Rn∣f(x)≤α0}, where α0=f(x0) and x0∈Rn. If dk satisfy the following conditions: θk≤π/2-μ, where θk stands for the angle between -∇f(xk) and dk, and μ∈(0,π/2) is a constant, then there must be a k satisfying ∇f(xk)=0 or ∇f(xk)→0 by Wolfe-Powell conditions.Proof.
We proof the theorem by contradiction. Suppose∇f(xk)≠0 or ∇f(xk)↛0 for all k, and there is a set {ki} and a constant ε>0 satisfy ∥∇f(xki)∥≥ε for all i. Because dk satisfies the angle condition θk≤π/2-μ, so
(17)∇f(xk)Tdk=-∥∇f(xk)∥∥dk∥cosθk≤-∥∇f(xk)∥∥dk∥sinμ<0.
Equation (17) shows that dk is a descending direction, so {f(xk)} is a decreasing sequence. Suppose the limit of {f(xk)} is ξ, and ξ>-∞. That is f(xk)→ξ, so f(xk)-f(xk+1)→0, take the Wolfe-Powell condition (16)(1) on index ki,
(18)f(xki)-f(xki+1)≥-ραki∇f(xki)Tdki≥∥∇f(xki)∥∥αkidki∥cosθki≥εsinμ∥αkidki∥.
It is easy to get ∥αkidki∥→0, again by the Wolfe-Powell condition (16)(2),
(19)[∇f(xki+1)-∇f(xki)]Tdki≥-(1-σ)∇f(xki)Tdki.
Further
(20)∥∇f(xki+1)-∇f(xki)∥≥ε(1-σ)sinμ.
Because of∥xki+1-xki∥=∥αkidki∥→0, (20) is in contradiction with the assumption that ∇f is uniformly continuous on Levα0. The contradiction suggests that ∇f(xk)→0.


## 4. Simulations on Convergence Properties

As the new searching directiondk satisfies the following equation:
(21)dk={UΣUH[-∇f(xk)]if∇2f(xk)>0U|Σ|UH[-∇f(xk)]else.So, if the Hessian matrix of all points in definition domain is positive, then the convergence rate of modified algorithm equals the classical Newton algorithm. The other side, if there are any points with its Hessian matrix negative, then the convergence rate at most equals the one of classical Newton algorithm.In addition, in order to verify that the improved algorithm has a wider convergence domain than the classical Newton algorithm, we employ a convex function:f(x,y)=-3(1-x)2e-x2-(y+1)2 as the objective function. Let the definition domain be (x,y)∈{[-3,1],[-3,1]}, and we choose the grid points by 0.1 interval, then use both classical Newton's algorithm and eigenvalue decomposition-based algorithm to find the minimum value. The results are drawn in Figure 1.Results of numerical experiment (a) objective function; (b) contour map; (c) convergence domain of Newton's algorithm; (d) convergence domain of the new algorithm.
(a)
(b)
(c)
(d)In Figure1(c), the green point means that the algorithm has found the minimum value using this point as the initial solution; and the red point means that the algorithm did not converge or has not found the minimum value. Obviously, the convergence domain of eigenvalue decomposition algorithm is bigger than the one of the classical Newton algorithm.


## 5. Conclusion

A new algorithm is put forward based on eigenvalue decomposition and classical Newton algorithm. The eigenvalue decomposition based-algorithm has a wider convergence domain than the classical Newton algorithm.



---

*Source: 523895-2013-03-26.xml*