With $L(u) = \sum (x - u)^2$, the problem to be solved is
minimizing $L$ over all $u$ satisfying the ultrametric
constraints (i.e., for all $i, j, k$, $u_{ij} \le \max(u_{ik},
u_{jk})$). This problem is known to be NP hard (Krivanek and
Moravek, 1986). We follow de Soete (1986) to use a heuristic based on an SUMT
(Sequential Unconstrained Minimization Technique) approach in turn
simplifying the suggestions in Carroll and Pruzansky (1980). One
iteratively minimizes $L(u) + \rho_k P(u)$, where $P(u)$ is a
non-negative function penalizing violations of the ultrametric
constraints such that $P(u)$ is zero iff $u$ is an
ultrametric. The $\rho$ values are increased according to the
rule $\rho_{k+1} = q \rho_k$ for some constant $q > 1$, until
convergence is obtained in the sense that the euclidean distance
between successive solutions $u_k$ and $u_{k+1}$ is small
enough. We then use a final rounding step to ensure that the returned
object exactly satisfies the ultrametric constraints. The starting
value $u_0$ is obtained by random shaking of the given
dissimilarity object.
The unconstrained minimizations are carried out using either
optim or nlm, using the
analytic gradients given in Carroll and Pruzansky (1980). The
following control parameters can be provided via the control
argument.
[object Object],[object Object],[object Object],[object Object],[object Object]
The default optimization using conjugate gradients should work
reasonably well for medium to large size problems. For small
ones, using nlm is usually faster. Note that the number of
ultrametric constraints is of the order $n^3$, where $n$ is
the number of objects in the dissimilarity object, suggesting to use
the SUMT approach in favor of constrOptim.
It should be noted that the SUMT approach is a heuristic which can not
be guaranteed to find the global minimum. Standard practice would
recommend to use the best solution found in sufficiently many
replications of the base algorithm.