Homework 8

1. This problem is an example of optimizing a non-convex function. (So far we have used

optimization to fit data. This problem shows the use of optimization in a different context.

In future classes we will see examples of non-convex optimization applied to data.) Consider

a model of m molecules. We will assume that each molecule lives in 2-dimensional space.

(Actual applications put the molecules in 3-dimensional space, but the optimizations are

not different and 2-dimensions will allow us to visualize the molecular configuration.) Let

molecule j have position pj = (xj , yj ). Let rij be the distance between molecules i and j,

that is rij = kpi i pjk. Set,

(U(r) is the Lennard-Jones model of the energy produced by Van der Waals forces between

neutral molecules, see https://en.wikipedia.org/wiki/Lennard-Jones_potential)

Our goal is to find the molecular configuration that minimizes the energy.

(a) The energy function above is invariant to shifts and rotations of the molecules and so

there is no unique minimum. The following modification of the energy function makes

the minimum unique. Explain what the modification does.

Above, p1 = (x1, y1) is the position of the first molecule. y2 is the y coordinate of the

second molecule.

(b) Consider first only two particles, p1 and p2. Let r12 = kp1 1 p2k. Then U(r12) is a

for two molecules at positions p1 = (x1, y1) and p2 = (x2, y2) respectively. The variable

p passed to the two functions should be p = (x1, y1, x2, y2). (The gradient should be 4-d

and the Hessian 4 × 4.)

(d) Now write functions gradE(p) and HE(p) which return the gradient and the Hessian

of the energy function from part (a). The variable p should be a 2m dimensional vector:

p = (x1, y1, x2, y2, . . . , xm, ym) (6)

In this case the gradient will be 2m dimensional and the Hessian will be 2m × 2m. Here

is some pseudo code to get you started:

# returns a vector giving the coordinates in the vector

# p=(x_1, y_1, x_2, y_2, ..., x_m, y_m) where the

# coordinates (x_i, y_i, x_j, y_j) occur

(e) To check your code from (c), notice that the solution that minimizes the energy for 2 and

3 molecules can be determined analytically. (Hint: find the distance r that minimizes

U(r)). Use those configurations to check your code. What should the gradient be at

those points? What property should the Hessian have at those points?

(f) Show in any way you like that the energy function is not convex or concave.

(g) Use Newton’s method with Hessian modification to find the minimum energy configuration with m = 3 molecules. Note, as mentioned above, you know the answer in this case,

but start your iteration at a different configuration. Plot the three points in their optimal configuration. (As a check of your optimization, check that your energy descends