Caching is a powerful technique that reduces the peak traffic loading by pre-storing popular contents in caching helpers during off-peak hours. In this work, the problem of probabilistic caching is revisited, in which users are allowed to request multiple contents sequentially. A novel algorithm based on the method of Lagrange multipliers is proposed to produce a policy that guarantees to yield a locally maximal content delivery success probability (CDSP) of the most demanding user, who requests the largest number of consecutive contents. Due to the non-convex nature of the problem, this algorithm may be trapped into an insignificant local maximum. We further propose an enhanced version of the algorithm based on the idea of simulated annealing, which enables the algorithm to statistically escape from a local maximum. Simulation results show that the proposed enhanced algorithm can attain a 45% CDSP improvement over the state-of-the-art when hundreds of contents are involved, and is significantly less sensitive to initial values. Moreover, to increase the overall system throughput, we propose an alternative metric of maximizing the weighted CDSP, instead of considering only the CDSP of the most demanding user. For this new metric, an algorithm adapted from the proposed algorithm is introduced, for which similar conclusions can be drawn.