In this paper, we consider underlay spectrum access in a cognitive radio network, where two coexisting cellular systems, i.e., primary and cognitive, share the same frequency band. The throughput performance of this system is directly linked to the tolerated interference level at the primary receiver. We investigate the fundamental trade-off between the interference tolerance in the primary system and the achievable throughput of the cognitive network. We formulate the network performance as a multi-objective optimization problem with a set of objectives including minimizing the interference imposed on each primary user, and maximizing the intended signal received at every secondary user. We then derive an equivalent standard semi-definite programming form and prove that the derived problem always yields rank-one solutions. The obtained solution set provides the best achievable throughput (characterized by the maximum intended signal power at each cognitive user) for a given level of interference tolerance in the primary system. It also gives the achievable gain on the system throughput if the primary system is able to compromise and increase its interference tolerance, such framework could be a base for negotiations between the operators. An improvement of 0.38bits/s/channeluse is observed on the achievable throughput for 1dB higher interference tolerance at the primary receivers.