<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\documentclass[11pt,onecolumn]{article}
\usepackage{amssymb, amsmath, amsthm,graphicx, paralist,algpseudocode,algorithm,cancel,url,color}
\usepackage{sectsty}
\usepackage{fancyvrb}
\usepackage{mathrsfs}
\usepackage{multirow}
\usepackage{hhline}
\usepackage{booktabs}
\usepackage[table]{xcolor}
\usepackage{tikz}
\usepackage{listings}
\usepackage{enumitem}

\newcommand{\bvec}[1]{\mathbf{#1}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\calO}{\mathcal{O}}
\DeclareMathOperator{\Tr}{Tr}
\DeclareMathOperator{\argmin}{argmin}
\DeclareMathOperator{\trace}{trace}
\DeclareMathOperator{\diag}{diag}
\sectionfont{\Large\sc}
\subsectionfont{\sc}
\usepackage[margin=1 in]{geometry}
\begin{document}
\noindent
\textsc{\Large CS 4220 / MATH 4260: Project 2}\\
Instructor: Anil Damle\\
Due: April 27, 2018\\

\subsection*{Policies}
For this project, each individual will be turning in their own write up and code. However, you may work in groups of up to three on the project, this includes helping each other write and debug code, and reading and editing each others reports. This is a bit beyond the level of collaboration allowed on the HW. Within a group you can look at ``solutions'' and discuss them in detail. However, you cannot simply copy each others. Furthermore, please list your collaborators (if any) in your project report. Part of the purpose of this project is to provide you with an opportunity to practice writing more free form reports and carefully choosing what plots, results, etc. are needed to convince us your solution is correct. Therefore, some of the goals are leading, but do not give a concrete list of exactly what has to be included. Please submit your code along with the report via CMS.\\
\hrule


\subsection*{Preamble}

For this project we are going to consider solving a simplified configuration problem. More specifically, we are going to look for minimal energy configurations of non-bonded atoms in three dimensional space using a simple model for atomic interactions. Practically, a molecular configuration problem contains many more components then we will omit for simplicity. If you are curious, I would encourage you to look further into this problem and I would be happy to point you to resources.

\subsection*{A simple model}

For the purpose of this problem, we are going to consider $N$ atoms in three dimensional Euclidean space and try to find energy minimizing configurations. A common model for the interaction of neutral atoms is the so-called Lennard-Jones potential. Specifically, given two atomic locations $x_i$ and $x_j$ in $\mathbb{R}^3$ we define $r_{ij} = \|x_i-x_j\|_2$ and the potential between atoms as 
\[
V_{ij} = \frac{1}{r^{12}} - \frac{2}{r^6}.
\]
Note that more generally there are several parameters in this model that define the optimal distance between two atoms, and the optimal energy. Here, since we are using this as a model problem we have simply set those coefficients for you.

Now, given $N$ atoms defined by their locations $\{x_i\}_{i=1}^N$the problem we wish to solve is 
\[
\min_{x_1,\ldots,x_N} \sum_{i&lt;j} V_{ij}.
\]
However, since $V_{ij}$ is invariant if we translate $x_i$ and $x_j$ by the same vector it makes sense to fix the location of one of the atoms to $(0, 0, 0)^T.$ Therefore, we assume $x_1 = (0, 0, 0)^T$ and seek to find local minima (ideally the global minima) of
\begin{equation}
\min_{x_2,\ldots,x_N} \sum_{i=1}^{N-1}\sum_{j=i+1}^{N} V_{ij},
\label{eqn:1}
\end{equation}
where $V_{1j}$ represents the interactions with the fixed atom at position $x_1.$ This is now an optimization problem in $3(N-1)$ variables.

\subsection*{For this project}
There are two concrete tasks for this project and one open ended one. In particular, you must implement two methods for solving~\eqref{eqn:1}. One should be gradient descent and the other can be either Newton's method or a Quasi-Newton method. Your implementations need to include a line search using sensible conditions and sensible convergence criteria. Clearly describe what you have implemented in your writeup. Using these implementations you should complete the following tasks. 

\begin{itemize}
\item For 2 and 3 atoms find what the globally optimal configurations using your implementations (discuss/illustrate what the configurations are). Argue why you believe you have found a global optima.
\item Illustrate the convergence rates both your algorithms achieve for 3 atoms when finding the aforementioned minimum. Do they match what you expect?
\item Explore computing configurations with more than 3 atoms and see what you can find and how well your implementations perform. Discuss your findings, what you observe about this problem, and where some of the difficulties arise. (This is deliberately open ended, tell us what you learn in your exploration.)
\end{itemize}


While these are itemized, your writeup should be structured as a report with narrative flow through what you have done for the project while addressing the tasks along the way. A portion of your grade will come from the quality of the writeup and how you effectively convey your arguments and answer the above questions.




\end{document}
</pre></body></html>