next up previous contents

Subsections


2 Distribution of Electrons on a Sphere

Given $n_p$ electrons, find the equilibrium state distribution (of minimal Coulomb potential) of the electrons positioned on a conducting sphere.

Formulation

This problem, known as the Thomson problem of finding the lowest energy configuration of $n_p$ point charges on a conducting sphere, originated with Thomson's plum pudding model of the atomic nucleus. This problem is representative of an important class of problems in physics and chemistry that determine a structure with respect to atomic positions.

The potential energy for $n_p$ points $ ( x_i,y_i,z_i)$ is defined by

\begin{displaymath}f(x,y,z) = \sum_{i=1}^{n_p-1}\sum_{j=i+1}^{n_p} \left((x_i-x_...
...(y_i-y_j)^2+(z_i-z_j)^2 \right)^{-{\textstyle{\frac{1}{2}}}} ,
\end{displaymath}

and the constraints on the $n_p$ points are

\begin{displaymath}
x_i^2+y_i^2+z_i^2 = 1, \qquad i = 1, \ldots, n_p.\end{displaymath}

Data for this problem appears in Table 2.1.

This problem has many local minima at which the objective value is relatively close to the objective value at the global minimum. Experimental and theoretical results [18,20] show that

\begin{displaymath}\min \left \{ f ( v_1, \ldots , v_{n_p} ) :
\Vert v_i \Vert =...
...
0 \le \varepsilon \le \left ( \frac{1}{n_p} \right ) ^{1/2} .\end{displaymath}

Also, the number of local minima grows exponentially with $n_p$. Thus, determining the global minimum is computationally difficult, and solvers are usually expected to find only a local minimum.



Table 2.1: Electrons on a sphere problem data
Variables $ 3 n_p$
Constraints $n_p$
Bounds 0
Linear equality constraints 0
Linear inequality constraints 0
Nonlinear equality constraints $ n_p $
Nonlinear inequality constraints 0
Nonzeros in $ \nabla ^2 f(x) $ $ 9 n_p^2 $
Nonzeros in $ c'(x) $ $ 3 n_p $

Performance

Results for the AMPL implementation are summarized in Table 2.2. The starting point is a quasi-uniform distribution of the points on a unit sphere. The best solution for $n_p = 100 $ is shown in Figure 2.1.



Table 2.2: Performance on electrons on a sphere problem
Solver $n_p=25$ $n_p=50$ $n_p=100$ $n_p=200$
LANCELOT 3.98 s 8.08 s 53.36 s 371.6 s
$f$ 2.43812e+02 1.05518e+03 4.44841e+03 1.84389e+04
$c$ violation 2.34380e-06 2.58920e-08 2.32410e-07 1.94010e-06
iterations 50 46 67 127
LOQO 0.84 s 7.94 s 179.06 s 2437.78 s
$f$ 2.43812e+02 1.05518e+03 4.44835e+03 1.84389e+04
$c$ violation 2.8e-09 4.9e-09 3.0e-09 1.9e-09
iterations 27 46 130 264
MINOS 6.22 s 36.85 s $\ddagger$ 794.08 s
$f$ 2.43812e+02 1.05518e+03 $\ddagger$ 1.25964e+04$\dagger$
$c$ violation 7.7e-08 1.2e-12 $\ddagger$ 6.6e+09$\dagger$
iterations 45 59 $\ddagger$ 38
SNOPT 9.65 s 10.68 s 73.66 s 1600.48 s
$f$ 2.43812e+02 1.05518e+03 4.44841e+03 1.84390e+04
$c$ violation 2.2e-09 1.8e-10 5.2e-10 9.0e-10
iterations 168 102 146 561
$\dagger$ Errors or warnings. $\ddagger$ Timed out.

MINOS cannot solve the problem for $n_p >
50$. For $n_p = 200$ it gives the error message unbounded (or badly scaled) problem.

Figure 2.1: Optimal distribution of electrons on a sphere, $n_p = 100$
\includegraphics[height=2.5in,clip]{ps/sphere100.ps}


next up previous contents
Liz Dolan
2001-01-02