University:
Massachusetts Institute of Technology
Course:
15.501/516 | Accounting
Academic year:

2023
Views:

364

Pages:

14
Author:

Karissa Bautista

1 Outline 1. 2. 3. 4. 5. Necessary and sucient optimality conditions Gradient methods The steepest descent algorithm Rate of convergence Line search algorithms 2 Last Lecture Slide 2 Nonlinear Optimization Applications Portfolio Selection Facility Location (Geometry Problems) Trac Assignment, Routing 3 The general problem f : 0 such that is a global minimum of N LP if f (x) f (y ) for all y 2 F . 1 Slide 4 4 Convex Sets and Functions Slide 5 A subset S 0 0 f (x + d) ; f (x ) Take limits as ! 0 0 rf (x )0 d 8d 2 0, 9d: rf ( (d: descent direction) su . small, f (x + d) < f (x) 7.10 Proof + rf (x) td + jjdjjR(x d) f (x + d) = f (x) where R(x d) ;! !0 0 f (x + d) ; f (x) = rf (x) td + jjdjjR(x d) rf ( x)td < 0, R(x d) ;! !0 0 ) 8 > 0 su . small f (x + d) < f (x). QED Slide 20 8 Algorithms for unconstrained optimization 8.1 Gradient Methods-Motivation Decrease f (x) until rf (x ) = 0 f (x + d) f (x) + rf (x)0 d If rf (x)0d < 0, then for small > 0, f (x + d) < f (x) 5 Slide 21 9 Gradient Methods 9.1 A generic algorithm x Slide 22 k+1 = xk + k dk If rf (xk ) = 6 0, direction dk satises: rf (xk )0 dk < 0 Step-length k > 0 Principal example: k+1 = xk ; k D k rf (xk ) x k D positive denite symmetric matrix 9.2 Principal directions Steepest descent: x Newton's method: Slide 23 k+1 = xk ; k rf (xk ) k+1 = xk ; k (r2 f (xk ));1 rf (xk ) x 9.3 Other directions Diagonally scaled steepest descent k 2 k ;1 D = Diagonal approximation to (r f (x )) Modied Newton's method k 2 0 ;1 D = Diagonal approximation to (r f (x )) Gauss-Newton method for least squares problems f (x ) = jjg(x)jj2 (rg(xk )rg(xk )0 );1 Slide 24 D k= 10 Steepest descent 10.1 The algorithm Step 0 Given 0, set k := 0. Step 1 k := ;rf ( k ). If jj kjj , then stop. Step 2 Solve min h() := f ( k + k ) for the x d x d x d step-length k , perhaps chosen by an exact or inexact line-search. Step 3 Set xk+1 xk + kdk, k k + 1. Go to Step 1. 6 Slide 25 10.2 An example Slide 26 minimize f (x1 x2) = 5x21 + x22 + 4x1x2 ; 14x1 ; 6x2 + 20 0 0 x = (x1 x2 ) = (1 1) f (x ) = 10 k Given x ;10xk ; 4xk + 14 dk k k k 1 2 d = ;rf (x1 x2 ) = = dk1 ;2x2k ; 4xk1 + 6 2 h() = f (xk + dk ) = 5(xk1 + dk1 )2 + (x2k + dk2 )2 + 4(x1k + dk1 )(x2k + dk2 ); ;14(xk1 + dk1 ) ; 6(xk2 + dk2 ) + 20 k )2 + (dk )2 1 2 k = 2(5(dk(d k2 k k 2 1 ) + (d20) + 4d1 d2 ) Start at x = (0 10) " = 10;6 k xk1 xk2 0:000000 10:000000 ;2:252782 8:786963 0:755548 3:200064 0:204852 2:903535 0:940243 1:537809 0:805625 1:465322 0:985392 1:131468 0:952485 1:113749 0:996429 1:032138 0:988385 1:027806 1 2 3 4 5 6 7 8 9 10 k 11 12 13 14 15 16 17 18 19 20 21 22 23 24 xk1 0:999127 0:997161 0:999787 0:999306 0:999948 0:999830 0:999987 0:999959 0:999997 0:999990 0:999999 0:999998 1:000000 0:999999 xk2 1:007856 1:006797 1:001920 1:001662 1:000469 1:000406 1:000115 1:000099 1:000028 1:000024 1:000007 1:000006 1:000002 1:000001 dk1 dk2 ;26:000000 ;14:000000 1:379968 ;2:562798 ;6:355739 ;3:422321 0:337335 ;0:626480 ;1:553670 ;0:836592 0:082462 ;0:153144 ;0:379797 ;0:204506 0:020158 ;0:037436 ;0:092842 ;0:049992 0:004928 ;0:009151 dk1 ;0:022695 0:001205 ;0:005548 0:000294 ;0:001356 0:000072 ;0:000332 0:000018 ;0:000081 0:000004 ;0:000020 0:000001 ;0:000005 0:000000 dk2 ;0:012221 ;0:002237 ;0:002987 ;0:000547 ;0:000730 ;0:000134 ;0:000179 ;0:000033 ;0:000044 ;0:000008 ;0:000011 ;0:000002 ;0:000003 ;0:000000 7 jjdk jj2 29:52964612 2:91071234 7:21856659 0:71152803 1:76458951 0:17393410 0:43135657 0:04251845 0:10544577 0:01039370 jjdk jj2 0:02577638 0:00254076 0:00630107 0:00062109 0:00154031 0:00015183 0:00037653 0:00003711 0:00009204 0:00000907 0:00002250 0:00000222 0:00000550 0:00000054 k 0:0866 2:1800 0:0866 2:1800 0:0866 2:1800 0:0866 2:1800 0:0866 2:1800 k 0:0866 2:1800 0:0866 2:1800 0:0866 2:1800 0:0866 2:1800 0:0866 2:1803 0:0866 2:1817 0:0866 0:0000 Slide 27 Slide 28 f (xk ) 60:000000 22:222576 12:987827 10:730379 10:178542 10:043645 10:010669 10:002608 10:000638 10:000156 f (xk ) 10:000038 10:000009 10:000002 10:000001 10:000000 10:000000 10:000000 10:000000 10:000000 10:000000 10:000000 10:000000 10:000000 10:000000 Slide 29 Slide 30 5 x2+4 y2+3 x y+7 x+20 1200 1000 800 600 400 200 0 10 5 0 −5 −10 y 0 −5 −10 10 5 Slide 31 x 10 8 6 4 2 0 −2 −5 0 10.3 Important Properties 5 f(xk+1 ) < f(x k ) < < f(x 0) (because dk are descent directions) Under reasonable assumptions of f(x), the sequence x0 x1 : : : will have at least one cluster point x Every cluster point x will satisfy rf(x) = 0 Implication : If f(x) is a convex function, x will be an optimal solution 8 Slide 32 11 Global Convergence Result Theorem: Slide 33 f : Rn ! R is continuously di /ble on F = fx 2 Rn : f (x) f (x0 )g closed, bounded set Every cluster point x of fxk g satises rf (x) = 0. 11.1 Work Per Iteration Two computation tasks at each iteration of steepest descent: Slide 34 Compute rf (xk ) (for quadratic objective functions, it takes O(n2 ) steps) to determine dk = ;rf (xk ) Perform line-search of h() = f (xk + dk ) to determine k = arg min h() = arg min f (xk + dk ) 12 Rate of convergence of algorithms Let z1 : : : zn : : : ! z be a convergent sequence. We say that the order of convergence of this sequence is p if p = sup p : lim sup jjzzk+1;;z jzp j < 1 k!1 k Let zj = lim sup jjzzk+1; ; p zj � The larger p , the k!1 k faster the convergence 12.1 Types of convergence 1. 2. 3. 4. p = 1 p = 1 p = 1 p = 2 Slide 35 0 < < 1, then linear (or geometric) rate of convergence = 0, super-linear convergence = 1, sub-linear convergence quadratic convergence 9 Slide 36 12.2 Examples zk = ak 0 < a < 1 converges linearly to zero, = a Slide 37 zk = a2k 0 < a < 1 converges quadratically to zero zk = k1 converges sub-linearly to zero k zk = k1 converges super-linearly to zero 12.3 Steepest descent zk = f (x k ), z = f (x ), where x = arg min f (x) Then an algorithm exhibits linear convergence if there is a constant < 1 such that Slide 38 f (x k+1) ; f (x ) , f (x k ) ; f (x ) for all k suciently large, where x is an optimal solution. 12.3.1 Discussion f (xk+1 ) ; f (x ) < 1 f (xk ) ; f (x ) If = 0:1, every iteration adds another digit of accuracy to the optimal objective value. Slide 39 If = 0:9, every 22 iterations add another digit of accuracy to the optimal objective value, because (0:9)22 0:1. 13 Rate of convergence of steepest descent 13.1 Quadratic Case 13.1.1 Theorem Slide 40 Suppose f (x) = 12 x0 Qx ; c x Q is psd 0 10 max = largest eigenvalue of Q min = smallest eigenvalues of Q Linear Convergence Theorem : If f(x ) is a quadratic function and then 12 0 f(x k+1) ; f(x ) @ max min ; 1 A f(x k ) ; f(x ) max + 1 min 13.1.2 Discussion 0 f(xk+1 ) ; f(x ) @ k f(x ) ; f(x ) max ; 1 min max + 1 min Q is psd, 12 A (Q) := max min is the condition number of Q (Q) 1 (Q) plays an extremely important role in analyzing computation involving Q f(x k+1) ; f(x ) f(x k ) ; f(x ) (Q) = max min 1.1 3.0 10.0 100.0 200.0 400.0 ( ) ; 1 2 (Q) + 1 For (Q) O(1) converges fast. For large (Q) ( ) ; 1 2 1 2 2 ( ) + 1 (1 ; ( ) ) 1 ; ( ) Q Therefore In k 12 Q Q (f(xk ) ; f(x )) (1 ; (2Q) )k (f(x 0) ; f(x )) (Q)(;ln) iterations, nds xk : (f(xk ) ; f(x )) (f(x0) ; f(x )) 11 Slide 42 Q Upper Bound on Number of Iterations to Reduce Convergence Constant the Optimality Gap by 0.10 0.0023 1 0.25 2 0.67 6 0.96 58 0.98 116 0.99 231 Q Slide 41 Slide 43 13.2 Example 2 Slide 44 f (x) = 21 x Qx ; c x + 10 14 20 5 Q = c= 6 5 1 0 0 (Q) = 30:234 );1 2 = 0:8760 = ((Q Q)+1 k 1 2 3 4 5 6 7 8 9 10 xk1 Slide 45 xk2 40:000000 ;100:000000 25:542693 ;99:696700 26:277558 ;64:668130 16:763512 ;64:468535 17:247111 ;41:416980 10:986120 ;41:285630 11:304366 ;26:115894 7:184142 ;26:029455 7:393573 ;16:046575 4:682141 ;15:989692 k 20 30 40 50 60 70 80 90 xk1 0:460997 ;0:059980 ;0:124280 ;0:132216 ;0:133195 ;0:133316 ;0:133331 ;0:133333 xk2 0:948466 3:038991 3:297005 3:328850 3:332780 3:333265 3:333325 3:333332 jjdk jj2 286:06293014 77:69702948 188:25191488 51:13075844 123:88457127 33:64806192 81:52579489 22:14307211 53:65038732 14:57188362 jjdk jj2 1:79847660 0:22196980 0:02739574 0:00338121 0:00041731 0:00005151 0:00000636 0:00000078 k 0:0506 0:4509 0:0506 0:4509 0:0506 0:4509 0:0506 0:4509 0:0506 0:4509 k 0:4509 0:4509 0:4509 0:4509 0:4509 0:4509 0:4509 0:0000 13.3 Example 3 k � f (xk ) f f(x(xk;)1 );;f f(x(x)� ) 6050:000000 3981:695128 2620:587793 1724:872077 1135:420663 747:515255 492:242977 324:253734 213:703595 140:952906 f (xk ) 3:066216 0:965823 0:933828 0:933341 0:933333 0:933333 0:933333 0:933333 f (x) = 21 x Qx ; c x + 10 14 20 5 Q = c = 5 16 6 0 0 12 0:658079 0:658079 0:658079 0:658079 0:658079 0:658079 0:658079 0:658079 0:658079 Slide 46 f (xk ) ; f (x� ) f (xk;1 ) ; f (x� ) 0:658079 0:658079 0:658079 0:658079 0:658078 0:658025 0:654656 0:000000 Slide 47 Slide 48 (Q) = 1:8541 (Q) ; 1 2 = (Q) + 1 = 0:0896 k 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 xk1 xk2 40:000000 ;100:000000 19:867118 ;1:025060 2:513241 ;4:555081 1:563658 0:113150 0:745149 ;0:053347 0:700361 0:166834 0:661755 0:158981 0:659643 0:169366 0:657822 0:168996 0:657722 0:169486 0:657636 0:169468 0:657632 0:169491 0:657628 0:169490 0:657627 0:169492 0:657627 0:169491 Slide 49 jjdk jj2 1434:79336491 385:96252652 67:67315150 18:20422450 3:19185713 0:85861649 0:15054644 0:04049732 0:00710064 0:00191009 0:00033491 0:00009009 0:00001580 0:00000425 0:00000075 k k � f (xk ) f f(x(xk;)1 );;f f(x(x)� ) 0:0704 76050:000000 0:0459 3591:615327 0:0704 174:058930 0:0459 12:867208 0:0704 5:264475 0:0459 4:905886 0:0704 4:888973 0:0459 4:888175 0:0704 4:888137 0:0459 4:888136 0:0704 4:888136 0:0459 4:888136 0:0704 4:888136 0:0459 4:888136 0:0000 4:888136 0:047166 0:047166 0:047166 0:047166 0:047166 0:047166 0:047166 0:047166 0:047166 0:047166 0:047161 0:047068 0:045002 0:000000 13.4 Empirical behavior The convergence constant bound is not just theoretical. It is typically experienced in practice. Analysis is due to Leonid Kantorovich, who won the Nobel Memorial Prize in Economic Science in 1975 for his contributions to optimization and economic planning. What about non-quadratic functions? { Suppose x = arg minx f (x) 13 Slide 50 Slide 51 Slide 52 { r2 f (x ) is the Hessian of f (x) at x = x { Rate of convergence will depend on (r2f ( )) x 14 Summary 1. Optimality Conditions 2. The steepest descent algorithm - Convergence 3. Rate of convergence of Steepest Descent 15 Choices of step sizes M in f (xk + dk ) Limited Minimization: M in 2 0s] f (xk + dk ) Constant stepsize k = s constant P Diminishing stepsize: k ! 0 k k = 1 Armijo Rule 14 Slide 53 Slide 54