s9_hobbit_village

Below one can find function plotting the village

def plot_village(coordinates, l=1):
    # Checking, that all the coordinates are less than l
    assert (coordinates <= l).all(), 'All the houses should be in a village'

    # Draw horizontal line
    plt.hlines(0, 0, l)
    plt.xlim(0, l)
    plt.ylim(-0.5, 0.5)

    # Draw house points
    y = np.zeros(np.shape(coordinates))
    plt.title('The Hobbit Village')
    plt.plot(coordinates,y,'o',ms = 10)
    plt.axis('off')
    plt.xlabel('Coordinates')
    fig = plt.gcf()
    fig.set_size_inches(15, 1)
    plt.show()

The inhabitants of a one-dimensional village want to connect to the Internet, so they need a central service station from which a cable will stretch to all the houses in the village. Let the price of the cable to be pulled from the station to each house independently be determined by some function p(d) . Then it is clear that the village will have to pay the following amount for access to the World Wide Web: P(w, x) = \sum\limits_{i=1}^N p(d_i) = \sum\limits_{i=1}^N p(|w - x_i|) w - station location, x_i - location of i house.

Write analytical solution w^* for minimization P(w,x), if p(d) = d^2

==YOUR ANSWER==

Write loss function P(x,w)

Plot loss function on the range (0, l)

Write gradient of loss function

Plot gradient of loss function on the range (0,l). Which point on the graph is of particular interest? Why?

Write function gradient_descent, which returns w_k after a fixed number of steps.

w_{k+1} = w_k - \mu \nabla P(w_k)

Modify gradient_descent to return all optimization trajectory. Plot loss function trajectory for the following learning rates \mu = 0.01, 0.1, 0.15, 0.19, 0.20, 0.21.
Draw conclusions.

Accelerate the process: use HB method and NAG Plot loss function trajectory for \mu = 0.01 and different values of momentum parameters. Draw conclusions.

Hint: use optimal parameters for step size and momentum from lecture

### YOUR CODE HERE