In the past, pressure dependent models (PDM) have suered from convergence diculties. In this paper conditions are established for the existence and uniqueness of solutions to the PDM problem posed as two optimization problems, one based on weighted least squares (WLS) and the other based on the co-content function. A damping scheme based on Goldstein's algorithm is used and has been found to be both reliable and robust. A critical contribution of this paper is that the Goldstein theorem conditions guarantee convergence of our new method. The new methods have been applied to a set of eight challenging case study networks, the largest of which has nearly 20,000 pipes and 18,000 nodes, and are shown to have convergence behaviour that mirrors that of the Global Gradient Algorithm on demand dependent model problems. A line search scheme based on the WLS optimization problem is proposed as the preferred option because of its smaller computational cost. Additionally, various consumption functions, including the Regularized Wagner function, are considered and four starting value schemes for the heads are proposed and compared. The wide range of challenging case study problems which the new methods quickly solve suggests that the methods proposed in this paper are likely to be suitable for a wide range of PDM problems.