Managing an asset in the presence of exogenous information that evolves over time can be a challenging task, especially if the information is a multi-dimensional stochastic process. Nevertheless, several of these problems have structural properties that can and should be exploited when developing a strategy to solve them. We focus on a class of such problems, namely complex storage problems, for which the optimal value function is a family of piecewise linear concave functions. We propose an approximate dynamic programming algorithm to handle these problems. The idea is to construct, iteratively, piecewise linear and concave value function approximations. The algorithm is a combination of Monte-Carlo simulation and stochastic approximation. It employs a pure exploitation scheme, where the states we visit depend on the decisions produced by solving the approximate problem. A projection operation guarantees that the approximations are concave over the iterations. We prove that our algorithm converges to an optimal policy, learning the optimal value functions for important regions of the state space, which is determined by the algorithm itself. It is a rare proof of convergence for a multistage setting where not all states have to be visited infinitely often by the algorithm. The proof relies on the problem class structural property. We proceed to study a practical application that fits into our framework: the mutual fund cash holding problem. We show that our solution closely matches the optimal one (in considerably less time), and outperform two static models. It is a simple policy that describes when money should be moved into and out of cash based on market performance. Next, we consider a subclass of storage problems called lagged acquisition, where assets are purchased over time to satisfy a random demand in the future. We provide an specialized proof and compare the rate of convergence of our algorithm to other approximation methods. Finally, we take on jet fuel hedging, proposing a novel trading strategy, which is optimal with respect to a utility that considers risk, return and prospective hedging effectiveness. We show for certain risk aversion levels that our approach dominates well established policies.