# An algorithm for checking if a nonlinear function f is always positive

Is there an algorithm to check if a given (possibly nonlinear) function f is always positive?

The idea that I currently have is to find the roots of the function (using newton-raphson algorithm or similar techniques, see http://en.wikipedia.org/wiki/Root-finding_algorithm) and check for derivatives, or finding the minimum of f, but they don't seems to be the best solution to this problem, also there are a lot of convergence issues with root finding algorithms.

For example, in Maple, function verify can do this, but I need to implement it in my own program. Maple Help on verify: http://www.maplesoft.com/support/help/Maple/view.aspx?path=verify/function_shells Maple example: assume(x,'real'); verify(x^2+1,0,'greater_than' ); --> returns true, since for every x we have x^2+1 > 0

Mirror question on stack-exchange: https://stackoverflow.com/questions/10625585/an-algorithm-for-checking-if-a-nonlinear-function-f-is-always-positive

 Some background on the question: The function $f$ is the right hand-side differential nonlinear model for a circuit. A nonlinear circuit can be modeled as a set of ordinary differential equations by applying modified nodal analysis (MNA), for sake of simplicity, let's consider only systems with 1 dimension, so $x' = f(x)$ where $f$ describes the circuit, for example $f$ can be $f(x) = 10x - 100x^2 + 200x^3 - 300x^4 + 100x^5$ ( A model for nonlinear tunnel-diode) or $f=10 - 2sin(4x)+ 3x$ (A model for josephson junction).

$x$ is bounded and $f$ is only defined in interval $[a,b] \in R$. $f$ is continuous. I can also make an assumption that $f$ is Lipschitz with Lipschitz constant L>0, but I don't want to unless I have to.

• What do we know about your function? Is it a polynomial? Exponomial? Trigonometric polynomial? Continuous? Do you mean for the domain to be compact? The integers? There are different answers for every combination of these! – Kevin O'Bryant May 16 '12 at 19:51
• This question is underspecified. Voting to close until the question is clarified. – Igor Rivin May 16 '12 at 20:01
• To decide whether a univariate polynomial is everywhere positive, have a look at Sturm's sequence (use wikipedia for basics). For a nice introduction to the theory, search for the paper "Basic algorithms in real algebraic geometry and their complexity: from Sturm's theorem to the existential theory of reals" by Marie-Françoise Roy. There is also the book perso.univ-rennes1.fr/marie-francoise.roy/bpr-ed2-posted1.h, but that might be an overkill for you. Someone else more familiar with the practical side might tell you about existing computer implementations. I do not know about it. – Boris Bukh May 16 '12 at 20:44
• For functions that involve sines and polynomials, have a look at the book "Fewnomials" by Khovanski, but turning the ideas there into working algorithms might require a substantial amount of work (which might have already been done, search). – Boris Bukh May 16 '12 at 20:46