Numerical methods. Note 8

[ Home ]

Nonlinear Equations and Function Optimization (Minimization).

Numerical Methods. Note « 8 »

System of n nonlinear equations

f_i(x₁,...,x_n)=0, i=1..n

can be solved numerically by Newtons method. Suppose that the point x is close to the root. Let us try to find the step Δx which brings us to the solution f_i(x+Δx)=0. The first order Taylor expansion gives a system of linear equations

f_i(x)+∑_k ^∂f_i/_{∂x_k}Δx_k = 0 ⇒ A⋅Δx = -F , A_ik ≡ [[^∂f_i/_{∂x_k}]], F ≡ [F_i]

The solution Δx to this equation gives the approximate direction and the step-size towards the root. The modified Newton's method instead of the full step uses a more conservative approach, fx:

λ = 1;  do {
	z = x + λΔx;
	λ = λ/2;
	} while( |f(z)|>(1-^λ/₂)*|f(x)| && λ>0.01)

Optimization is the problem of finding minimum (or maximum) of a given function, often with some constraints. The Nelder-Mead method or downhill simplex method is a commonly used nonlinear optimization algorithm in n-dimensional space. The method finds a minimum by transforming a simplex (a polytope of n+1 vertices) according to the function values at the vertices, moving it downhill until it converges towards the minimum (maximum).

Definitions:

simplex: a figure (polytope) represented by n+1 points p_k, k=1..(n+1), where each point p_k is an n-dimensional vector.
highest point, p_hi : f(p_hi) = max_(k) f(p_k);
lowest point, p_lo : f(p_lo) = min_(k) f(p_k);
centroid, p_ce : p_ce = ¹/_n ∑_{(k ≠ hi)} p_k

Operations on the simplex:

Reflection: p_hi → p_re = p_ce + (p_ce - p_hi),
Reflection-and-Expansion: p_hi → p_ex = p_ce + 2(p_ce - p_hi),
Contraction: p_hi → p_co = p_ce + ½(p_hi - p_ce),
Reduction: p_k≠lo = ¹/₂(p_k+p_lo), k=1..(n+1)

Algorithm:

do{	try Reflection
	if( f(p_re)<f(p_lo) ){ do Reflection-and-Expansion } 
	elseif( f(p_re)<f(p_hi) ){ do Reflection }
	else { 	try Contraction
		if( f(p_co)<f(p_hi) ){do Contraction}
		else{ do Reduction }
	} until converged

Problems

Implement the Modified Newton's method and the downhill simplex method
Solve the system of two equations (1-x)=0, 10(x-y²)=0.
Find the minimum of a paraboloid f(x,y)=10(x-1)²+20(y-2)².