Financial Engineering is a multidisciplinary field involving finance and economics, mathematics, statistics, engineering and computational methods. The emphasis of FE & RM Part II will be on the use of simple stochastic models to (i) solve portfolio optimization problems (ii) price derivative securities in various asset classes including equities and credit and (iii) consider some advanced applications of financial engineering including algorithmic trading and the pricing of real options. We will also consider the role that financial engineering played during the financial crisis. We hope that students who complete the course and the prerequisite course (FE & RM Part I) will have a good understanding of the "rocket science" behind financial engineering. But perhaps more importantly, we hope they will also understand the limitations of this theory in practice and why financial models should always be treated with a healthy degree of skepticism.
Review of Linear Optimization
Loading...
Del curso dictado por Columbia University
Financial Engineering and Risk Management Part II
405 calificaciones
De la lección
Background Material
Conoce a los instructores
Martin HaughCo-Director, Center for Financial Engineering
Industrial Engineering & Operations Research
Garud IyengarProfessor
Industrial Engineering and Operations Research Department
>> . In this module, we will be walking through
a review of linear optimization using a hedging example.
We are going to see how there are two kinds of optimization problems, something
called a primal optimization problem, something called a dual optimization
problem, how they are related. And we also introduced the idea of La
Grangian relaxation. Here's the hedging problem that we are
interested in. I've got d assets.
So take d, just to fix ideas, take d to be 3 or 4.
But some number of assets that are there in the market.
The price of these assets at time 0 is r to the d.
It's some price vector, which has d components, where every component tells me
the price of that particular asset. At time t equal to 1, the market outcomes
are uncertain. I don't know what, which state the market
is going to be, it's going to be in one of m possible states.
So here's the situation at time T equal to zero, and I'm in state zero, And I could
go to one of n different possible states. Go from one, two, all the way to, down to
m. What do I mean by a state?
For my purposes, state is simply telling me what are the different prices that can
happen. So I'm going to characterize every state
by the prices of the asset in that particular state And I can do it in 2
different ways. I could either tell you, what is the price
of all the assets in any given state, Or I can tell you the price of a given in all
possible states and we'll flip between these two ideas as we go through.
We'll use the power of matrices to see what it means, sometimes, it's easier to
represent it one way, Sometimes it's easier to represent it the other way.
And understanding it both ways gives us an insight of which one is more beneficial
for the particular application that I'm looking for.
So, to motivate that, I'm going to define something called Sj.
So S sub j, will be a column vector, and it will tell me the price of asset j in
all possible states, So it's s1j, s2j all the way down to smj.
J is fixed, it's asset j and the number of states would ran-, go from 1 to m.
Now how do I represent all the assets in the market?
I'm just going to take these column and stack them.
S1 would refer to the column corresponding to S, asset one S2, asset two and so one
up to S D. If I write them out in gory detail, you
end up getting this matrix. The matrix has M rows, because it's got M
states, its got D columns because its got D assets.
And what going on here, every row here, tells you the price of all the assets in a
particular state. So what I've circled here, are the prices
in state 1, S1d, 12S, 11S, 12, all the way up to S1D.
Genetically, somewhere it's going to be Sm1, Sm2 , all to Smd.
So every row tells me what happens to all the assets in a given state, every column
tells me what happens to a particular asset in all the different states.
Alright, so that's how I'm going to describe my market.
At times 0 I know the price, at time 1, which is the place where the market opens
again, I don't know the price, it's uncertain, it's going to be one of n
possible states, but I know that if the state is given to me, what the prices are.
Now you might think that this is a very simple representation of the market, and
indeed it is. But it turns out, that even in the most
modern methods, of risk management, like value at risk, and conditional value at
risk, people represent what happens to the market By a model which looks very much
like this. Except instead of talking about states,
we'll talk about simulations. I'm going to simulate returns and I'm
going to say, depending on all of these different scenarios, what happens?
But essentially the, the main ideas are going to be captured by this simple toy
model. Alright, I know what happens to the asset.
Now, what I want to do with these assets is to hedge an obligation.
I'm going to walk through what does hedging mean.
So, I have an obligation. What is an obligation?
It's a vector x in rm. Why m?
Because the obligation depends on the state.
In a good state I might had to pay more, in a bad state I might had to pay less.
So depending upon which state occurs, I'm going to pay an obligation xi, if this
state i occurs. And what I want to do, is I want to buy a
portfolio now, I want to buy a certain number of shares of the assets right now,
in order to have enough money to pay my obligation.
So, I'm going to choose a portfolio theta. Theta-1 through theta-d are going to be
the number of shares that I'm going to purchase of each of these assets.
I'm going to allow for the possibility of short selling, so thetas could be
negative, or I'll buy them long, which is, when thetas are positive.
And I want to do, I want to choose this portfolio, so I can hedge the obligation
that, That I'm interested in hedging. So I'll step you through what it means and
what, what hedging will ensue and then we'll go to what is the linear
optimization problem that we end up getting.
Okay! So at time 0, I'm going to put, buy a
position theta at rd. Why d?
Because it's got d different assets. So theta J's the number of shares of
assets J that I purchased, where J goes from 1 through d.
What's the cost of this purchase? The cost of the position theta, is simply
the price of every asset times the number of shares that I produce.
A lot of those assets! So it's pj times theta j, sum from j equal
to 1 through d. It's the inner product of the vector p,
with the vector theta. And we know that inner products are
nothing but p transpose times theta. What happens at time t equal to 1?
So, if a state i occurs, then I'm going to liquidate my position.
And when I liquidate positions, I'm going to sell the assets.
And what's going to happen? In state i, the price of asset j is s, i,
j, I hold theta j positi-, shares of this asset, so by selling asset j I get Sij
times theta j But I'm going to liquidate the entire portfolio.
So j I'm going to sum from 1 equal to d and that's the amount of money, that's the
pay-off that I'm going to get in the stake.
Its just Sij time theta j sum from j equal to 1 through d, That gives me yi.
And if you just think about it for a moment, if I stock up all the pay-offs as
a vector. If I call a vector y to be y1, y2, all the
way up to y m, the pay-offs in the m states This is nothing but the matrix S,
Times the vector theta. Just to remind you, this is my matrix S,
it has prices for every state as rows. So the payoff in the first state would be
this row times the vector. And the second state would be this row
times the vector. And that's exactly what is being done
here. Sij, as j goes from 1 through D, is a row.
You take the i'th row, multiply it by the vector, you get the payoff in the i'th
state. And therefore, the vector y is simply the
matrix, times theta. Now I want to look at this, in a different
way. I want to think of this, as not
multiplying row, row by row but column by column.
So, instead of looking at this matrix S, as row by row as we have done so far, I'm
going to put them in columns. I've got the column for the first asset,
column for the second asset, column for the d asset and, that's going to multiply
theta-1 theta-2 up to theta-d. And you can see that this multiplication
is nothing but, this row, times this column, so you'll get theta j times Sj.
J is summed from 1 through, that should not be an n, but a d.
It goes from j equals 1, through d. Interpreting it this way, you end up
getting a different interpretation of what is going on.
Now, the pay-offs ys are nothing but linear combinations of the columns.
So vector y, will, I can represent, I can generate a particular pay-off, if it's in
the range of the matrix S. Remember in the concept, we had introduced
this concept in the model of matrices, that a vector y, belongs to the range, of
s, if these are all vectors s-theta, where theta is in, r to the d.
And therefore, y belongs to the range of S.
And remember, we had also introduced the notion of rank.
We had said, that rank tells me how rich that space is.
Can I, how many different vectors can I generate in the range?
So if the rank of the matrix S is n, is equal to m, meaning all possible pay-offs
can be generated, then I can hedge everything.
If on the other hand, the rank of the matrix s, is less than m, that means there
are certain pay-offs. There are certain pay-off vectors that can
not be generated because they can not be produced as if I'm make, taking the matrix
S and multiplying it to theta. So that's the concept that's going to play
a role in the course.We're going to talk about complete markets and incomplete
markets, and that has to do with the rank of this matrix.
Before we get there, here's a simpler notion.
We'll say that a pay-off y hedges x, if y is greater than or equal to x.
Component by component, the pay-off that I've generated using my portfolio is
greater than the pay-off that I need to hedge or give-, the payoff that I need to
give at time 1. Alright, now comes our first optimization
problem. What's the optimization problem?
I want to minimize the price of the portfolio such that it hedges my
obligation. I want to minimize p transpose theta, such
that s-theta is greater or equal to x. And, what are some features about this
optimization problem? The objective!
What I'm trying to maximize or minimize is a linear function, linear function of
theta. The constraints!
Constraints, and what thetas that I can choose, are again linear constraints, as
theta must be greater than or equal to x. Linear or inequality.
So any optimization problem, which has a linear objective function, either
minimization or maximization it doesn't matter, and all the constraints are either
linear inequalities, as is the case here, or linear equalities.
We will call that problem, a linear optimization problem, or a linear program.
It turns out that linear programs are very rich, there's a rich theory about them,
and you can do a lot of interesting things with them.
You can model lots of problems, you can solve them very efficiently, you can get a
lot of interpretation out of them. So the one thing that we're going to focus
on in linear optimization, and the interpretation of linear optimization is
the notion of duality. And what do I mean by the notion of
duality? For every linear program, I can write
another linear program which is intimately connected to it, and this connection is
called duality. So I've got a linear program here minimize
x, c transpose x, Ax greater than or equal to b.
Here's another linear program. Maximize B transpose U, A transpose U
equal to C and U is greater than or equal to 0.
Min goes to max. Now, for the purposes of this course, you
will not be responsible for how I generated the dual linear program from the
primal linear program, or the second linear program from the first linear
program, we will give you that in the course.
The only thing that you're going to be responsible for is, to understand the
relationship, and we'll emphasize this again during the course.
They're here from-, some of the interesting resolve that comes from this
duality concept. The first thing is something called weak
duality. What it says is that this minimization
problem. So the way I, the picture that I have, I
wanted to keep in mind is that here's my value P.
For all feasible values, for all xs, such that Ax is greater than or equal to wha-,
b, I get some numbers on this side. Why do I get greater?
Because I'm trying to minimize. So I get the lowest possible number is p.
I've got another number d. Which is the value of this second linear
program down here. For all Us that are feasible, meaning that
satisfies A transpose U equal to C, and U is greater than or equal to 0, I'll get
values that are less than this D. Why?
Because this is a maximization problem. The largest possible thing that I can get
is B transpose U, is going to be equal to D.
The first theorem says, that in fact, this picture that I'm drawing is correct.
That P is going to be greater than D. There's no reason for it to be that way,
they could have crossed. But the nice thing is, if you construct
the dual linear program correctly, and in the next slide I'm going to show you a
simple example. Again let me emphasize you're not
responsible for knowing it. Just walking through the exercise, and
understanding how I'm going to use the duality.
So the primal and the dual are intimately connected; the optimum value of the primal
P is greater than equal to the optimum value of the dual D.
And because this is true, you end up getting a chain of inequalities that are
very good. We know that c transpose x is greater than
equal to p. Why?
Because I''m trying to minimize c transpose x, so for any feasible x,
anything that satisfies the inequality Ax greater than equal to b, I'll get a value
greater that b. The second piece is also true, D is
greater than equal to b, transpose u because I'm trying to maximize b transpose
u. And the inner part comes because of the v
duality. So now this gives you a very interesting
way, if I can find an x, and I can find a u, such that c transpose x is close to b
transpose u, then I know that the x must be very close to optimal, And u must also
be very close to optimal for the dual. Why?
Because P is greater than, equal to D, if these two at, points are very close, it
must, it must be that P is also very close to c transpose x, which means that it's
optimum. Similarly, b transpose u must be close to
D, which means that is optimum. You end up, you can go one step further,
and say that when either P, or D, is finite, either the primal value is finite,
or the dual value is finite, then in fact, they must be equal.
And finally, the reason why we call them dual, is because if you go from the primal
to the dual, and from, you take the dual of the dual, you get back the primal, and
that's why they're called dual linear programs.
Going a little bit further. Here's another pair of primal dual linear
programs that we'll be, that we'll be using in the course.
Minimize over x, c transpose x, Ax equals b, they, it's equal to maximize u, b
transpose u, A transpose u equal to c. And this equality, I'm putting it there to
emphasize the fact that there is strong duality between them.
But to keep in mind that this equality holds only if you can show that either
this one, p or this one, b is finite. So if p, or d is less than, is less than,
is not equal to let's say, plus infinity or minus infinity, in that case these two
values are the same, and in that sense they are equal.
So, the last piece in this module, we're going to walk through and tell you how to
construct a duel, it's a very general concept called La Grangian relaxation.
And we'll use that in the next module on non linear programming, as well.
So here's the problem. The primal problem is, minimize c
transpose x, Ax, greater than or equal to b.
Now I'm going to take a vector u, which is greater than or equal to zero.
And so u is component wise greater then or equal to 0, and remember Ax is going to be
greater than equal to b. So Ax minus b is component wise greater
than equal to 0, you take some vector which is component wise greater than equal
to the oh, multiplied to another vector that is component wise greater than equal
to 0, you end up getting a number, which is greater than or equal to 0.
So I'm subtracting it, so I'm getting a number, which is less than c transpose x.
So this linear program, which has a changed objective function involving this
vector u, is going to have a value, which is going to be less than equal to P.
B transpose U does not involve the decision x, it does not involve the
minimization, the minimization is going on over x, it does not involve x, so I pull
that out. I end up getting a new problem, which is
minimize c minus a transpose u times x. And what happened to this constraint?
I threw it away! Why did I throw it away?
It's complicated. I don't know how to deal with constraints,
so I threw it away. But I'm guaranteed that if I throw away
these constraints my set over which I can optimize, the xs over that I can chose
become larger, and therefore this minimum only becomes smaller.
So I end up getting that this quantity, is going to be smaller than the previous
line. Now, because I don't have any constraints,
I have a very simple problem. I've got some vector, let's call this
vector d. I've got d transpose x.
So I want to minimize d transpose x. So here's my d vector.
I want to minimize this, d transpose x, and I can choose my x to be anything.
So what am I going to do? I'm going to choose my x to be in the
negative direction and going off to infinity.
Here's my b, here's my x! If I multiply d and x together I get a
very large negative number. So if I have vector d which is not equal
to 0, I can make this optimization problem equal to minus infinity and that's what
this says. If d is not equal to 0 and, just to
emphasize d's equal to c minus A transpose u, if this is not equal to 0 you get to
minus infinity. If in fact, d is equal to 0, which means
that c is equal to A transpose u, then I can't do anything over here.
This vector is equal to 0, I multiply to any other vector, I'll get a 0.
So you end up getting that this minimization problem has a value equal to
0. And p is greater then equal to b transpose
u. Now u is arbitrary, the only thing that I
needed to do was, which is missed over here, is that I needed to have that u must
be greater than equal to zero. So now, you have p must be greater than
equal to maximize b transpose u, which is the value here, provided A transpose u is
equal to c and u is greater than equal to 0.
That immediately gives you a weak duality, a little bit more work gives you a strong
duality. So here's the connection.
Max-, minimize C transpose x, Ax greater than or equal to B is equal to maximize B
transpose U, A transpose U equal to C, and U greater than equal to 0.
That's what we derived over here. What we did, we dualize constraints, and
this word will show up some times during the course.
Dualize means I take the constraints and multiply them by a variable which has a
particular sign. We had a constraint Ax minus b, I
multiplied by a vector of u which is greater than equal to 0, that's
dualization and then I'd relax the constraint.
I have this constraint Ax greater than equal to b, I didn't like it, it was too
complicated, I threw it away. I'd relaxed them!
And by doing dualization and relaxation, you end up getting something called a La
Grangian relaxation, which gives you duals, And gives you some very nice
properties that we'll explore more in the course.
Explora nuestro catálogo
Inscríbete de manera gratuita y obtén recomendaciones personalizadas, actualizaciones y ofertas.
Coursera brinda acceso universal a la mejor educación del mundo, al asociarse con las mejores universidades y organizaciones, para ofrecer cursos en línea.
© 2018 Coursera Inc. Todos los derechos reservados.
