Gradient descent for solving polynomial equations while encouraging variables to be nonzero

Question

I would like to use gradient descent to "randomly sample" solutions to a set of homogeneous polynomial equations. Because the equations are homogeneous, setting all variables to 0 is a valid solution. I'd like to somehow "bias" the search to finding solutions with many of the variables non-zero. Is there an easy way to do this?

---

My thoughts so far:

Because the polynomial constraints are homogeneous, solutions clearly have a scaling freedom. So if there is a solution with some variable $x_i$ non-zero, then there also exists a solution with this variable scaled to 1. If the resulting new polynomials still have no constant terms, then there is still a scaling freedom. I can continue "fixing" the remaining scaling freedom by choosing variables to scale to 1 until a constant term appears.

A related idea. I could "force" only considering solutions with some variables non-zero by choosing some term from one of the polynomials, and adding a new constraint: term = 1. Because if there is any solution with that term non-zero, I can scale the solution so that term is 1. This is kind of a weaker form of the scaling idea above.

However both of these ideas cause some problems. First, it requires fixing some variables as non-zero upfront. Depending on which ones I fix, I'll get different solutions (or maybe none at all). Should I just "randomly" make a choice of which variables to fix?

Another problem with these ideas is with the other variables. While searching for a solution there is a pressure to reduce the size of all terms in polynomials without a constant term. If most of the polynomials still have no constant term, this seems to push many variables to zero. So I haven't really solved the initial problem.

So... another approach:

Let's start by laying out the basics. Given a set of polynomial constraints $\{p_i\}$ in variables $\bar{x} = \{x_i\}$, if we want to find a solution we can define a "goal" scalar $$ E = \sum_i |p_i(\bar{x})|^2 $$ and try gradient descent from a random initial $\bar{x}$ to minimize $E$. This may get stuck in local minima (of which there are various strategies to handle if necessary, but hopefully the descent will just succeed with some reasonable probability), but if solutions exist, they will be at global minima of $E$.

Using this idea, we could also try to optimize for two goals by just summing them. Or if we just want to "encourage" a property, we could come up with a function $f(\bar{x}) \ge 1$ that is closer to 1 when near the encouraged property, and minimize the product $fE$ because solutions of $\{p_i\}$ will still be minimums of $fE$ but along the descent it will be encouraged for $f$ to be small as well. (These are likely very standard techniques since they seem like natural extensions of gradient descent solving of polynomial constraints, but I do not know what the names are for these techniques.)

So maybe there is some judicious choice of $f$ that would encourage as many variables to be non-zero as possible, but not cause the variables to explode in value while trying to solve via gradient descent?

Answer 1

Have you considered adding one more equation to the system? For example, assuming that there is a non-trivial solution $\vec{x}$ to $$ p_1(\vec{x}) = 0, \\ p_2(\vec{x}) = 0, \\ \vdots \\ p_k(\vec{x}) = 0, $$ it is easy to show that $\vec{x}$ is a solution (potentially after scaling $\tfrac{\vec{x}}{\|\vec{x}\|_2}$) to $$ p_1(\vec{x}) = 0, \\ p_2(\vec{x}) = 0, \\ \vdots \\ p_k(\vec{x}) = 0, \\ \|\vec{x}\|_{2}^2 = 1. $$

$2$-norm is sort of an arbitrary choice, just fits the "polynomial" theme. $\infty$-norm is probably another good choice, that would give you solution scaled with respect to the largest element (in some sense, "encouraging" sparsity).

You don't even have to pick a norm, any sufficiently smooth function $f$ which satisfies the following two conditions should give you a well-defined, well-conditioned model:

1. $f$ is convex
2. $f(\vec{x}) = 0$ if and only if $\vec{x} = 0$

Edit: I found another formulation, but the resulting problem is more difficult to solve $$ p_1(\vec{x}) = 0, \\ p_2(\vec{x}) = 0, \\ \vdots \\ p_k(\vec{x}) = 0, \\ \|\vec{x}\|_{2}^2 + s^2 = m, \\ \|\vec{x}\|_{\infty}^2 = 1, $$ where $m \leq n$ with $n,m\in\mathbb{Z}^+$, $\vec{x}\in\mathbb{R}^n$ and $s$ is a slack variable. Now, $\|\vec{x}\|_{\infty}^2 = 1$ forces at least one entry of $\vec{x}$ to be equal to 1 or -1 and guarantees that none of entries are larger than 1. $\|\vec{x}\|_{2}^2 + s^2 = m$ guarantees that number of nonzero entries in $\|\vec{x}\|$ is between $1$ and $m$. However, this system is only guaranteed to have a solution $n=m$ in general and it is very sensitive to the initial guess.

Answer 2

In situations where if $x$ is a solution, $\alpha x$ is also a solution for all $\alpha\in {\mathbb R}$, the solution is typically to only work on "normalized" sets of objects. In your current context, there are two possibilities:

• Only ever work with "monic" polynomials, i.e., the ones for which the leading coefficient equals one.
• Only work with polynomials $p$ that have norm one, i.e., $\|p\|=1$. Which norm you choose is unimportant (from a conceptual perspective, but perhaps not from a practical perspective).