Optimization problems of beamforming in multi-user amplify-and-forward (AF) wireless relay networks are indefinite (nonconvex) quadratic programs, which require effective computational solutions. Solutions to these problems have often been obtained by relaxing the original problems to semi-definite programs (SDPs) of convex optimization. Most existing works have claimed that these relaxed SDPs actually provide the optimal beamforming solutions. This paper, however, shows that this is not the case in many practical scenarios where SDPs fail to provide even a feasible beamforming solution. To fill this gap, we develop in this paper a nonsmooth optimization algorithm, which provides the optimal solution at low computational complexity.