What's the most efficient way to minimise the following non-linear function?

Question

I have a non-linear functional $Q\!:\!\mathbb{R}^N\!\times\mathbb{R}^N\!\!\to\!\mathbb{R}$ that I want to minimise (or rather, find the local minimum of, within the vicinity of an initial guess). \begin{align*} Q(\boldsymbol{\theta}, \boldsymbol{\phi}) \ =\ \frac{1}{2}\sum_{m=1}^{N}\sum_{n\in \mathcal{N}_{\!m}} (\mathbf{x}_{m,n} - \mathbf{x}_{n,m})\!\cdot\!(\mathbf{x}_{m,n} - \mathbf{x}_{n,m}) \end{align*} where $\boldsymbol{\theta}=[\theta_1\ \theta_2\ ...\ \theta_N]^T$, $\boldsymbol{\phi}=[\phi_1\ \phi_2\ ...\ \phi_N]^T$, $N$ is the total number of vertices of a graph embedded on a surface, and $\mathcal{N}_m$ is the set of global indices ($\textit{i.e.}$ in the range $[1,N]$) of all vertices neighbouring vertex $m$. Further, \begin{align*} \mathbf{x}_{m,n}(\theta_m, \phi_m) = \mathbf{x}_m + r_m\mathbf{u}_{mn}, \end{align*} where $r_m\!\in\mathbb{R}$ and $\ \mathbf{x}_m\!\in\mathbb{R}^3$ are known, and \begin{align*} \mathbf{u}_{mn}(\theta_m, \phi_m) \ =\ \frac{(\mathbf{n}_m\!\times\mathbf{d}_{mn})\times\mathbf{n}_m}{\sqrt{(\mathbf{n}_m\!\times\mathbf{d}_{mn})\!\cdot\!(\mathbf{n}_m\!\times\mathbf{d}_{mn})}}, \end{align*} for known $\mathbf{d}_{mn}\!\in\mathbb{R}^3$, and \begin{align*} \mathbf{n}_m(\theta_m, \phi_m) = \begin{bmatrix} \cos(\theta_m)\sin(\phi_m)\\[0.12cm] \sin(\theta_m)\sin(\phi_m)\\[0.12cm] \cos(\phi_m) \end{bmatrix} \end{align*}

The terms $\mathbf{x}_{n,m}$, $\mathbf{u}_{nm}$, and $\mathbf{n}_n$ are defined in a similar manner, by swapping the indices.

1. Can anyone give me some advice about the most efficient/pragmatic way to solve this problem numerically? Since the whole function is analytic, I can compute both the gradient and the Hessian of $Q$. Therefore is Newton's method the most appropriate for this?

2. Additionally, considering that I have two vectors of unknowns, $\boldsymbol{\theta}$ and $\boldsymbol{\phi}$, do I simply 'stack' $\boldsymbol{\theta}$ on top of $\boldsymbol{\phi}$ and treat it as a $2N$ system of equations with a $2N\!\times\!2N$ Hessian?

Answer 1

This is a highly nonlinear problem so I suggest the use of a convenient solver. Follows a MATHEMATICA script which I hope, models approximately the problem.

n = 3;
m = 3;
SeedRandom[1];
R = RandomReal[{1, 2}, n];
Theta = Table[Subscript[theta, k], {k, 1, n}];
Phi = Table[Subscript[phi, k], {k, 1, n}];
X = RandomReal[{-2, 2}, {n, 3}];
d = RandomReal[{-2, 2}, {n, m, 3}];
vn[theta_, phi_] := {Cos[theta] Sin[phi], Sin[theta] Sin[phi],  Cos[phi]}
u[phi_, theta_, d_] := Cross[Cross[vn[phi, theta], d], vn[phi, theta]]/Sqrt[Cross[vn[phi, theta], d].Cross[vn[phi, theta], d]]
x[i_, j_] := X[[i]] + R[[i]] u[Theta[[i]], Phi[[j]], d[[i, j]]];
Q = Sum[Sum[(x[i, j] - x[j, i]).(x[i, j] - x[j, i]), {j, 1, m}], {i, 1, n}];
vars = Join[Phi, Theta];  
sol = NMinimize[F, vars]

You can choose as well an initial point

inic = {Table[0, n + m]};
sol = NMinimize[Q, vars, Method -> {"Automatic", "InitialPoints" -> inic}]

To calculate the hessian eigenvalues

H = Grad[Grad[Q, vars], vars] /. Last[sol] // Eigenvalues