## Convexity counterexample

June 12, 2013 Leave a comment

Here’s a fun counterexample: a function that is jointly convex in any of the variables, but not in all variables at once. The function is

To see why this is, note that the Hessian of is equal to

This matrix is equal to , where is the identity matrix and is the all-ones matrix, which is rank 1 and whose single non-zero eigenvalue is . Therefore, this matrix has eigenvalues of , as well as a single eigenvalue of , and hence is not positive definite.

On the other hand, any submatrix of size is of the form , but where now is only . This matrix now has eigenvalues of , together with a single eigenvalue of , and hence is positive definite. Therefore, the Hessian is positive definite when restricted to any variables, and hence is convex in any variables, but not in all variables jointly.