Approaches like infinitesimal perturbation analysis and the likelihood ratio method have drawn a great deal of attention recently, as ways of estimating the gradient of a performance measure with respect to continuous parameters in a dynamic stochastic system. In this paper, we experiment with the use of these estimators in stochastic approximation algorithms, to perform so-called "single-run optimizations" of steady-state systems. We also compare them to finite-difference estimators, with and without common random numbers. Under mild conditions, for an objective function that involves the mean system time in a GI/G/1 queue, we prove that many variants of these algorithms converge to the minimizer. In most cases, however, the simulation length must be increased from iteration to iteration; otherwise the algorithm may converge to the wrong value. One exception is a particular implementation of infinitesimal perturbation analysis, for which the single-run optimization converges to the optimum even with a fixed (and small) number of ends of service per iteration. We have performed extensive numerical experiments with a simple M/M/1 queue, which illustrate the basic convergence properties and possible pitfalls of the various techniques. Our convergence proofs are quite involved. As a by-product, we obtain new structural results for the GI/G/1 queue that could be of independent interest.