Tutorial: Using MATLAB@ for Mathematical
Programming
APS502 - Financial Engineering I
Dexter Wu
Mechanical and Industrial Engineering
University of Toronto
November 10, 2015
APS502 (MIE, U of T) using MATLAB @ November 10, 2015 1 / 22
Outline
Matrix Construction.
Optimization toolbox in MATLAB@.
LP and QP solver.
Numerical examples in MATLAB@.
Q&A and Exercises
APS502 (MIE, U of T) using MATLAB @ November 10, 2015 2 / 22
Basic operators
De…nition
A Matrix is a table of numbers, similar to a spreadsheet.
2 3
1 4 7
4 0
A= 2 5 8 5 , B = [2, 1] , C = ,
3
3 6 9
2 3
3 4
3 5 7 4 3 1 3
D=4 5 3 5 , DT = ,E = ,E 1 =
4 3 2 1 1 1 4
7 2
Matlab code:
1 >> A = [1 4 7; 2 5 8; 3 6 9;]
2 >> B = [2 1]; C = [0; 3;];
3 >> D = [3 4; 5 3; 7 2;]; D_trans = D’;
4 >> E = [4 3; 1 1;]; E_inv = inv(E);
APS502 (MIE, U of T) using MATLAB @ November 10, 2015 3 / 22
Basic Operators
Operators Examples
1 2 5 7 1+5 2+7
+, - + =
3 4 6 8 3+6 4+8
1 2 5 7 1 5+2 6 1 7+2 8
=
*, ^ 3 4 6 8 3 5+4 6 3 7+4 8
(matrix multiplication)
1 2 0 5 7 2 1 5 2 7 0 2
. =
.*, .^ 3 4 1 6 8 5 3 6 4 8 1 5
(array multiplication)
A/B = A*inv(B)
n, /
AnB = inv(A)*B (B = I )
A(1:3, 4:6) sub-matrix of A that
:, ’
row from 1 to 3 and column from 4 to 6
APS502 (MIE, U of T) using MATLAB @ November 10, 2015 4 / 22
Building Matrix
Manual Entry
By some standard functions
1 zeros(m,n) creates an (m,n) matrix of zeros;
2 ones(m,n) creates an (m,n) matrix of ones;
3 eye(n) creates the (n,n) identity matrix;
By loops
1 cat(dim, A, B)
2 blkdiag() or diag(v)
3 repmat(), reshape() can simplify the loop
APS502 (MIE, U of T) using MATLAB @ November 10, 2015 5 / 22
Sparse Matrix
A sparse matrix is a matrix mostly populated by zeros
There are many engineering and optimization problems that can
be stated using sparse coe¢ cient matrices (ex: graph/network
optimization)
MATLAB has the ability to create, store and manipulate sparse
matrices e¢ ciently
APS502 (MIE, U of T) using MATLAB @ November 10, 2015 6 / 22
Create sparse matrix
A = sparse(m, n) creates an (m,n) sparse matrix of zeros
B = sparse(A) converts matrix A to a sparse matrix B
APS502 (MIE, U of T) using MATLAB @ November 10, 2015 7 / 22
Optimization toolbox
Optimization Toolbox provides widely used algorithms for
standard and large-scale optimization.
The toolbox includes solvers for:
1 Linear Programming (LP)
2 Quadratic Programming (QP)
3 Binary Integer Programming (BIP)
4 Non-Linear Programming (NLP)
APS502 (MIE, U of T) using MATLAB @ November 10, 2015 8 / 22
Solve LPs using linprog (1)
Linprog solves a problem of this form:
min f T x
x
s.t. A x b
Aeq x = beq
lb x ub
where f , x, lb, ub = n 1 vector;
A = m1 n matrix, Aeq = m2 n matrix;
b = m1 1 vector, beq = m2 1 vector.
APS502 (MIE, U of T) using MATLAB @ November 10, 2015 9 / 22
Solve LPs using linprog (2)
Syntax:
[x, fval, exit‡ag, output, lambda] = linprog(f, A, b, Aeq, beq, lb, ub,
x0, options)
Linprog takes 6 input variables:
f: Objective coe¢ cient
A, b: Inequality constraints ( )
Aeq, beq: Equality constraints
lb, ub: Variable bounds
x0: Initial guess
options: set parameters (e.g. Algorithm) for the solver
Linprog returns 5 output variables:
x: Optimal Solution
fval: Objective Function Value
exit‡ag: optimal, infeasible, unbounded, etc.
output: information about the algorithm
lambda: dual variables
APS502 (MIE, U of T) using MATLAB @ November 10, 2015 10 / 22
LP example (1)
Solve below LP:
min 2x1 x2 + x3
x
s.t. 2x1 3x2 x3 9
2x1 x2 4
x1 + 3x3 = 6
x1 , x3 0, x2 0
Build the input arguments for linprog:
c = [2, -1, 1]’
A = [2, -3, -1; 2, -1, 0] b = [9; -4]
Aeq = [1, 0, 3] beq = [6]
ub = [inf; 0; inf;]
lb = [0; -inf; 0;]
Ignore for now: x0, options
Call linprog from Matlab
[x, fval] = linprog(c, A, b, Aeq, beq, lb, ub)
APS502 (MIE, U of T) using MATLAB @ November 10, 2015 11 / 22
LP example (2)
Solve below LP:
max 2x1 + x2 + 3x3 + x4
x
s.t. x1 + x2 + x3 + x4 5
2x1 x2 + 3x3 = 4
x1 x3 + x4 1
x1 , x3 0, x2 , x4 unrestricted
Build the input arguments for linprog:
c = -[2, 1, 3, 1]’
A = [1 1 1 1; -1 0 1 -1;] b = [5; -1]
Aeq = [2, -1, 3, 0] beq = [-4]
lb = [0; -inf; 0; -inf;] ub = [inf; inf; inf; inf;]
Ignore for now: x0, options
Call linprog from Matlab
[x, fval] = linprog(c, A, b, Aeq, beq, lb, ub)
APS502 (MIE, U of T) using MATLAB @ November 10, 2015 12 / 22
LP example (3) - Bond Portfolio Optimization
Suppose that a bank has the following liability schedule:
Year 1 Year 2 Year 3
$12,000 $18,000 $20,000
The bank wishes to use three bonds to form a portfolio (a collection
of bonds) today to hold until all bonds have matured and that will
generate the required cash to meet the liabilities.
Bond 1 2 3
Price 102 99 98
Coupon 5 3.5 3.5
Maturity year 1 2 3
APS502 (MIE, U of T) using MATLAB @ November 10, 2015 13 / 22
LP example (3) - Bond Portfolio Optimization
Let xi = amount of bond i purchased, the problem can be formulated
as below LP:
min102x1 + 99x2 + 98x3
x
s.t. 105x1 + 3.5x2 + 3.5x3 12000
103.5x2 + 3.5x3 18000
103.5x3 20000
x1 , x2 , x3 0
Build the input arguments for linprog:
c = [102 99 98]’
A = -[105 3.5 3.5; 0 103.5 3.5; 0 0 103.5] b = -[12000; 18000; 20000]
Aeq = [] beq = []
lb = [0; 0; 0;] ub = [inf; inf; inf;]
Ignore for now: x0, options
Call linprog from Matlab
[x, fval] = linprog(c, A, b, Aeq, beq, lb, ub)
APS502 (MIE, U of T) using MATLAB @ November 10, 2015 14 / 22
Solve QPs using quadprog (1)
Quadprog solves a problem of this form:
1 T
min 2 x Hx +fTx
x
s.t. A x b
Aeq x = beq
lb x ub
where f , x, lb, ub = n 1 vector;
A = m1 n matrix, Aeq = m2 n matrix;
b = m1 1 vector, beq = m2 1 vector;
H = n n symmetric matrix, usually require PSD.
APS502 (MIE, U of T) using MATLAB @ November 10, 2015 15 / 22
Solve QPs using quadprog (2)
Syntax:
[x, fval, exit‡ag, output, lambda] = quadprog(H, f, A, b, Aeq, beq, lb,
ub, x0, options)
Linprog takes 7 input variables:
H: Symmetric matrix represents the quadratic term in objective
f: Coe¢ cient vector for the linear term in objective
A, b: Inequality constraints ( )
Aeq, beq: Equality constraints
lb, ub: Variable bounds
x0: Initial guess
options: set parameters (e.g. Algorithm) for the solver
Linprog returns 5 output variables:
x: Optimal Solution
fval: Objective Function Value
exit‡ag: optimal, infeasible, unbounded, etc.
output: information about the algorithm
lambda: dual variables
APS502 (MIE, U of T) using MATLAB @ November 10, 2015 16 / 22
QP example (1)
Solve below QP:
min .5x12 x1 x2 + x22 2x1 6x2
x
s.t. x1 + x2 2
x1 + 2x2 2
2x1 + x2 3
x1 , x2 0
Build the input arguments for quadprog:
H = [1 -1; -1 2]
c = [-2 -6]’
A = [1 1; -1 2; 2 1;] b = [2; 2; 3;]
Aeq = [] beq = []
lb = [0; 0;] ub = [inf; inf;]
Ignore for now: x0, options
Call quadprog from Matlab
[x, fval] = quadprog(H, c, A, b, Aeq, beq, lb, ub)
APS502 (MIE, U of T) using MATLAB @ November 10, 2015 17 / 22
QP example (2) - MVO
The Mean-Variance Optimization (MVO) model is given as follows:
min ∑ni=1 ∑nj=1 σij xi xj
x
s.t. ∑ni=1 µi xi R
n
∑ i =1 i
x = 1
(x 0)
In matrix form the MVO model is
min 12 x T Qx
x
s.t.µT x R
eT x = 1
(x 0)
MVO can be solved by quadprog.
APS502 (MIE, U of T) using MATLAB @ November 10, 2015 18 / 22
QP example (2) - MVO
Consider 3 securities with expected return given in Table 1 and with
covariance given in Table 2:
expected security 1 security 2 security 3
return (i = 1) (i = 2) (i = 3)
µi 9.73% 6.57% 5.37%
covariance σij i =1 i =2 i =3
i =1 0.02553 -0.00327 0.00019
i =2 -0.00327 0.013400 -0.00027
i =3 0.00019 -0.00027 0.00125
If the goal return of portfolio is 5.5%, solve MVO with and without
short selling.
APS502 (MIE, U of T) using MATLAB @ November 10, 2015 19 / 22
QP example (2) - MVO
MVO can be formulated as follows:
min(0.02553)x12 + (0.01340)x22 + (0.00125)x32
x
+2( 0.00327)x1 x2 + 2(0.00019)x1 x3 + 2( 0.00027)x2 x3
s.t.(0.0972)x1 + (0.0657)x2 + (0.0537)x3 0.055
x1 + x2 + x3 = 1
(x1 , x2 , x3 0) short selling is prohibited
Build the input arguments for quadprog:
Q = [0.02553, -0.00327, 0.00019; -0.00327, 0.013400, -0.00027;
0.00019, -0.00027, 0.00125;]
c = [0 0 0]’
A = -[0.0972, 0.0657, 0.0537] b = -[0.055]
Aeq = [1 1 1] beq = [1]
ub = [inf; inf; inf;]
lb = [-inf; -inf; -inf;] % with short selling
lb = [0; 0; 0;] % without short selling
APS502 (MIE, U of T) using MATLAB @ November 10, 2015 20 / 22
QP example (2) - MVO
Vary R and we can get e¢ cient frontiers of MVO:
APS502 (MIE, U of T) using MATLAB @ November 10, 2015 21 / 22
Numerical examples
Numerical examples in MATLAB
APS502 (MIE, U of T) using MATLAB @ November 10, 2015 22 / 22
