-
作者：Zamani, Moslem; Abbaszadehpeivasti, Hadi; de Klerk, Etienne
作者单位：Tilburg University; Universite Catholique Louvain
摘要：Recently, semidefinite programming performance estimation has been employed as a strong tool for the worst-case performance analysis of first order methods. In this paper, we derive new non-ergodic convergence rates for the alternating direction method of multipliers (ADMM) by using performance estimation. We give some examples which show the exactness of the given bounds. We also study the linear and R-linear convergence of ADMM in terms of dual objective. We establish that ADMM enjoys a glob...
-
作者：Li, Yongchun; Xie, Weijun
作者单位：University System of Georgia; Georgia Institute of Technology
摘要：The truncated singular value decomposition (SVD), also known as the best low-rank matrix approximation with minimum error measured by a unitarily invariant norm, has been applied to many domains such as biology, healthcare, among others, where high-dimensional datasets are prevalent. To extract interpretable information from the high-dimensional data, sparse truncated SVD (SSVD) has been used to select a handful of rows and columns of the original matrix along with the best low-rank approximat...
-
作者：Dussault, Jean-Pierre; Migot, Tangi; Orban, Dominique
作者单位：University of Sherbrooke; University of Sherbrooke; Universite de Montreal; Polytechnique Montreal
摘要：Adaptive cubic regularization (ARC) methods for unconstrained optimization compute steps from linear systems involving a shifted Hessian in the spirit of the Levenberg-Marquardt and trust-region methods. The standard approach consists in performing an iterative search for the shift akin to solving the secular equation in trust-region methods. Such search requires computing the Cholesky factorization of a tentative shifted Hessian at each iteration, which limits the size of problems that can be...
-
作者：Dunbar, Alex; Sinha, Saumya; Schaefer, Andrew J.
作者单位：Emory University; University of Minnesota System; University of Minnesota Twin Cities
摘要：Multiobjective integer programs (MOIPs) simultaneously optimize multiple objective functions over a set of linear constraints and integer variables. In this paper, we present continuous, convex hull and Lagrangian relaxations for MOIPs and examine the relationship among them. The convex hull relaxation is tight at supported solutions, i.e., those that can be derived via a weighted-sum scalarization of the MOIP. At unsupported solutions, the convex hull relaxation is not tight and a Lagrangian ...
-
作者：Cao, Liyuan; Berahas, Albert S.; Scheinberg, Katya
作者单位：Peking University; University of Michigan System; University of Michigan; Cornell University
摘要：In this paper, we present convergence guarantees for a modified trust-region method designed for minimizing objective functions whose value and gradient and Hessian estimates are computed with noise. These estimates are produced by generic stochastic oracles, which are not assumed to be unbiased or consistent. We introduce these oracles and show that they are more general and have more relaxed assumptions than the stochastic oracles used in prior literature on stochastic trust-region methods. ...
-
作者：Andreani, Roberto; Haeser, Gabriel; Mito, Leonardo M.; Ramirez, Hector
作者单位：Universidade Estadual de Campinas; Universidade de Sao Paulo; Universidad de Chile; Universidad de Chile
摘要：The constraint nondegeneracy condition is one of the most relevant and useful constraint qualifications in nonlinear semidefinite programming. It can be characterized in terms of any fixed orthonormal basis of the, let us say, l-dimensional kernel of the constraint matrix, by the linear independence of a set of l(l + 1)/2 derivative vectors. We show that this linear independence requirement can be equivalently formulated in a smaller set, of l derivative vectors, by considering all orthonormal...
-
作者：Ahrens, Markus; Henke, Dorothee; Rabenstein, Stefan; Vygen, Jens
作者单位：Dortmund University of Technology; University of Bonn
摘要：We develop new algorithmic techniques for VLSI detailed routing. First, we improve the goal-oriented version of Dijkstra's algorithm to find shortest paths in huge incomplete grid graphs with edge costs depending on the direction and the layer, and possibly on rectangular regions. We devise estimates of the distance to the targets that offer better trade-offs between running time and quality than previously known methods, leading to an overall speed-up. Second, we combine the advantages of the...
-
作者：Guenin, Bertrand; Heo, Cheolwon
作者单位：University of Waterloo; Korea Institute for Advanced Study (KIAS)
摘要：Even-cycle matroids are elementary lifts of graphic matroids. Pinch-graphic matroids are even-cycle matroids that are also elementary projections of graphic matroids. In this paper we analyze the structure of 1-, 2-, and 3-separations in these matroids. As a corollary we obtain a polynomial-time algorithm that reduces the problem of recognizing pinch-graphic matroids to internally 4-connected matroids. Combining this with earlier results (Guenin and Heo in Recognizing even-cycle and even-cut m...
-
作者：Beneteau, Laurine; Chalopin, Jeremie; Chepoi, Victor; Vaxes, Yann
作者单位：Universite de Toulon; Centre National de la Recherche Scientifique (CNRS); Aix-Marseille Universite
摘要：The median of a graph G with weighted vertices is the set of all vertices x minimizing the sum of weighted distances from x to the vertices of G. For any integer p = 2, we characterize the graphs in which, with respect to any non-negative weights, median sets always induce connected subgraphs in the pth power Gp of G. This extends some characterizations of graphs with connected medians (case p = 1) provided by Bandelt and Chepoi (SIAM J Discrete Math 15(2):268-282, 2002. https:// doi. org/10.1...
-
作者：Dey, Santanu S.; Dubey, Yatharth; Molinaro, Marco; Shah, Prachi
作者单位：University System of Georgia; Georgia Institute of Technology; Pontificia Universidade Catolica do Rio de Janeiro; Pontificia Universidade Catolica do Rio de Janeiro
摘要：Full strong-branching (henceforth referred to as strong-branching) is a well-known variable selection rule that is known experimentally to produce significantly smaller branch-and-bound trees in comparison to all other known variable selection rules. In this paper, we attempt an analysis of the performance of the strong-branching rule both from a theoretical and a computational perspective. On the positive side for strong-branching, we identify vertex cover as a class of instances where this r...
