In this paper, we consider a two-way cognitive relay network comprising two sources and multiple relays. The relays use a simple Amplify-and-Forward relaying mechanism. For such networks, we formulate the max-min and sum capacity optimization problems. The formulated optimization problems are non-convex and nonlinear in nature. We obtain the optimal solution of the optimization problems by using a known technique called Global Optimization Algorithm (GOP). We note that the computational complexity of the GOP algorithm grows exponentially with the number of relays. Therefore, we propose low-complexity heuristics that provide suboptimal solutions to the given optimization problems. The simulation results show that the performance of the heuristics is close to that of the respective optimal solutions.