So if I understood your question correctly you are trying to solve a non-linear system of equations of the form
$ Ax + x^{T}Bx = b .$
Restating it as
$ ( A + x^{T}B ) x = b $ $ \Leftrightarrow x = (A + x^{T}B)^{-1}b = f(x) $ $ \Leftrightarrow x - f(x) = 0 $
a fixed point is found. Any root-finding method can now be used. For example, the simplest approach would be a fixed-point iteration of the form
$ x_{i+1} = (A + x_{i}^{T}B)^{-1}b ,$
but alternatives include Newton's or any other higher order method of the Housholder family.
Note 1: In $x_{i+1} = (A + x_{i}^{T}B)^{-1}b$ the matrix $(A + x_{i}^{T}B)^{-1}$ should not be interpeted as computing the inverse but as solving the linear system of equations $(A + x_{i}^{T}B)x_{i+1} = b$. This system of equations will be solved multiple times until some criterion is met (e.g. the residual $r = \lvert ( A + x^{T}B ) x - b \rvert $ being smaller than some prescribed tolerance $\epsilon_{tol}$).
Note 2: this works assuming an unique solution exists. The closer your initial guess $x_0$ is to the "exact" solution, the less number of iterations you will need. As such a first step towards improving your method is to get a better initial guess. Another possibility is to use a method with a larger convergence radious first (e.g. a fix-point iteration), and then switch to a method with better convergence properties when some residual criterion is met (e.g. switch to Newton's method if $r<10^{-2}$).