diana aldea mendes - isctehome.iscte-iul.pt/~deam/html/slidesa5.pdf · diana aldea mendes...
TRANSCRIPT
ISCTE/FCUL - Mestrado Matematica Financeira
Aula 5
17 de Janeiro de 2009 Ano lectivo: 2008/2009
Diana Aldea Mendes
Departamento de Metodos Quantitativos, IBS - ISCTE Business School
Gab. 207 AA, [email protected], http://iscte.pt/˜deam
Mestrado Matemática Financeira 01/17/2009 Optimização, Aula 5
1
Optimization Toolbox Matlab
>> [xsol,fopt,exitflag,output,grad,hessian] = fminunc (fun,x0,options)
Input arguments:
- fun: a Matlab function m-file that contains the function to be minimzed
- x0: Startvector for the algorithm, if known, else [ ]
options: options are set using the optimset funciton, they determine what algo-
rism to use,etc.
Output arguments:
Mestrado Matemática Financeira 01/17/2009 Optimização, Aula 5
2
- xsol: optimal solution
- fopt: optimal value of the objective function; i.e. f(xopt)
- exitflag: tells whether the algorithm converged or not, exitflag > 0 means
convergence
- output: a structure for number of iterations, algorithm used and PCG itera-
tions(when LargeScale=on)
- grad: gradient vector at the optimal point xsol.
- hessian: hessian matrix at the optimal point xsol.
Mestrado Matemática Financeira 01/17/2009 Optimização, Aula 5
3
To display the type of options that are available and can be used with the
fminunc.m use
>>optimset(’fminunc’)
Hence, from the list of option parameters displayed, you can easily see that some
of them have default values. However, you can adjust these values depending
on the type of problem you want to solve. However, when you change the
default values of some of the parameters, Matlab might adjust other parameters
automatically.
There are two types of algorithms that you can use with fminunc.m
Mestrado Matemática Financeira 01/17/2009 Optimização, Aula 5
4
(i) Medium-scale algorithms: The medium-scale algorithms under fminunc.m
are based on the Quasi-Newton method. This options used to solve problems of
smaller dimensions. As usual this is set using
>>OldOptions=optimset(’fminunc’);
>>Options=optimset(OldOptions,’LargeScale’,’off’);
With medium Scale algorithm you can also decide how the search direction dk
be determined by adjusting the parameter HessUpdate by using one of:
>>Options=optimset(OldOptions,’LargeScale’,’off’,’HessUpdate’,’bfgs’);
>>Options=optimset(OldOptions,’LargeScale’,’off’,’HessUpdate’,’dfp’);
Mestrado Matemática Financeira 01/17/2009 Optimização, Aula 5
5
>>Options=optimset(OldOptions,’LargeScale’,’off’,’HessUpdate’,’steepdesc’);
(ii) Large-scale algorithms: By default the LargeScale option parameter of Mat-
lab is always on. However, you can set it using
>>OldOptions=optimset(’fminunc’);
>>Options=optimset(OldOptions,’LargeScale’,’on’);
When the ’LargeScale’ is set ’on’, then fminunc.m solves the given unconstrained
problem using the trust-region method. Usually, the large-scale option of fmin-
unc is used to solve problems with very large number of variables or with sparse
hessian matrices. Such problem, for instance, might arise from discretized opti-
mal control problems, some inverse-problems in signal processing, etc.
Mestrado Matemática Financeira 01/17/2009 Optimização, Aula 5
6
However, to use the large-scale algorithm under fminunc.m, the gradient of the
objective function must be provided by the user and the parameter ’GradObj’
must be set ’on’ using:
>>Options=optimset(OldOptions,’LargeScale’,’on’,’GradObj’,’on’);
Hence, for the large-scale option, you can define your objective and gradient
functions in a single function m-file :
function [fun,grad]=myFun(x)
fun = ...;
if nargout > 1
Mestrado Matemática Financeira 01/17/2009 Optimização, Aula 5
7
grad = ...;
end
However, if you fail to provide the gradient of the objective function, then fmi-
nunc uses the medium-scale algorithm to solve the problem.
Experiment: Write programs to solve the following problem with fminunc.m us-
ing both the medium and large-scale options and compare the results: minimize
f(x1, x2, x3) = x21 + 3x22 + 5x
23
Solution
Define the problem in an m-file, including the derivative in case if you want to
use the LargeScale option.
Mestrado Matemática Financeira 01/17/2009 Optimização, Aula 5
8
function [f,g]=fun1(x)
%Objective function for example (a)
%Defines an unconstrained optimization problem to be solved with fminunc
f=x(1)ˆ2+3*x(2)ˆ2+5*x(3)ˆ2;
if nargout > 1
g(1)=2*x(1);
g(2)=6*x(2);
Mestrado Matemática Financeira 01/17/2009 Optimização, Aula 5
9
g(3)=10*x(3);
end
Next you can write a Matlab m-file to call fminunc to solve the problem.
function [xopt,fopt,exitflag]=unConstEx1
options=optimset(’fminunc’);
options.LargeScale=’off’; options.HessUpdate=’bfgs’;
% assuming the function is defined in the
Mestrado Matemática Financeira 01/17/2009 Optimização, Aula 5
10
% in the m file fun1.m we call fminunc
% with a starting point x0
x0=[1,1,1];
[xopt,fopt,exitflag]=fminunc(@fun1,x0,options);
If you decide to use the Large-Scale algorithm on the problem, then you need to
simply change the option parameter LargeScale to on.
function [xopt,fopt,exitflag]=unConstEx1
options=optimset(’fminunc’);
Mestrado Matemática Financeira 01/17/2009 Optimização, Aula 5
11
options.LargeScale=’on’;
options.Gradobj=’on’;
%assuming the function is defined as in fun1.m
%we call fminunc with a starting point x0
x0=[1,1,1];
[xopt,fopt,exitflag]=fminunc(@fun1,x0,options);
To compare the medium- and large-Scale algorithms on the problem given above
you can use the m-function TestFminunc
Mestrado Matemática Financeira 01/17/2009 Optimização, Aula 5
12
The Matlab fminsearch.m function uses the Nelder-Mead direct search (also
called simplex search) algorithm. This method requires only function evaluations,
but not derivatives. As such the method is useful when
• the derivative of the objective function is expensive to compute;
• exact first derivatives of f are difficult to compute or f has discontinuities;
• the values of f are ’noisy’.
x = fminsearch(FUN,X0)
starts at X0 and attempts to find a local minimizer X of the function FUN. FUN
is a function handle. FUN accepts input X and returns a scalar function value
F evaluated at X. X0 can be a scalar, vector or matrix.
Mestrado Matemática Financeira 01/17/2009 Optimização, Aula 5
13
function f = myfun(x,c)
f = x(1)ˆ2 + c*x(2)ˆ2;
>> c = 1.5; % define parameter first
>> x = fminsearch(@(x) myfun(x,c),[0.3;1])
x = lsqnonlin (FUN,X0)
starts at the matrix X0 and finds a minimum X to the sum of squares of the
functions in FUN. FUN accepts input X and returns a vector (or matrix) of
function values F evaluated at X. NOTE: FUN should return FUN(X) and not the
Mestrado Matemática Financeira 01/17/2009 Optimização, Aula 5
14
sum-of-squares sum(FUN(X).ˆ2)). (FUN(X) is summed and squared implicitly
in the algorithm.)
The default algorithm when OPTIONS.LargeScale = ’off’ is the Levenberg-
Marquardt method with a mixed quadratic and cubic line search procedure. A
Gauss-Newton method is selected by setting OPTIONS.LargeScale=’off’ and
OPTIONS.LevenbergMarquardt=’off’.
function F = myfun(x,c)
F = [ 2*x(1) - exp(c*x(1))
-x(1) - exp(c*x(2))
Mestrado Matemática Financeira 01/17/2009 Optimização, Aula 5
15
x(1) - x(2) ];
>> c = -1; % define parameter first
>> x = lsqnonlin(@(x) myfun(x,c),[1;1])
Try bandem.m and datdemo.m
Outros m-files
Algoritmo de Powell: powell.m
[xo,Ot,nS]=powell(S,x0,ip,method,Lb,Ub,problem,tol,mxit)
Mestrado Matemática Financeira 01/17/2009 Optimização, Aula 5
16
- S: objective function
- x0: initial point
- ip: (0): no plot (default), (>0) plot figure ip with pause, (<0) plot figure ip
- method: (0) Coggins (default), (1): Golden Section
- Lb, Ub: lower and upper bound vectors to plot (default = x0*(1+/-2))
- problem: (-1): minimum (default), (1): maximum
- tol: tolerance (default = 1e-4)
Mestrado Matemática Financeira 01/17/2009 Optimização, Aula 5
17
- mxit: maximum number of stages (default = 50*(1+4*˜(ip>0)))
- xo: optimal point
- Ot: optimal value of S
- nS: number of objective function evaluations
Para ver um exemplo correr o m-file: powell run.m
Algoritmo de Newton: newtons.m (para sistemas nao-lineares)
- [x,fx,xx] = newtons(f,x0,TolX,MaxIter,varargin)
Mestrado Matemática Financeira 01/17/2009 Optimização, Aula 5
18
Para exemplificar, correr o m-file: newtonsEx.m
M-file newton.m para minimizar funcoes nao-lineares
- [xo,Ot,nS]=newton(S,x0,ip,G,H,Lb,Ub,problem,tol,mxit)
Exercıcios: Determine, caso existem, os mınimos das seguintes funcoes:
1. f (x) = x1x22x33x44 exp(−x1 − x2 − x3 − x4)
2. f (x) = 100 (x2 − sin (x1))2 + 0.25x21
Mestrado Matemática Financeira 01/17/2009 Optimização, Aula 5
19
3. f (x) = (x1 + 10x2)2 + 5 (x3 − x4)
4 + 10 (x1 − x4)4
4. f (x) = ex1+x2+1 − e−x1−x2−1 + e−x1−1
Mestrado Matemática Financeira 01/17/2009 Optimização, Aula 5
20