A cognitive radio scenario is considered where the signals transmitted by a secondary user (SU) are relayed by multi-antenna relays using an amplify-and-forward cooperation protocol. In this paper, the optimal power allocation and beamforming scheme is derived for the SU transmitters (SU-TXs), which minimizes the exact outage probability of the SU network with relay selection, under both a transmit power constraint and a constraint on the interference power generated at every primary user receiver. After deriving the optimal structure of the beamforming matrix, several distributed resource allocation algorithms are obtained for different levels of channel state information (CSI) at the SU-TXs: perfect CSI and imperfect CSI are considered, along with the case where only channel distribution information is available. The numerical results show that the multi-antenna relays can significantly improve the performance of the SU network, which would otherwise be severely limited by the harsh interference constraints. Furthermore, we also investigate how the number of relays, the number of antennas, and the level of CSI impact the performance of the SU network. Finally, we point out that the proposed algorithms outperform several algorithms presented in the literature.