In this paper, a novel adaptive beamforming algorithm is proposed under a linearly and quadratically constrained minimum variance (LQCMV) beamforming framework, based on a dual-domain projection approach that can efficiently implement a quadratic-inequality constraint with a possibly rank-deficient positive semi-definite matrix, and the properties of the proposed algorithm are analyzed. As an application, relaxed zero-forcing (RZF) beamforming is presented which adopts a specific quadratic constraint that bounds the power of residual interference in the beamformer output with the aid of interference-channel side-information available typically in wireless multiple-access systems. The dual-domain projection in this case plays a role in guiding the adaptive algorithm towards a better direction to minimize the interference and noise, leading to considerably faster convergence. The robustness issue against channel mismatch and ill-posedness is also addressed. Numerical examples show that the efficient use of interference side-information brings considerable gains.