-
作者：Xia, Yong; Yang, Meijia; Wang, Shu
作者单位：Beihang University; Chinese Academy of Sciences; Academy of Mathematics & System Sciences, CAS
摘要：We study the n-dimensional problem of finding the smallest ball enclosing the intersection of p given balls, the so-called Chebyshev center problem (CCB). It is a minimax optimization problem and the inner maximization is a uniform quadratic optimization problem (UQ). When p = n, (UQ) is known to enjoy a strong duality and consequently (CCB) is solved via a standard convex quadratic programming (SQP). In this paper, we first prove that (CCB) is NP-hard and the special case when n = 2 is polyno...
-
作者：Davarnia, Danial; Van Hoeve, Willem-Jan
作者单位：Iowa State University; Carnegie Mellon University
摘要：As an alternative to traditional integer programming (IP), decision diagrams (DDs) provide a new solution technology for discrete problems exploiting their combinatorial structure and dynamic programming representation. While the literature mainly focuses on the competitive aspects of DDs as a stand-alone solver, we investigate their complementary role by introducing IP techniques that can be derived from DDs and used in conjunction with IP to enhance the overall performance. This perspective ...
-
作者：Chen, X.; Toint, Ph L.
作者单位：Hong Kong Polytechnic University; University of Namur
摘要：This paper studies high-order evaluation complexity for partially separable convexly-constrained optimization involving non-Lipschitzian group sparsity terms in a nonconvex objective function. We propose a partially separable adaptive regularization algorithm using a pth order Taylor model and show that the algorithm needs at most O((p+1)/(p-q+1)) evaluations of the objective function and its first p derivatives (whenever they exist) to produce an (d)-approximate qth-order stationary point. Ou...
