In a typical video rate allocation problem, the objective is to optimally distribute a source rate budget among a set of (in)dependently coded data units to minimize the total distortion. Conventional Lagrangian approaches convert the lone rate constraint to a linear rate penalty scaled by a multiplier in the objective, resulting in a simpler unconstrained formulation. However, the search for the "optimal" multiplier - one that results in a distortion minimizing solution among all Lagrangian solutions that satisfy the original rate constraint - remains an elusive open problem in the general setting. To address this problem, we are the first in the literature to construct a computation-efficient search strategy to identify this optimal multiplier numerically in the general dependent coding scenario. Specifically, we first formulate a general rate allocation problem where each data unit can be dependently coded at different quantization parameters (QP) using a previous unit as predictor, or left uncoded at the encoder and subsequently interpolated at the decoder using neighboring coded units. After converting the original rate-constrained problem to the unconstrained Lagranglan counterpart, we design an efficient dynamic programming (DP) algorithm that finds the optimal Lagrangian solution for a fixed multiplier. In extensive monoview and multiview video coding experiments, we show that for fixed target rate constraints, our algorithm Is able to find the optimal multipliers in a distortion minimum sense among all Lagrangian solutions. Moreover, we show that our simple solution is able to compete with complex rate control (RC) solutions used in video compression standards such as HSVC and 3D-HEVC, which outlines the importance of the proper choice of the Lagrangian multipliers.