Chapter 4: Unconstrained Optimization - McMaster University

1 Chapter 4: Unconstrained Optimization Unconstrained Optimization problemminxF(x)ormaxxF(x) Constrained Optimization problemminxF(x)ormaxxF(x)subject tog(x) = 0and/orh(x)<0orh(x)>0 Example: minimize the outer area ofa cylinder subject to a fixed functionF(x) = 2 r2+ 2 rh, x=[rh]Constraint:2 r2h=V1 Outline: Part I: one-dimensional Unconstrained Optimization Analytical method Newton s method Golden-section search method Part II: multidimensional Unconstrained Optimization Analytical method Gradient method steepest ascent (descent) method Newton s method2 PART I: One-Dimensional Unconstrained Optimization Techniques1 Analytical approach (1-D)minxF(x)ormaxxF(x) LetF (x) = 0and findx=x . IfF (x )>0,F(x ) = minxF(x),x is a local minimum ofF(x); IfF (x )<0,F(x ) = maxxF(x),x is a local maximum ofF(x); IfF (x ) = 0,x is a critical point ofF(x)Example1:F(x) =x2,F (x) = 2x= 0,x = (x ) = 2>0.

2 Therefore,F(0) = minxF(x)Example2:F(x) =x3,F (x) = 3x2= 0,x = (x ) = is not a localminimum nor a local :F(x) =x4,F (x) = 4x3= 0,x = (x ) = example 2,F (x)>0whenx < x andF (x)>0whenx > x .In example 3,x is a local minimum ofF(x).F (x)<0whenx < x andF (x)>0whenx > x .3F (x)=0F (x)<0F (x)>0F (x)=0F (x)>0F (x)=0F (x)<0F (x)>0F (x)<0F (x)>0F (x)>0F (x)=0 Figure 1: Example of constrained Optimization problem2 Newton s MethodminxF(x)ormaxxF(x)Usexkto denote the current (xk+p) =F(xk) +pF (xk) +p22F (xk) +.. F(xk) +pF (xk) +p22F (xk)4F(x ) = minxF(x) minpF(xk+p) minp[F(xk) +pF (xk) +p22F (xk)]Let F(x) p=F (xk) +pF (xk) = 0we havep= F (xk)F (xk)Newton s iterationxk+1=xk+p=xk F (xk)F (xk)Example: find the maximum value off(x) = 2 sinx x210with an initial guessofx0= :f (x) = 2 cosx 2x10= 2 cosx x55f (x) = 2 sinx 15xi+1=xi 2 cosxi xi5 2 sinxi 15x0= ,x1= ,x2= : Same as method for solvingF (x) = 0.

3 Quadratic convergence,|xk+1 x | |xk x |2 May diverge Requires both first and second derivatives Solution can be either local minimum or maximum63 Golden-section search for Optimization in 1-DmaxxF(x)(minxF(x)is equivalent tomaxx F(x))Assume: only 1 peak value (x ) in(xl, xu) < 2 intermediate values,x1andx2so thatx1=xl+d,x2=xu d, andx1> (x1)andF(x2)and update the search range IfF(x1)< F(x2), thenx < x1. Updatexl=xlandxu=x1. IfF(x1)> F(x2), thenx > x2. Updatexl=x2andxu=xu. IfF(x1) =F(x2), thenx2< x < x1. Updatexl=x2andxu= =x1ifF(x1)> F(x2), andx =x2ifF(x1)< F(x2)7F(x1)>F(x2)(new )Xl(new )Xl(new )Xu(new )Xl(new )Xu(new )XlX2X1 XuXl(new )Xu(new )XlXuX1X2 XlX2X1 XuF(x1)<F(x2)XlXuX1X2 XuFigure 2: Golden search: updating search range Calculate a.

4 If a< threshold, end. a= xnew xoldxnew 100%8 The choice ofd Any values can be used as long asx1> x2. Ifdis selected appropriately, the number of function evaluations can be 3: Golden search: the choice ofdd0=l1,d1=l2=l0 d0=l0 l1. Therefore,l0=l1+ Thenl0l1= (l1+l2)l2. Then1 =(l2l1)2+ Thenr2+r 1 = 0, andr= 5 12 (xu xl) (xu xl)is referred to as the golden error a= xnew xoldxnew 100%ConsiderF(x2)< F(x1). That is,xl=x2, andxu= case (a),x > x2andx closer tox2. x x1 x2= (xl+d) (xu d)= (xl xu) + 2d= (xl xu) + 2r(xu xl)= (2r 1)(xu xl) (xu xl)For case (b),x > x2andx closer toxu. x xu x1=xu (xl+d) =xu xl d= (xu xl) r(xu xl) = (1 r)(xu xl) (xu xl)Therefore, the maximum absolute error is(1 r)(xu xl) (xu xl).10 a xx 100% (1 r)(xu xl)|x | 100%= (xu xl)|x | 100%Example: Find the maximum off(x) = 2 sinx x210withxl= 0andxu= 4asthe starting search :Iteration 1:xl= 0,xu= 4,d= 5 12(xu xl) = ,x1=xl+d= ,x2=xu d= (x1) = ,f(x2) = (x2)> f(x1),x =x2= ,xl=xl= 0andxu=x1= 2:xl= 0,xu= ,d= 5 12(xu xl) = ,x1=xl+d= ,x2=xu d= (x1) = ,f(x2) = (x1)> f(x2),x =x1= ,xl=x2= Unconstrained Optimization4 Analytical Method Definitions: Iff(x, y)< f(a, b)for all(x, y)near(a, b),f(a, b)is a local maximum; Iff(x, y)> f(a, b)for all(x, y)near(a, b),f(a, b)is a local minimum.

5 Iff(x, y)has a local maximum or minimum at(a, b), and the first order partialderivatives off(x, y)exist at(a, b), then f x|(a,b)= 0,and f y|(a,b)= 0 If f x|(a,b)= 0and f y|(a,b)= 0,then(a, b)is a critical point or stationary point off(x, y). If f x|(a,b)= 0and f y|(a,b)= 012and the second order partial derivatives off(x, y)are continuous, then When|H|>0and 2f x2|(a,b)<0,f(a, b)is a local maximum off(x, y). When|H|>0and 2f x2|(a,b)>0,f(a, b)is a local minimum off(x, y). When|H|<0,f(a, b)is a saddle off(x, y):H=[ 2f x2 2f x y 2f y x 2f y2] |H|= 2f x2 2f y2 2f x y 2f y x When 2f x yis continuous, 2f x y= 2f y x. When|H|>0, 2f x2 2f y2> (saddle point):f(x, y) =x2 y2. f x= 2x, f y= f x= 0, thenx = 0. Let f y= 0, theny = ,(0,0)is a critical point.

6 2f x2= x(2x) = 2, 2f y2= y( 2y) = 2 2f x y= x( 2y) = 0, 2f y x= y(2x) = 0|H|= 2f x2 2f y2 2f x y 2f y x= 4<0 Therefore,(x , y ) = (0,0)is a saddle :f(x, y) = 2xy+ 2x x2 2y2, find the optimum off(x, y).Solution: f x= 2y+ 2 2x, f y= 2x f x= 0, 2x+ 2y= f y= 0,2x 4y= = 2andy = 1, ,(2,1)is a critical point. 2f x2= x(2y+ 2 2x) = 2 2f y2= y(2x 4y) = 4 2f x y= x(2x 4y) = 2, or14 y2yFigure 4: Saddle point15 2f y x= y(2y+ 2 2x) = 2|H|= 2f x2 2f y2 2f x y 2f y x= ( 2) ( 4) 22= 4>0 2f x2<0.(x , y ) = (2,1)is a local Ascent (Descent) MethodIdea: starting from an initial point, find the function maximum (minimum) alongthe steepest direction so that shortest searching time is direction: directional derivative is maximum in that direction gradi-ent derivativeDhf(x, y) = f x cos + f y sin = [ f x f y] [cos sin ] : inner productGradient16 When[ f x f y] is in the same direction as[cos sin ] , the directional derivativeis maximized.

7 This direction is called gradient off(x, y).The gradient of a 2-D function is represented as f(x, y) = f x~i+ f y~j, or[ f x f y] .The gradient of ann-D function is represented as f(~X) =[ f x1 f x2.. f xn] ,where~X= [x1x2.. xn] Example:f(x, y) =xy2. Use the gradient to evaluate the path of steepest ascentat (2,2).Solution: f x=y2, f y= 2xy. f x|(2,2)= 22= 4, f y|(2,2)= 2 2 2 = 8 Gradient: f(x, y) = f x~i+ f y~j= 4~i+ 8~j = tan 184= , =4 42+82,sin =8 42+ derivative at (2,2): f x cos + f y sin = 4 cos + 8 sin = 6= , for example, = , thenDh f|(2,2)= f x cos + f y sin = 4 cos + 8 sin = < ascent methodIdeally: Start from(x0, y0). Evaluate gradient at(x0, y0). Walk for a tiny distance along the gradient direction till(x1, y1). Reevaluate gradient at(x1, y1)and repeat the : always keep steepest direction and walk shortest distanceCons: not practical due to continuous reevaluation of the : Start from(x0, y0).

8 Evaluate gradient (h) at(x0, y0).18 Evaluatef(x, y)in directionh. Find the maximum function value in this direction at(x1, y1). Repeat the process until(xi+1, yi+1)is close enough to(xi, yi).Find~Xi+1from~XiFor a 2-D function, evaluatef(x, y)in directionh:g( ) =f(xi+ f x|(xi,yi) , yi+ f y|(xi,yi) )where is the coordinate ann-D functionf(~X),g( ) =f(~X+ f|(~Xi) )Letg ( ) = 0and find the solution = .Updatexi+1=xi+ f x|(xi,yi) ,yi+1=yi+ f y|(xi,yi) .19 Figure 5: Illustration of steepest ascent20 Figure 6: Relationship between an arbitrary directionhandxandycoordinates21 Example:f(x, y) = 2xy+ 2x x2 2y2,(x0, y0) = ( 1,1).First iteration:x0= 1,y0= 1. f x|( 1,1)= 2y+ 2 2x|( 1,1)= 6, f y|( 1,1)= 2x 4y|( 1,1)= 6 f= 6~i 6~jg( ) =f(x0+ f x|(x0,y0) , y0+ f y|(x0,y0) )=f( 1 + 6 ,1 6 )= 2 ( 1 + 6 ) (1 6 ) + 2( 1 + 6 ) ( 1 + 6 )2 2(1 6 )2= 180 2+ 72 7g ( ) = 360 + 72 = 0, = iteration:x1=x0+ f x|(x0,y0) = 1+6 = ,y1=y0+ f y|(x0,y0) = 1 6 = f x|( , )= 2y+ 2 2x|( , )= 2 ( ) + 2 2 = , f y|( , )= 2x 4y|( , )= 2 4 ( ) = f= ~i+ ~jg( ) =f(x1+ f x|(x1,y1) , y1+ f y|(x1,y1) )=f( + , + )= 2 ( + ) ( + ) + 2( + ) ( + )2 2( + )2= 2+ + ( ) = + = 0, = iteration:x2=x1+ f x|(x1,y1) = + 1 = ,y2=y1+ f y|(x1,y1) = + 1 = 1.

9 (x , y ) = (2,1)236 Newton s MethodExtend the Newton s method for 1-D case to multidimensional (~X), approximatef(~X)by a second order Taylor series at~X=~Xi:f(~X) f(~Xi) + f (~Xi)(~X ~Xi) +12(~X ~Xi) Hi(~X ~Xi)whereHiis the Hessian matrixH= 2f x21 2f x1 x2.. 2f x1 xn 2f x2 x1 2f x22.. 2f x2 xn.. 2f xn x1 2f xn x2.. 2f x2n At the maximum (or minimum) point, f(~X) xj= 0for allj= 1,2, .. , n, or f=~0. Then f(~Xi) +Hi(~X ~Xi) = 0 IfHiis non-singular,~X=~Xi H 1i f(~Xi)24 Iteration:~Xi+1=~Xi H 1i f(~Xi)Example:f(~X) = + f(~X) =[x15x2]H=[ 2f x2 2f x y 2f y x 2f y2]=[1 00 5]~X0=[51],~X1=~X0 H 1 f(~X0) =[51] [1 0015][55]=[00]Comments: Newton s method Converges quadratically near the optimum Sensitive to initial point Requires matrix inversion Requires first and second order derivatives25