In the context of exotic derivatives, arbitrage-free implied volatility surfaces are a crucial ingredient to sophisticated pricing routines. We use a non-linear optimization technique to fit an arbitrage-free implied volatility surface efficiently to market data. The fitting procedure is tailor-made for any analytic parametrization of the single volatility skews. We carry out this approach for a certain parametrization by implementing an Interior-Point method, discuss its shortcomings, potentials, as well as specific smoothing techniques. Besides all the theory, we give various fitting details and examples by using real market data.