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.
why?
.
why
E.g. for the Legendre transformation.
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 ); trueacer
parameters
Another issue would be parameters, on which assumptions may hold as here:
Probably, it would be better to state explicitly the variable as another argument.
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 FAILAnd while replacing abs(x) with sqrt(x^2) gives the correct answer,
isconvex(sqrt(x^2)); truethe following is wrong,
isconvex(-sqrt(x^2)); trueThat 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); trueAlec
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
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
thanks
I value your comments, Alec.
acer
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); trueconvexity
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?
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 FAIL10-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.
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
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