On The Existence Of Convex Decompositions Of Partially Separable Functions.

The concept of a partially separable function f is generalized to include all functions f that can be expressed as a finite sum of element functions f//i whose Hessians have nontrivial nullspaces. Such functions can be efficiently minimized by partitioned variable metric methods, provided that each element function f//i is convex. If this condition is not satisfied, one attempts to convexify the given decomposition by shifting quadratic terms among the original f//i such that the resulting modified element functions are at least locally convex. To avoid tests on the numerical value of the Hessian, the authors study the totally convex case where all locally convex f with a particular separability structure have a convex decomposition. It is shown that total convexity only depends on the associated linear conditions on the Hessian matrix.