find minimum value of a function symbolically

[Pablo Puente]

Hi,

I could not find a  function in Sympy that finds the  minimum of a function symbolically. 

In case it is not implemented yet, would it make sense to add it? 

minimize() and maximize() are used in several of the Wester test cases. This is an example of how I implemented one of the test cases. Maybe can be used as a basis:

def _minmaximize(expr, x, si):

    f = Lambda(x, expr)

    f1 = f(x).diff(x)

    f2 = Lambda(x,f1.diff(x))

    m = None

    mp = None

    for p in solve(f1,x):

        if Gt(si*f2(p),0)==True  and ((m == None) or Lt(si*(f(p)-m),0)==True):

            m=f(p)

            mp = p

    return (m,mp)

def _minimize(expr, x):

    return _minmaximize(expr, x, +1)

def _maximize(expr, x):

    return _minmaximize(expr, x, -1)

def test_U13():

    assert _minimize(x**4 - x + 1, x)[0] == -3*2**Rational(1,3)/8 + 1

[Tim Lahey]

Hi,

I can see the utility for something like this in general. But, I think the general case should have an option for function boundaries (e.g., x >=0). I ran into an error once in a paper where they defined the maximum in a manner similar to this and it turned out that the maximum was at the boundary (x=0 in that case).

Cheers,

Tim.

---
Tim Lahey, Ph.D.
Post-Doctoral Fellow
Systems Design Engineering
University of Waterloo

> --
> You received this message because you are subscribed to the Google Groups "sympy" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to sympy+un...@googlegroups.com.
> To post to this group, send email to sy...@googlegroups.com.
> Visit this group at http://groups.google.com/group/sympy.
> For more options, visit https://groups.google.com/groups/opt_out.

[Pablo Puente]

Hi,

Yes, the general implementation will require some work.  Continuous functions are the easy ones. Piecewise functions handling would have to be consider.

Additionally I already found some other missing cases in my first attempt, some functions might reach a minimum at -oo or +oo. This has some small improvements:

def _minimize(expr, x):

    f = Lambda(x, expr)

    f1 = f(x).diff(x)

    f2 = Lambda(x,f1.diff(x))

    m = None

    mp = None

    for p in solve(f1,x):

        if Gt(f2(p),0)==True  and ((m == None) or Lt(f(p),m)==True):

            m=f(p)

            mp = p

    if f(oo) < m:

        m = f(oo)

        mp=oo

    if f(-oo)<m:

        m=f(-oo)

        mp=-oo

    return (m,mp)

def _maximize(expr, x):

    (m,mp) = _minimize(-expr, x)

    return (-m, mp)

def test_U13():

    assert _minimize(x**4 - x + 1, x)[0] == -3*2**Rational(1,3)/8 + 1

It would be nice to support functions or more than one variable, for example a special function for 2 variables could be:

def _minimize2(expr, x, y):

    f = Lambda((x,y), expr)

    f1x = f(x,y).diff(x)

    f1y = f(x,y).diff(y)

    d = solve((f1x,f1y),(x,y))

    m = f(d[x],d[y])

    mp=(d[x],d[y])

    if f(oo,oo) < m:

        m = f(oo,oo) 

        mp = (oo,oo)

    if f(-oo,-oo) < m:

        m = f(-oo,-oo)

        mp = (-oo,-oo)

    if f(oo,-oo) < m:

        m = f(oo,-oo)

        mp = (oo,-oo)

    if f(-oo,oo) < m:

        m = f(-oo,oo)

        mp = (-oo,oo)

    return (m,mp)        

def _maximize2(expr, x, y):

    (m,mp) = _minimize2(-expr, x, y)

    return (-m,mp)

def test_U14():

    f = 1/(x**2 + y**2 + 1)

    assert [_minimize2(f,x,y)[0], _maximize2(f,x,y)[0]] == [0,1]

Best Regards,

Pablo

[Sergey Kirpichev]

On Thursday, October 10, 2013 12:30:18 AM UTC+4, Pablo Puente wrote:

It would be nice to support functions or more than one variable, for example a special function for 2 variables could be:

def _minimize2(expr, x, y):

1) You should be aware about saddle points.

 

    if f(oo,oo) < m:

        m = f(oo,oo) 

        mp = (oo,oo)

    if f(-oo,-oo) < m:

        m = f(-oo,-oo)

        mp = (-oo,-oo)

    if f(oo,-oo) < m:

        m = f(oo,-oo)

        mp = (oo,-oo)

    if f(-oo,oo) < m:

        m = f(-oo,oo)

        mp = (-oo,oo)

2) Extremum could be on f(x, oo) as well...

 

[Aaron Meurer]

Piecewise defined functions aren't the only functions that aren't
continuous. Functions can have discontinuities simply by dividing by 0
(this will produce either a removable or infinite discontinuity).
Also, some functions are discontinuous by definition, like Heaviside.
And that's not to mention functions that aren't differentiable (for
instance, the minimum of abs(x) is 0, which is not a differentiable
point on the function).

I think to do this right, a prerequisite would be a function that
returns on what interval a function is continuous, which has been
requested many times.

Aaron Meurer

[Ondřej Čertík]

On Wed, Oct 9, 2013 at 9:47 PM, Aaron Meurer <asme...@gmail.com> wrote:
> Piecewise defined functions aren't the only functions that aren't
> continuous. Functions can have discontinuities simply by dividing by 0
> (this will produce either a removable or infinite discontinuity).
> Also, some functions are discontinuous by definition, like Heaviside.
> And that's not to mention functions that aren't differentiable (for
> instance, the minimum of abs(x) is 0, which is not a differentiable
> point on the function).
>
> I think to do this right, a prerequisite would be a function that
> returns on what interval a function is continuous, which has been
> requested many times.

Isn't the best way to do it like in calculus:

* return all critical points (zero derivative, discontinuity or the
end points of the given interval)

* evaluate at critical points and take the minimum

Ondrej