-
作者：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...
-
作者：Pessoa, Artur; Sadykov, Ruslan; Uchoa, Eduardo; Vanderbeck, Francois
作者单位：Universidade Federal Fluminense
摘要：Major advances were recently obtained in the exact solution of vehicle routing problems (VRPs). Sophisticated branch-cut-and-price (BCP) algorithms for some of the most classical VRP variants now solve many instances with up to a few hundreds of customers. However, adapting and reimplementing those successful algorithms for other variants can be a very demanding task. This work proposes a BCP solver for a generic model that encompasses a wide class of VRPs. It incorporates the key elements fou...
-
作者：Konemann, Jochen; Pashkovich, Kanstantsin; Toth, Justin
作者单位：University of Waterloo; University of Ottawa
摘要：We provide an efficient algorithm for computing the nucleolus for an instance of a weighted cooperative matching game. This resolves a long-standing open question posed in Faigle (Math Programm, 83: 555-569, 1998).
-
作者：Knop, Dusan; Koutecky, Martin; Mnich, Matthias
作者单位：Czech Technical University Prague; Technion Israel Institute of Technology; Charles University Prague; Hamburg University of Technology; University of Bonn
摘要：Many fundamental NP-hard problems can be formulated as integer linear programs (ILPs). A famous algorithm by Lenstra solves ILPs in time that is exponential only in the dimension of the program, and polynomial in the size of the ILP. That algorithm became a ubiquitous tool in the design of fixed-parameter algorithms for NP-hard problems, where one wishes to isolate the hardness of a problem by some parameter. However, in many cases using Lenstra's algorithm has two drawbacks: First, the run ti...
