Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

1. You have taken over the management of a paper production firm. You find that the firm is contracted to deliver 3,000, 6,000, 5,000, and 2,000 reams of paper over the next four periods. At the moment, there are 500 reams of paper in stock.

You want to devise a production schedule to deliver the paper over the next four periods. There are two ways to produce paper:

• An efficient machine that can produce paper at the cost of $1 per ream. Currently, this machine is calibrated to produce 4,000 reams of paper each period.

— It can be recalibrated from one period to the next to produce more paper at a cost of $3 per extra ream. (For example, if the current production level is 4,000 per period, and yon wish to use the machine to produce 4,100 in the next period, this will cost an extra $300.)

—It can also be recalibrated from one period to the next to produce less paper at a, cost of $0.80 per ream. (For example, if the current production level is 4.100 per period, and yon wish to use the machine to produce 4,000 in the next period, this will cost an extra $80.)

• An emergency machine that can produce paper at the cost of $1.40 per ream. This machine can produce any amount of paper in a period without any recalibration costs.

Any paper that is left over at the end of a period incurs $0.05 per ream storage cost. You would like to reduce the output of the efficient machine to 3,000 reams per period at the end of the fourth period. Furthermore, you need at least 500 reams of paper in inventory by the end of the fourth period, and you pay an additional penalty of $0.15 per ream over 500.

(a) (14 points) Formulate the optimal production schedule problem as a linear program.

(b) (6 points) 命 Please refer to the Jupyter Notebook for this question. Implement the model in Gurobi. Make sure that the model can take into account data of different sizes.

2. We consider a one-period financial market with n assets.

• At the start of the period, each asset j 6 [n] has a known price % > 0. The vector of prices is denoted 7T € R 华

• It is unknown what the prices of the assets will be at the end of the period. However, market research has produced N scenarios for the price vectors: pi,... E 衅. Here, pij denotes the end price of asset j in scenario i.

To clarify, at the end of the period, one, and only one, scenario i G [N] will take place. So the prices for the assets will be represented by one, and only one, vector p" i.e., the prices will be p/.i,...

for assets 1,..., n. However, we do not know which scenario will take place, and we do not have any probabilities on the scenarios taking place.

• A portfolio is a vector x G R" where each entry Xj tells us how many units of asset j we own. Note that we assume the number of units owned may be fractional.

Furthermore, the portfolio may have negative amounts: Xj < 0 means that we "short sell" asset j at the start of the period. That is, we "sell” Xj units of the asset, and we have TTjXj extra money to spend on other assets. However, we do so under the contract that at the end of the period we must buy Xj units back at the new price, whatever it turns out to be. (Short selling is used when we have a strong belief that the price of the asset will decrease.)

• The value of the portfolio x at the start of the period is given by 7r丁％ = ^顶冬川 If scenario i conies to pass, the value of the portfolio at the end of the period is pjx =习项冬川 PijXj.

• An arbitrage opportunity exists when there exists a portfolio x such that in every scenario, the value of the portfolio at the end of the period is at least as much as the value at the start, and in at least one scenario, the value of the portfolio is strictly greater than the value at the start.

(a) (14 points) Given starting prices tt and scenario prices pi,..., Pn , formulate a linear programming model for detecting the presence of an arbitrage opportunity, and explain how to use it.

Hint: After you formulate your model, you should consider two questions: (i) if there is an arbitrage opportunity, what is the output of the model going to be: and (ii) if there is no arbitrage opportunity, what is the output of the model going to be?

The second question requires you to think carefully about what it means when no arbitrage opportunity to exist. To help you along, suppose that no arbitrage exists. Consider some arbitrary portfolio x where the ending value is greater than or equal to the starting value in all scenarios, i.e., pjx > x for all i 6 [N]. What can we now infer from the knowledge that no arbitrage exists?

(b) (6 points) W Please refer to the Jupyter Notebook for this question. Implement the model in Gurobi. Make sure that the model can take into account data of different sizes.

3. You own a property development firm. You consider investing in three development projects, each of which will take 1.5 years, or six quarters, to complete. For each project, each quarter marks a completion milestone, which may incur costs (e.g., from buying building materials and paying wages) or generate income (e.g., if completed parts of the project are sold to buyers). The table below shows the projected cash flow stream for each project across the six quarters.

Each column shows the amount that must be paid (negative numbers) or the amount earned (positive numbers) for each project at the start of the corresponding quarter, in units of millions of dollars. The last column shows the estimated value of the projects at the end of quarter 6. (Note: project B has negative value at the end since it is a condition to demolish the development at the end of the 1.5 years. Therefore for an initial investment of $2.5 million over two quarters, the project will earn $4.7 million over four quarters, but cost $1 million to demolish at the end.)

It is possible to invest a fractional amount into each project. This means that cash fiows are reduced proportionally. For example, if you were to invest 40% into project A, the cash flow would be -1.2, -0.4, -0.72, 0.16, 0.72, 0.72, 2.2. However, once you decide on your investment fraction, it stays the same until the end of the projects.

Your firm has certain amounts to invest at the start of each quarter, given in the following table (in millions):

QI Q2 Q3 Q4 Q5 Q6 end

0?5~~04~~038~~~~0?34~~03^

You can supplement these amounts by borrowing money each quarter at an interest rate of 3.5% per quarter. You have borrowing capacity of $2 million each quarter. Any loan taken out at the start of a quarter iniist be paid back (including interest) at the end of the quarter. You can also choose to invest money in bonds, which increase in value by 3% per quarter; there is no limit for investing in bonds. Bond investments are also paid each quarter.

Your goal is to choose how much to invest in the projects, how much to borrow each quarter, and how much to invest in bonds each quarter in order maximize the net worth of your portfolio at the end of Q6.

(a) (14 points) Formulate a linear program to find the optimal investment plan. Solve your linear program (using code from part (b)) and interpret the sohition.

Hint: it may help you write the model cleanly if you define constants for the input data. For example, let Cij be the income stream from project i G (A, B, C} at the start of quarter j 6 [n], where n = 6.

(b) (6 points) 斜 Please refer to the Jupyter Notebook for this question. Implement the model in Gurobi. Make sure that the model can take into account data of different sizes.

4. Suppose that we have data points (x，[,yi) for i G [A⁷*], where Xi E are feature vectors and y, € (±1} are binary outputs, or labels. The linear classification problem aims to find a linear function = a ^vx + b such that sign(/'(%/)) = for as many data points i 6 [N] as possible. Note that the sign function is defined as

(1, r > 0 sign(r) ：=〈 0, 尸=0

[-1, r < 0.

A linear classifier /(x) = a^Tx+b correctly classifies a data point (亿牝 饥)if and only if yif(xi) = ?/»(q ¹ xi+b) > 0. Sometimes, the quantity Xi + b) is called the margin of the point i.

In this question, we will explore two popular techniques for training a linear classifier: the support vector machine and the hard margin classifier.

Note: parts (a), (b) and (c) are challenging. However, you may use an earlier part to answer later parts, even if you cannot complete the earlier part.

(a) (4 points) Show that given any a > 0 and v 6 Rⁿ, we have

max{.Tz : ||z||i = a} = a||*y||oo-

Note: this part does not require any linear programming modelling, only mathematical arguments.

Hint: the optimal z will always satisfy VjZj = You may use this, but you need to justify why

this is true to receive full marks. We can then change variables Wj = \zj\ and equivalently maximize \^vj\^wj over the constraints w > 0, £项曰川 叫 = a. For this new problem, show that the optimal solution w always satisfies Wj = 0 whenever \vj \ < ||。||8・

(4 points) The -margin of a data point {xi, yi) on a linear function /(or) = o7x + b is the smallest perturbation 6 needed to make+ d) + b have a different sign to y,’, This is written as:

祐(％ b) = mm{||5||i : yi(a^T(Xi + 5) + h) < 0). d

Show that max{0,切(。丁的 + 6)}

Note: this part does not require any linear programming modelling, only mathematical arguments.

Hint: using part (a), show that we equivalently have

mm{v^Tz : ||z||i =a} = 一0||祈|8.

Use this to derive the optimal value of

mm[yi(a^T(xi + d) + b) : ||<5||i = a}.

8

(5 points) Assume that we can find a. b such that 快(a⁷以 + 6) > 0 for all i G [N]^ thus we have 《((!」))=.妃J. Suppose we wish to choose a and b to maximise the smallest -margin 7/(a, 6) amongst i € [N]:

max min

Q,b z€[m] ||q|〔8

This is called the hard margin classifier. To solve for the hard margin classifier, we consider the following program:

min Halloo (2a)

s.t. yi(a^T^i + b) > 1, Vi G [N]. (2b)

Reformulate this as a linear program, and show why any optimal solution (q： b) to (2) is also an optimal solution for (1).

Hint: to show that any optimal solution (a)b) to (2) is also an optimal solution for (1), we can use the contrapositive: show that whenever (a, b) is not optimal for (1), it also cannot be optimal for (2).

(d) (3 points) Describe a simple example (e.g., four labelled data points in R²) when perfect classification with a linear classifier is impossible. What would happen if we used (2) to solve this example?

(e) (4 points) Consider the hinge loss:

hz(a,b) _ { 1 _物0丁皿 + b),

Formulate a linear program to choose a, b that minimizes the sum of the hinge losses ^汇小珥九/(。，b). This is called the support vector machine.

(f) (10 points) @ Please refer to the Jupyter Notebook for this question. Build functions to implement the support vector machine and the hard margin classifier in Gurobi. given a dataset. Make sure that your model can take into account data of different sizes.