1 Brent's PRAXIS minimizer is available in FORTRAN 77. July 1995
3 "Algorithms for Minimization Without Derivatives"
4 by Richard P. Brent, Prentice-Hall, 1973
7 This book by Brent was a groundbreaking effort.
8 (I believe that it was his Ph.D. thesis at Stanford.)
9 His algorithms for finding roots and minima in
10 one dimension have good performance for typical problems
11 and guaranteed performance in the worst case.
12 (A later rootfinder by J. Bus and Dekker gave
13 a much lower bound for the worst case,
14 but no better performance in typical problems.)
15 These algorithms were implemented in both ALGOL W
16 and FORTRAN by Brent, and have been used fairly widely.
18 Brent also gave a multi-dimensional minimization algorithm,
19 PRAXIS, but only shows an implementation in ALGOL W.
20 This routine has not been widely used, at least in the U.S.
21 The PRAXIS package has been translated into FORTRAN
22 by Rosalee Taylor, Sue Pinski, and me, and
23 I am making it available via anonymous ftp for use as
24 freeware (please do not remove our names).
28 [enter your userid as password]
34 Brent's method and its performance
36 Newton's method for minimization can find the minimum of a
37 quadratic function in one iteration, but is sometimes not
38 convenient to use. In the 1960s, several researchers found
39 iterative methods that solve quadratic problems exactly in a
40 finite number of steps. C. S. Smith (1962) and
41 M. J. D. Powell (1964) devised methods
42 that had this property and did not require derivatives.
43 G. W. Stewart modified the Davidon-Fletcher-Powell quasi-Newton
44 method to use finite difference approximations to approximate
45 the gradient. Powell's method, or later versions by Zangwill,
46 were the most successful of the early direct search methods
47 having the property of finite convergence on quadratic functions.
49 Powell's method was programmed at Harwell as subroutine VA04A,
50 and is available as file va04a.f in the same directory as praxis.f.
51 VA04A is not extremely robust, and can give underflow, overflow,
52 or division by zero. va04a.f has several documented patches in it
53 where I tried to get around various abnormal terminations.
54 I do not recommend VA04A very strongly.
56 Brent's PRAXIS added orthogonalization and several other features
57 to Powell's method. Brent also dealt carefully with roundoff.
59 William H. Press et al. in their book "Numerical Recipes"
61 "Brent has a number of other cute tricks up his sleeve,
62 and his modification of Powell's method is probably
63 the best presently known."
65 Roger Fletcher was less enthusiastic in his review of Brent's book
66 in The Computer Journal 16 (1973) 314:
67 "... I am not convinced that the modifications to Powell's
68 method are the best. Use of eigenvector directions
69 is not independent of scale changes to the variables,
70 and the use of searches in random directions is hardly
71 appealing. Nonetheless all the algorithms are demonstrated
72 to be competitive by numerical examples."
74 The methods of Powell, Brent, et al. require that the function
75 for which a local minimum is sought must be smooth;
76 that is, the function and all of its first partial derivatives
79 Brent compared his method to the methods of Powell, of Stewart,
80 and of Davies, Swann, and Campey. Indirectly, he compared it
81 also to the Davidon-Fletcher-Powell quasi-Newton method.
82 He found that his method was about as efficient as the best
83 of these in most cases, and that it was more robust than others
84 in some cases. (Pages 139-155 in Brent's book give fair
85 comparisons to other methods. The results in Table 7.1 on
86 page 138 are correct, but do not include progress all the way
87 to convergence, and are therefore not too useful.)
89 On least squares problems, all of these general minimization
90 methods are likely to be inefficient compared to least squares
91 methods such as the Gauss-Newton or Marquardt methods.
93 In addition to the scale dependence that Fletcher deplored,
94 PRAXIS also had the disadvantage that it required N, the number
95 of parameters, to be greater than or equal to two.
96 The failure to handle N=1 is an unnecessary and pointless limitation.
101 We have followed Brent's PRAXIS rather closely.
102 I have added a patch to try to handle the case N=1,
103 and an option to use a simpler pseudorandom number generator,
104 DRANDM. The handling of N=1 is not guaranteed.
106 The user writes a main program and a function subprogram
107 to compute the function to be minimized.
108 All communication between the user's main program and PRAXIS
109 is done via COMMON, except for an EXTERNAL parameter giving
110 the name of the function subprogram.
111 The disadvantages of using COMMON are at least two-fold:
113 1) Arrays cannot have adjustable dimensions.
115 2) Because some actual parameters are COMMON variables,
116 the FORTRAN version of PRAXIS probably will not pass
117 the Bell Labs PFORT package as being 100% standard FORTRAN.
118 Nevertheless, this usage will not cause any conflict in
119 any commercial FORTRAN compiler ever written.
120 (If it does, I will apologize and rewrite PRAXIS.)
122 The advantage of using COMMON is that it is not necessary to pass
123 about fifteen more parameters every time the user calls PRAXIS.
124 At present all arrays are dimensioned (20) or (20,20),
125 and this can easily be increased using two simple global editing
126 commands. (In this case, increase the value of NMAX.)
128 There are no DATA statements in PRAXIS, and it was not necessary
129 to use any SAVE statements.
131 We have used DOUBLE PRECISION for all floating point computations,
132 as Brent did. We recommend using DOUBLE PRECISION on all computers
133 except possibly Cray computers, in which REAL is reasonably precise.
134 The value of "machine epsilon" is computed in subroutine PRASET
135 using bisection, and is called EPSMCH.
136 Brent computes EPSMCH**4 and 1/EPSMCH**4 in PRAXIS,
137 and uses these quantities later.
138 Because EPSMCH in DOUBLE PRECISION is less than 1E-16,
139 these fourth powers of EPSMCH and 1/EPSMCH will underflow
140 and overflow on such machines as VAXs and PCs,
141 which have a range of only about 1E38, grossly insufficient
142 for scientific computation. For such machines, Brent recommends
143 increasing the value of EPSMCH.
144 EPSMCH=1E-9 or possibly even 1E-8 might be necessary.
145 A better solution would be to eliminate the explicit use of
146 these fourth powers, accomplishing the same result implicitly.
148 A "bug bounty" of $10 U.S. will be paid by me for the first
149 notification of any error in PRAXIS.
150 The same bounty also applies to any substantive poor design
151 choice (having no redeeming advantages whatever) in the FORTRAN
152 package. (The patch for N=1 is not included, although any
153 suggested improvements in that will be considered carefully.)
155 praxis.f includes test software to run any of the test problems
156 that Brent ran, and is set to run at least one case of each problem.
157 I have run these on an IBM 3090, essentially the same
158 architecture that Brent used, and obtained essentially the same
159 results that Brent shows on pages 140-155. The Hilbert problem with
160 N=12, for which Brent shows no termination results and for which
161 the results in Table 7.1 are correct but not relevant,
162 runs a long time; I cut it off at 3000 function evaluations.
163 I don't particularly like Brent's convergence criterion,
164 which allows this sort of extremely slow creeping progress,
165 but have not modified it.
167 Please notify me of any problems with this software,
168 or of any suggested modifications.
171 Computer Science Department
172 Oklahoma State University
173 Stillwater, Oklahoma 74078, U.S.A.
projects / debian / gnuradio / blob