We consider hedging of a contingent claim by a 'semi-static' strategy composed of a dynamic position in one asset and static (buy-and-hold) positions in other assets. We give general representations of the optimal strategy and the hedging error under the criterion of variance-optimality and provide tractable formulas using Fourier-integration in case of the Heston model. We also consider the problem of optimally selecting a sparse semi-static hedging strategy, i.e. a strategy which only uses a small subset of available hedging assets. The developed methods are illustrated in an extended numerical example where we compute a sparse semi-static hedge for a variance swap using European options as static hedging assets.