RS – Num Opt
                                                 Numerical Optimization
                                      General Setup
                                      • Let f(.) be a function such that
                                                      xRn  f b , xR
                                      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           x2
                                                 U(x) 10x*40  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)e5x24x2
                                             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()54xx2
                                                                                                                                                                                  x10
                                                                                                                 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*24x*2]
                                                                                                            x  f'(x)                                                                                       (x*10)2                                                                       0
                                                                                                                        x* 1002 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