Your problem seems
First eliminate $x_1$ by solving an ordinary least squares, and then you need to be solvable as essentially solve a so-called problem of the form: $\min x_2^TMx_2$ s.t. $\|x_2\|=g$, for appropriate $M$. This problem is the famous trust-region subproblem, aka, TRS, (the constraint $\|x_2\|=g$ may be written with an appropriate diagonal matrix as $\|Dx\| = g$).
Please have a look at the following references (and references therein), which provide algorithms and discussion on how to solve such problems; perhaps you can simplify or adapt one of their methods:
- LSTRS: http://ta.twi.tudelft.nl/wagm/users/rojas/lstrs-paper.pdf
- Moré-Sorensen TRS algorithm (in the book on Trust-region subproblems)
- http://www.optimization-online.org/DB_HTML/2002/09/530.html
It seems that the Newton method suggested by Robin above might work for you. The
Depending on how large $A$ is, or what kind of structure it has, different TRS methods organize their computation may be preferred. Example, for speedsmall matrices, so in case where you can afford to do Cholesky, the More-Sorensen method is usually very hard to beat. If your matrix $A$ is however large and sparse, a more careful implementation then you might helpprefer the LSTRS method instead.
