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

2012-05-16T19:45:41Z

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: http://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.

Answer by Igor Rivin for An algorithm for checking if a nonlinear function f is always positive

2012-05-17T00:03:09Z

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.

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

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

Answer by Igor Rivin for An algorithm for checking if a nonlinear function f is always positive