On the Set of Possible Minimizers of a Sum of Known and Unknown Functions

Kananart Kuwaranancharoen, Shreyas Sundaram

Published 2020-03-19Version 1

The problem of finding the minimizer of a sum of convex functions is central to the field of optimization. Thus, it is of interest to understand how that minimizer is related to the properties of the individual functions in the sum. In this paper, we consider the scenario where one of the individual functions in the sum is not known completely. Instead, only a region containing the minimizer of the unknown function is known, along with some general characteristics (such as strong convexity parameters). Given this limited information about a portion of the overall function, we provide a necessary condition which can be used to construct an upper bound on the region containing the minimizer of the sum of known and unknown functions. We provide this necessary condition in both the general case where the uncertainty region of the minimizer of the unknown function is arbitrary, and in the specific case where the uncertainty region is a ball.