Semi-Definite Relaxation (SDR) techniques for AC optimal power flow (OPF) have recently been proposed as a means of obtaining a provably global optimal solution for many IEEE benchmark power systems. Solving the resulting semi-definite programs (SDP) can, however, be computationally intensive. Therefore new algorithms and techniques that enable more efficient computations are needed to extend the applicability of SDP based AC OPF algorithms to very large power networks. This paper proposes a three-stage algorithm for AC OPF based storage placement in large power systems. The first step involves network reduction whereby a small equivalent system that approximates the original power network is obtained. The AC OPF problem for this equivalent system is then solved by applying an SDR to the non-convex problem. Finally, the results from the reduced system are transferred to the original system using a set of repeating optimizations. The efficacy of the algorithm is tested through case studies using two IEEE benchmark systems and comparing the solutions obtained to those of DC OPF based storage allocation. The simulation results demonstrate that the proposed algorithm produces more accurate results than the DC OPF based algorithm.