In production optimization, we seek to determine the well settings (bottomhole pressures, flow rates) that maximize an objective function such as net present value. In this paper we introduce and apply a new approximate dynamic programming (ADP) algorithm for this optimization problem. ADP aims to approximate the global optimum using limited computational resources via a systematic set of procedures that approximate exact dynamic programming algorithms. The method is able to satisfy general constraints such as maximum watercut and maximum liquid production rate in addition to bound constraints. ADP has been used in many application areas, but it does not appear to have been implemented previously for production optimization. The ADP algorithm is applied to two-dimensional problems involving primary production and water injection. We demonstrate that the algorithm is able to provide clear improvement in the objective function compared to baseline strategies. It is also observed that, in cases where the global optimum is known (or surmised), ADP provides a result within 1-2% of the global optimum. Thus the ADP procedure may be appropriate for practical production optimization problems.