A new gradient estimation method is proposed that relies on efficient computation of the negative gradient of the average linear quadratic cost function completely in the frequency domain. Based on the proposed theory, a new iterative tuning method is developed to solve linear multi-input multi-output Active Noise/Vibration Control problems. Compared with published iterative tuning methods, the new method has the added advantage that the number of experiments per iteration is reduced to one. Combined with the other advantage of relatively simple controller structures, the method is suitable for realtime implementation as an adaptive controller. (C) 2010 Elsevier Ltd. All rights reserved.