Recorded seismic reflection waveforms contain information as to the small-scale variations of impedance and the large-scale variations of velocity. This information can be retrieved by minimizing the misfit between the recorded waveforms and synthetic seismograms as a function of the model parameters. Because of the different physical characters of the velocity and the impedance, we update these parameters in an alternating fashion, which amounts to a relaxation approach to the minimization of the waveform misfit. As far as the impedance is concerned, this minimization can be performed efficiently using gradient algorithms. For the inversion for seismic velocities, gradient methods do not work nearly as well; therefore, we use different minimization methods for determining impedances and velocities. However, the determination of the impedance and the determination of the velocity are strongly coupled; relaxation is most effective when this coupling is as weak as possible. Weak coupling can be achieved partially by parameterizing the impedances not as a function of depth but as a function of traveltime. A nonlinear, nonlocal method is presented for determining the smooth reference velocity from seismic reflection data. This technique is applied both to synthetic seismograms and to real marine data. In both cases, the velocity information implicitly contained in the curvature of the reflection hyperbolas was fully retrieved using nonlinear waveform optimization. In this way, it is possible to reconstruct both the impedance contrast and the smooth reference velocity from band-limited seismic reflection data using a single waveform-fit criterion.