An efficient optimization procedure combining the frequency approximation technique and the component-mode synthesis method is proposed for the structural dynamic optimization of the large structures subject to prescribed natural frequency constraints. Frequency constraints are approximated by using the first-order sensitivities with respect to both design parameters and their reciprocals. The component-mode synthesis method proposed by the authors in Ref.[8] is used for the repetitive detail finite-element analysis and sensitivity analysis. The validity of the proposed optimization procedure is confirmed through the numerical implementation of some examples. The presented approximation technique requires much smaller number of repetitive analysis than that using the sensitivities with respect to design parameters only, and further improvement in the numerical efficiency is achieved by the adoption of the introduced component-mode synthesis.