UNCONSTRAINED OPTIMIZATION ALGORITHMS IN MATLAB / OPTIMIZATION TOOLBOX
For up-to-date information: http://www.mathworks.se/help/techdoc/ref/helpbrowser.html
Only the simplest algorithms are part of the basic distribution of MATLAB.
FUNCTIONS IN THE STANDARD VERSION OF MATLAB
fminbnd: Minimum of a function within an interval [a,b] fminsearch: Minimum of a function with few (2-6) variables (Amoeba)
TMA 4180 Optimeringsteori/HEK
fminbnd
SYNTAX: x = fminbnd(fun,x1,x2) x = fminbnd(fun,x1,x2,options) x = fminbnd(fun,x1,x2,options,P1,P2,...) (obsolete) [x,fval] = fminbnd(...) [x,fval,exitflag] = fminbnd(...) [x,fval,exitflag,output] = fminbnd(...) fun: m-file, [x1 x2]: options: P1, P2, : built-in function or an inline object. search interval Structure*) of parameters. Set by the optimset function. Parameters needed in and passed on to fun. (obsolete)
ALLOWED OPTIONS: Display off=no output; iter =output at each iteration; final displays just the final output. MaxFunEvals Maximum number of function evaluations allowed. MaxIter Maximum number of iterations allowed. TolX Termination tolerance on x. *) Vector/array of various things
TMA 4180 Optimeringsteori/HEK 2
EXAMPLE: [x,fval,exitflag] =fminbnd('cos',3,4,optimset('TolX',1e-12,'Display','iter')) Function-count 1 2 3 4 5 6 7 8 9 x 3.38197 3.61803 3.23607 3.13571 3.1413 3.14159 3.14159 3.14159 3.14159 f(x) -0.971249 -0.888633 -0.995541 -0.999983 -1 -1 -1 -1 -1 Procedure initial golden golden parabolic parabolic parabolic parabolic parabolic parabolic
Optimization terminated successfully: The current x satisfies the termination criteria using OPTIONS.TolX of 1.000000e-012 For a short version of output, use : [x,fval,exitflag,output] =
TMA 4180 Optimeringsteori/HEK
fminsearch
SYNTAX x = fminsearch(fun,x0) x = fminsearch(fun,x0,options) [x,fval] = fminsearch(...) [x,fval,exitflag] = fminsearch(...) [x,fval,exitflag,output] = fminsearch(...)
OPTIONS structure fields: As for fminbnd + Display TolFun simplex (all corners) Termination tolerance on the function value.
Note: The search strategy in Matlab also includes an outside contraction
TMA 4180 Optimeringsteori/HEK
EXAMPLE: [x,fval] = fminsearch('banana', [-1.2, 1] , optimset('TolX',1e-3,'Display','iter')) Iteration Func.-count 1 3 2 5 3 7 4 9 5 11 6 13 7 15 8 16 9 18 10 19 .. 63 119 64 120 65 122 66 124 67 126
TMA 4180 Optimeringsteori/HEK
min f(x) 6.361 4.40994 4.29678 4.29678 4.17987 4.17987 4.17987 4.17987 4.07932 4.07932 2.0633e-007 2.0633e-007 2.0633e-007 2.0633e-007 6.10245e-008
Procedure initial expand expand contract outside contract inside contract outside contract inside reflect expand reflect contract inside reflect contract inside contract inside contract inside
5
optimset
(Type optimset on command line for full info about available options)
SYNTAX:
options = optimset( 'param1' , value1 , 'param2' , value2,...)
options = optimset options = optimset(optimfun) options = optimset(oldopts,'param1',value1,...) options = optimset(oldopts,newopts)
PARAMETERS:
MATLAB AND OPTIMIZATION TOOLBOX:
Display MaxFunEvals MaxIter TolFun TolX [ off | iter | simplex|{final} ] [ positive integer ] [ positive integer ] [ positive scalar ] [ positive scalar ]
TMA 4180 Optimeringsteori/HEK
MATLAB OPTIMIZATION TOOLBOX ONLY (incomplete):
DerivativeCheck Diagnostics DiffMaxChange DiffMinChange GoalsExactAchieve GradConstr GradObj Hessian HessPattern HessUpdate JacobPattern Jacobian LargeScale LevenbergMarquardt LineSearchType MaxPCGIter MeritFunction MinAbsMax PrecondBandWidth TolCon TolPCG TypicalX [ on | {off} ] [ on | {off} ] [ positive scalar | {1e-1} ] [ positive scalar | {1e-8} ] [ positive scalar integer | {0} ] [ on | {off} ] [ on | {off} ] [ on | {off} ] [ sparse matrix ] [ {bfgs} | dfp | gillmurray | steepdesc ] [ sparse matrix ] [ on | {off} ] [ {on} | off ] [ on | off ] [ cubicpoly | {quadcubic} ] [ positive integer ] [ singleobj | {multiobj} ] [ positive scalar integer | {0} ] [ positive integer | Inf ] [ positive scalar ] [ positive scalar | {0.1} ] [ vector ]
TMA 4180 Optimeringsteori/HEK
ROUTINES IN MATLAB OPTIMIZATION TOOLBOX
fminunc: Unconstrained minimization
Medium size: BFGS Quasi-Newton (or Amoeba). Different strategies for line search. Large size: Trust region methods. Different strategies for approximations to the Hessian matrix. Preconditioned Conjugate Gradient (PCG).
lsqnonlin:
Non-linear least square (includes simple interval constraints)
Medium size: Gauss/Newton or Levenberg/Marquardt Large size: Trust region methods or Gauss/Newton solved using PCG.
TMA 4180 Optimeringsteori/HEK
fminunc
Syntax x = fminunc(fun,x0) x = fminunc(fun,x0,options) [x,fval] [x,fval,exitflag] [x,fval,exitflag,output] [x,fval,exitflag,output,grad] [x,fval,exitflag,output,grad,hessian]
= fminunc(...) = fminunc(...) = fminunc(...) = fminunc(...) = fminunc(...)
Function, (gradient, (Hessian)):
function [f,g,H] = myfun(x) f = ... % Compute the objective function value at x if nargout > 1 % fun called with two output arguments g = ... % gradient of the function evaluated at x if nargout > 2 % fun called with three arguments H = ... % Hessian evaluated at x end options = optimset('GradObj',on,'Hessian',on,...)
TMA 4180 Optimeringsteori/HEK
OPTIONS:
LargeScale GradObj
Medium-scale algorithm only:
DerivativeCheck DiffMaxChange DiffMinChange LineSearchType
Large-scale algorithm only:
HessPattern MaxPCGIter PrecondBandWidth TolPCG TypicalX
TMA 4180 Optimeringsteori/HEK
10
Example: fminunc
function [f,g] = uncoex(x) f = 3*(x(1)-1)^2 + 2*x(1)*x(2) + x(2)^2; if nargout > 1 g(1) = 6*(x(1)-1)+2*x(2); g(2) = 2*x(1)+2*x(2); end options = optimset('GradObj','on','Display','iter',); x0 = [10,9]; [x,fval] = fminunc('uncoex',x0,options) Norm of step First-order optimality *)
Iteration
f(x)
CG-iterations
1 504 1 72 0 2 23.8973 10 12.5 1 3 -1.5 4.34752 5.33e-015 1 Optimization terminated successfully: First-order optimality less than OPTIONS.TolFun, and no negative/zero curvature detected x = [1.5000 -1.5000] fval = -1.5000
TMA 4180 Optimeringsteori/HEK
*) Infinity norm of the gradient.
11
lsqnonlin
SYNTAX
x = lsqnonlin(fun,x0) x = lsqnonlin(fun,x0,lb,ub) x = lsqnonlin(fun,x0,lb,ub,options) [x,resnorm] [x,resnorm,residual] [x,resnorm,residual,exitflag] [x,resnorm,residual,exitflag,output] [x,resnorm,residual,exitflag,output,lambda] [x,resnorm,residual,exitflag,output,lambda,jacobian] = lsqnonlin(...) = lsqnonlin(...) = lsqnonlin(...) = lsqnonlin(...) = lsqnonlin(...) = lsqnonlin(...)
function [F,J] = myfun(x) F = ... % objective function values at x if nargout > 1 % two output arguments J = ... % Jacobian of the function evaluated at x end options = optimset('Jacobian','on')
TMA 4180 Optimeringsteori/HEK
12
Both the large-scale and medium-scale algorithms: Diagnostics Display Jacobian MaxFunEvals MaxIter TolFun TolX Medium-scale algorithm only: DerivativeChec DiffMaxChange DiffMinChange. LevenbergMarquardt LineSearchType Large-scale algorithm only: JacobPattern MaxPCGIter PrecondBandWidth TolPCG. TypicalX
TMA 4180 Optimeringsteori/HEK 13
Example: lsqnonlin
function F = nonlsqfun(x) k = 1:20; F = 2 + 2*k-exp(k*x(1))-exp(k*x(2)); options = optimset('Display','iter'); x0 = [0.3 0.4]; [x,resnorm] = lsqnonlin('nonlsqfun',x0,[ ],[ ],options) Norm of step 1 0.231124 1.04515 10 2.5 First-order optimality 3.49e+008 1.15e+008 1.77e+007 1.77e+007 1.77e+007 0.0177 0.0177 0.00378
Iter. Func-count f(x) 1 4 2.048e+007 2 7 5.80e+006 3 10 850620 4 13 850620 5 16 850620 -------------------------------------------30 91 1449.48 1.19209e-006 31 94 1449.48 1.19209e-006 32 97 1449.48 2.98023e-007 Optimization terminated successfully: Norm of the current step is less than OPTIONS.TolX x = 0.1652 0.1652 resnorm = 1.4495e+003
TMA 4180 Optimeringsteori/HEK
CG-iterations 0 1 1 1 0 0 1 0
14
