-
作者：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(...
-
作者：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 ...
-
作者：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...
-
作者：Bauschke, Heinz H.; Bui, Minh N.; Wang, Xianfu
作者单位：University of British Columbia; North Carolina State University
摘要：Beck and Teboulle's FISTA method for finding a minimizer of the sum of two convex functions, one of which has a Lipschitz continuous gradient whereas the other may be nonsmooth, is arguably the most important optimization algorithm of the past decade. While research activity on FISTA has exploded ever since, the mathematically challenging case when the original optimization problem has no minimizer has found only limited attention. In this work, we systematically study FISTA and its variants. ...
-
作者：Cannelli, Loris; Facchinei, Francisco; Kungurtsev, Vyacheslav; Scutari, Gesualdo
作者单位：Purdue University System; Purdue University; Sapienza University Rome; Czech Technical University Prague
摘要：We propose a new asynchronous parallel block-descent algorithmic framework for the minimization of the sum of a smooth nonconvex function and a nonsmooth convex one, subject to both convex and nonconvex constraints. The proposed framework hinges on successive convex approximation techniques and a novel probabilistic model that captures key elements of modern computational architectures and asynchronous implementations in a more faithful way than current state-of-the-art models. Other key featu...
