Homework 3 Solution

All exercise numbers refer to the course text, Numerical Optimization (second edition, 2006).




Exercise 3.2 from the textbook: Show by drawing a picture that if 0 < c2 < c1 < 1 in the weak Wolfe conditions, there may be no that satis es these conditions.



Exercise 3.6 from the textbook.



Write a Matlab code to implement the extrapolation-bisection line search (EBLS) procedure discussed in class (and speci ed below). Use parameters c1 = 10 3 and c2 = 0:5 in EBLS, and rather than iterating \forever," allow a maximum of 25 adjustments of . The header line of your routine should be



function [x,alpha] = EBLS(fun, x, d, alpha start)




Where the output alpha is the value of identi ed by the procedure, and the input alpha start is the initial guess . The other parameters are as follows:




fun - a pointer to a function (such as obja, objb, rosenbrock)




x - a strucure with three elds x.p, x.f, and x.g in which x.p contains the point x, while x.f and x.g contain the function and gradient values corresponding to x. On input, x.p is set to the starting point values (for example, x = struct(’p’, [-1.2, 1.0]);) while x.f and x.g are set to the corresponding function and gradient values. On input, it is assumed that x.f and x.g are set to the current function and gradient values at x.p. On output, it is assumed that x.p is set to x + d (where is the step length identi ed by the EBLS procedure), and x.f and x.g are set to the corresponding values of function and gradient.







d - a vector containing the search direction










1















The routine should call on fun to evaluate the objective function and gradient as computed points, as follows




x.f = feval(fun,x.p,1);




and




x.g = feval(fun,x.p,2);




respectively. (The last argument \1" and \2" indicates to feval to return the function and gradient, respectively.)




Given 0 < c1 < c2 < 1, set L 0, U +1, ; repeat




if f(x + d) f(x) + c1 rf(x)T d then

Set U and (U + L)=2;

else if rf(x + d)T d < c2rf(x)T d then

Set L ;




if U = +1 then

Set 2L;




else




Set = (L + U)=2;




end if




else




Stop (Success!);




end if




until Forever




4. Test your routine by writing a Matlab program SteepDescentLS.m to implement the steepest descent method, with dk = f(xk). Ter-minate when either krf(xk)k2 10 4 or 100000 function evaluations have been taken, whichever comes rst. The rst line of the function should be




function [inform,x] = SteepDescentLS(fun,x,sdparams)




The inputs fun and x are as described above, while sdparams is the following structure:




sdparams = struct(’maxit’,100000,’toler’,1.0e-4,’eta’,0.0);










2















Here, maxit is the maximum number of (outer) iterations of the de-scent method, toler is the convergence threshold for krfk, and eta is explained below.




The output inform is a structure containing two elds: inform.status is 1 if the gradient tolerance is achieved and 0 if not, while inform.iter is the number of steps taken. The output x is the solution structure, with point, function, and gradient values at the nal value of xk.




Test SteepDescentLS on the three functions below. (Matlab codes that implement these functions can be downloaded under the names obja.m, objb.m, and rosenbrock.m.) Your program will be tested using the code descentLS.m, which can also be downloaded.




(a) f(x) = x12
+ 5x22 + x1 5x2


(b) f(x) = x12
+ 5x1x2 + 100x22
x1 + 4x2
(c) f(x) = 100(x2 x12)2 + (1
x1)2 (Rosenbrock’s banana function).



Note that the global variables numf and numg are reported by the pro-gram descentLS and incremented by the function evaluation routines.




Do not print out the value of x at each iteration!




For the initial guess of steplength at each invocation of EBLS within




SteepDescentLS, try a number of possibilities:




= 1;




= ( nal successful value of from previous call to EBLS), where is a chosen parameter greater than 1.




These are indicated in your code by the setting of sdparams.eta. If this variable is set of 0, use = 1. Otherwise, use =sdparams.eta.




Experiment with di erent values of , tabulating the dependence of the total number of iterations and the total number of function evaluations on this quantity. Do you see any pattern?




Write a routine to perform steepest descent with backtracking line search. At iteration k, you should start the backtracking with some value k, and choose k to be the rst scalar in the sequence k; k; 2 k; : : :



for which the su cient decrease condition




f(xk + dk) f(xk) + c1 rf(xk)T dk;




3















is satis ed. Use the values c1 = :001 and = 0:5 in your code. The rst line of your code should be







function [inform,x] = SteepDescentBacktrack(fun,x,sdparams)




where the arguments have the same meaning and settings as in SteepDescentLS. Your program will be tested using the code descentBacktrack.m, which can also be downloaded.




Experiment with the same ways of choosing the initial guess k of steplength at iteration k as for SteepDescentLS. What value of are most e ective? Is the choice of more critical in the case of SteepDescentBacktrack than for SteepDescentLS?




Submit your codes for SteepDescentBacktrack.m, SteepDescentLS.m, EBLS.m, and the output from descentBacktrack.m and descentLS.m. Also hand in your written responses to the rst questions and to the questions about the performance of your code.

































































































4