-
作者：Dey, Santanu S.; Molinaro, Marco; Wang, Qianyi
作者单位：University System of Georgia; Georgia Institute of Technology
摘要：In this paper, we study how well one can approximate arbitrary polytopes using sparse inequalities. Our motivation comes from the use of sparse cutting-planes in mixed-integer programing (MIP) solvers, since they help in solving the linear programs encountered during branch-&-bound more efficiently. However, how well can we approximate the integer hull by just using sparse cutting-planes? In order to understand this question better, given a polyope (e.g. the integer hull of a MIP), let be its ...
-
作者：Lu, Zhaosong; Xiao, Lin
作者单位：Simon Fraser University; Microsoft
摘要：In this paper we analyze the randomized block-coordinate descent (RBCD) methods proposed in Nesterov (SIAM J Optim 22(2):341-362, 2012), Richtarik and Taka (Math Program 144(1-2):1-38, 2014) for minimizing the sum of a smooth convex function and a block-separable convex function, and derive improved bounds on their convergence rates. In particular, we extend Nesterov's technique developed in Nesterov (SIAM J Optim 22(2):341-362, 2012) for analyzing the RBCD method for minimizing a smooth conve...
-
作者：Nesterov, Yu
作者单位：Universite Catholique Louvain
摘要：In this paper, we present new methods for black-box convex minimization. They do not need to know in advance the actual level of smoothness of the objective function. Their only essential input parameter is the required accuracy of the solution. At the same time, for each particular problem class they automatically ensure the best possible rate of convergence. We confirm our theoretical results by encouraging numerical experiments, which demonstrate that the fast rate of convergence, typical f...
-
作者：Angulo, Alejandro; Espinoza, Daniel; Palma, Rodrigo
作者单位：Universidad de Chile; Universidad de Chile
摘要：In this paper, we consider the semi-continuous knapsack problem with generalized upper bound constraints on binary variables. We prove that generalized flow cover inequalities are valid in this setting and, under mild assumptions, are facet-defining inequalities for the entire problem. We then focus on simultaneous lifting of pairs of variables. The associated lifting problem naturally induces multidimensional lifting functions, and we prove that a simple relaxation in a restricted domain is a...
-
作者：Kilinc-Karzan, Fatma; Yildiz, Sercan
作者单位：Carnegie Mellon University
摘要：Balas introduced disjunctive cuts in the 1970s for mixed-integer linear programs. Several recent papers have attempted to extend this work to mixed-integer conic programs. In this paper we study the structure of the convex hull of a two-term disjunction applied to the second-order cone and develop a methodology to derive closed-form expressions for convex inequalities describing the resulting convex hull. Our approach is based on first characterizing the structure of undominated valid linear i...
-
作者：Harchaoui, Zaid; Juditsky, Anatoli; Nemirovski, Arkadi
作者单位：Inria; Communaute Universite Grenoble Alpes; Universite Grenoble Alpes (UGA); University System of Georgia; Georgia Institute of Technology
摘要：Motivated by some applications in signal processing and machine learning, we consider two convex optimization problems where, given a cone , a norm and a smooth convex function , we want either (1) to minimize the norm over the intersection of the cone and a level set of , or (2) to minimize over the cone the sum of and a multiple of the norm. We focus on the case where (a) the dimension of the problem is too large to allow for interior point algorithms, (b) is too complicated to allow for com...
-
作者：Curtis, Frank E.; Jiang, Hao; Robinson, Daniel P.
作者单位：Lehigh University; Johns Hopkins University
摘要：We propose an augmented Lagrangian algorithm for solving large-scale constrained optimization problems. The novel feature of the algorithm is an adaptive update for the penalty parameter motivated by recently proposed techniques for exact penalty methods. This adaptive updating scheme greatly improves the overall performance of the algorithm without sacrificing the strengths of the core augmented Lagrangian framework, such as its ability to be implemented matrix-free. This is important as this...
-
作者：Grapiglia, Geovani N.; Yuan, Jinyun; Yuan, Ya-xiang
作者单位：Universidade Federal do Parana; Coordenacao de Aperfeicoamento de Pessoal de Nivel Superior (CAPES); Chinese Academy of Sciences; Academy of Mathematics & System Sciences, CAS
摘要：A nonlinear stepsize control framework for unconstrained optimization was recently proposed by Toint (Optim Methods Softw 28:82-95, 2013), providing a unified setting in which the global convergence can be proved for trust-region algorithms and regularization schemes. The original analysis assumes that the Hessians of the models are uniformly bounded. In this paper, the global convergence of the nonlinear stepsize control algorithm is proved under the assumption that the norm of the Hessians c...
-
作者：Drusvyatskiy, D.; Vavasis, S. A.; Wolkowicz, H.
作者单位：University of Washington; University of Washington Seattle; University of Waterloo
摘要：We investigate geometric features of the unit ball corresponding to the sum of the nuclear norm of a matrix and the norm of its entries-a common penalty function encouraging joint low rank and high sparsity. As a byproduct of this effort, we develop a calculus (or algebra) of faces for general convex functions, yielding a simple and unified approach for deriving inequalities balancing the various features of the optimization problem at hand, at the extreme points of the solution set.
-
作者：Leston-Rey, Mario; Wakabayashi, Yoshiko
作者单位：Universidade de Sao Paulo
摘要：We study a framework, which we call a generalized kernel system, introduced by Frank. We prove some integral and fractional packing theorems in this framework which, in particular, imply an improvement over the best known upper bounds on the size of the packing, one due to Gabow and Manu, for packing arborescences from a given root, and another, due to Schrijver, for packing branchings from given root-sets in a digraph.
