Fin500J: Mathematical Foundations in

Finance

Topic 5: Numerical Methods for Optimization

Philip H. Dybvig
Reference: Optimization Toolbox User’s Guide in Matlab, 2008 by the
MathWorks, Inc.
Slides designed by Yajun Wang

Fin500J Topic 5 Fall 2010 Olin Business School 1

Recall, with optimization, we are seeking f
'(x) = 0
f '(x) = 0
f "(x)< 0
f(x)

f '(x) = 0
f "(x)>0 x

Fin500J Topic 5 Fall 2010 Olin Business School 2

 2
Find the maximum of x
f ( x) 2 sin x 
10
To solve the root problem for
' x
f ( x) 2 cos x  0
5
and the second condition is satisfied at the root
'' 1
f ( x*)  2 sin x *   0
5

Fin500J Topic 5 Fall 2010 Olin Business School 3

 2
 We can solve f '(x) =0
by Bisection using initial
1
interval [1,2], Newton’s
0 with initial point 1.2 or
Secant method with
y=2sinx-x 2/10

-1
initial points 1.2 and 2
-2
presented in Topic 3.

-3
 We can also solve it in
-4 Matlab.
-5 >> f=@(x) 2*cos(x)-
-6 -4 -2 0 2 4 6
x 1/5*x;
>> fzero(f,[1,2])
ans =1.4276

Fin500J Topic 5 Fall 2010 Olin Business School 4

Objectives : Using Optimization Toolbox in
Matlab to
Solve unconstrained optimization with multiple
variables
Solve linear programming problem
Solve quadratic programming problem (for example:
optimal portfolio)
Solve nonlinear optimization with constraints
Mostly, we will focus on minimization in this topic,
max f(x) is equivalent to min –f(x)

Fin500J Topic 5 Fall 2010 Olin Business School 5

Linear Programming/Quadratic
Programming/Nonlinear Programming

If f(x) and the constraints are linear, we have

linear programming

If f(x) is quadratic, and the constraints are linear,

we have quadratic programming

If f(x) in not linear or quadratic, and/or the

constraints are nonlinear, we have nonlinear
programming

Fin500J Topic 5 Fall 2010 Olin Business School 6

 • Unconstrained Minimization Problem:
min f(x1, x2,…xn)

• Optimality Condition: x* is a local minimum if

f ( x * ) 0 and 2 f(x* ) is positive definite.
x x  1 x  x 1 -x  1
• Example:min f(x) e 1 2  e 1 2  e 1 ,
 e x1  x2  1  e x1  x2  1  e - x1  1 
f ( x)  x  x  1 ,
 e 1 2  e x1  x2  1 
 
•What values of x make
f ( x) 0 ?

Fin500J Topic 5 Fall 2010 Olin Business School 7

 Step 1: Write an M-file objfun.m and save under
the work path of matlab
function f=objfun(x)
f=exp(x(1)+x(2)-1)+exp(x(1)-x(2)-1)+exp(-x(1)-1);

Step 2: >>optimtool in the commend window to

open the optimization toolbox

Fin500J Topic 5 Fall 2010 Olin Business School 8

  We use the
function
fminunc to
solve
unconstrained
optimization
problem
“objfun”

Fin500J Topic 5 Fall 2010 Olin Business School 9

 '' f ' ( x k  x)  f ' ( x k )  f ' ( x k )
k
f (x )  
x x
f ' (xk )
 x  '' k . Multiple variable case :
f (x )
x -2 f ( x k )  1 f ( x k ).

Fin500J Topic 5 Fall 2010 Olin Business School 10

  Newton’s method may fail if Hessian is not positive
definite

Fin500J Topic 5 Fall 2010 Olin Business School 11

  The function “fminunc” uses BFGS (Broyden, Fletcher,
Goldfarb and Shanno) Hessian Update in the Quasi-Newton
algorithm. The formula given by BFGS is

Fin500J Topic 5 Fall 2010 Olin Business School 12

 Both the objective function and the constraints are
linear
 Example: maximizing profit or minimizing cost
 Objective function
Max or Min Z = c1x1 +c2x2 +…..cnxn

where cj = payoff of each unit of the jth activity

xj = magnitude of the jth activity
 The constraints can be represented by
ai1x1 +ai2x2+…..ainxn  bi
where aij = amount of the ith resource that is
consumed for each
unit of the jth activity, bi = amount of the ith
resource available
 Finally, we add the constraint that all activities have a
Fin500J Topic 5
positive value,Fallx2010
i  0
Olin Business School 13
 Product
Resource Regular Premium Resource Availability
Raw Gas 7 11 77 x1 =
3
(m /tonne)
amount of
Production Time 10 8 120 regular and
(hr/tonne)

Storage 9 6
x2 =
(tonne) amount of
Profit (/tonne) 150 175 premium

Total Profit = 150 x1 + 175 x2

Maximize Z = 150 x1 + 175 x2 Objective
7x1 + 11x2  77 function
(material constraint)
10x1 + 8x2  120 (time constraint)
x1  9 (storage constraint)
x2  6 (storage constraint)
x1,x2  0 (positivity constraint)
Fin500J Topic 5 Fall 2010 Olin Business School 14
(1) 7x1 + 11x2  77
→x2  -7/11 x1 +7

(2) 10x1 + 8x2  120

→ x2  -5/4x1 + 15
(3) x1  9

(4) x2  6

(5) x1,x2  0

Fin500J Topic 5 Fall 2010 Olin Business School 15

 Now we need to add the objective function to the
plot. Start with
Z = 0 (0=150x1 + 175x2)
and
Z = 500 (500=150x1 + 175x2)
Z=1200
Z=1550
Still in feasible region
x1*= 9
x2*  1.5

Fin500J Topic 5 Fall 2010 Olin Business School 16

 Example:

 Step 1: >>optimtool in the

commend window to open the
optimization
toolbox
 Step 2: Define matrices A, Aeq and
the vectors f, b, lb, ub

Fin500J Topic 5 Fall 2010 Olin Business School 17

  File->export to
workspace
 can export the
results including
lambda,etc.

Fin500J Topic 5 Fall 2010 Olin Business School 18

  Step 1: >>optimtool in the commend window to open the
optimization
toolbox
 Step 2: Define matrices H,A and the vectors f, b

Fin500J Topic 5 Fall 2010 Olin Business School 19

Fin500J Topic 5 Fall 2010 Olin Business School 20
 H=[0.017087987 0.003298885
0.001224849; 0.003298885
0.005900944 0.004488271;
0.001224849 0.004488271
0.063000818]
f=[0; 0; 0]
A=[1 1 1; -0.026 -0.008 -0.074;
-1 0 0; 0 -1 0; 0 0 -1]
b=[1000; -50; 0; 0; 0]

The function ‘quadprog ’ uses

an active set strategy. The
first phase involves the
calculation of a feasible point.
The second phase involves
the generation of an iterative
sequece of feasible points
that converge to the solution.

Fin500J Topic 5 Fall 2010 Olin Business School 21

 Formulation

Fin500J Topic 5 Fall 2010 Olin Business School 22

 Find x that solves

 Step 1: Write an M-file objfunc.m for the objective function.

function f=objfunc(x)
f=exp(x(1))*(4*x(1)^2+2*x(2)^2+4*x(1)*x(2)+2*x(2)+1);

 Step 2: Write an M-file confun.m for the constraints.

function [c, ceq]=confun(x)
%Nonlinear inequality constraints
c=[1.5+x(1)*x(2)-x(1)-x(2); -x(1)*x(2)-10];
%Nonlinear equality constraints
ceq=[];
 Step 3: >>optimtool to open the optimization toolbox

Fin500J Topic 5 Fall 2010 Olin Business School 23

Fin500J Topic 5 Fall 2010 Olin Business School 24
  The basic idea is analogous to
min f(x), Newton’s method for unconstrained
x
optimization.
subject to
 In unconstrained optimization, only
g i(x) 0 i 1,...me . the objective function must be
g i(x) 0 i me  1,...m. approximated, in the NLP, both the
objective and the constraint must be
modeled.
 An sequential quadratic
programming method uses a
quadratic for the objective and a
linear model of the constraint ( i.e., a
quadratic program at each iteration)

Fin500J Topic 5 Fall 2010 Olin Business School 25