留学生作业代写 MIE1624H – Introduction to Data Science and Analytics Lecture 9

Lead Research Scientist, Financial Risk Quantitative Research, SS&C Algorithmics Adjunct Professor, University of Toronto
MIE1624H – Introduction to Data Science and Analytics Lecture 9 – Optimization
University of Toronto March 15, 2022

Overview of Optimization

Optimization
▪Optimization problem
▪ Examples:
– Minimize cost – Maximize profit

Optimization
▪Optimization problem

Optimization
◼ Optimization problem
◼ Minimizing convex quadratic (QP) objective function over a polyhedron
(linear constraints)
general form

Optimization
▪Optimization problem
▪ Examples:
– Minimize cost – Maximize profit
▪Multi-objective optimization: simultaneously optimizing two or more conflicting objectives subject to certain constraints
▪ Examples:
– Minimize cost & Minimize environmental impact – Minimize risk & Maximize return

Multi-objective optimization
◼ Solving multi-objective optimization problems:

Linear Optimization Examples

Workforce planning
◼ Restaurant is open 7 days a week
◼ Based on past experience, the number of workers needed on a particular day:
◼ Every worker works five consecutive days, and then takes two days off ◼ Minimize the number of workers that staff the restaurant
◼ Decision variables:
❑ (wrong) xi is the number of workers that work on day i
❑ (right) xi is the number of workers who begin their five-day shift on day i ◼ Objective function:
◼ Bounds on variables: 10

Workforce planning
◼ Constraints:
❑ Consider the constraint for Monday’s staffing level of 14
❑ Who works on Monday? Those who start their shift on Monday (x1)
❑ Those who start on Tuesday (x2) do not work on Monday, nor do those who start on Wednesday (x3)
❑ Those who start on Thursday (x4) do work on Monday, as do those who start on Friday (x5), Saturday (x6), and Sunday (x7)
❑ This gives the constraint:
◼ Similar argument give a total formulation

Workforce planning – expression formulation
◼ Constraints:
❑ Consider the constraint for Monday’s staffing level of 14
❑ Who works on Monday? Those who start their shift on Monday (x1)
❑ Those who start on Tuesday (x2) do not work on Monday, nor do those who start on Wednesday (x3)
❑ Those who start on Thursday (x4) do work on Monday, as do those who start on Friday (x5), Saturday (x6), and Sunday (x7)
◼ Similar argument give a total formulation:

Workforce planning – matrix formulation
Mathematical formulation Solver formulation

Road design problem
◼ Given point A and B, and a map, find a road that will be the cheapest to construct/maintain
Source: . Hare, A Multi-Haul Model for Vertical Alignment Optimization of Road Design

Road design problem – costs (easiest to hardest to compute)
◼ Cost depends on many factors
◼ Land acquisition  0% to 25%
◼ Bridges, tunnels, etc.  0% to 20%
◼ Per km cost (final paving, maintenance)  5% to 15% ◼ Earthwork  20% to 50%
◼ Long term economic costs  ?
◼ Environmental issues  ?
Source: . Hare, A Multi-Haul Model for Vertical Alignment Optimization of Road Design

Road optimization
◼ Level 1: Horizontal Alignment (HA)
◼ Look at a map and select a path for the road to follow
◼ Evaluate HA based on safety constraints and Vertical Alignment
◼ Level 2: Vertical Alignment (VA)
◼ Use HA to build a cross section of the terrain
◼ Determine a VA for the future road
◼ Evaluate VA based safety constraints and Earthwork
◼ Level 3: Earthwork (EW)
◼ Determine how to move earth in order to make the terrain fit the VA ◼ Cost based on minimization
Vertical Alignment and Earthwork can be modelled and solved simultaneously as a mixed-integer linear optimization problem
Source: . Hare, A Multi-Haul Model for Vertical Alignment Optimization of Road Design

Road optimization – earthwork
Source: . Hare, A Multi-Haul Model for Vertical Alignment Optimization of Road Design

Overview of Optimization Techniques

Optimization
◼ Optimization problem
◼ Minimizing convex quadratic (QP) objective function over a polyhedron
(linear constraints)
general form

Solving linear optimization problems
◼ Maximizing/minimizing linear (LP) function over a polyhedron
◼ Interior Point Methods vs. Simplex-type Methods

Solving linear optimization problems
◼ Simplex Method – graphical view
standard form
Source: , Interior Point Algorithm Fundamentals

Solving linear optimization problems
◼ Simplex Method – graphical view Current Basis
Maximize z = 3×1 + 2×2 + 2×3
(x4, x5, x6) (x4, x1, x6) (x3, x1, x6) (x3, x1, x2)
Source: , Interior Point Algorithm Fundamentals
(7,0,0) x1

Solving linear optimization problems
◼ Interior Point Method (barrier algorithm in CPLEX)
Simplex solution path
Barrier central path
o Predictor
o Corrector Optimum
Source: , Interior Point Algorithm Fundamentals

Solving linear optimization problems
◼ Higher dimensions

Solving mixed-integer optimization problems
◼ Mixed-integer optimization problems (MIP) ◼ continuous variables
◼ integer variables
feasible solutions =
x2 objective optimum of
LP relaxation
IP optimum
rounding down optimum of LP relaxation

Non-linear Optimization for Portfolio Selection

Measuring risk and portfolio selection
Portfolio return distribution (
Variance (standard deviation)
) is assumed to be Gaussian (Normal)
◼ Consider n assets with random returns:
➢ proportion invested in asset i
➢ exp. return and standard dev. of
the return of asset i
➢ variance-covariance matrix
◼ Portfolio expected return and variance: ◼ Set of admissible portfolios:
Mean 0 return
Portfolio Return ( )
Probability density

Portfolio selection
Consider n assets with random returns:
➢ proportion of total funds invested in asset i
➢ expected return and standard deviation of the return of asset i
➢ correlation coefficient of i’s and j’s returns
➢ vector of expected returns
➢ variance-covariance matrix (PSD)
Expected return and variance of the resulting portfolio:
Set of admissible portfolios:

Portfolio selection
A feasible portfolio w is efficient if it has:
❑ maximal expected return among all portfolios with the same variance, ❑ minimumvarianceamongallportfolioswiththesameexpectedreturn.
Mean-variance optimization (Markowitz, 1952):
Alternative formulations
Solving for all the values of V, R, or  gives efficient portfolios: 33

Mean-variance portfolio selection in Python
Step 1 – compute minimum Step 2 – compute Step 3 – compute efficient variance portfolio maximum return portfolio frontier (mean-variance)

Mean-variance portfolio selection in Python
# Random data for 10 stocks
Q = np.random.random((n,n))
Q = np.dot(Q,Q.T)/1000 # covariance matrix mu = np.random.rand(n) / 100 # expected return
# Compute minimum variance portfolio
w1 = cp.Variable(n)
prob1 = cp.Problem(cp.Minimize(cp.quad_form(w1, Q)),
[sum(w1) == 1,
prob1.solve(verbose=True)
# Display minimum variance portfolio
w_minVar = w1.value
var_minVar = np.dot(w_minVar, np.dot(Q, w_minVar))
ret_minVar = np.dot(mu, w_minVar)
print(“Minimum variance portfolio:\n”)
Step 1 – compute minimum variance portfolio
print(“Standard deviation =”, np.sqrt(var_minVar))
Solution status =”, prob1.status)
Solution value =”, prob1.value)
Variance =”, var_minVar) Expected return =”, ret_minVar)
Minimum variance portfolio:
Solution status = optimal
Solution value = 0.001899092402601308
Variance = 0.001899092402601308 Expected return = 0.003267477841642341 Standard deviation = 0.043578577335673864

Mean-variance portfolio selection in Python
# Random data for 10 stocks
Q = np.random.random((n,n))
Q = np.dot(Q,Q.T)/1000 # covariance matrix mu = np.random.rand(n) / 100 # expected return
# Compute maximum return portfolio
w2 = cp.Variable(n)
[sum(w2) == 1,
prob2.solve(verbose=True)
# Display maximum return portfolio
w_maxRet = w2.value
var_maxRet = np.dot(w_maxRet, np.dot(Q, w_maxRet))
ret_maxRet = np.dot(mu, w_maxRet)
print(“Maximum return portfolio:\n”)
Step 2 – compute maximum return portfolio
print(“Standard deviation =”, np.sqrt(var_maxRet))
Solution status =”, prob2.status)
Solution value =”, prob2.value)
Expected return =”, ret_maxRet) Variance =”, var_maxRet)
Maximum return portfolio:
Solution status = optimal
Solution value = 0.00893492393857598
Expected return = 0.00893492393857598
Variance = 0.00445041529455067
Standard deviation = 0.0667114330122706

Mean-variance portfolio selection in Python
# Target returns
targetRet = np.linspace(ret_minVar,ret_maxRet,50)
# Compute efficient frontier
w = cp.Variable(n)
eps = cp.Parameter()
eps.value = targetRet[0]
prob3 = cp.Problem(cp.Minimize(cp.quad_form(w, Q)),
sum(w) == 1,
w_front = []
var_front = []
ret_front = []
for epsilon in targetRet:
eps.value = epsilon
prob3.solve(verbose=False)
w_front.append(w.value) var_front.append(np.dot(w.value, np.dot(Q, w.value))) ret_front.append(np.dot(mu, w.value))
# Plot efficient frontier
ax = plt.gca()
ax.scatter(x=np.sqrt(var_minVar), y=ret_minVar, marker=’D’, s=50, color=’DarkGreen’,
label=’minimum variance portfolio’)
ax.scatter(x=np.sqrt(var_maxRet), y=ret_maxRet, marker=’s’, s=50, color=’DarkMagenta’,
label=’maximum return portfolio’)
ax.plot(np.sqrt(var_front), ret_front, ‘k-‘, label=’efficient frontier’) ax.scatter(x=np.sqrt(np.diag(Q)), y=mu, color=’Blue’, label=’individual stocks’) ax.set_xlabel(‘Volatility (Standard Deviation)’)
ax.set_ylabel(‘Expected Return’)
plt.title(‘Efficient Frontier’)
ax.legend(loc=”lower right”)
plt.show()
Step 3 – compute efficient frontier (mean-variance)

Sharpe ratio
◼ Sharpe ratio (reward-to-variability ratio) measures the excess return (risk
premium) per unit of risk (deviation) in an investment asset or a portfolio
◼ Idea: how much additional return you are receiving for the additional volatility of holding the risky asset or portfolio over a risk-free asset – the higher the better:
◼ Sharpe ratio is a risk-adjusted measure of return that can be used to evaluate performance of a portfolio (ratio helps to make portfolios’ performance comparable by making an adjustment for risk)
◼ Example:
❑ Manager A generates a return of 15%, while manager B generates a return of 12%. Is manager A performing better than manager B?
❑ Risk free-rate is 5%, manager A’s portfolio has a standard deviation of 8%, while manager B’s portfolio has a standard deviation of 5%.
❑ Sharpe ratio for manager A is 1.25, while manager B’s ratio is 1.4, which is better than manager A.
❑ Based on these calculations, manager B was able to generate a higher return on a risk-adjusted basis.
◼ Flaw of averages 38

Maximizing Sharpe ratio
◼ Sharpe ratio for a portfolio = excess expected return per unit of risk:
◼ Optimization problem that corresponds to maximizing Sharpe’s ratio: non-linear
possibly non-convex difficult to solve
◼ A portfolio with the maximum Sharpe ratio can be found by computing efficient frontier and evaluating Sharpe ratios for each portfolio on the frontier

Non-linear Optimization for COVID-19 Modeling – Curve Fitting

China – number of COVID-19 cases

China – fitting exponential function with linear regression
Exponential growth is described by exponential function Exponential growth saturates as growth rate is decreasing

China – fitting logistic function with non-linear optimization
Exponential growth is described by exponential function Saturated growth is described
by logistic function

SIR Models

Models of growth
◼ Exponential growth – change in the number of cases is proportional to the
current number of cases
◼ Solve differential equation
◼ Solution of differential equation

Models of growth
◼ Logistic growth – the rate of growth slows as the population reaches the carrying capacity
◼ consequence of exponential growth is that as ◼ there is a limit to how large can get
◼ Solve differential equation
◼ Solution of differential equation 47

Canada – linear regression
Exponential growth is described by an exponential function Natural logarithm of exponential function is a linear function

Canada – fitting logistic function with optimization
Exponential growth is described by exponential function Logarithmic growth is described
by logistic function

Canada – fitting logistic function with optimization
Curve fitting with optimization
Fitting logistic function with 4 unknown parameters:

Canada – fitting logistic and generalized logistic functions
Logistic function Generalized logistic function
(Richards’ curve)

Canada – modeling a number of daily cases
Derivative of logistic function Derivative of generalized
logistic function

Canada – modeling reproduction number R Logistic function
Generalized logistic function
(Richards’ curve)

Italy – fitting logistic and generalized logistic functions
Logistic function Generalized logistic function
(Richards’ curve)

Italy – modeling a number of daily cases
Derivative of logistic function Derivative of generalized
logistic function

Coronavirus infections peak
Source: https://www.economist.com/graphic-detail/2020/04/17/coronavirus-infections-have-peaked-in-much-of-the-rich-world

China – fitted logistic function (1st wave)
Logistic function

China – fitted logistic function (2nd wave)
Logistic function

China – number of daily cases model (1st wave)
Derivative of logistic function

China – number of daily cases models (1st and 2nd waves)
Derivative of logistic function

Analytics of COVID-19

Analytics of COVID-19
“The Hammer and the Dance” – strategy from 19 March 2020 article

Other Non-linear Optimization Examples

Cell tower location optimization

Cell tower location optimization
1. Initialization(celltowersetupfunction)
Inputs – number of towers, side length of the field, random seed
Output – initial position of each tower, upper and lower bound of the field, radius of tower coverage
2. Definingobjectivefunction(circlesIntersectfunction)
o Objective function of the problem is to maximize the cell coverage area, given the field size
o Maximum possible coverage area is the sum of all cell tower coverage areas, any overlap between cell towers will reduce total coverage area
o Hence, objective function of the problem is to minimize the total overlap area between cell towers
o Sum of intersection areas between each pair of circles is convex objective function that we are minimizing
2a. Helper function areaIntersect
1. Two circles are not overlapping, intersection area = 0
2. One circle is inside another circle, intersection area = smaller circler’s
3. Two circles partially overlap, intersection area = point of intersection and
arc area formula

Cell tower location optimization – overlapping circles
Consider two circles of radii R and r whose centers are separated by a distance d.
The area of overlap between them (assuming ) is
Source: https://scipython.com/book/chapter-8-scipy/problems/p84/overlapping-circles/

Cell tower location optimization

Aircraft conflict avoidance
Source: , Solving aircraft conflicts by continuous optimization and mixed-integer nonlinear programming

 Constrained Non-linear
Optimization Algorithms

Solving non-linear optimization problems
◼ Convex non-linear objective function (NLP), linear or non-linear constraints ◼ Illustrated solution technique – Interior Point Methods
◼ Other solution techniques – SQP

程序代写 CS代考加微信: powcoder QQ: 1823890830 Email: powcoder@163.com

Related Posts