Description

Assignment 4
Total: 40 Points

General Instruction
• Submit uncompressed file(s) in the Dropbox folder via BeachBoard (Not email).

1. (40 points) Solve the n-airports problem using gradient based optimization algorithm.
i. Find n-airports.ipynb. ii. A random initial state is given as Figure 1a.

(a) An initial state (b) An optimal state
Figure 1: n-airports problem state
iii. The objective function is given by
n
f(x1,y1,x2,y2,x3,y3) = XX(xi − xc)2 + (yi − yc)2
i=1 c∈Ci
where n is the number of the airports and Ci is the set of cities whose closest airport is airport i.
iv. The goal of the program is determining the locations of airports that minimize theobjective function using gradient based optimization. By updating
(x1,y1,x2,y2,x3,y3) ← (x1,y1,x2,y2,x3,y3) − α∇f(x1,y1,x2,y2,x3,y3) where 0 1 is a constant, find an optimal location of the airports as Figure 1b.
CECS 451 Assignment 4 – Page 2 of 2

Figure 2: Objective as a function of epoch