2
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • 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
    Commented May 16, 2012 at 19:51
  • 1
    $\begingroup$ This question is underspecified. Voting to close until the question is clarified. $\endgroup$
    – Igor Rivin
    Commented May 16, 2012 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
    Commented May 16, 2012 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
    Commented May 16, 2012 at 20:46

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .