A methodology is developed for optimising the design of simple lightweight structures, such as those found attached to aircraft wings, which experience excitation over a wide frequency range at intermediate frequencies and above. The optimisation focuses on ensuring that constraints on fatigue damage are satisfied whilst weight is reduced; an understanding is gained of the design space presented by these structures. Small-scale structures are employed to model plate fairing surrogates, first in isolation and then attached to a flexible beam. The plates undergo synthetic random fatigue loading using Finite Element analyses with Fatigue Damage then computed in the frequency domain using the Dirlik method. The modal behaviour is compared, and the effect of the addition of semicircular notches is assessed. The design space presented by a plate where the thicknesses of different regions are allowed to vary is found to be non-smooth and irregular, motivating a global optimisation approach. Finally, a global optimisation of a system of two plates attached to a flexible beam is performed. Qualitative and quantitative comparisons between the optimal fairing designs obtained under this optimisation are made. The global optimization is found to perform well in cases where low-frequency excitation is present, but provides no design improvement over local optimisation in cases which exclusively contain higher frequencies.