A steepest descent based bit allocation method with polynomial iteration complexity for minimizing the sum of frame distortions under a total bit rate constraint is presented for a predictive video coder. Previous algorithms that solve this problem have been based on Lagrangian Relaxation followed by unconstrained optimization. Some of these methods have complexity exponential in the prediction depth in the worst case. Moreover, the convergence properties of the faster methods are difficult to analyze. A steepest descent method is utilized here for its comparatively low computational complexity, excellent performance and ease of analysis. Sufficient conditions for global optimality are presented without assuming independent encoding of frames. Results for dependent bit allocation through the assignment of quantizer step-sizes to frames in MPEG-2 encoded sequences suggest that these optimality conditions are to a large extent satisfied in practice. A PSNR improvement of up to 1.5 dB is obtained over the standard TM5 rate control algorithm for MPEG-2.