Unlike the situation with gain and phase margins in robust stabilization, the problem to determine an exact maximum delay margin is still an open problem, although extensive work has been done to establish upper and lower bounds. The problem is that the corresponding constraints in the Nyquist plot are frequency dependent, and encircling the point <formula><tex>$s=-1$</tex></formula> has to be done at sufficiently low frequencies, as the possibility to do so closes at higher frequencies. In this paper we present a new method for determining a sharper lower bound by introducing a frequency-dependent shift. The problem of finding such a bound simultaneously with gain and phase margin constraints is also considered. In all these problems we take an analytic interpolation approach.