2
$\begingroup$

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?

$\endgroup$
0

2 Answers 2

2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Interesting approach. In the second idea, the derivative of the inf norm during descent looks like it could be very noisy, changing which variable it depends on. I wonder if I could get a similar effect by bounding the entries of x to [-1,1] during descent? The smaller s is, the more non-zero variables will be in the solution. So to "encourage" s to be small during descent, I could try optimizing $(1 + s^2)\ E$. This will still converge to zero when all the equations are satisfied, but encourages s to be reduced during the descent! $\endgroup$
    – PPenguin
    Feb 6 at 0:11
2
$\begingroup$

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).
$\endgroup$
2
  • $\begingroup$ That is good advice to pre-condition the polynomials themselves, but that is before the gradient descent, and in my case the polynomials already all have the same "norm". What should I do during the gradient descent regarding the variable values to encourage finding solutions with many non-zero variables? $\endgroup$
    – PPenguin
    Feb 3 at 6:39
  • 1
    $\begingroup$ @PPenguin I don't understand the question. I thought the issue is that the problem is underdetermined. Perhaps you should state more clearly in the question what the problem actually is that you are trying to solve. $\endgroup$ Feb 3 at 16:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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