From: "R.G. Vickson" Subject: Re: Convex functions Date: Fri, 24 Sep 1999 17:57:47 -0400 Newsgroups: sci.math Keywords: convexity and related notions James Park wrote: > Thanks. Is a positive semidefinite hessian both necessary and sufficient > for convexity, or is it just sufficient? It is necessary, but not sufficient. Example: f = x1-x2^2 has Hessian | 1 0 | H = | 0 0 | at x1 = x2 = 0. H is positive semidefinite, but f is not convex near (x1,x2) = (0,0). A function can even be strictly convex (everywhere) but have a Hessian that is positive semidefinite at isolated points but positive definite everywhere else. > What does pseudo-convex mean? Quasi-convex means that f[ax+(1-a)x'] <= max{f(x),f(x')} (0 < a < 1) Pseudo-convex means >= 0 implies f(x2) >= f(x1); that is, if the function is going up locally in some direction at x1 it goes up globally in that direction. (Here, = inner product of vectors a and b.) Having a minimization objective that is pseudo-convex or quasi-convex is almost as good as having a convex one, for under reasonably broad conditions, a local constrained minimum is guaranteed to be global. However, _testing_ for pseudo- or quasi-convexity is hard; there are AFIK no computationally tractable second derivative tests that will do it. Usually one has to use the fact that the final f is built up from simpler convex or pseudo or quasi convex pieces and that the pieces are put together appropriately to preserve the desired properties. See, eg., O.L. Mangasarian, Nonlinear Programming, McGraw-Hill, 1969, Greenberg and Pierskalla, "A Review of Quasi-Convex Functions", Operations Research, vol. 29 (1971), pp. 1553-1570, Schaible et al., Generalized Concavity in Optimization and Economics, Academic Press, 1980. > > Do you know any way to test for it? > J.D. > On Thu, 23 Sep 1999, R.G. Vickson > wrote: > > > If a symmetric matrix is positive semidefinite and the ith diagonal element is > > zero, then it is necessary to have ALL elements in row i and column i equal to > > zero (easy proof below). Therefore, your example, with all diagonals = 0 but > > some or all off-diagonals nonzero give _indefinite_ Hessians, so are neither > > convex nor concave. > > > > Of course, the function could still be pseudo-convex or quasi-convex, but I > > don't think there are any second-derivative tests for these properties.