University:
Whitman College
Course:
MATH-350 | Foundations of Machine Learning
Academic year:

2020
Views:

417

Pages:

13
Author:

Leia Mcknight

Optimization and Calculus To begin, there is a close relationship between finding the roots to a function and optimizing a function. In the former case, we solve g(x) = 0 for x. In the latter, we solve: f 0 (x) = 0 for x. Therefore, discussions about optimization often turn out to be discussions about finding roots. In that spirit, we look at a very basic algorithm for finding roots- An algorithm called “The Bisection Method”. The Bisection Method The motivation for this method comes from the Intermediate Value Theorem from CalculusIn this case, suppose that our function g is continuous on [a, b], and further g(a) and g(b) have different signs (more compactly g(a)g(b) < 0), then there is a c in the interval such that g(c) = 0. Now, given such an interval [a, b], we can get a better approximation by breaking the interval in half. Here is the algorithm written in Matlab: function xc=bisect(f,a,b,tol) % Bisection Method, xc=bisect(f,a,b,tol) % Computes an approximation to f(x)=0 given that the % root is bracketed in [a,b] with f(a)f(b)<0. Will run % until TOL is reached, and will output the solution xc. % % EXAMPLE: f=inline(’x^3+x-1’); % xc=bisect(f,0,1,0.00005); %Error check and initialization: fa=feval(f,a); fb=feval(f,b); if sign(fa)*sign(fb)>=0 error(’Root may not be bracketed’); end iter=0; while (b-a)/2>tol iter=iter+1; c=(a+b)/2; fc=feval(f,c); if fc==0 %This means that (a+b)/2 is the root1 break %Break out of the while loop and %continue execution end if sign(fc)*sign(fa)<0 %New interval is [a,c] (reset b) b=c; fb=fc; else a=c; fa=fc; %New interval is [c,b] (reset a) end end fprintf(’Finished after %d iterates\n’,iter); xc=(a+b)/2; The nice thing about the bisection method is that it is easy to implement. It takes a lot of iterations to converge, however. Newton’s Method Another method we have from Calculus is Newton’s Method. Newton’s Method is a lot faster, but it also requires the computation of the derivative. The formula is given below. If you’re not sure where the formula comes from, we’ll review it in class (you can also look it up online or in a calculus text). Newton’s Method Newton’s method is used to locate a root to a function g. It uses an initial guess and produces a sequence of values that (hopefully) converge to a root. Given g(x), and an initial guess of the root, x0 , we iterate the following: xi+1 = xi − g(xi ) g 0 (xi ) In Matlab, this is straightforward as long as we have a separate function that will input x and output both the value of the function g and the value of g 0 . Here’s an example of how that would work: function out=NewtonMethod(F,x0,numits,tol) % Inputs to Newton’s Method: % F- Name of a function that returns BOTH % values of g(x) and g’(x) % x0= Initial value of x. % numits= Maximum number of iterations % tol = Tolerance (like 1e-6) measures % change between iterates of x for k=1:numits 2 [g,gprime]=feval(F,x0); if abs(gprime 0 and fxx (a, b) > 0, then f (a, b) is a local min. • If D > 0 and fxx (a, b) < 0, then f (a, b) is a local max. • If D < 0, then f (a, b) is a saddle point. The Hessian of f : Hf = fxx (x, y) fxy (x, y) fyx (x, y) fyy (x, y) = 3x2 − 1 0 0 1 Therefore, the second derivatives test is a test using the determinant of the Hessian (more generally, we would need the eigenvalues of the Hessian). At (±1, 0), the determinant is positive and fxx (±1, 0) is positive. Therefore, f (±1, 0) = 1/4 is the local minimum. We have a saddle point at the origin. Newton’s Method, Matlab Here is a function that will implement the multidimensional Newton’s method in Matlab. When you write the file for your function, you will need to include the gradient and the Hessian. In the previous example, here’s the test function file: function [y,dy,hy]=newttest(x) % A test function for Newton’s Method for Optimization % The input is the VECTOR x (with elements x,y below) % % y = (1/4)x^4-(1/2)x^2+(1/2)y^2 % dy = Gradient = [x^3-x; y] (The gradient will output as a COLUMN) % hy = Hessian = [3x^2-1, 0;0,1] 9 y=(1/4)*x(1)^4-(1/2)*x(1)^(1/2)*x(2)^2; dy=[x(1)^3-x(1); x(2)]; hy=[3*x(1)^2-1, 0;0,1]; Here’s the main function we’ll use: function out=MultiNewton(F,x0,numits,tol) % Newton’s Method defined for optimizing multi-dimensional F. % % F- Name of a function that returns % F, the gradient AND the Hessian % % x0= Initial value of x. % % numits= Maximum number of iterations % % tol = Tolerance (like 1e-6) measures % change between iterates of x for k=1:numits [g,gradg,hessg]=feval(F,x0); % % This is an error check to see if the matrix is % non-invertible. You don’t need to know this, % but we’re using the "condition number" % if cond(hessg)>1000000 error(’The Hessian Matrix is not invertible’); end xnew=x0-inv(hessg)*gradg; d=norm(xnew-x0); if d> out=MultiNewton(’newttest’,[0.65;0.5],100,1e-6); Newton used 8 iterations out = 1 0 Steepest Descent The method of steepest descent is an algorithm that will search for local extrema by taking advantage of the fact about gradients: The gradient of a function at a given point will point in the direction of fastest increase (of the function). Therefore, if we started at a point (or vector) ~a, if we want to find a local maximum, we should move in the direction of the gradient. To locate a local minimum, we should move in the direction negative to the gradient. Exercise: Prove the statement given. Therefore, the method of steepest descent proceeds as follows: Given a starting point ~a and a scalar α (which is referred to as the step size), we iterate the following: ~xi+1 = ~xi − α∇f (~xi ) The method is fairly quick, but can have bad convergence properties- Mainly because we have that step size. There is a way to get “best” step size α. In the following, we’ll continue with finding the local minimum. Once we choose a direction of travel, the idea will be to follow that line until we find the minimum of the function (along the line). That is, we have a small optimization problem: arg mint f (~a − t∇f (~a)) This is called a line search, and can be time consuming. Before continuing, let’s look at this more closely. Define a new function φ(t) as the output along the line:   a1 − tu1  a2 − tu2    φ(t) = f (~a − t~u) = f   ..   . an − tun where ~u is a vector and f depends on x1 , . . . , xn . 11 Then optimizing this means to find where the derivative of φ is zero. Let’s compute the derivative using the chain rule: φ0 (t) = ∂f ∂xn ∂f ∂f ∂f ∂x1 + ··· + = u1 + · · · + un = −∇f (~a − t~u) · ~u ∂x1 ∂t ∂xn ∂t ∂x1 ∂xn (Note the minus sign from differentiating −t~u). Thus, setting this to zero and solving should give us an optimal step size. Example: Apply the method of steepest descent to the following, and try to determine the optimal step size: f (x, y) = 4x2 − 4xy + 2y 2 with initial point (2, 3). Try to determine the best step size at each iteration. SOLUTION: Compute the gradient and evaluate it at (2, 3): ∇f = [8x − 4y, −4x + 4y] ⇒ ∇f (2, 3) = [4, 4] For some fixed h, our next point will be: ~x1 = ~x0 − h∇f (~x0 ) = 2 3 −h 4 4 = 2 − 4h 3 − 4h To find the optimal path, we define φ(t) to be the function restricted to the line: φ(t) = f (~x0 − t∇f (~x0 )) We differentiate to find the minimum: 0 φ (t) = −∇f (~x0 − h∇f (~x0 )) · ∇f (~x0 ) = −[4 − 16t, 4] 4 4 = −32 + 64t Therefore, the derivative is zero for t = 1/2, and the second derivative is positive, so this is indeed where the minimum occurs. Now, using that step size: 1 4 2 0 = ~x1 = − 4 1 3 2 Exercises 1. Use the bisection method (in Matlab) to find the root correct to 6 decimal places: 3x3 + x2 = x + 5. 2. Suppose we have a function f so that f (0, 1) = 3 and ∇f ((0, 1)) = [1, −2]. Use the linearization of f to estimate f (1/2, 3/2). 12 3. Let f (x, y) = x2 y + 3y. Compute the linearization of f at x = 1, y = 1. 4. Let f (x, y) = xy + y 2 . At the point (2, 1), in which direction is f increasing the fastest? How fast is it changing? 5. Use the second derivatives test to classify the critical points of the following functions: (a) f (x, y) = x2 + xy + y 2 + y (b) f (x, y) = xy(1 − x − y) 6. Use Matlab and our Newton’s Method program to find two critical points of f correct to three decimal places. f (x, y) = x4 + y 4 − 4x2 y + 2y Hint: There are three of them in −1 ≤ x ≤ 1, −1 ≤ y ≤ 1, so try several starting points. 7. Perform the computations involved in the second step of the method of steepest descent example (with f (x, y) = 4x2 − 4xy + 2y 2 ). 8. We said that, in order to optimize the step size, we set the derivative of φ to zero: φ0 (t) = ∇f (~a − t~u) · ~u = 0 Show that this implies the following theorem about the method of steepest descent: ∇f (~xi+1 ) · ∇f (~xi ) = 0 or, the gradient vectors from one step to the next are orthogonal to each other. 13

Optimization and Calculus - Study Notes

Related Documents

Description

Related Documents

Free up your schedule!

Take 5 seconds to unlock