In this paper, we present a novel multigrid-based technique for on-chip power supply network optimization. We reduce a large-scale network to a much coarser one which can be efficiently optimized. The solution for the original network is then quickly computed using a back-mapping process. We model the power grid by an RLC network and use time-varying current sources to capture the on-chip switching. Our technique is capable of optimizing power grid and decoupling capacitance simultaneously. Experimental results show that the proposed technique provides more robust and area-efficient solutions than those obtained by the earlier approaches. It also provides a significant speed-up and brings up a possibility of incorporating power supply network optimization into other physical design stages such as signal routing.