6

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 the f, but they don't seems to be the best solutions 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

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

Adel Ahmadyan
  • 164
  • 8
  • Does Maple's `verify` work for all possible functions? How about, say, a ten-degree polynomial? – Kevin May 16 '12 at 20:03
  • 2
    I'm assuming you mean a **continuous**, probably **polynomial** function *(after all, `f(x) = -1 iff program X halts else +1` is a valid function)*? If so, what is the actual problem? You mentioned two solutions: find the roots of the function *(check the value of the function at one point between each of the roots)* or the roots of the derivative *(check the value of the function at each of these points)* - either one of these should work. – BlueRaja - Danny Pflughoeft May 16 '12 at 20:23
  • A very good point, yes, the function should be continuous. Root-finding was my initial solution, but in my case, there are several convergence issues with it. I'm looking for a better algorithm. – Adel Ahmadyan May 16 '12 at 20:37
  • 4
    Do you have an analytic form for `f`, or just a black-box function to evaluate it? What about its derivatives? – Danica May 16 '12 at 20:57
  • Instead of looking for the roots of the function, you could look for all extremas, i.e. points where the derivative is zero; if any of these is negative the function is negative. – Mathias May 16 '12 at 21:12
  • We construct the f using Modified Nodal Analysis, so we know the analytical form of f and it's derivatives. On the other hand, if it was black-box and continous, there is no way to say with absolute certainty that it is always positive, the only solution is to use statistical hypothesis testing or estimation theory (like ML or MAP) which is not the focus of my question. – Adel Ahmadyan May 16 '12 at 21:19
  • @Mathias, Complexity of looking at exterma's is the same as finding the minimums or finding roots of the f. (i.e. root finding of the derivatives of f instead of f itself) – Adel Ahmadyan May 16 '12 at 21:21

1 Answers1

3

If I understand your problem correctly, it boils down to counting the number of (real) roots in an interval without necessarily identifying them. In fact, you don't even need to get the exact number, just whether or not it's equal to zero.

If your function is a polynomial, I think that Sturm's theorem may be applicable. The Wikipedia article claims two other procedures are preferred, so you might want to check those out, too. I'm not sure if Descartes' rule of signs works on an interval, but Budan's theorem does appear to.

mhum
  • 2,928
  • 1
  • 16
  • 11