Non-linear least squares fitting problem

I am trying to figure out the appropriate technique for a non-linear least
squares fitting problem where the Hessian is rank deficient by one. These are
typically low order, maybe four or five, with a few hundred discrete points.
I've looked on plato.

As an aside, I noticed an interesting article on Optimization Online regarding
the DIRECT algorithm. Is this technique related to multilevel coordinate
search?
.