Optimization theory and nonlinear programming method have successfully been applied into wire-lined networks in developing efficient resource allocation and congestion control schemes. However, for wireless networks, allocating the resource among the soft quality of service (QoS) traffic remains an important design challenge. Mathematically, the most difficulty comes from the nonconcave utility function of soft QoS traffic in the network utility maximization (NUM) problem. Previous result on this problem has only been able to find its suboptimal solution. Facing this challenge, this chapter discusses some key theorems to find the optimal solution, and then present a complete algorithm called utility-based allocation for soft QoS (USQ) to obtain the desired optimal solution. The proposed theorems and algorithm act as designing guidelines for resource allocation of soft QoS traffic in a wireless network, which take into account the total available resource of network, and the users channel qualities. The chapter illustrates the performance of the algorithm via some numerical examples.