For $f : \mathbb{R}^{n \times 1} \to \mathbb{R}$ a double differentiable function with bounded hessian, not necessarily convex, is any known polynomial algorithm, in the general case, which can assert if for a given $C \in \mathbb{R}^{n \times 1}$ with $\|C\| \geq k > 0$ exists $X \in \mathcal{B}(0_{n \times 1}, R)$ such that $$ f(X) + C^T \cdot X = 0$$

Consider $k$ and $R$ as some positive constants. Is any work in this direction published?


I doubt you can do so in polynomial time without any additional condition.

Let $g$ be an arbitrary polynomial function, and let $f$ be defined by $f(X) = g(X) - C^{T}X$ over $B(0, R)$, and an appropriate extension so that it's twice differentiable with bounded Hessian over $\mathbb{R}^{n}$. Then, $f(X) + C^{T}X = 0$ reduces to $g(X) = 0$, i.e., your setting is equivalent to finding a root of $g$ in $B(0, R)$.

(I believe that deciding whether an arbitrary polynomial has a root of at most norm $R$ is already NP-hard, but I'm not 100% sure).

Now, since 3SAT can be written as finding a root of a polynomial (make a polynomial for each clause and multiply all of them), finding a root of an arbitrary polynomial is NP-hard.

Thus, unless P = NP, there is little chance that you can solve your problem for general $f$ in polynomial time. (note that the value of $R, k$ are insignificant, since we can always re-scale everything).

  • $\begingroup$ Assuming that an algorithm is found, but which requires for instance something like $ \|C\| \geq \| \frac{\partial f}{\partial x} \| } + R $. Can this be still used to assert the zeros of $f(x)$ ? Can you expand a little on the insignificancy of $R$ and $k$ ? $\endgroup$
    – C Marius
    May 30 '21 at 16:01
  • $\begingroup$ For the example I give, you can assume without loss of generality that $R=1$ by replacing $X$ with $X / R$. This does not affect the assumptions on $f$. You can also assume w.l.o.g that $k=1$ by multiplying $f$ by $1/k$. $\endgroup$
    – mtanneau
    May 31 '21 at 20:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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