The idea of writing something on detecting the convexity of a function, started after one of us (J. Dutta)
visited Jon Borwein in Newcastle in 2014. In the celebrated book by Borwein and Lewis titled Convex analysis and
there are two exercise problems where in one is asked to prove the convexity of two
different function. Proving the continuity of those two functions by hand was extremely cumbersome and one had to
resort to the use of the mathematical package MAPLE in order to actualyy compute the second derivative and also draw
its graph in order to get some more confidence about the nature of the function. In fact it took a good amount of
analysis to finally conclude that the functions were convex. This was the first time that we got the idea that
proving the convexity of a function is not all that easy but is also exciting at the same time. Thus we provide some
more examples of functions which one needs to use computational tool to detect its convexity, including the problems
in Borwein and Lewis (2006).
Recently Ahmadi and Parillo (2013) has also answered a long standing conjecture of Shor, which said that it is
NP-hard to detect the convexity of a polynomial function of degree four and above. They showed the NP-hardness of
detecting the convexity of polynomials by reducing the problem of a biquadratic optimization to this problem. We use
an approach based on algebraic geometry to discuss this issue.
In the last section we collect some other notion of convexity, like Schur convexity, geodesic convexity and
matrix convexity. We consider this article/talk as a survey on the issue of convexity detection and the exciting
challenges it throws at us.
J. M. Borwein and A. S. Lewis, Convex Analysis and Nonlinear Optimization
, 2nd Edition, Springer 2006
Ahmadi, Amir Ali; Olshevsky, Alex; Parrilo, Pablo A.; Tsitsiklis, John N. NP-hardness of deciding convexity of
quartic polynomials and related problems. Math. Program. 137 (2013), no. 1-2, Ser. A, 453-476