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.

  • 2
    $\begingroup$ What kinds of things are the $A$s and the $x$, and what is that circle with an x in it? $\endgroup$ Mar 4 '14 at 10:11
  • $\begingroup$ 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. $\endgroup$
    – cfp
    Mar 4 '14 at 10:34
  • $\begingroup$ 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^*)$. $\endgroup$ 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.

The usual techniques apply, available are Gröbner based methods if the matrices have rational entries and homotopy continuation methods like LHCPack. Project-Lift-Intersect methods are becoming available, but are not commonly used.

  • $\begingroup$ Yes. So much is clear. The question is whether the fact I'm searching for one specific solution means efficiency gains can be made. $\endgroup$
    – cfp
    Mar 4 '14 at 16:43
  • $\begingroup$ The task is that hard. Even if the equations were only quadratic. Finding one solution is not much easier than finding all solutions, and by that it is meant all complex solutions. One may try Newton's method, but if it does not start close to one solution, in all probability the iteration will diverge. Using line-search to force descend may help. But one may rapidly land in an almost flat curved valley where the iteration then stalls. $\endgroup$ Mar 4 '14 at 16:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.