Problems 1
6.15. Explore the behavior of steepest descent by running polyconverge .m with different parameters.
(a) Try mu=-.01, 0, .0001, .02, .03, .05, 1.0, 10.0. Can mu be too large or too small?
(b) Try N=5, 40, 100, 5000. Can N be too large or too small?
(c) Try a variety of values of x(l). Can x(l) be too large or too small?
As an alternative to simulation, observe that the process (6.6) is itself a linear time invariant system, of the general form x[k + 1] = ax[k] + b (6.7)
which is stable as long as |a| < 1. For a constant input, the final value theorem of z-Transforms (see (A.55)) can be used to show that the asymptotic (convergent) output value is lim/,,-^ x^ = jzr^- To see this without reference to arcane theory, observe that if x^. is to converge, then it must converge to some value, say x*. At convergence, x[k + 1] = x[k] = x*, and so (6.7) implies that x* = ax* + b, which implies that x* = fzr^- (This holds assuming |a| < 1). For example, for (6.6), x* = = 2, which is indeed the minimum.
Thus both simulation and analysis suggest that the iteration (6.6) is a viable way to find the minimum of the function J(x), as long as ¡j, is suitably small. As will become clearer in later sections, such solutions to optimization problems are almost always possible - as long as the function J(x) is different.iable. Similarly, it is usually quite straightforward to simulate the algorithm to examine its behavior in specific cases, though it is not always so easy to carry out a theoretical analysis.
By their nature, steepest descent and hill climbing methods only use local information. This is because the update from a point x[k] depends only on the value of x[k] and on the value of its derivative evaluated at that point. This can be a problem, since if the objective function has many minima, the steepest descent algorithm may become "trapped" at a minimum that is not (globally) the smallest. These are called local minima. To see how this can happen, consider the problem of finding the value of x which minimizes the function
Applying the chain rule, the derivative is e"0-1 M cos(;c) - O.le"0'1 ^ sin(a:) sign(;c)
is the formal derivative of \x\. Solving directly for the minimum point is nontrivial (try it!). Yet implementing a steepest descent search for the minimum can be done straightforwardly using the iteration x[k+ 1] = x[k}~ fie-01\x[k]\(cos(x[k}) - 0.1sin(a;[fc]) sign(a;)). (6.9) To be concrete, replace the update equation in polyconverge .m with x(k+l)=x(k)-mu*exp(-0.l*abs(x(k)))*(cos(x(k))-0.1* sin(x(k))*sign(x(k)));
Post a comment