An algorithm for checking if a nonlinear function f is always positive - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-25T13:44:55Z http://mathoverflow.net/feeds/question/97152 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/97152/an-algorithm-for-checking-if-a-nonlinear-function-f-is-always-positive An algorithm for checking if a nonlinear function f is always positive Adel Ahmadyan 2012-05-16T19:45:41Z 2012-05-17T00:12:09Z <p>Is there an algorithm to check if a given (possibly nonlinear) function f is always positive?</p> <p>The idea that I currently have is to find the roots of the function (using newton-raphson algorithm or similar techniques, see <a href="http://en.wikipedia.org/wiki/Root-finding_algorithm" rel="nofollow">http://en.wikipedia.org/wiki/Root-finding_algorithm</a>) 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.</p> <p>For example, in Maple, function verify can do this, but I need to implement it in my own program. Maple Help on verify: <a href="http://www.maplesoft.com/support/help/Maple/view.aspx?path=verify/function_shells" rel="nofollow">http://www.maplesoft.com/support/help/Maple/view.aspx?path=verify/function_shells</a> Maple example: assume(x,'real'); verify(x^2+1,0,'greater_than' ); --> returns true, since for every x we have x^2+1 > 0</p> <p>Mirror question on stack-exchange: <a href="http://stackoverflow.com/questions/10625585/an-algorithm-for-checking-if-a-nonlinear-function-f-is-always-positive">http://stackoverflow.com/questions/10625585/an-algorithm-for-checking-if-a-nonlinear-function-f-is-always-positive</a></p> <p> 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). </p> <p>$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.</p> http://mathoverflow.net/questions/97152/an-algorithm-for-checking-if-a-nonlinear-function-f-is-always-positive/97170#97170 Answer by Igor Rivin for An algorithm for checking if a nonlinear function f is always positive Igor Rivin 2012-05-17T00:03:09Z 2012-05-17T00:12:09Z <p>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 <a href="http://www.math.washington.edu/~thomas/frg/frgbook/Parrilo.pdf" rel="nofollow">this reference.</a></p> <p>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.</p>