This paper describes Newton and quasi-Newton optimization algorithms for dynamics-based robot movement generation. The robots that we consider are modeled as rigid multibody systems containing multiple closed loops, active and passive joints, and redundant actuators and sensors. While one can, in principle, always derive in analytic form the equations of motion for such systems, the ensuing complexity, both numeric and symbolic, of the equations makes classical optimization-based movement- generation schemes impractical for all but the simplest of systems. In particular, numerically approximating the gradient and Hessian often leads to ill-conditioning and poor convergence behavior. We show in this paper that, by extending (to the general class of systems described above) a Lie theoretic formulation of the equations of motion originally developed for serial chains, it is possible to recursively evaluate the dynamic equations, the analytic gradient, and even the Hessian for a number of physically plausible objective functions. We show through several case studies that, with exact gradient and Hessian information, descent-based optimization methods can be forged into an effective and reliable tool for generating physically natural robot movements.