The University of Sydney School of Mathematics and Statistics Assignment MATH2070/2970: Optimisation and Financial Mathematics Semester 2, 2017 Web...

No idea about Q4 and not sure about Q3

Copyright 1 10 Marks 3. Short Term Financing Corporations often face the problem of having to satisfy certain cash

flows over several months. They may be negative, as when the corporation needs to pay, for

example, a manufacturer, or they may be positive, as when they have scored a contract and

receive payment. Corporations have usually several options to do the financing and want to

maximize their wealth at the final time.

Consider the following short term financing problem

Month

Net Cash Flow Jan

-210 Feb

-170 Mar

230 Apr

-180 May

30 Jun

270 Net cash flows are given in thousands of dollars.

The corporation has access to the following financing option: They can

• Take a line of credit of up to $200, 000 at an interest rate of 1.8% per month

• In any of the first 3 months, issue a 90-day commercial paper yielding a total interest of

2.2% for the 3-month period

• Invest any excess funds at an interest rate of 0.4% per month.

Formulate this short term financing problem as a Linear Programming problem (not necessarily

in standard form). This question only requires you to formulate the problem and does not ask

you to solve it.

(Hint: When considering the variables accounting for the credit taken, it is convenient to consider

these variables as the balance on the credit line rather than as incremental borrowings for each

month. Similarly for the excess funds, it is convenient to define them as accounting for the

overall excess fund.)

10 Marks

4. Support Vector Machines: Classifying observed data constitutes a major activity in many

areas of engineering, economy and science. For example, given a cohort of patients which have

been exposed to some specific medical treatment, one wishes to find certain criteria based on

their medical records, which determine whether the treatment is likely to help the patient or

not. Machine Learning aims at solving such questions. One first starts with a data set where

the classification is known and can then apply the classification to a new set of medical records

with unknown classification.

On a more abstract level, suppose that several d-dimensional data points u, so called feature

vectors, are mapped to one of a finite set C of classes. Consider here two classes with labels

C = {1, −1}. Samples in class 1 are referred to as positive and those in class −1 as negative.

In the above example, these would be the classifications whether patients responded well to a

medical treatment or did not respond to it. Let us call the feature vectors u which are classified

as positive as u+ and those which are known to be negative as u− . We are seeking a hyperplane

aT x = α

separating the two. For two-dimensional feature vectors this situation is depicted in the following

figure.

Formulate the problem of finding the dividing hyperplane, i.e. a ∈ Rd and α ∈ R, as a linear

programming problem.

(Hint: Use δ to convert a problem which involves strict inequalities into the standard form of

linear programming.)

7 Marks 2 u+ u pi 5. When formulating the Simplex Algorithm we identified the feasible corner points as basic solutions. Proof the following theorem which establishes an equivalence between basic solutions

and extreme points in convex sets.

Definition: A point x in a convex set C is said to be an extreme point (or corner point

as we called them in the lectures) if there are no two distinct points x1 and x2 such that

x = λx1 + (1 − λ)x2 for some λ, 0 < λ < 1.

Theorem Let A be a m × n matrix of rank m and b an n-vector. Let K be a convex polytope

consisting of all n-vectors satisfying

Ax ≤ b

x ≥ 0.

A vector x is an extreme point of K if and only if x is a basic feasible solution. 3 10 Marks