does this system of quadratic equations have an analytical solution?

Question

I have the following system of equations:

$$ \sum_i {k_i^2 a_{i1} + k_i b_{i1} + c_{i1}} = d_{1} \\ \sum_i {k_i^2 a_{i2} + k_i b_{i2} + c_{i2}} = d_{2} \\ . \\ . \\ . \\ \sum_i {k_i^2 a_{in} + k_i b_{in} + c_{in}} = d_{n} $$

I know $a_{in}, b_{in}, c_{in}, d_{n}$ and I would like to determine $k_i$. Does this have an analytical solution using something like least squares?

My problem consists of determining the $k_i$ values, multiplying them by a set of $i=1...M$ numbers, performing a separate operation on those numbers, then recalculating the $k_i$ values and iterating through these steps thousands of times until the operation converges.

Here, M can range anywhere from hundreds to tens of thousands, so I do not believe any kind of numerical optimization would work, which is why I would like an analytical solution. Also, the number of equations can vary, but is typically on the order of ~5 or so.

This is a highly underdetermined problem, but it is okay if I do not find the exact solution (if there even is one). I just need any one of the possibly infinite number of solutions to determine the $k_i$'s, as the iterative scheme should drive it close to the correct solution.

Answer 1

This will really depend on the data of your problem. Note first that you can rewrite the constraints as

$$x^TM_ix=0$$

where $M_i:=\begin{bmatrix}A_i & b_i/2\\b_i^T/2 & c_i-d_i\end{bmatrix}$, $x=(k_1,\ldots,k_M,1)$, where $A_i$ is a diagonal matrix and the other parameters are obvious from the context.

The matrix $M_i$ is symmetric and we have that $A_i$ is positive definite. This means that we have three possible cases:

1. The matrix $M_i$ is positive definite.
2. The matrix $M_i$ is positive semidefinite with one eigenvalue at zero and the others are positive.
3. The matrix $M_i$ is indefinite with one negative eigenvalues and the others are positive.

From the Schur complement, establishing in which case we are amounts to checking the sign of $c_i-d_i-b_iA_i^{-1}b_i/4$. If this expression is positive, then we are in case 1, if it is zero we are case 2 and if negative we are in case 3.

When we are in case 1, there is no solution $x$ such that we have $x^TM_ix=0$.

When we are in case 2, there is one solution $x$ such that $x^TM_ix=0$ and it is given by the only $x$ in the null-space of $M_i$ for which the last entry is equal to 1.

In case 3, the matrix $M_i$ is congruent to the matrix $$C=\begin{bmatrix}I & 0\\0 & -1\end{bmatrix},$$

which means that there exists a matrix $Z_i$ such that $M_i=Z_i^TCZ_i$. In fact, it is possible to prove that

$$Z_i=\begin{bmatrix}A_i^{1/2} & A_i^{-1/2}b_i/2\\0 & d_i-c_i-b_iA_i^{-1}b_i/4\end{bmatrix}$$ and thus we get

$$(x+A_i^{-1}b_i/2)^TA_i(x+A_i^{-1}b_i/2)=d_i-c_i-b_iA_i^{-1}b_i/4>0,$$

which is an equation of an ellipse in $\mathbb{R}^M$. So, we have an infinite number of solutions.

This leads us to the following remarks.

1. If any of the $M_i$ is positive definite, then the problem has no solution.
2. If one of the $M_i$ has a zero eigenvalue (and the others are in case 3), then it is very likely that the problem has no solution because unless there is some fine tuning of the $M_i$'s so that all the ellipses exactly go through that point in the null-space. It is very unlikely. If more than one matrices are in case 2, then it is also very unlikely that the points in the null-space are the same.
3. If all the $M_i$'s have a negative eigenvalues there is hope for a solution but as $M$ increases this will get less and less likely. A solution here will exist if and only of the ellipses intersect.

So, if we do not have more details on the problem, we cannot go much further that that.