On the existence of convex decompositions of partially separable functions

Abstract:

The concept of a partially separable function f developed in [4] is generalized to include all functions f that can be expressed as a finite sum of element functions fi whose Hessians have nontrivial nullspaces Ni, Such functions can be efficiently minimized by the partitioned variable metric methods described in [5], provided that each element function fi is convex. If this condition is not satisfied, we attempt to convexify the given decomposition by shifting quadratic terms among the original fi such that the resulting modified element functions are at least locally convex. To avoid tests on the numerical value of the Hessian, we study the totally convex case where all locally convex f with the separability structure N(Formula presented.) have a convex decomposition. It is shown that total convexity only depends on the associated linear conditions on the Hessian matrix. In the sparse case, when each Ni is spanned by Cartesian basis vectors, it is shown that a sparsity pattern corresponds to a totally convex structure if and only if it allows a (permuted) LDLT factorization without fill-in. © 1984, The Mathematical Programming Society Inc.. All rights reserved.

Año de publicación:

1984

Keywords:

• partial separability
• Positive Definite Matrices
• Optimization
• sparsity
• decomposition
• 90C30
• Perfect Elimination
• 65F99
• 65K05

Fuente:

scopus