convexity

I seems that Maple doesn't know anything about the convexity of functions.

It would be nice to have a command to check the convexity of (real) functions in Maple, also Maple should have knowledge on the convexity of known functions: for example: constant function, linear function , abs,  sin  (convex on a specific region) etc.
To deal with the calculus of convex functions: for example Maple should know such theorems: if f(x) and g(x) are convex functions and g(x) is non-decreasing then g(f(x)) is convex, etc.

 

 

Axel Vogt's picture

why?

.

why

E.g. for the Legendre transformation.

acer's picture

convexity

There's a lot of scope for improving this code below. (A probabilistic fallback might also be worthwhile. I suspect that a fallback that using testeq & signum might not work; testeq is rather limited.)

Note that `is` can depend upon Digits.

> isconvex := proc(expr,A::realcons:=-infinity,B::realcons:=infinity)
> local a,b,t,x,use_expr,res;
>   x := indets(expr,name) minus {constants};
>   if nops(x) = 1 then
>     x := op(x);
>   else error;
>   end if;
>   # For more than one variable, one could test
>   # positive-definiteness of the Hessian.
>   res := is( diff(expr,x,x) >=0 )
>            assuming x>=A, x<=B;
>   if res<>FAIL then
>     return res;
>   else
>     userinfo(1,'isconvex',`falling back to the definition`);
>     # Is it better to expand, or simplify, or put
>     # Normalizer calls around the two-arg evals or
>     # their difference, oder...?
>     use_expr:=expand(expr);
>     is( eval(use_expr,x=(1-t)*a+t*b) <=
>         (1-t)*eval(use_expr,x=a)+t*eval(use_expr,x=b) )
>       assuming a<=b, t>=0, t<=1, b<=B, a>=A;
>   #else
>   ##Is global optimization another fallback?
>   end if;
> end proc:

> # note: this shows that none of the examples
> # below had to fall back to the defn after failing
> # a 2nd deriv test. But many such will exist.
> infolevel[isconvex]:=1:

> isconvex( y^2 );
                                     true

>
> isconvex( y^3 );
                                     false

> isconvex( y^3, 0 );
                                     true

>
> isconvex( (y-3)^2 );
                                     true

>
> isconvex( (y-3)^4 );
                                     true

>
> isconvex( exp(y) );
                                     true

> isconvex( -exp(y) );
                                     false

>
> isconvex( -sin(y), 0, Pi );
                                     true

acer

parameters

Another issue would be parameters, on which assumptions may hold as here:

isconvex( (x-a)^2 ) assuming a::real;

Error, (in assuming) when calling 'isconvex'. 
Received: 'testing against an invalid type'

Probably, it would be better to state explicitly the variable as another argument.

alec's picture

abs

Fails for abs though,

isconvex(abs(x));
isconvex:   falling back to the definition

                                 FAIL

isconvex(abs(x^3));
isconvex:   falling back to the definition

                                 FAIL

And while replacing abs(x) with sqrt(x^2) gives the correct answer,

isconvex(sqrt(x^2));

                                 true

the following is wrong,

isconvex(-sqrt(x^2));

                                 true

That was caused by the following Maple feature

diff(sqrt(x^2),x,x);

                              2
                             x          1
                         - ------- + -------
                             2 3/2     2 1/2
                           (x )      (x )

normal(%);

                                  0

is(%%<=0);
                                 true

is(%%%=0);

                                 true

Alec

acer's picture

sure

As is, it fails for lots of things. Obviously I was implying that when I wrote that there is lots of room for improvement.

Note also that there was a comment in the code about whether/how to normalize. Testing for differentiability (another tricky area) is also possible.

Testing for convexity is similar to lots of computer algebra tasks in that there are lots of theoretical and practical holes. Unless someone starts it off, even if only for discussion, there will always be nothing.

"Pragmatism. Is that all you have have to offer?" - Guildenstern

acer

alec's picture

I agree

I agree and it is great that you started doing that. The procedure as it is should work if the is could be corrected.

That's an old topic - what 1/x - 1/x should return. Currently it is 0 in Maple, but that creates problems as one can see in the last example.

That is one thing where domains may be useful - if 1/x is an element of the field of rational functions, it should be 0. If it is an expression representing a function, it should be undefined at 0.

Alec

 

acer's picture

thanks

I value your comments, Alec.

acer

alec's picture

Thank you

Acer,

Thank you! I extremely value all yours, Robert Israel's, Joe Riel's, Jacques Carette, Dave Linder, and several other people posts.

If Maplesoft hired me 5 or 7 years ago, Maple would be already much better by now, I think.

Alec

also wrong

I think inequality should be strict, otherwise:

isconvex(x);
                                 true

alec's picture

convexity

Linear functions are convex, just not strictly convex. Same as constants are increasing, but not strictly increasing.

Alec

strict

With that terminology, an option "strict" would be useful.

Thanks

 

Thanks for your thinking on this issue. it is very interesting and valuable.

The following is also problematic and the constant function as well:

isconvex(1/(x*x))

Such new property would be also useful in Maple (convex, convace, strictly convex...).
It is pity that Maple doesn't have strong enough basic routines (like is etc.) .
Anyway the isconcave routine is simply to change expr to -expr in isconvex, isnt' it?

 

acer's picture

twice differentiable

In order to use the test of the 2nd derivative being nonnegative, the expression should be twice differentiable. That is one way of seeing why it falls down for 1/(x*x), which is not even once differentiable.

The code might be altered to check differentiability, running limit of the derivative(s) against values returned by discont or fdiscont. (There is an existing "property" named 'differentiable' known to is&assume&assuming, but it's for "functionals".)

If the method is edited to force use of the definition, avoiding the 2nd derivative test, then one gets behaviour like,

> isconvex(1/(x*x));
isconvex:   falling back to the definition
                                     false
 
>
> isconvex(-sqrt(x^2));
isconvex:   falling back to the definition
                                     false
 
> isconvex(1/(x*x),0,infinity);
isconvex:   falling back to the definition
                                     true
 
> isconvex(-sqrt(x^2),-infinity,0);
isconvex:   falling back to the definition
                                     true
 
> isconvex(abs(x));
isconvex:   falling back to the definition
                                     FAIL

10-15 years ago I used to hear experts say that it was only a misdemeanor if Maple's answer was wrong only on a set of measure zero. Nowadays more Maple routines return and accept piecewise results, and in turn people have come to expect more of the same. Given that not all of Maple is prepared to handle piecewise(), what havoc would be caused by having diff(1/x^2,x) return piecewise(x=0,undefined,-2/x^3) ?

acer

diff etc.

Perhaps diff could have an option like int has the 'Allsolutions' to return piecewise.

I 'm not experienced with the theorem provers (like Isabelle, Coq, PVS) , I have just read about them.  So I wonder if they can check such properties?  Some of them have interface to Maple.

 

 

alec's picture

concavity option

By the way, there is a concavity option in Student:-Calculus1:-FunctionChart (or FunctionPlot) drawing arrows up on the intervals where a function is stritly convex (i.e. concave up) and arrows down where a function is strictly concave.

Alec

acer's picture

interesting find

That's an interesting find.

That routine works by computing (approximations, while Digits=8, to) the zeros, extrema, and inflections of the expression. Then it reverts Digits and determines convexity/concavity by taking signum(eval(diff(expr,x,x),x=mid)) for 'mid' the midpoint between each pair of those points of interest.

I see using signum as mildly superior to using `is` directly, since signum can sometimes use evalr and a few other techniques as well as `is`.

I note that these Calculus1 routines (including `Roots`) demand a finite range. I'm not so sure about the wisdom of setting of Digits to 8 while finding critical points.

While determining subintervals on which the expression is (piecewise) convex is interesting, that routine doesn't quite bring all the same inferences. For one thing, it uses only a finite range. It also doesn't actually make an statement about adjoining subintervals, I suspect. Sure x^2 is convex from a..0 and also from 0..b, which it shows. But that's not as strong a statement as saying that, yes, "x^2 is convex from a..b" or yes, "x^2 is convex".

acer

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.
}