-
作者：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...
-
作者：Zhang, Yangjing; Zhang, Ning; Sun, Defeng; Toh, Kim-Chuan
作者单位：National University of Singapore; Hong Kong Polytechnic University; National University of Singapore
摘要：The sparse group Lasso is a widely used statistical model which encourages the sparsity both on a group and within the group level. In this paper, we develop an efficient augmented Lagrangian method for large-scale non-overlapping sparse group Lasso problems with each subproblem being solved by a superlinearly convergent inexact semismooth Newton method. Theoretically, we prove that, if the penalty parameter is chosen sufficiently large, the augmented Lagrangian method converges globally at an...
-
作者：Malitsky, Yura
作者单位：University of Gottingen
摘要：The paper presents a fully adaptive algorithm for monotone variational inequalities. In each iteration the method uses two previous iterates for an approximation of the local Lipschitz constant without running a linesearch. Thus, every iteration of the method requires only one evaluation of a monotone operatorFand a proximal mappingg. The operatorFneed not be Lipschitz continuous, which also makes the algorithm interesting in the area of composite minimization. The method exhibits an ergodicO(...
-
作者：Kovacevic, Raimund; Wets, Roger J-B; Wozabal, David
作者单位：Technische Universitat Wien; University of California System; University of California Davis; Technical University of Munich
-
作者：Hao, Tianyu; Pang, Jong-Shi
作者单位：University of Southern California
摘要：Generalizing certain network interdiction games communicated to us by Andrew Liu and his collaborators, this paper studies a bilevel, non-cooperative game wherein the objective function of each player's optimization problem contains a value function of a second-level linear program parameterized by the first-level variables in a non-convex manner. In the applied network interdiction games, this parameterization is through a piecewise linear function that upper bounds the second-level decision ...
-
作者：Gurbuzbalaban, Mert; Ozdaglar, Asuman; Vanli, Nuri Denizcan; Wright, Stephen J.
作者单位：Rutgers University System; Rutgers University New Brunswick; Massachusetts Institute of Technology (MIT); University of Wisconsin System; University of Wisconsin Madison; University of Wisconsin System; University of Wisconsin Madison
摘要：We consider coordinate descent (CD) methods with exact line search on convex quadratic problems. Our main focus is to study the performance of the CD method that use random permutations in each epoch and compare it to the performance of the CD methods that use deterministic orders and random sampling with replacement. We focus on a class of convex quadratic problems with a diagonally dominant Hessian matrix, for which we show that using random permutations instead of random with-replacement sa...
-
作者：Ben-Tal, Aharon; El Housni, Omar; Goyal, Vineet
作者单位：Technion Israel Institute of Technology; Tilburg University; Columbia University
摘要：We consider the problem of designing piecewise affine policies for two-stage adjustable robust linear optimization problems under right-hand side uncertainty. It is well known that a piecewise affine policy is optimal although the number of pieces can be exponentially large. Asignificant challenge in designing a practical piecewise affine policy is constructing good pieces of the uncertainty set. Here we address this challenge by introducing a new framework in which the uncertainty set is appr...
-
作者：Ryu, Ernest K.
作者单位：University of California System; University of California Los Angeles
摘要：Given the success of Douglas-Rachford splitting (DRS), it is natural to ask whether DRS can be generalized. Are there other 2 operator resolvent-splittings sharing the favorable properties of DRS? Can DRS be generalized to 3 operators? This work presents the answers: no and no. In a certain sense, DRS is the unique 2 operator resolvent-splitting, and generalizing DRS to 3 operators is impossible without lifting, where lifting roughly corresponds to enlarging the problem size. The impossibility...
