The squared error loss function for the unidimensional metric scaling problem has a special geometry. It is possible to efficiently find the global minimum for every coordinate conditioned on every other coordinate being held fixed. This approach is generalized to the case in which the coordinates are polynomial functions of exogenous variables. The algorithms shown in the paper are linear in the number of parameters. They always descend and, at convergence, every coefficient of every polynomial is at its global minimum conditioned on every other parameter being held fixed. Convergence is very rapid and Monte Carlo tests show the basic procedure almost always converges to the overall global minimum.