Applications of simulated annealing to the optimization of radiation treatment plans, in which a set of beam weights are iteratively adjusted so as to minimize a cost function, have been motivated by its potential for finding the global or near‐global minimum among multiple minima. However, the method has been found to be slow, requiring several tens of thousands of iterations to optimize 50 to 100 variables. A technique to improve the efficiency for finding a solution is reported, which is generally applicable to the optimization of continuous variables. In previous applications of simulated annealing to treatment planning optimization, only one or two weights are varied each iteration. This approach is to change all weights simultaneously, using random changes that are initially large to coarsely sample the cost function, then are reduced with iteration to probe finer structure. The performance of different methods are compared in optimizing a plan for treatment of the prostate, in which the search space consists of 54 noncoplanar beams and the cost function is based on tumor control and normal tissue complication probabilities. The proposed method yields solutions with similar values of the cost function in only a fraction of the iterations compared either to a fixed single weight adjustment technique, or to a method which combines the Nelder and Mead downhill simplex with simulated annealing.