Embedded Systems October 2000 Vol13_11

Issue link:

Contents of this Issue


Page 18 of 181

Jack W. Crenshaw Moving Right Along When last seen, at the close of las t month 's e pisode , our he ro was busily hammering away in his work- shop, constructing software for hi s Zappo-Ray, po rtable anti-Bre nt fun c- tio n minimize r. His inte ntion was to put togethe r a set of snap-togeth er modul es th a t we re both simple e no ugh to read and understand, and effecti ve enough to handl e eve n to ugh extra te rrestrial and pathologi- cal fun ctio ns. The last module con- structed was the stub version of th e pa rabolic fit shown in Listing l. (In cide ntall y, thi s li sting corrects two e rro rs that cre pt into th e ve rsio n pl-e- sen ted las t month. Bonus question fo r extra cre di t: wha t we re the e rrol-s?) No te th e last two lines of para_shrinkO, which swap the two endpoin ts of the bracketing region. These were put there to match the same two lines in goLd_shri nkO. They have to be there in goLd_shrinkO, to force it to bisect the regions on the left and right side on alternate calls. They don ' t really have to be th e re fo r para_shri nkO, but it seemed a good idea to leave the o utput state in a con- di tio n simila r to tha t whi ch goLd_shri nkO would do. At the close of last month 's session, we plotted the three points being maintain ed by th e minimizer, and noted th e same bothersome effect I had observed earlier: the parabolic fit, if left unaided, tends to hang on to dis- tant endpoints a lot longer than we would wish. In the case of bisection methods, the algorithm has no choice but to pull those endpoin ts closer together. That's what bisection is all abo ut. Either the new point is high enough to use as a new bracketing point, or it's low enough to bring the opposite point in . Eith er way, the endpoin ts move inexorably closer togethe r. In fact, it's the distance between end- points, rathe r than the stability of the midpoin t, that we use as the criterion fo r deciding when we've converged. The method of parabolic fit doesn 't Where should we put this logic? Well , we can always put it in the driver function, exte rnal to fun ction para_shrinkO. I think it bette r to place it within para_shrinkO itself. That is, we allow the [- unction itself to decide whether the minimum it's rec- ommending is acceptabl e, and have it return a Boolean depending on the result. To begin, defin e the logical val-iables: Jack reaches a temporary solution to the problem of minimization. Optimizations will come later. work the same way, so twe can 't guar- antee that each endpoint will be alter- nately moved. This te nde ncy to hang o nto di s- ta nt points leads to two se pa rate pro blems: First, the solution isn ' t ve ry satisfacto ry because we' re fit- ting a curve thro ugh points th at a re no t well-conditi o ned ( two po ints close togeth e r, third ve ry fa r away). Second, we can ' t use the distance be twee n bracketing poin ts in o ur hal t criterio n . No doubt thi s prob- lem is th e reason Bre nt came up with a complex and inscrutable a lgo- rithm fo r deciding when th e solu- tio n was good e no ugh. Our challenge this month is to come up with the logic to keep the parabolic fit under con trol, and to force the use of a bisection method to help e nsure a stabl e and smooth descent to the minimum. #define FALSE 0 #define TRUE (!FALSE) (I've put these definitions in my stan- dard library header, jmath.h) . The n alte r para_shri nk() to return a Boolean. For starters, we canjust fo rce it to always return TRUE. Alternating methods We seem to have established that let- ting the parabolic method run open loop is not veI l' satisfYing, since it tends not to pull in the endpoin ts. The next obvious approach might be to alternate between parabolic and bisection metIl- ods. We can do tIlat by simply putting a counter in para_shrinkO, and having it reUlrn FALSE every otIler pass. Not surprisingly, such an approach is going to take more function evaluations, but Embedded Systems Programming oaOBER 2000 17

Articles in this issue

Archives of this issue

view archives of EETimes - Embedded Systems October 2000 Vol13_11