|
|
Fox' Gradient Search with Adaptive Stepsize
|
|
by Dr. William P. Fox (WFox@fmarion.edu) and Dr. William H. Richardson
(WRichardson@fmarion.edu) Dept. of Math., Francis Marion University, Florence.
Adaptation and minor improvements to Maple18 (Maple 2015) by Dr. Henk
Koppelaar (Koppelaar.Henk@GMail.com)
This worksheet solves nonlinear optimization problems by the method of steepest ascent.
Given a function  and a current point  , the search direction is taken to be the
gradient of  at  . The step length is computed by line search, i.e. as the step
length that maximizes  along the gradient direction.
Algorithm for the Gradient Method of Steepest Ascent :
Step 1. Enter the function to be maximized f, the maximum number of iterations allowed n,
starting point  , and an accuracy tolerance t.
Step 2. Choose λ to maximize, 
Step+ 3. Move to next point 
Step 4 . If !["|| Grad[ f(`x__k`, `y__k`))]||>t "](/view.aspx?SI=154132/9c9b79eb3f744f7e7bbcc1eeb57c7dd8.gif) , return to Step 2. Otherwise, we can terminate.
We may also terminate if the number of points found by iterating is greater than the
number n of allowed iterations (in Step 1).
|
>
|
|
|
>
|
![STEEPEST := proc (n, tol, ptx1, ptx2, f) local numIter, numfeval, numgeval, f1, p1, p2, rv, x1pt, x2pt, temp, max1, mg, v1, v2, newt, lambda, nv1, nv2, Fvalue, P, z, z1, z2; description "Fox and Richardson's algorithm adapted by Henk Koppelaar (Delft University of Technology)"; f1 := f; temp := Gradient(f1, [x1, x2]); p1 := unapply(temp[1], x1, x2); p2 := unapply(temp[2], x1, x2); x1pt := ptx1; x2pt := ptx2; numIter, numgeval, numfeval := 1, 1, 1; P := Matrix(n, 2); P[1, 1] := x1pt; P[1, 2] := x2pt; printf("\n\n----------------------------------------------------------------------------"); printf("\n\n Starting point (%7.4f, %7.4f) \n\n", x1pt, x2pt); printf(" Iter Gradient Vector G magnitude of G x[k] Step Length\n\n "); label_7; rv := Vector([p1(x1pt, x2pt), p2(x1pt, x2pt)]); numgeval := numgeval+1; printf("%5d, (%8.4f, %8.4f)", numIter, rv[1], rv[2]); max1 := n; mg := convert(sqrt(rv.rv), float, 5); printf("%12.4f", mg); if mg < tol or max1 <= numIter then goto(label_6) else numIter := numIter+1 end if; v1 := x1pt+t*rv[1]; v2 := x2pt+t*rv[2]; newt := evalf(subs({x1 = v1, x2 = v2}, f1)); numfeval := numfeval+1; z := diff(newt, t); z1 := unapply(z, t); z2 := fsolve(z1(t), t, t = 0 .. infinity); lambda := min(z2); nv1 := evalf(subs({t = lambda}, v1)); nv2 := evalf(subs({t = lambda}, v2)); printf(" (%10.4f, %10.4f), %10.4f \n", x1pt, x2pt, lambda); x1pt := nv1; x2pt := nv2; P[numIter, 1] := x1pt; P[numIter, 2] := x2pt; goto(label_7); label_6; P[numIter+1, 1] := x1pt; P[numIter+1, 2] := x2pt; printf(" (%8.4f,%8.4f)\n", x1pt, x2pt); printf("\n\n----------------------------------------------------------------------------"); printf("\n\n Approximate Solution: (%8.4f,%8.4f)\n", x1pt, x2pt); Fvalue := evalf(subs(x1 = x1pt, x2 = x2pt, f1)); printf(" Maximum Functional Value: %8.4f", Fvalue); printf("\n Number gradient evaluations:%22d", numgeval); printf("\n Number function evaluations:%22d", numfeval); printf("\n\n----------------------------------------------------------------------------") end proc](/view.aspx?SI=154132/2b3b8531614fe3751d76b12620ecee07.gif)
|
|
>
|
|
|
----------------------------------------------------------------------------
Starting point ( 0.6000, 4.0000)
Iter Gradient Vector G magnitude of G x[k] Step Length
1, ( 6.8000, -12.8000) 14.4940 ( 0.6000, 4.0000), 0.1917
2, ( -0.7138, -0.3792) 0.8083 ( 1.9034, 1.5465), 1.2772
3, ( 0.1409, -0.2652) 0.3004 ( 0.9917, 1.0622), 0.1917
4, ( -0.0148, -0.0079) 0.0168 ( 1.0187, 1.0113)
----------------------------------------------------------------------------
Approximate Solution: ( 1.0187, 1.0113)
Maximum Functional Value: 0.9998
Number gradient evaluations: 5
Number function evaluations: 4
----------------------------------------------------------------------------
| |
|
>
|
|
|
----------------------------------------------------------------------------
Starting point ( 1.0000, 1.0000)
Iter Gradient Vector G magnitude of G x[k] Step Length
1, ( 47.0000, 105.0000) 115.0400 ( 1.0000, 1.0000), 0.0380
2, ( 32.7185, -14.6454) 35.8470 ( 2.7852, 4.9882), 0.0857
3, ( 10.2936, 22.9964) 25.1950 ( 5.5883, 3.7335), 0.0380
4, ( 7.1658, -3.2075) 7.8509 ( 5.9793, 4.6069), 0.0857
5, ( 2.2544, 5.0365) 5.5180 ( 6.5932, 4.3321), 0.0380
6, ( 1.5694, -0.7025) 1.7195 ( 6.6788, 4.5234), 0.0857
7, ( 0.4938, 1.1031) 1.2085 ( 6.8133, 4.4632), 0.0380
8, ( 0.3437, -0.1539) 0.3766 ( 6.8320, 4.5051), 0.0857
9, ( 0.1081, 0.2416) 0.2647 ( 6.8615, 4.4919), 0.0380
10, ( 0.0753, -0.0337) 0.0825 ( 6.8656, 4.5011), 0.0857
11, ( 0.0237, 0.0529) 0.0580 ( 6.8720, 4.4982), 0.0380
12, ( 0.0165, -0.0074) 0.0181 ( 6.8729, 4.5002), 0.0857
13, ( 0.0052, 0.0116) 0.0127 ( 6.8744, 4.4996), 0.0380
14, ( 0.0036, -0.0016) 0.0040 ( 6.8745, 4.5001), 0.0857
15, ( 0.0011, 0.0025) 0.0028 ( 6.8749, 4.4999), 0.0380
16, ( 0.0008, -0.0004) 0.0009 ( 6.8749, 4.5000)
----------------------------------------------------------------------------
Approximate Solution: ( 6.8749, 4.5000)
Maximum Functional Value: 392.8125
Number gradient evaluations: 17
Number function evaluations: 16
----------------------------------------------------------------------------
| |
|
>
|
|
|
----------------------------------------------------------------------------
Starting point ( 0.5000, 0.5000)
Iter Gradient Vector G magnitude of G x[k] Step Length
1, ( -0.6487, 1.3513) 1.4989 ( 0.5000, 0.5000), 0.2874
2, ( 0.4084, 0.1961) 0.4530 ( 0.3136, 0.8883), 1.7041
3, ( -0.2993, 0.6235) 0.6917 ( 1.0095, 1.2224), 0.2001
4, ( 0.1097, 0.0526) 0.1216 ( 0.9496, 1.3472), 0.7345
5, ( -0.0298, 0.0621) 0.0689 ( 1.0302, 1.3859), 0.1868
6, ( 0.0090, 0.0043) 0.0099 ( 1.0246, 1.3975)
----------------------------------------------------------------------------
Approximate Solution: ( 1.0246, 1.3975)
Maximum Functional Value: 8.8277
Number gradient evaluations: 7
Number function evaluations: 6
----------------------------------------------------------------------------
| |
|
|
