Numerical Methods in Finance
and Economics
STATISTICS IN PRACTICE
Advisory Editor
Peter Bloomfield
North
Carolina
State
University,
USA
Founding Editor
Vic Barnett
Nottingham Trent University,
UK
Statistics in Practice
is an important international series of texts which provide detailed cov-
erage of statistical concepts, methods and worked case studies in specific fields of investiga-
tion and study.
With sound motivation and many worked practical examples, the books show in down-to-
earth terms how to select and use an appropriate range
of
statistical techniques in a particular
practical field within each title’s special topic area.
The books provide statistical support for professionals and research workers across a
range of employment fields and research environments. Subject areas covered include medi-
cine and pharmaceutics; industry, finance and commerce; public services; the earth and envi-
ronmental sciences, and
so
on.
The books also provide support to students studying statistical courses applied to the

&
Sons, Inc. All rights reserved.
Published by John Wiley
&
Sons, Inc., Hoboken, New Jersey.
Published simultaneously in Canada.
No
part of this publication may be reproduced, stored in a retrieval system,
or
transmitted in any form
or
by any means, electronic, mechanical, photocopying, recording, scanning,
or
otherwise, except as
permitted under Section
107
or
108
of
the
1976
United States Copyright Act, without either the prior
written permission of the Publisher,
or
authorization through payment of the appropriate per-copy fee to
the Copyright Clearance Center, Inc.,
222
Rosewood Drive, Danvers, MA
01923, (978) 750-8400,
fax

You
should consult with a professional where appropriate. Neither the
publisher nor author shall be liable for any loss of profit
or
any other commercial damages, including
but not limited to special, incidental, consequential,
or
other damages.
For
general information on
our
other products and services
or
for technical support, please contact
our
Customer Care Department within the United States at
(800) 762-2974,
outside the United States at
(317) 572-3993
or
fax
(317) 572-4002.
Wiley also publishes its books in a variety of electronic formats. Some content that appears in print may
not be available in electronic format.
For
information about Wiley products, visit
our
web site at
www.wiley.com.
Library

Printed in the United States of America.
10 9 8 7 6 5 4 3 2 1
This book is dedicated
to
Commander Straker, Lieutenant
Ellis,
and all
SHAD0
operatives. Thirty-five years ago they introduced me to the art
of
using
both computers
and
gut feelings to make decisions.
This Page Intentionally Left Blank
Preface to the Second Edition
From the Preface to the First Edition
Part
I
Background
Contents
1
Motivation
1.1
Need for numerical methods
1.2 Need for numerical computing environments:
why MATLAB?
1.3
Need for theory
For further

2.3.2
2.3.3
2.3.4
2.3.5
Critique
2.4.1
Utility theory
2.4.2
Mean-variance portfolio Optimization
2.4.3
MATLAB functions to deal with mean-
variance portfolio optimization
2.4.4
Critical remarks
2.4.5
Alternative risk measures: Value at Risk
Modeling the dynamics
of
asset prices
2.5.1
2.5.2
Standard Wiener process
2.5.3
Stochastic integrals and stochastic
2.5.4
Ito’s lemma
2.5.5
Generalizations
2.6
Derivatives pricing

of
fixed-income securities
Interest rate sensitivity and bond portfolio
immunization
MATLAB functions to deal with fixed-
income securities
2.4
Stock portfolio optimization
and quantile- based measures
From discrete to continuous time
2.5
diflerential equations
Simple binomial model for option pricing
2.7
33
37
42
42
49
57
60
64
65
66
73
74
81
83
88
88

of
Numerical Analysis
3.1 Nature
of
numerical computation
3.1.1 Number representation, rounding, and
3.1.2 Error propagation, conditioning, and
3.1.3
Solving systems
of
linear equations 145
3.2.1 Vector and matrix norms 146
3.2.2
3.2.3
3.2.4 Tridiagonal matrices
3.2.5
truncation
instability 141
Order
of
convergence and computational
complexity 143
3.2
Condition number for
a
matrix 149
Direct methods for solving systems
of
linear equations
Iterative methods for solving

a
functional equation
by
a
collocation
method
124
126
127
130
131
137
138
138
154
159
160
173
177
183
1
79
188
191
192
195
198
204
x
CONTENTS

4.3.3
Acceptance-rejection method
4.3.4
Setting the number
of
replications
4.5.1
Antithetic sampling
4.5.2
Common random numbers
4.5.3
Control variates
4.5.4
Variance reduction
by
conditioning
4.5.5
Stratified sampling
4.5.6
Importance sampling
4.6
Quasi-Monte Carlo simulation
4.6.1
Generating Halton low-discrepancy
sequences
4.6.2
Generating Sobol low-discrepancy
sequences
For further reading
References

233
235
24
0
244
244
251
252
255
260
261
267
269
281
286
287
289
290
293
CONTENTS
xi
5.2.2
Explicit and
implicit
methods for
the
heat
equation
5.3.1
5.3.2

309
31
3
320
314
324
324
6 Convex Optimization
327
6.1 Classification
of
optimization problems 328
6.1.1 Finite- us. infinite-dimensional problems 328
6.1.2 Unconstrained us. constrained problems
333
6.1.3 Convex us. non-convex problems
333
6.1.4 Linear us. non-linear problems 335
6.1.5 Continuous us. discrete problems
337
6.1.6 Deterministic us. stochastic problems
337
6.2.1 Steepest descent method 339
6.2.2 The subgradient method
34
0
6.2.3 Newton and
the
trust region methods
34

CONTENTS
6.4.3 Duality
in
linear programming
6.4.4 Interior point methods
6.5.1 Linear programming
in
MATLAB
6.5.2
A
trivial LP model for bond portfolio
management
6.5.3 Using quadratic programming to trace
evgicient
portfolio frontier
6.5.4 Non-linear programming
in
MATLAB
6.5 Constrained optimization
in
MATLAB
6.6 Integrating simulation and optimization
S6.1 Elements
of
convex analysis
S6.1.1 Convexity
in
optimization
S6.1.2 Convex polyhedra
and

378
380
383
385
387
389
389
393
396
397
4
01
4
02
4
03
410
411
414
7.3
Pricing bidimensional options
by
binomial lattices 41
7
7.4
Pricing
by
trinomial lattices 422
7.5
Summary 425

Estimating Greeks
by
Monte Carlo sampling
For further reading
References
8.4
8.5
9
Option Pricing
by
Finite Diflerence Methods
9.1
9.2
Applying
finite diflerence methods to the Black-
Scholes equation
Pricing a vanilla European option
by
an explicit
method
9.2.1
Financial interpretation
of
the instability
of
the explicit method 481
Pricing a vanilla European option
by
a fully
implicit method

simulation
10.4.1
A
MATLAB implementation
of
the least
squares approach
44
6
44
6
44
7
450
4
54
4
55
458
468
4
72
4
73
4
75
4
75
4
78

programming
11.3.1 Sampling for scenario tree generation
11.3.2 Arbitrage free scenario generation
1
1.4
L-shaped method for two-stage linear stochastic
programming
11.5
A
comparison with dynamic programming
For
further
reading
References
transaction costs
12 Non- Convex Optimization
12.1 Mixed-integer programming models
12.1.1 Modeling with logical variables
12.1.2 Mixed-integer portfolio optimization
12.2 Fixed-mix model based on global optimization
12.3 Branch and bound methods for non-convex
optimization
12.3.1 LP-based branch and bound for MILP
models
12.4 Heuristic methods for non-convex optimization
For further reading
References
models
51 9
521

Appendices
Appendix A Introduction to MATLAB Programming 603
A.l MATLAB environment 603
A.3 MATLAB programming 61 6
Appendix B Refresher
on
Probability Theory and Statistics 623
A.2 MATLAB graphics 614
B.l Sample
space,
events, and probability
B.2 Random variables, expectation, and variance
B.2.1 Common continuous random variables
B.3
Jointly
distributed random variables
B.4 Independence, covariance,
and
conditional
expectation
B.5 Parameter estimation
B. 6 Linear regression
For further reading
References
Appendix C Introduction
to
AMPL
C.
1
Running optimization models in AMPL

9
652
655
655
656
657
This Page Intentionally Left Blank
Preface
to
the
Second
J
Edition
After the publication of the first edition of the book, about five years ago,
I have received a fair number of messages from readers, both students and
practitioners, around the world.
The recurring keyword, and the most im-
portant thing to me, was
useful.
The book had, and has, no ambition of
being a very advanced research book. The basic motivation behind this sec-
ond edition is the same behind the first one: providing the newcomer with
an easy, but solid, entry point to computational finance, without too much
sophisticated mathematics and avoiding the burden of difficult
C++
code,
also covering relatively non-standard optimization topics such
as
stochastic
and integer programming. See also the excerpt from the preface to the first

to solve a wide array of problems in Economics. From the point of view of
my students in such
a
course, the present book has many deficiencies:
For
instance, it does not cover ordinary differential equations and it does not
deal with computing equilibria
or
rational expectations models; furthermore,
practically all of the examples deal with option pricing
or
portfolio manage-
ment. Nevertheless, given my experience, I believe that they can benefit from
a more detailed and elementary treatment of the basics, supported by simple
examples.
Moreover, I believe that students in Economics should also get
lK.L.
Judd,
Numerical Methods
in
Economics,
MIT
Press,
1998.
2M.
J. Miranda and
P.L.
Fackler,
Applied Computational Economics and Finance,
MIT

edition, advanced optimization applications are left to the last chapters,
so
they do not get into the way of most financial engineering students. The book
consists
of
twelve chapters and three appendices.
0
Chapter
1
provides the reader with motivations for the use of numerical
methods, and for the use of MATLAB
as
well.
0
Chapter
2
is an overview of financial theory.
It
is aimed at students in
Engineering, Mathematics,
or
Operations Research, who may be inter-
ested in the book, but have little
or
no financial background.
0
Chapter
3
is devoted to the basics of classical numerical methods. In
some sense, this is complementary to chapter

spective strengths and weaknesses, both for option pricing and scenario
generation in stochastic optimization. Regarding Monte Carlo as a tool
for integration rather than simulation is also helpful to properly frame
the application of low-discrepancy sequences (which is also known un-
der the more appealing name of quasi-Monte Carlo simulation). There
is some new material on Gaussian quadrature, an extensive treatment
of variance reduction methods, and some application to vanilla options
to illustrate simple but concrete applications immediately, leaving more
complex cases to chapter
8.
0
Chapter
5
deals with basic finite difference schemes
for
partial differ-
ential equations. The main theme is solving the heat equation, which
PREFACE
xix
is the prototype example of the class of parabolic equations, to which
Black-Scholes equation belongs. In this simplified framework we may
understand the difference between explicit and implicit methods,
as
well
as the issues related to convergence and numerical stability. With
re-
spect to the first edition,
I
have added an outline of the Alternating
Direction Implicit method to solve the two-dimensional heat equation,

8
is naturally linked to chapter
4
and deals with more advanced
applications of Monte Carlo and low-discrepancy sequences to exotic
options, such
as
barrier and Asian options. We also deal briefly with the
estimation of option sensitivities (the Greeks) by Monte Carlo methods.
Emphasis is on European-style options; pricing American options by
Monte Carlo methods is
a
more advanced topic which must be analyzed
within an appropriate framework, which is done in chapter
10.
a
Chapter
9
applies the background of chapter
5
to option pricing by finite
difference methods.
a
Chapter 10 deals with numerical dynamic programming. The main rea-
son for including this chapter is pricing American options by Monte
Carlo simulation, which was not covered in the first edition but
is
gain-
ing more and more importance.
I

a
practical point of view, stochastic programming has an interesting po-
tential both for dynamic portfolio management and for option hedging
in incomplete markets.
Chapter
12
also deals with the relatively exotic topic of non-convex opti-
mization. The main aim here is introducing mixed-integer programming,
which can be used for portfolio management when practically relevant
constraints call for the introduction of logical decision variables. We also
deal, very shortly, with global optimization, i.e., continuous non-convex
optimization, which is important when we leave the comfortable domain
of easy optimization problems (i.e., minimizing convex cost functions or
maximizing concave utility functions). We also outline heuristic prin-
ciples such as local search and genetic algorithms. They are useful to
integrate simulation and optimization and are often used in computa-
tional economics.
Finally, we offer three appendices on MATLAB, probability and statis-
tics, and AMPL. The appendix on MATLAB should be used by the
unfamiliar reader to get herself going, but the best way to learn MAT-
LAB is by trying and using the online help when needed. The appendix
on probability and statistics is just
a
refresher which is offered for the
sake of convenience. The third appendix on AMPL is new, and it reflects
the increased role of algebraic languages to describe complex optimiza-
tion models. AMPL is
a
modeling system offering access to a wide array
of optimization solvers. The choice

to plan
B,
and interest-rate derivatives are just outlined in the second chapter
to point out their peculiarities with respect to stock options. In fact, when
planning this new edition, many reviewers warned that there was little hope to
cover interest-rate derivatives thoroughly in
a
limited amount of pages. They
require a deeper understanding of risk-neutral pricing, interest rate modeling,
and market practice.
I
do believe that the many readers interested in this
PREFACE
xxi
topic can use this book to build
a
solid basis in numerical methods, which is
helpful to tackle the more advanced texts on interest-rate derivatives.
Interest-rate derivatives are not the only significant omission. I could also
mention implied lattices and financial econometrics. But since there are excel-
lent books covering those topics and I see this one just
as
an entry point or a
complement, I felt that it was more important to give
a
concrete understand-
ing of the basics, including some less familiar topics. This is also why I prefer
using MATLAB, rather than
C++
or

the book. Some pointed out typos,
errors, and inaccuracies. Offering apologies for possible omissions,
I
would like
to
thank I-Jung Hsiao, Sandra Hui, Byunggyoo Kim, Scott Lyden, Alexander
Reisz, Ayumu Satoh, and Aldo Tagliani.
Supplements.
As with the first edition,
I
plan to keep
a
web page containing
the (hopefully short) list of errata and the (hopefully long) list of supplements,
as well as the MATLAB code described in the book. My current URL is:
http://staff.polito.it/paolo.brandimarte
For comments, suggestions, and criticisms, my e-mail address is
paolo. brandimarteQpolito. it
One of the many corollaries of Murphy’s law says that my URL is going
to change shortly after publication of the book. An up-to-date link will be
maintained both on Wiley Web page:
ht tp
:
//www
.
wile
y
.
com/mat hemat i cs
and on The Mathworks’ web page:

I
give in a Master’s course on numerical
methods for finance, aimed
at
graduate students in Economics, and in an
optimization course aimed at students in Industrial Engineering. Hence, this
is
not a research monograph; it is
a
textbook for students. On the one hand,
students in Economics usually have little background in numerical methods
and lack the ability to translate algorithmic concepts into a working program;
on the other hand, students in Engineering do not see the potential application
of quantitative methods to finance clearly.
Although there is an increasing literature on high-level mathematics applied
to financial engineering, and
a
few books illustrating how cookbook recipes
may be applied to a wide variety of problems through use of
a
spreadsheet, I
believe there is some need for an intermediate-level book, both interesting to
practitioners and suitable for self-study. I believe that students should:
Acquire
reasonably
strong foundations in order to appreciate the issues
behind the application
of
numerical methods
Be able to translate and check ideas quickly in

as
possible and of immediate use. MATLAB is a
flexible high-level computing environment which allows us to implement non-
trivial algorithms with
a
few lines of code. It has also been chosen because of
its increasing potential for specific financial applications.
It may be argued that the book is more successful
at
raising questions than
at
giving answers. This is a necessary evil, given the space available to cover
such a wide array of topics. But if, after reading this book, students will want
to read others, my job will have been accomplished. This was meant to be a
crossroads, after all.
PS1.
Despite all of my effort, the book is likely to contain some errors and
typos.
I
will maintain a list of errata, which will be updated, based on reader
feedback. Any comment
or
suggestion on the book will also be appreciated.
My
e-mail address is:
paolo.
brandimarteOpolito. it.
PS2.
The list of errata will be posted on
a