On the Location of the Minimizer of the Sum of Strongly Convex Functions

Kananart Kuwaranancharoen, Shreyas Sundaram

Published 2018-04-20Version 1

The problem of finding the minimizer of a sum of convex functions is central to the field of distributed optimization. Thus, it is of interest to understand how that minimizer is related to the properties of the individual functions in the sum. In the case of single-dimensional strongly convex functions, it is easy to show that the minimizer lies in the interval bracketed by the smallest and largest minimizers of the set of functions. However, a similar characterization for multi-dimensional functions is not currently available. In this paper, we provide an upper bound on the region containing the minimizer of the sum of two strongly convex functions. We consider two scenarios with different constraints on the upper bound of the gradients of the functions. In the first scenario, the gradient constraint is imposed on the location of the potential minimizer, while in the second scenario, the gradient constraint is imposed on a given convex set in which the minimizers of two original functions are embedded. We characterize the boundaries of the regions containing the minimizer in both scenarios.