A new algorithm for the optimization of 3-dimensional radiotherapy plans is presented. The RONSC algorithm (Random Optimization with Non-linear Score functions and Constraints) is based on the idea of random search in the space of feasible solutions. RONSC takes advantage of some specific properties of the dose distribution and derivable information such as dose-volume histograms and calculated estimates of tumor control and normal tissue complication probabilities. The performance of the algorithm for clinical and test cases is discussed and compared with the performance of the simulated annealing algorithm, which is also based on the idea of random search.