APPLIED OPTIMIZATION METHODS 2019/20 ASSIGNMENT This is a group assignment to be submitted online to my.wbs by 19 March noon. Please combine all submitted documents (report, matlab code) into a single .zip or .rar file for submission. The report should be typed and have no more than 5 pages. The Matlab files should have plenty of comments to facilitate understanding. Please note that you are also expected to fill in the peer assessment form. Failure to do so will result in a loss of marks. 1. Question 1 The Thompson problem is to determine the stable positions of n classical electrons on the surface of sphere. We can write the generalized Thomson problem as follows (1) min n−1∑ i=1 n∑ j=i+1 1 ||xi − xj || s.t ||xi||2 = 1, i = 1, . . . , n, where xi ∈ Rd for i = 1, . . . , n are decision variables and ||x|| = √√√√ d∑ k=1 x2k for x ∈ Rd. Note that when d = 3, we obtain the original Thompson problem in physics. This problem is an instance of the general equality constrained optimisation problem (2) min x∈Rn¯ f(x) s.t. hi(x) = 0, i = 1, . . . , m¯. For the generalized Thompson problem, there are n¯ = n·d decision variables and m¯ = n constraints. In order to solve the general equality constrained optimisation problem, we can apply the sequential quadratic programming (SQP) algorithm, which is described as follows: Step 1. Choose an initial point x(0), multipliers u(0), a tolerance > 0, and set k = 0. Step 2. Compute the direction dk and the next multipliers u (k+1) as the optimal solution and the multipliers, respectively, of the following quadratic optimisation problem (3) min ∇f(x(k))Td+ 1 2 dT ( Hf (x (k)) + m∑ i=1 u (k) i Hhi(x (k)) ) d s.t. hi(x (k)) +∇hi(x(k))Td = 0, i = 1, . . . ,m. Step 3. Update x(k+1) = x(k) + dk. Step 4. If ||dk|| ≤ , stop. Otherwise, set k ← k + 1 and go to Step 2. For this question, consider the following tasks. 1. Derive the KKT conditions of the quadratic optimisation problem (3) and show that dk and u(k+1) can be obtained by solving a system of linear equations in general. 2. Implement the SQP algorithm in Matlab for the generalized Thompson problem given the dimension d, d ≥ 2, and the number of points n, n ≥ 2. Explain all necessary inputs of the algorithm. 1 2 ASSIGNMENT 3. Solve the Thompson problem with d = 2 and n = 20 using different initial points and multipliers. The tolerance should be set to = 1e−6. Discuss the convergence of the algorithm. Visualise and analyse the solutions. 4. Modify the problem so that the (global) optimal solution can be unique when d = 2. Im- plement the SQP algorithm in Matlab to solve the modified problem. Solve the Thompson problem with d = 3 and n = 10 using different initial points and multipliers. Visualise and analyse the solutions. 2. Question 2 In a chaotic warehouse organisation (used for example by Amazon), the same product may be stored at different locations. This means that if an order of n different products needs to be collected from the warehouse, it is possible to select, for each product, the most convenient of the storage locations. Given a set of n products to be collected, and all the storage locations for each product, the optimisation problem is then to identify the shortest tour from the depot to one of the storage locations of every product and then back to the depot. For simplicity, let us assume that storage locations are specified as (x, y) coordinates on a plane, and distances between storage locations are simply Euclidean distances. For this question, consider the following tasks. 1. Write a Matlab programme that reads in a matrix of product locations from a file, and plots the location of all products on the plane. For simplicity, we assume there are n = 20 products and each product is stored at exactly m = 5 locations. Each row of the file contains all the (x, y) coordinates for one product (i.e., x1y1x2y2 . . . xmym). An example file can be downloaded from my.wbs (WarehouseExample.txt). The depot is always located at (0, 50), and the warehouse has dimension 100× 100. 2. Develop a simple construction heuristic for this problem in Matlab. Describe the heuristic, motivate your design choices, and report the solution found. 3. Modify the programme from 1.) such that it displays the found solution graphically. 4. Run the algorithm again assuming that each product is stored in only one location (the first location of the file). How much shorter is the tour to collect the products when each product is stored in multiple locations? 4. Develop an evolutionary algorithm to solve the problem. Think about representation, crossover, and mutation. Be creative, there is no single correct solution. Describe the algorithm, motivate your design choices, and report the solution found.
