In this paper, an algorithm is introduced for feasibility problems associated with frequency-dependent, linear matrix inequalities-these problems correspond to H-2 or H-infinity robust performance tests for a given controller, in the face of feedback perturbations. To this effect, an auxiliary H-2 cost-functional is introduced and a sequence of H-2 problems with a single linear constraint is considered in which the H-2 cost-functional is kept unchanged while the linear constraints are iteratively modified. It is shown that, in each step, the auxiliary optimal solution moves closer (in the sense of a weighted quadratic norm) to the target feasible set. Conditions are also established under which the sequence of solutions to the auxiliary problems yields a solution to the original feasibility problem. The method is illustrated by a numerical example corresponding to a H-infinity robust performance test for a multivariable system.