Geek House

Newton Method is a important algorithm in calculate the zero point for a function. The idea comes from using the primary item in Talor series to apporximate the function.

f(x) =

If we only reserve the first two items of the series, and solve the equation f(x) = 0, we get

Hence, we could formulate a iterative algorithm to approximate the zero point using the equation:

And the proof for convergence can refer to

http://www.mathcs.emory.edu/ccs/ccs315/ccs315/node17.html

For a real function in vector space, the solution is similar, while we need to consider the Taylor Series in a vector space.

Since in the convex optimization problem, a useful solution is to find the stationary point of the target function, where the gradient is zero.

= 0

We can introducte Newton Method to solve this problem. Similar as before, approximate the function above using Taylor Series. Then we got

G(f, 0) + H(f, 0)*[X1-X0] = 0;

H(f) means the hessian matrix of f.

X1 = X0 - inv(H(f, 0))*G(f, 0)

Repeat this process, it will converge to the optimizer since f is a convex function.

And an important part of this algorithm is to calculate the Hessian matrix of a function. We can implement it in MatLab using the symbolic toolkit. The code is as follows.

function H = Hessian(f, X)
    V = symvar(f);
    n = size(V,2);
    varstr = findsym(f);
    varstr(1,size(varstr,2)+1) = ',';
    splitter = regexp(varstr,',');
    count = 1;
    index = 1;
    while 1
        S(count,:) = varstr(1, index:(splitter(1,count)-1));
        index = splitter(1,count)+1;
        count = count+1;
        if index > size(varstr,2)
            break
        end
    end
    for i=1:n
        for j=1:n
            sym_H(i,j) = diff(diff(f, S(i,:)), S(j,:));
        end
    end
    H = subs(sym_H, V, X);
end

The calculation of gradient is similar. Then the work left would be very trivial.