In this paper, we investigate the problem of power optimization in CMOS circuits using gate sizing and voltage selection for a given clock period specification. Several solutions have been proposed for power optimization during gate sizing and voltage selection. Since the problem formulation is nonlinear in nature, nonlinear programming (NLP) based solutions will yield better accuracy, however, convergence is difficult for large circuits. On the other hand, heuristic solutions will result in faster but less accurate solutions. In this work, we propose a new algorithm for gate sizing and voltage selection based on NLP for power optimization. The algorithm uses gate level heuristics for delay assignment which disassociates the delays of all the paths to the individual gate level, and each gate is then separately optimized for power with its delay constraint. Since the optimization is done at the individual gate level, NLP converges quickly while maintaining accuracy. Experimental results are presented for ISCAS benchmarks which clearly illustrate the efficacy of the proposed solution.