How does one solve for a generalized quadratic in multiple dimensions as in $a w^Tw + b^T w + c = 0$?

Question

Consider:

$$a w^Tw + b^T w + c = 0 $$

I would like to find a vector $w \in \mathbb{R}^D$ that satisfies the above equation. I realize that I need to choose D numbers to satisfy 1 equation, so my intuition (from linear algebra) tells me that there might be an infinite set of solutions for this (1 equation D unknowns). Thus, I thought that maybe additional constraints are needed. I am honestly not too worried about which one to choose as long as it satisfies the equation. However, if I really had to choose a criterion to choose a $w$ I would first require it to be real vector and perhaps choose $w$ closest to some other fixed (aprior chosen) $x$ (say for simplicity closest to the origin $x=0$). So the additional constraint is:

$$ min_w \| w - x\|^2 $$

or even

$$ \| w - x\|^2 = 0 $$

another constraint could be (normalized vector) is also good:

$$ \| w \|^2 = 1 $$

I mostly care to satisfy the "generalized quadratic", the additional constraint is there just incase its needed (no complex number solutions).

Also Ideally I'd like to implement the solution in a maths program, for example, python or matlab.

Answer 1

If $a=0$, let $w=\frac{-cb}{\left\|b\right\|^2}$

WLOG, assume that $a>0$

Let's try to complete the square, Note that your equality is just $$\left(\sqrt{a}w+\frac{1}{2\sqrt{a}}b\right)^T\left(\sqrt{a}w+\frac{1}{2\sqrt{a}}b\right)+c-\frac{b^Tb}{4a}=0$$

$$\left\|\sqrt{a}w+\frac{1}{2\sqrt{a}}b\right\|^2=\frac{b^Tb}{4a}-c$$

Now, if the RHS is nonnegative, you can choose $$\sqrt{a}w+\frac{1}{2\sqrt{a}}b=v$$

where $v$ satisfies $$\left\|v\right\|^2=\frac{b^Tb}{4a}-c$$

and solve for $w$.

For instance, you can choose $v=\left(\sqrt{\frac{b^Tb}{4a}-c}\right)e_i$ and $$w=-\frac{b}{2a}+\frac{v}{\sqrt{a}}$$

Answer 2

Let us take $D=2$. Denoting by $x$ and $y$ the components of $w$, and by $u$ and $v$ those of $b$, your question can be re-phrased into "find points on the curve with equation"

$$a(x^2+y^2)+ux+vy+c=0$$

Assuming $a \neq 0$ (see Remark 2), an equivalent form is :

$$x^2+y^2+2u'x+2v'y+c'=0 \ \ (1) \ \text{with} \ u'=u/(2a), v'=v/(2a), c'=c/a$$

or

$$(x-u')^2+(y-v')^2=p \ \ \text{with} \ \ p:=u'^2+v'^2-c'$$

($p$ is called the "power") which may describe either the set of points constituting a circle, or a point or the void set, according to the fact that the RHS can be considered as the square of a radius or not.

Conclusion:

if $p>0$ ; it is a circle ; an infinite number of solutions.

if $p=0$ : a single point ; a single solution $(u',v')$.

if $p<0$ : no solution.

Remark 1 : the particular case $D=2$ is illustrative of the general case, with (hyper)spheres instead of circles. Working with $D=3$ might be a good idea to get an idea of the generalization.

Remark 2 : In the case $a=0$, the equation is that of an hyperplane : one has always an infinite number of solutions.

Remark 3 : the sign of $p$ is clearly the sign of $D=u^2+v^2-4ac$. The fact that this expression looks like a discriminant is not mere chance. It is linked to a way to write the initial condition under a certain matrix form

Let $A=aI_n$:

$$a w^Tw + b^T w + c = w^T\begin{pmatrix}A&b\\b^T&c\end{pmatrix}w$$

and the use of Schur's determinant formula.

Answer 3

Multiply through by $4a$ (a scalar assumed nonzero) to get $$ \begin{align} (2aw)^T(2aw)+2b^T(2aw)+4ac &=0\\ \end{align} $$ Note that $b^Tw$ is real, so it is equal to its transpose, $w^Tb$. So you can complete the square: $$ \begin{align} (2aw+b)^T(2aw+b) &=b^Tb-4ac\\ \left\lVert 2aw+b\right\rVert^2 &=\lVert b\rVert^2-4ac\\ \left\lVert w+\frac{b}{2a}\right\rVert^2 &=\frac{\lVert b\rVert^2-4ac}{4a^2}\\ \left\lVert w+\frac{b}{2a}\right\rVert &=\sqrt{\frac{\lVert b\rVert^2-4ac}{4a^2}} \end{align} $$

So the solution set is a sphere of radius $\sqrt{\frac{\lVert b\rVert^2-4ac}{4a^2}}$ centered at $-\frac{b}{2a}$. Of course this solution set is empty if $\lVert b\rVert^2-4c$ is negative. Note that over $\mathbb{R}^1$, this is exactly the quadratic formula, since a sphere in $\mathbb{R}^1$ with positive radius is precisely two points.

---

You ask for additional constraints to pin down one vector in particular on this sphere. Hopefully it is clear that the "$\lVert w\rVert=1$" idea won't pan out in general. Generally you could look to your other suggestion that you minimize the norm of $w$, but that won't give a unique vector if $b=0$.

Instead, you can parametrize the sphere. The solution set is a $D-1$ dimensional sphere, and you can use stereographic projection from $\mathbb{R}^{D-1}\cup\{\text{one point}\}$ to $S^{D-1}$ to parametrize a unit sphere, then scale to radius $\sqrt{\frac{\lVert b\rVert^2-4ac}{4a^2}}$ and shift to center $-\frac{b}{2a}$. This will give you a parametrization of all solutions to your equation.