# Lowest norm solution to a system of polynomial equations

I have a system of cubic equations:

$$0=A_0+A_1 x+A_2 ( x \otimes x ) + A_3( x \otimes x \otimes x )$$

where $\dim A_0 = \dim x$ (so there are as many equations as unknowns). You may assume that the system has finitely many solutions, and at least one.

I seek an efficient numerical algorithm that is guaranteed to converge to the solution with minimum $L_2$ norm (i.e. that for which $\| x \|_2$ is lowest).

One algorithm would be to use the Homotopy continuation method to find all the solutions, then to just pick the one with lowest norm. However, my hunch is that a much faster algorithm ought to be possible, either by exploiting the fact that with $x$ small, $0 \approx A_0 + A_1 x$, or by repeated numerical minimisation of:

$$\|A_0+A_1 x+A_2 ( x \otimes x ) + A_3( x \otimes x \otimes x )\|_2 + \lambda \| x \|_2$$

where $\lambda$ is gradually reduced from a very large value to $0$.

Has this problem been analysed before? If so, directions to the relevant literature would be a great help. As indeed would comments on my hunches, or further ideas.

Thanks in advance for any assistance.

• What kinds of things are the $A$s and the $x$, and what is that circle with an x in it? Mar 4 '14 at 10:11
• The $A$s are matrices. If $x$ is length $n$, then $A_0$ is $n\times 1$, $A_1$ is $n \times n$, $A_2$ is $n \times n^2$ and $A_3$ is $n \times n^3$. The "circle with an x in it" is the usual Kronecker product.
– cfp
Mar 4 '14 at 10:34
• Or in tensor notation $x\in V$, $A_0\in V$, $A_1\in V\otimes V^*$, $A_2\in V\otimes (V^*\odot V^*)$, $A_3\in V\otimes (V^*\odot V^*\odot V^*)$. Mar 4 '14 at 16:16

This system is a ordinary system of $n$ polynomials of degree $3$ in $n$ variables written in a fancy form. So it may have up to $3^n$ solutions.