-
作者：Herings, P. Jean-Jacques; Zhan, Yang
作者单位：Tilburg University; Nanjing University; Nanjing University
-
作者：Applegate, David; Hinder, Oliver; Lu, Haihao; Lubin, Miles
作者单位：Alphabet Inc.; Google Incorporated; Pennsylvania Commonwealth System of Higher Education (PCSHE); University of Pittsburgh; University of Chicago
摘要：First-order primal-dual methods are appealing for their low memory overhead, fast iterations, and effective parallelization. However, they are often slow at finding high accuracy solutions, which creates a barrier to their use in traditional linear programming (LP) applications. This paper exploits the sharpness of primal-dual formulations of LP instances to achieve linear convergence using restarts in a general setting that applies to alternating direction method of multipliers (ADMM), primal...
-
作者：Ling, Shuyang
作者单位：New York University; NYU Shanghai
摘要：Group synchronization aims to recover the group elements from their noisy pairwise measurements. It has found many applications in community detection, clock synchronization, and joint alignment problem. This paper focuses on the orthogonal group synchronization which is often used in cryo-EM and computer vision. However, it is generally NP-hard to retrieve the group elements by finding the least squares estimator. In this work, we first study the semidefinite programming (SDP) relaxation of t...
-
作者：Bertsimas, Dimitris; den Hertog, Dick; Pauphilet, Jean; Zhen, Jianzhe
作者单位：Massachusetts Institute of Technology (MIT); University of Amsterdam; University of London; London Business School
摘要：Robust convex constraints are difficult to handle, since finding the worst-case scenario is equivalent to maximizing a convex function. In this paper, we propose a new approach to deal with such constraints that unifies most approaches known in the literature and extends them in a significant way. The extension is either obtaining better solutions than the ones proposed in the literature, or obtaining solutions for classes of problems unaddressed by previous approaches. Our solution is based o...
-
作者：Cardinal, Jean; Steiner, Raphael
作者单位：Universite Libre de Bruxelles; Swiss Federal Institutes of Technology Domain; ETH Zurich
摘要：We consider the computational problem of finding short paths in the skeleton of the perfect matching polytope of a bipartite graph. We prove that unless P = NP, there is no polynomial-time algorithm that computes a path of constant length between two vertices at distance two of the perfect matching polytope of a bipartite graph. Conditioned on P not equal NP, this disproves a conjecture by Ito et al. (SIAM J Discrete Math 36(2):1102-1123, 2022). Assuming the Exponential Time Hypothesis we prov...
-
作者：Bot, Radu Ioan; Csetnek, Erno Robert; Dang-Khoa Nguyen
作者单位：University of Vienna
摘要：This work aims to minimize a continuously differentiable convex function with Lipschitz continuous gradient under linear equality constraints. The proposed inertial algorithm results from the discretization of the second-order primal-dual dynamical system with asymptotically vanishing damping term addressed by Bot and Nguyen (J. Differential Equations 303:369-406, 2021), and it is formulated in terms of the Augmented Lagrangian associated with the minimization problem. The general setting we c...
-
作者：Kozak, David; Molinari, Cesare; Rosasco, Lorenzo; Tenorio, Luis; Villa, Silvia
作者单位：Istituto Italiano di Tecnologia - IIT; University of Genoa; Colorado School of Mines; University of Genoa
摘要：We propose and analyze a randomized zeroth-order optimization method based on approximating the exact gradient by finite differences computed in a set of orthogonal random directions that changes with each iteration. A number of previously proposed methods are recovered as special cases including spherical smoothing, coordinate descent, as well as discretized gradient descent. Our main contribution is proving convergence guarantees as well as convergence rates under different parameter choices...
-
作者：Nam Ho-Nguyen; Wright, Stephen J.
作者单位：University of Sydney; University of Wisconsin System; University of Wisconsin Madison
摘要：We study a model for adversarial classification based on distributionally robust chance constraints. We show that under Wasserstein ambiguity, the model aims to minimize the conditional value-at-risk of the distance to misclassification, and we explore links to adversarial classification models proposed earlier and to maximum-margin classifiers. We also provide a reformulation of the distributionally robust model for linear classification, and show it is equivalent to minimizing a regularized ...
-
作者：Barbato, Michele; Grappe, Roland; Lacroix, Mathieu; Lancini, Emiliano
作者单位：University of Milan; Centre National de la Recherche Scientifique (CNRS); CNRS - Institute for Information Sciences & Technologies (INS2I)
摘要：Given a graph G = (V, E) and an integer k >= 1, the graph H = (V, F), where F is a family of elements (with repetitions allowed) of E, is a k-edge-connected spanning subgraph of G if H cannot be disconnected by deleting any k - 1 elements of F. The convex hull of incidence vectors of the k-edge-connected subgraphs of a graph G forms the k-edge-connected subgraph polyhedron of G. We prove that this polyhedron is box-totally dual integral if and only if G is series-parallel. In this case, we als...
-
作者：Rockafellar, R. Tyrrell
作者单位：University of Washington; University of Washington Seattle
摘要：Second-order sufficient conditions for local optimality have long been central to designing solution algorithms and justifying claims about their convergence. Here a far-reaching extension of such conditions, called variational sufficiency, is explored in territory beyond just classical nonlinear programming. Variational sufficiency is already known to support multiplier methods that are able, even without convexity, to achieve problem decomposition, but further insight has been needed into ho...
