134x Filetype PDF File size 1.30 MB Source: www.bauer.uh.edu
RS – Num Opt Numerical Optimization General Setup Let f(.) be a function such that xRn f b , xR where b is a vector of unknown parameters. In many cases, b will not have a closed form solution. We will estimate b by minimizing some loss function. Popular loss function: A sum of squares. Let {y,x} be a set of measurements/constraints. That is, we fit f(.), t t in general a nice smooth function, to the data by solving: 1 , 2 b min 2 yt f xt b t , or min b 2 with y f x b t t t t t 1 RS – Num Opt Finding a Minimum - Review When f is twice differentiable, a local minima is characterized by: 1. f (b )=0 (f.o.c.) min 2. hT H b T h h (s.o.c.) 0, for all small enough f min Usual approach: Solve f (b )=0 for b min min Check H(b ) is positive definitive. min Sometimes, an analytical solution to f (b )=0 is not possible or hard to find. min For these situations, a numerical solution is needed. Notation: f (.): gradient (of a scalar field). : Vector differential operator (“del”). Finding a Univariate Minimum Finding an analytic minimum of a simple univariate sometimes is easy given the usual f.o.c. and s.o.c. Example:Quadratic Function 2 Ux()54x x2 U(x) 10x*40 x*2 x 5 2U(x) x2 10 0 Analytical solution (from f.o.c.): x*= 0.4. Thefunction is globally convex, that is x*=2/5 is a global minimum. Note: To find x*, we find the zeroes of the first derivative function. 2 RS – Num Opt Finding a Univariate Minimum Minimization in R: We can easily use the popular R optimizer, optim to find the minimumofU(x)--in this case, not very intersting application! Example:CodeinR >f<-function(x) (5*x^2-4*x+2) >optim(10, f, method="Brent",lower=-10,upper=10)$par [1] 0.4 >curve(f,from=-5,to=5) Finding a Univariate Minimum Straightforward transformations add little additional complexity: U(x)e5x24x2 U(x) 2 x U(x*)10x*4 0 x*5 Again, we get an analytical solution from the f.o.c. =>x*=2/5. Since U(.) is globally convex, x*=2/5 is a global minimum. Usual Problems: Discontinuities, Unboundedness 3 RS – Num Opt Finding a Univariate Minimum - Discontinuity Be careful of discontinuities. Need to restrict range for x. Example: 2 fx()54xx2 x10 600 400 200 0 7 5 1 6 4 0 2 4 6 8 19 13 -8 - - -2 10 12 14 16 18 20 - -1 -1 - -1 -200 -400 -600 -800 Finding a Univariate Minimum - Discontinuity This function has a discontinuity at some point in its range. If we restrict the search to points where x >-10, then the function is defined at all points f (x) (10x*4)(x*10)[5x*24x*2] x f'(x) (x*10)2 0 x* 1002 2710 0.411532 . 10 After restricting the range of x, we find an analytical solution as usual –i.e., by finding the zeroes of f ′(x). 4
no reviews yet
Please Login to review.