Application Center - Maplesoft
  Submit your work
Application Center Applications Steepest Ascent Method Preview

App Preview:

Steepest Ascent Method

You can switch back to the summary page by clicking here.

Learn about Maple
Download Application



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 f(x, y) and a current point x__0, y__0,  the search direction is taken to be the
gradient of f(x, y)  at x__0, y__0. The step length is computed by line search,  i.e. as the step
length that maximizes f(x, y) 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 x, y,  and an accuracy tolerance  t.

 

Step 2. Choose  λ to maximize,   f(L(k)) = f((x__k, y__k)+lambda*Grad(f(x__k, y__k)))

 

Step+ 3. Move to next point (`x__k+1`, `y__k+1`) = (x__k, y__k)+lambda*Grad(f(x__k, y__k))

 

Step 4 . If   "|| Grad[ f(`x__k`, `y__k`))]||>t ",  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).

 

> 

with(VectorCalculus)
> 

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
> 

f := -x1^2+2*x1*x2-2*x2^2+2*x2; STEEPEST(10, 0.5e-1, .6, 4.0, f)



----------------------------------------------------------------------------

 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

----------------------------------------------------------------------------

> 

f := -4*x1^2-15*x2^2+55*x1+135*x2-100; STEEPEST(20, 0.1e-2, 1.0, 1.0, f)



----------------------------------------------------------------------------

 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

----------------------------------------------------------------------------

> 

f := 2*x1*x2+2*x2-exp(x1)-exp(x2)+10; STEEPEST(50, 0.5e-1, .5, .5, f)



----------------------------------------------------------------------------

 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

----------------------------------------------------------------------------