The University of Sydney School of Mathematics and Statistics Assignment MATH2070/2970: Optimisation and Financial Mathematics Semester 2, 2017 Web Page: http://www.maths.usyd.edu.au/u/IM/MATH2070/ Lecturer: Georg Gottwald Due on 5.00pm Thursday 7th September on TurnitIn as well as a hardcopy in the collection boxes on Carslaw Level 6 MATH2070: Do all questions except Question 5. MATH2970: Do all questions except Question 2. 1. Consider the following linear programming problem Z = 2x1 x2 minimize x1 + x2 2 subject to x1 x2 6 x1,2 0 with (a) Write the problem in standard form. 3 Marks (b) Solve the problem in standard form graphically. Also, 3 Marks Introduce appropriate slack or surplus variables and define the boundaries of the feasible region in your graphical representation. Explain why slack variables are added and not subtracted from the left hand sides of the constraints. Indicate the shortest path to optimality. (c) Solve the problem manually using the simplex algorithm. Determine the optimal solution 4 Marks x? and the optimal value Z ? . Explain every step you make. In particular How do you choose certain values to enter the basis? Explain why. How do you choose which variables should leave the basis? Explain why. How do you decide when to stop? Explain why. 2. Consider the following linear programming problem maximize Z = 4x1 + 14x2 subject to 2x1 + 7x2 21 7x1 + 2x2 21 x1,2 0 with Solve the problem manually using the simplex algorithm. At each step record which variables enter and leave the basis. In particular, Determine the optimal solution x? and the optimal value Z ? . What is special about the optimal solution? (You might find it helpful to sketch the problem graphically). c 2017 The University of Sydney 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