Page 340 - Applied Numerical Methods Using MATLAB

UNCONSTRAINED OPTIMIZATION 329

search like the quadratic approximation method.

α k−1 = ArgMin f(x k−1 − αg k−1 /||g k−1 ||) (7.1.8)
α
Step 2. Move the approximate minimum by the step-size α k−1 along the direc-
tion of the negative gradient −g k−1 to get the next point

x k = x k−1 − α k−1 g k−1 /||g k−1 || (7.1.9)

Step 3.If x k ≈ x k−1 and f(x k ) ≈ f(x k−1 ), then declare x k to be the minimum
and terminate the procedure. Otherwise, go back to step 1.

function [xo,fo] = opt_steep(f,x0,TolX,TolFun,alpha0,MaxIter)
% minimize the ftn f by the steepest descent method.
%input: f = ftn to be given as a string ’f’
% x0 = the initial guess of the solution
%output: x0 = the minimum point reached
% f0 = f(x(0))
if nargin < 6, MaxIter = 100; end %maximum # of iteration
if nargin < 5, alpha0 = 10; end %initial step size
if nargin < 4, TolFun = 1e-8; end %|f(x)| < TolFun wanted
if nargin < 3, TolX = 1e-6; end %|x(k)- x(k - 1)|<TolX wanted
x = x0; fx0 = feval(f,x0); fx = fx0;
alpha = alpha0; kmax1 = 25;
warning = 0; %the # of vain wanderings to find the optimum step size
fork=1: MaxIter
g = grad(f,x); g = g/norm(g); %gradient as a row vector
alpha = alpha*2; %for trial move in negative gradient direction
fx1 = feval(f,x - alpha*2*g);
for k1 = 1:kmax1 %find the optimum step size(alpha) by line search
fx2 = fx1; fx1 = feval(f,x-alpha*g);
if fx0 > fx1+TolFun & fx1 < fx2 - TolFun %fx0 > fx1 < fx2
den = 4*fx1 - 2*fx0 - 2*fx2; num = den - fx0 + fx2; %Eq.(7.1.5)
alpha = alpha*num/den;
x=x- alpha*g; fx = feval(f,x); %Eq.(7.1.9)
break;
else alpha = alpha/2;
end
end
if k1 >= kmax1, warning = warning + 1; %failed to find optimum step size
else warning = 0;
end
if warning >= 2|(norm(x - x0) < TolX&abs(fx - fx0) < TolFun), break; end
x0 = x; fx0 = fx;
end
xo=x; fo=fx;
if k == MaxIter, fprintf(’Just best in %d iterations’,MaxIter), end
%nm714
f713 = inline(’x(1)*(x(1) - 4 - x(2)) + x(2)*(x(2)- 1)’,’x’);
x0 = [0 0], TolX = 1e-4; TolFun = 1e-9; alpha0 = 1; MaxIter = 100;
[xo,fo] = opt_steep(f713,x0,TolX,TolFun,alpha0,MaxIter)