MSBA 403:
Optimization
Lecture 3
November 20, 2020
Example: Supply planning
§ A manufacturer of hardware tools is deciding how many of two products — wrenches and pliers – to produce per day, for the current quarter.
§ The firm faces constraints on steel availability (in lbs), molding machine capacity (in hours), and assembly machine capacity (in hours) per day. Further, there are limits on the demand for both wrenches and pliers.
§ Taking these constraints into account, the firm formulates the following linear program to determine how many wrenches (W) and pliers (P) to produce (in 1000s):
max 130W + 100P W,P
s.t. 1.5W + P 27 W + P 21
0.3W + 0.5P 9 W 15
P 16
W, P 0.
(Steel availability) (Molding capacity) (Assembly capacity)
(Wrench demand) (Pliers demand)
2
Modeling uncertainty
§ We have so far assumed all model parameters are known
§ What if there was uncertainty in some of the model parameters? § Uncertainty in demand
§ Uncertainty in profit due to fluctuating prices or production costs
§ Uncertainty in machine capacity
§ One way to capture uncertainty in a linear or integer program is by using a two- stage modeling approach
3
Example: Supply planning
§ In the current quarter, the firm had contracted with a steel supplier for 27,000 lbs of steel per day.
§ Suppose the firm is now deciding how much steel to contract for with local suppliers for the next quarter. Steel contracts are arranged for daily delivery over the entire quarter, and the market price is $58/1,000 lbs.
§ There are now two sources of uncertainty:
1)The assembly machine capacity for next quarter is uncertain. The firm has ordered new assembly machines to replace failing equipment, but it is uncertain whether the new machines will be delivered on time. There is a 50% chance of successful delivery. If the new machines are successfully delivered, the assembly capacity will be 10,000 hours. If not, the assembly capacity will drop to 8,000 hours.
2)Further, the profit margin on wrenches is uncertain due to fluctuations in market demand. For simplicity, assume that the profit per 1000 wrenches will be either $90 or $160 with equal probability.
§ Assume that the uncertainty in assembly machine capacity and wrench profit are independent of each other.
4
Example: Supply planning
The sequence of events is now as follows:
1. The firm decides how much steel to purchase (Stage 1).
2. The assembly capacity and wrench profit becomes known.
3. After the uncertainty is resolved, the firm decides how many wrenches and pliers to produce
(Stage 2).
There are now four scenarios to consider:
Scenario
Assembly Capacity (hours/day)
Wrench Profit ($/1000s)
Probability
1
8,000
160
0.25
2
10,000
160
0.25
3
8,000
90
0.25
4
10,000
90
0.25
How can we account for these uncertainties in a new linear programming model?
5
Example: Supply planning
§ First we create a new decision variable, S, to represent the amount of steel to purchase
§ We will also need new decision variables, Ws and Ps, to represent how many wrenches and
pliers to produce under scenario s = 1,2,3,4
§ Note: Because steel supply decision must be made before the uncertainties are realized, there
is only one decision variable for steel
§ What should the objective function be? A natural choice is the expected profit:
0.25(160W1 + 100P1) + 0.25(160W2 + 100P2) + 0.25(90W3 + 100P3) + 0.25(90W4 + 100P4) 58S
scenario 1 scenario 2 scenario 3 scenario 4
steel cost
6
Example: Supply planning
§ Because assembly capacity depends on which scenario occurs, we require a separate assembly constraint for each scenario:
0.3W1 + 0.5P1 8 0.3W2 + 0.5P2 10 0.3W3 + 0.5P3 8 0.3W4 + 0.5P4 10
(scenario 1)
(scenario 2) (scenario 3) (scenario 4)
7
Example: Supply planning
§ The full formulation is then given by
max 0.25(160W1 + 100P1) + 0.25(160W2 + 100P2) + 0.25(90W3 + 100P3) + 0.25(90W4 + 100P4) 58S
W,P,S
s.t. 0.3W1 + 0.5P1 8
0.3W2 + 0.5P2 10
0.3W3 + 0.5P3 8
0.3W4 + 0.5P4 10
Ws +Ps 21, s=1,2,3,4 Ws 15, s=1,2,3,4
Ps 16, s=1,2,3,4
1.5Ws +Ps S, s=1,2,3,4 Ws,Ps 0, s = 1,2,3,4
S 0.
Molding capacity and demand constraints are the same across all 4 scenarios
Steel supply is now a decision variable
8
Example: Supply planning
§ The previous formulation maximizes the expected value of profit
§ What if we wish to maximize profit under the worst case scenario?
9
Example: Supply planning
§ The following LP maximizes a lower bound on the profit under all four scenarios max V
W,P,S,V
s.t. V
V 160W2 + 100P2 58S
V 90W3 +100P3 58S
V 90W4 +100P4 58S 0.3W1 + 0.5P1 8
0.3W2 + 0.5P2 10
0.3W3 + 0.5P3 8
0.3W4 + 0.5P4 10
Ws +Ps 21, s=1,2,3,4 Ws 15, s=1,2,3,4
Ps 16, s=1,2,3,4
1.5Ws +Ps S, s=1,2,3,4 Ws,Ps 0, s = 1,2,3,4
S 0.
160W1 + 100P1 58S
Profit under each of the 4 scenarios
10
Non-linear programming
§ We have so far focused on problems where the objective and constraints are linear functions of the decision variables (which can be either continuous or integer)
§ Certain optimization problems may require the use of a non-linear objective or constraint
§ Not all non-linear optimization problems are easy to find optimal solutions to (more on this in Lecture 4)
11
Portfolio optimization
§ One of the most well known applications of non-linear programming is portfolio optimization
§ In finance, a portfolio is a collection of assets (e.g. stocks and bonds) defined by a set of weights over the possible assets
§ The weight in asset i, wi, is the fraction of your money invested in i
§ The goal of portfolio optimization is to select a portfolio (i.e. a weight vector) that balances risk and reward
12
Example: 3-Asset Portfolio
§ Consider a portfolio constructed from three assets: MGM, JP Morgan, and Gold
§ Each asset is a random variable, with an expected return and variance, based on historical
data
§ The expected monthly returns and covariance matrix of the three assets from Oct 2008 – Oct 2018 are:
50/50 JPM and MGM
(October 2008 – October 2018)
35000
30000
25000
20000
15000
10000
5000 0
What if we invested in JPM and MGM with equal weights?
0
100
200
300
400 500 600
50/50 JPM/MGM
JPM
MGM
50/50 JPM and Gold
(October 2008 – October 2018)
35000
30000
25000
20000
15000
10000
5000 0
What if we invested in JPM and Gold with equal weights?
0
100
200
300
Negative covariance between JPM and Gold reduces variance of portfolio (i.e. risk)
400 500 600
50/50 JPM/Gold
JPM
Gold
How can we use optimization to construct an “optimal” portfolio?
16
The Markowitz Problem
§ One approach: Minimize risk (i.e. portfolio variance) subject to the constraint that the expected return of the portfolio is at least ⍴
§ This approach was pioneered by Harry Markowitz in 1952
§ Gave rise to modern finance theory and led to a Nobel Prize in Economics in 1990 § Many mutual funds and portfolio managers use some variation of this model
17
Example: Portfolio optimization
§ Suppose we want to build a portfolio by investing only in JPM and Gold
§ Let wJ and wG be the weight of our portfolio in JPM and Gold, respectively
§ How can we find values of wJ and wG that will minimize risk (variance) while achieving a target expected monthly return of at least 0.45%?
18
Example: Portfolio optimization
§ Let J and G be random variables representing JP Morgan and Gold’s monthly returns
§ From our data, we can estimate the following: § E(J) = 0.5
§ E(G) = 0.4
§ Var(J) = 6.4
§ Var(G) = 2.5
§ Cov(J,G) = -0.68
§ Using this data, we can now formulate a quadratic program to solve for the optimal wJ and wG
§ Reminder: we want to minimize risk subject to a constraint on expected return
19
Sum of 2 random variables
§ Some useful things to know:
§ Let X and Y be any random variables § Then
E(aX + bY ) = aE(X) + bE(Y )
Var(aX + bY ) = a2Var(X) + b2Var(Y ) + 2abCov(X, Y )
Cov(X,X) = Var(X)
Example: Portfolio optimization
§ Expressing these formulas in terms of our variables, we get
Var(wJ J + wGG) = wJ2 Var(J) + wG2 Var(G) + 2wJ wGCov(J, G)
E(wJ J + wGG) = wJ E(J) + wGE(G)
§ Using the estimates from our data, we can now formulate the portfolio optimization problem as
the following quadratic program:
wJ ,wG
s.t. 0.5wJ + 0.4wG 0.45
wJ +wG =1 wJ,wG 0.
min 6.4w2 + 2.5w2 10.364www
J G JJGG
What if we want to invest in n assets?
21
Sum of n random variables
§ The portfolio is the sum of random variables, given by
Xn
wi Xi
! X!X
where
Xn
i=1
§Note that
n i=1
n i=1
i=1
wi = 1.
E
=
wiE(Xi)
wiXi
Xn Xn Xn
Var wiXi = wiwjCov(Xi,Xj) i=1 i=1 j=1
The Markowitz Problem
§ Let wi be weight on asset i, ri be expected return of asset i, C be covariance matrix, and ρ be the target return of the portfolio
§ Then the portfolio optimization problem is nn
min
w
s.t.
X X wi wj Cij i=1 j=1
(Variance of returns / risk level)
(Expected return should be at least ρ)
n i=1
wiri ⇢ wi = 1
Xn
(Weights add up to 1)
i=1
wi 0,
i = 1,…,n.
Reminder: Not all non-linear programs are computationally
“easy” to solve, but this one generally is
23
In-class assignment 2:
Portfolio optimization
24