作者：Clarkson, Jake; Lin, Kyle Y.; Glazebrook, Kevin D.
作者单位：Lancaster University; United States Department of Defense; United States Navy; Naval Postgraduate School; Lancaster University
摘要：Consider a two-person zero-sum search game between a hider and a searcher. The hider hides among n discrete locations, and the searcher successively visits individual locations until finding the hider. Known to both players, a search at location i takes t(i) time units and detects the hider-if hidden there-independently with probability alpha(i) for i = 1, ..., n. The hider aims to maximize the expected time until detection, whereas the searcher aims to minimize it. We prove the existence of a...
作者：Kerdreux, Thomas; Colin, Igor; d'Aspremont, Alexandre
作者单位：Centre National de la Recherche Scientifique (CNRS); CNRS - Institute for Information Sciences & Technologies (INS2I); Universite PSL; Ecole Normale Superieure (ENS); Huawei Technologies
摘要：The Shapley-Folkman theorem shows that Minkowski averages of uniformly bounded sets tend to be convex when the number of terms in the sum becomes much larger than the ambient dimension. In optimization, Aubin and Ekeland show that this produces an a priori bound on the duality gap of separable nonconvex optimization problems involving finite sums. This bound is highly conservative and depends on unstable quantities; we relax it in several directions to show that nonconvexity can have a much mi...
