This article presents a new algorithm to optimize the multivariate optimal allocation problem. Many researchers have studied and proposed new methods for the solution this problem, which can be performed by choosing one of the following goals: (i) minimizing the weighted combination of relative variances, considering the sample size fixed or (ii) minimizing the sample size in a way that the coefficients of variation are lower or equal to the previously fixed coefficients of variation. The proposed algorithm is based on a nonlinear optimization method denoted hyperbolic penalty. Results obtained for real populations show that the algorithm is a good alternative to solve this problem.