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

[edit] 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.

  • 1
    $\begingroup$ 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! $\endgroup$ – Kevin O'Bryant May 16 '12 at 19:51
  • 1
    $\begingroup$ This question is underspecified. Voting to close until the question is clarified. $\endgroup$ – Igor Rivin May 16 '12 at 20:01
  • 3
    $\begingroup$ 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. $\endgroup$ – Boris Bukh May 16 '12 at 20:44
  • 1
    $\begingroup$ 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). $\endgroup$ – Boris Bukh May 16 '12 at 20:46

For polynomials, non negativity can be verified by using semidefinite programming (this is theoretically fast [polynomial time], practically, not the fastest thing you had ever done.) There are many references, see for example, Nemirovsky's very nice notes on convex optimization, or this reference.

The non negativity of polynomials can also be related to the Fejer-Riesz theorem (which deals with trigonometric polynomials on the unit circle), there are fast approximate algorithms based on signal processing techniques.


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.