Is there a standard method for determining whether a function is Convex or Non-Convex?
I had always thought that determining the convexity of a function can be done using the classical definition of Convexity (https://princeton.edu/~aaa/Public/Teaching/ORF523/S16/ORF523_S16_Lec7_gh.pdf):
This means that we would have to find a specifically find a value of (x1,x2) such that this inequality does not hold and we could conclude that this function we are trying to study violates the conditions of Convexity and therefore must be Non-Convex. We would effectively be doing a "Proof by Contradiction" - we will try to find a single counterexample to show why some function is Non-Convex ... however, I see that if we never find such a pair (x1,x2) that violates the Convexity Inequality, we could theoretically sit in "Convexity Purgatory" forever and be unable to determine whether the function is Convex or Non-Convex. For example, perhaps (x1 = 3.2, x2 = 1.1) satisfies the Convexity Inequality, but perhaps (x1 = 3.20000002, x2 = 1.111111118) might not satisfy the Convexity Inequality - does this mean we should search forever until the Convexity Inequality is violated? I am already starting to see problems in this approach.
Recently, I came across the following preposition (https://wiki.math.ntnu.no/_media/tma4180/2016v/note2.pdf):
At first glance, this seems to be a much more practical approach to determine whether some function is Convex or Non-Convex. Although I do not fully understand why a Convex Function MUST have a positive semi definite Hessian - I can accept that this condition (instead of the Convexity Inequality mentioned above) might result in a more "practical" way to determine whether a function is Convex or Non-Convex.
For instance, we can evaluate the Hessian Matrix (i.e. Matrix of Partial Second Derivatives) of some function and check if all the Eigen Values of this Hessian Matrix are all greater than 0 ... however, for multivariate functions, the Hessian Matrix might grow very big, and I am not sure if this approach will still be practical. But at the same time, I am not sure if modern "matrix solvers" (and "symbolic differentiation software") are able to effectively use approximation methods to obtain these Hessian Matrices and their Eigen Values ... thus making this approach an effective method for determining whether or not multivariate functions are Convex or Non-Convex.
Is there a standard method that is used to determine whether a function is Convex or Non-Convex?
In practical and applied purposes, do we ever really want to know if a function is Convex or Non-Convex? In Machine Learning applications, perhaps if we knew right away that we were dealing with a Convex Function - we might decide to use an optimization algorithm better suited for Convex Optimization (e.g. Newton Methods, BFGS) instead of Stochastic Gradient Descent (SGD has advantages in Non-Convex Optimization) ... but I feel that it might be too difficult (and also irrelevant) to determine whether the function we are dealing with is Non-Convex and most functions are probably Non-Convex anyways.
In other words, regardless of the function : On your marks, get set... Stochastic Gradient! GO! :)
Thank you!