Mathematics留学生代做、代写Programming、C/C++编程语言调试、C#设计代做

日期：2019-11-29 12:51

Object-Oriented Programming

and Its Applications

School of Mathematics

The University of Edinburgh

ASSIGNMENT 3

Newton’s Method

Task 3.1. Recall that Newton’s method can be used to obtain a zero of a function F : Rn !

Rn. The Newton iterations are given by

xk+1 = xk

F(xk), k = 0, 1,...,

where x0 2 Rn is the initial estimate and J(x) 2 Rn⇥n denotes the Jacobian matrix.

On the other hand, if F : Rn ! Rm, where m 6= n, then the Jacobian matrix J(x) is an

m ⇥n matrix, which implies that it is not invertible (recall that only square matrices can be

invertible). Therefore, Newton’s method is not applicable for finding a zero of F if m 6= n.

However, we can overcome this obstacle by approaching the same problem from a di↵erent

perspective. Suppose that F : Rn ! Rm, where m 6= n. We can think of F as a vector of m

real-valued functions, i.e.,

where fi : Rn ! R for each i = 1,...,m.

Therefore, F(x) = 0, where 0 2 Rm, if and only if fi(x) = 0 for each i = 1,...,m. Using

this observation, we can define a new function f : Rn ! R as follows:

(1) f(x) = Xmi=1

(fi(x))2 .

Note that f(x)

0 for each x 2 Rn and f(x) = 0 if and only if fi(x) = 0 for each

i = 1,...,m. Therefore, in order to compute a zero of F : Rn ! Rm, we can try to solve

the following unconstrained optimization problem:

(2) min x2Rn (1/2)f(x),

where f is given by (1). The factor (1/2) is used to simplify the expressions for the gradient

and the Hessian matrix.

The gradient of f is given by

rf(x) = J(x)

TF(x), 1

and the Hessian of f is given by

r2

f(x) = J(x)

T J(x) +Xm

i=1

fi(x)r2

fi(x).

(1) (C#) The table below presents the population of the UK (in millions) between 1955

and 2015:

Year Period (t) Population (yt)

Suppose that you would like to establish a relation between t (period number) and

yt (population in millions). Below are three proposed relations:

(i) yt = x1ex2t

(ii) yt = x1

1 + x2ex3t

(iii) yt = x1 + x2t + x3t

2 + x4t

3

Using the given data, you need to find the best possible parameters (x1, x2 for model

(i); x1, x2, x3 for model (ii); x1, x2, x3, x4 for model (iii)). For each of the three models,

define appropriate functions and implement the suggested approach in C#.

(2) (On paper) Give a brief discussion of your solution approach and your choices of

initial solutions you used in the Newton’s method. Among the three proposed models,

discuss which one would be a better choice in terms of explaining the relation between

t and yt. In your discussion, pay attention to the behaviour of the proposed model

for large values of t. Justify your answer.

Clustering

Task 3.2. Given a collection of objects, clustering is concerned with organising objects in

a group in such a way that objects in the same group are “similar” to one another. Suppose

that we have n objects labelled 1, 2,...,n and dij denotes the distance between object i and

object j, where i = 1,...,n; j = 1,...,n. Then D = (dij ) 2 Rn⇥n is the distance matrix

of interest. Clearly, dii = 0 for each i = 1,...,n and the similarity between objects i and j

decreases as dij increases.

(1) (C#) Consider data points in Rd. Write a C# code for computing the following

distance measures that will map every pair of locations i, j 2 V observations, where

2

V = {1,...,n}, to a single distance measure. The output should be the n⇥n distance

matrix:

• Euclidean distance:

• Manhattan distance:

• Mahalanobis distance:

where S 2 Rd⇥d is the sample covariance matrix of the full dataset given by

is the sample mean and xi = [x1i, x2i, ..., xdi]

T 2 Rd denotes the coordinates of

point i, i = 1,...,n.

(2) (C#) Implement the following clustering algorithms:

• Greedy approach: Place every data point in a separate cluster. Then place

the two clusters with minimum distance in a new cluster. Calculate the mean

location of the new cluster. Find the two clusters with the minimum distance

between them and merge them again. Repeat until all data points are in one

cluster. Based on this approach you can prune the obtained clustering scheme on

di↵erent levels. Figure 1 illustrates a representation of a clustering realisation for

a dataset with 5 data points. Based on it, we can infer that the best clustering

consisting of 3 clusters, for example, is (A),(B),(C, D, E).

• Fixed number of clusters approach: For a prespecified number of clusters k,

pick randomly k points of the dataset as cluster centres. Assign each of the

remaining n

k points to the nearest cluster centre. Repeat until convergence

the following two steps. Firstly, calculate the new cluster centres for each cluster

by computing their mean. Then, remove all labels and re-assign each point to

the nearest cluster centre. Test all of the introduced methods on the two datasets

provided.

(3) (C#) Apply the two clustering methods for all distance measures across the two

datasets. The data is in files cluster2.csv and cluster4.csv. The first column in each

dataset is the index of the entry. The first dataset is two-dimensional while the latter

one is four-dimensional.

3

Figure 1. Clustering realisation

(4) (On paper) Report your findings. Allocate the appropriate number of clusters for

each dataset. Discuss the results for the proposed distance measures. Visualise your

findings with appropriate plots.

Large-Scale TSP

Task 3.3. Recall the TSP problem: We are given a set of n cities V = {1,...,n} and

pairwise distances dij for each i 2 V and j 2 V . We would like to compute a tour that visits

each city exactly once and returns to the starting city.

TSP is a hard problem to be solved to optimality. Therefore, heuristic approaches are

used to obtain good solutions. However, if the number of cities n is large, then even the

heuristic approaches can be computationally very expensive. One way to tackle a large-scale

TSP problem is as follows: Cluster the set of cities to form groups with smaller number of

cities. Solve the TSP problem in each cluster separately using a heuristic approach. Finally,

merge the resulting TSP tours to obtain a good TSP tour for the original TSP problem.

(1) (On paper) Consider a TSP instance with n cities in which (x1, y1),(x2, y2),...,(xn, yn)

denote the coordinates of the n cities. Describe a heuristic approach based on clustering,

computing a TSP tour for each cluster, and merging the resulting TSP tours

to obtain a TSP tour for the original TSP problem. Describe your procedures clearly,

specify the inputs and outputs, and remember to justify your procedures.

(2) (C#) Implement the procedure in part (1) and test your code on the two TSP instances

provided (tsp1.csv and tsp2.csv). They both consist of 200 datapoints in two

dimensions.

4

(3) (On paper) Give a brief discussion of your results for di↵erent inputs (i.e., number

of clusters, choice of the TSP heuristic, etc.) and compare your solutions with the

solution from the nearest neighbour heuristic on the original instance.

5

INSTRUCTIONS

Written Report. Your report should be typeset (preferably in LATEX). It should consist

of the following parts:

(1) A cover page with the names of the group members.

(2) A main body that includes the solutions of the written parts of each task.

(3) An appendix that includes your C# codes, figures, tables, plots, references, etc.

For each task, your report should include:

(1) A short section explaining how your code is structured and why it is done so. You

should explain how you avoid code duplication, how you ensure flexibility, etc.

(2) The choices of the parameters used in your experiments along with their justifications.

You may consider including tables and figures in the appendix.

(3) A discussion and interpretation of your results.

(4) Any other information related to your solution.

Your report should fulfill the following requirements:

(1) The main body should consist of a maximum of 5 pages with at least 10pt font and

at least 2 cm margins on each of the four sides.

(2) The appendix does not count towards the page limit. However, the appendix should

only contain the C# codes and any other supplementary material supporting the

content of the main body (e.g., tables, figures, plots, references, etc.). We expect you

to provide a single program with multiple classes and methods. Everything should

run from a single sln file in less than 5 minutes.

Steps.

(1) Check the list of the groups on Learn. (2 students per group)

(2) Download the data files on Learn (for Tasks 3.2 and 3.3).

(3) For submission, go to the Learn page and submit the assignment. There are two

parts to be submitted:

• The report in PDF format.

• A zip file that contains all of your C# codes, including all files required for your

code execution (e.g. tsp1.csv, libraries, code bases).

Deadline. The deadline is Friday, 29th of November at noon. Late submissions will follow

standard university policy. The project is considered submitted only once all two parts have

been submitted.