Gradient-based optimization may not be suited if the objective and constraint functions in a nonlinear model predictive control (NMPC) optimization problem are not differentiable. Some well-known derivative-free optimization (DFO)-algorithms are investigated, and a novel warm-start modification to the Wedge DFO-algorithm is proposed. Together with a gradient-based SQP-algorithm these are applied to the NMPC problem and compared in a single-shooting NMPC formulation to a subsea oil-gas separation process. The findings are that DFO is significantly more robust against the numerical issues, compared to a gradient-based SQP tested. Moreover, the warm-start modification reduces the computational complexity. (C) 2014 Elsevier Ltd. All rights reserved.