It is well-known that the Capon beamformer is sensitive to array steering vector errors and may result into a worse performance than classical data-independent beamformers. This paper follows a different path from the well-established Diagonal Loading techniques and designs a robust Capon beamformer by a recent extension of the Adaptive Projected Subgradient Method. The proposed method marks a computational complexity of O(N2), where N is the number of array elements. The simulation results show that the proposed beamformer achieves excellent performance especially in cases where the Diagonal Loading techniques face difficulties, i.e. in cases where the Interference to Noise Ratio (INR) is moderately larger than SNR.