Subsections

• Formulation
• Performance

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

$$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}}}} ,$$

and the constraints on the $n_p$ points are

$$x_i^2+y_i^2+z_i^2 = 1, \qquad i = 1, \ldots, n_p.$$

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

$$\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} .$$

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$