Feasibility problem with polynomial inequalities

Question

I have several nonconvex quadratic multivariate polynomials $(f_i)_{i\in I}$ for which I need to find a point $\overline{x}$ such that $$(\forall i\in I)\quad f_i(\overline{x})\leq 0.$$ I feel like there should be an (at least heuristically) reasonable algorithm for carrying this out using the gradients of the $(f_i)_{i\in I}$. However, I am struggling to find one.

work so far: I am familiar with the case where the functions $f_i$ are such that $\nabla f_i$ is Lipschitz continuous (in which case you can take steps in the direction of negative gradients for violated inequalities, and you rescale the gradient by a parameter bounded by the inverse of the Lipschitz constant). However, for the non-Lipschitz case (i.e. these multivariate polynomials), I am not sure what is really "standard" in this field. It looks like there are several approaches in the literature, e.g., here, but I don't know if this is actually implementable (e.g., in their algorithm they just say "solve (3.3)" which they only say is possible if you know your function's Lipschitz constant).

Also, for this problem, I cannot use 2nd-order methods since $I$ is too big.

Answer 1

If you can easily compute the roots (which seems to be the case, as your $f$s are quadratics), you can turn the problem into a simple min/max problem over finitely many reals.

Consider the sets $\left\{ x\in\mathbb{R}:f_{i}(x)\le0\right\},i\in I$. Your task is to find a point in the intersection. These sets have a simple structure that you can exploit, and in fact, find all intersection points.

To each polynomial $f$ corresponds either

1. a finite interval $[a,b]$ if $f=(x-a)(x-b),a<b$;
2. a pair of infinite intervals $(-\infty, a]\cup[b,\infty)$ if $f=-(x-a)(x-b),a<b$;
3. the entire $(-\infty,\infty)$ if $f$ has a negative primary coefficient and no real roots (or a double-root);
4. a single number $a$ if $f=(x-a)^2$;
5. no solution to the problem at all if $f$ is always positive (no roots, positive primary coefficient).

Case 3 gives no restrictions, case 5 ends the solution instantly, and case 4 can be treated like case 1 by taking the interval $[a,a]$. Let's look at cases 1 and 2:

• For $j$ s.t. $f_j=(x-a_j)(x-b_j)$ you have $$\bigcap_j [a_j,b_j]=[\max a_j,\min b_j].$$
• For $j$ s.t. $f_j=-(x-a_j)(x-b_j)$ it's analogous: $$\bigcap_{j}\left(\left(-\infty,a_{j}\right],\left[b_{j},\infty\right)\right)=\left(-\infty,\min a_{j}\right]\cup\left[\max b_{j},\infty\right).$$

Computing the min/max is a matter of simple iteration given $\{a_i\}$ and $\{b_i\}$.

In the end you'll have a finite interval and a pair of infinite intervals where finding a common point should be easy to do by hand.