  It has been shown that a global minimizer of a smooth determinant of a matrix
function corresponds to the largest cycle of a graph. When it exists, this is a
Hamiltonian cycle. Finding global minimizers even of a smooth function is a
challenge. The difficulty is often exacerbated by the existence of many global
minimizers. One may think this would help, but in the case of Hamiltonian
cycles the ratio of the number of global minimizers to the number of local
minimizers is typically astronomically small. There are various equivalent
forms of the problem and here we report on two.
  Although the focus is on finding Hamiltonian cycles, and this has an interest
in and of itself, this is just a proxy for a class of problems that have
discrete variables. The solution of relaxations of these problems is typically
at a degenerate vertex, and in the neighborhood of the solution the Hessian is
indefinite. The form of the Hamiltonian cycle problem we address has the virtue
of being an ideal test problem for algorithms designed for discrete nonlinear
problems in general. It is easy to generate problems of varying size and
varying character, and they have the advantage of being able to determine if a
global solution has been found. A feature of many discrete problems is that
there are many solutions. For example, in the frequency assignment problem any
permutation of a solution is also a solution. A consequence is that a common
characteristic of the relaxed problems is that they have large numbers of
global minimizers and even larger numbers of both local minimizers, and saddle
points whose reduced Hessian has only a single negative eigenvalue. Efficient
algorithms that seek to find global minimizers for this type of problem are
described. Results using BONMIN, a solver for nonlinear problems with
continuous and discrete variables, are also included.
