Problem 1  (the secant condition).   Prove that the secant condition holds for the following two formulas:

1. Bk+1  = Bk +  , assuming v ⊤ sk   0.

2. The BFGS update.

Problem 2 (Lennard-Jones potential).   The Lennard-Jones potential is:

V (r) = 4ϵ [ (   ) 12  − (   ) 6] .                                                          (1)

The force due to this potential is just F (r) = −dV/dr . If you plot F (or do an image search), you will see that there is net zero force if r = σ, a very strong repelling force for r  < σ, and a very weak attractive force if r > σ . In this problem, we will explore doing a simple molecular dynamics simulation in 2D using the Lennard-Jones potential.  Consider a set of m particles in Rm  with positions given by (xi, yi), i = 1, . . . , m.  Let rij   be the distance between particles i and j .  The total potential energy for this system of particles is:

m

f(x1 , y1 , . . . , xm, ym) =   V (rij)

Do the following:

1. Set σ = ϵ = 1, and develop an algorithm for minimizing f using gradient, descent, SR1, or BFGS—it is your choice which method to use.

2. Apply this algorithm to systems with m = 3, 4, . . . 10 particles and visualize your results:

• Make sure to initialize randomly, and note that if your particles are too far apart initially, it will take a while to reach a local minimum because of the weak attractive force. On the other hand, because of the strong repelling forces, it is important to use a backtracking line search.

• Plot your local minimizers by using a scatter plot for the positions of (xi, yi). Addition- ally, draw a circle of radius σ = 1 surrounding each particle.  It may also help to plot each dot/circle pair using a different color.

• There are numerous local minimizers for this system. See how many you can find.

Problem 3 (Fermat’s principle).   Consider a particle traveling with speed c(x, y) meters per second. If we assume that the particle travels between two points r0  and r 1  following the minimum travel time trajectory r(t), where r(0) = r0  and r(1) = r 1 , then r : [0, 1] → R2  can be found by minimizing:

minimize       F [r] =  dt.                                                    (3)

This is a minimization problem where the variable being minimized over is a function instead of a vector. One approach to solving this problem is to use the calculus of variations, which is outside the scope of this class. Another approach is to approximate the integral in (3) using a quadrature rule and then solve the resulting finite-dimensional minimization problem.

Consider solving this problem for (x, y) ∈ R2, where the particle speed is:

c(x, y) = 1 +^4 − 3x − y .

One simple but useful quadrature rule is the composite trapezoid:

 f (t)dt =  ∆ti + O (1m(x) ∆ti(2)) ,

(4)

(5)

where a = t0  < t1  < · · · < tm  = b, and where ∆ti  = ti  − ti−1  > 0. Note: it may be helpful for you to determine where c is defined.

Proceed in the following steps:

1. Use the composite trapezoid rule to approximate the integral in (3) for an arbitrary number of points (i.e., m + 1 points, as above).  To keep things simple, use uniform spacing—i.e., choose the ti’s such that ∆ti  = h for all i, and let (xi, yi) = r(ti) for each i. Denote your cost function by f (x0 , y0 , . . . , xm, ym)  and write down the new finite-dimensional minimization problem to solve. Compute the gradient ∇f (x0 , y0 , . . . , xm, ym).

2. Let  (x0 , y0 )  =  (0, 0)  and  (xm, ym)  =  (1, 1).   Solve your minimization problem for m  = 5, 10, 20, 40, 80, 160 using gradient descent, SR1, and BFGS. Note that iteration k is a vector:

(xk), y , x) , y)).

(6)