Nonlinear Optimization using Newton’s Method

by Trent Guidry27. December 2011 13:28

Newton's method for optimization is similar to Newton's method for root finding.  The primary difference between the two is that instead of finding zero values for the system of equations it finds zero values for the system of first derivatives of the equations. 

 

For this algorithm:

  1. Start with a set of guess values for the x's.
  2. Either:
    1. Calculate the Hessian using either analytical or numerical second order derivatives.  Invert the Hessian to get the Hessian inverse.
    2. Calculate the Hessian inverse with out calculating the Hessian using either analytical or numerical methods.
  3. Calculate the objective function's gradient using analytical or numerical first derivatives.
  4. Calculate the change in the x's by multiplying the negative of the Hessian inverse by the gradient.
  5. Calculate the new x's.
  6. Go to step 2) until either the optimization algorithm converges or diverges.

 

Example

For this example, there is a local minimum at x1 = 1 and x2 = 2, with an objective function value of 0.

Initial Guess Values:

x1 = 3

x2 = 3

Objective function value = 27

Iteration 1

Gradient

24
15

Hessian

18 0
0 18

Inverse Hessian

0.055556 0
0 0.055556

Delta X

24*0.055556 = -1.333
15*0.055556 = -0.8333

New X

3 - 1.333 = 1.6667
3 - 0.8333 = 2.16667

Objective function value = 1.801

Iteration 2

Gradient

5.3333
2.08333

Hessian

10 0
0 13

Inverse Hessian

0.1 0
0 0.076923

Delta X

-5.3333 * 0.1 = -0.5333
-2.08333 * 0.076923  = -0.16026

New X

1.6667 - 0.5333 = 1.1333
2.16667 - 0.16026 = 2.00641

Objective function value = 0.060

Iteration 3

Gradient

0.853333
0.077046

Hessian

6.8 0
0 12.03846

Inverse Hessian

0.147059 0
0 0.083067

Delta X

-0.853333 * 0.147059= -0.12549
-2.08333 * 0.076923 = -0.16026

New X

1.1333 - 0.12549 = 1.007843
2.00641 - 0.16026 = 2.00001

Objective function value = 0.000185

Iteration 4

Gradient

0.047243
0.000123

Hessian

0.16537 0
0 12.000

Inverse Hessian

0.16537 0
0 0.083333

Delta X

-0.047243 * 0.16537= -0.00781
-0.000123 * 0.083333  = - 0.00001

New X

1.007843 - 0.00781= 1.0000
2.00001 - 0.16026 = 2.0000

 Objective function value = 2.79E-9