-
作者：Alacaoglu, Ahmet; Cevher, Volkan; Wright, Stephen J.
作者单位：University of British Columbia; Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne; University of Wisconsin Madison; University of Wisconsin System; University of Wisconsin Madison
摘要：We prove new complexity bounds for the primal-dual algorithm with random extrapolation and coordinate descent (PURE-CD), which has been shown to obtain promising practical performance for solving convex-concave min-max problems with bilinear coupling and dual separability. Such problems arise in many machine learning contexts, including empirical risk minimization, matrix games, and image processing. Our results either match or improve the best-known complexities of first-order algorithms for ...
-
作者：Li, Tianjiao; Lan, Guanghui
作者单位：University System of Georgia; Georgia Institute of Technology
摘要：Line search (or backtracking) procedures have been widely employed into first-order methods for solving convex optimization problems, especially those with unknown problem parameters (e.g., Lipschitz constant). In this paper, we show that line search is superfluous in attaining the optimal rate of convergence for solving a convex optimization problem whose parameters are not given a priori. In particular, we present a novel accelerated gradient descent type algorithm called auto-conditioned fa...
-
作者：Schade, Jamico; Sinha, Makrand; Weltge, Stefan
作者单位：Technical University of Munich; University of Illinois System; University of Illinois Urbana-Champaign
摘要：Standard mixed-integer programming formulations for the stable set problem on n-node graphs require n integer variables. We prove that this is almost optimal: We give a family of n-node graphs for which every polynomial-size MIP formulation requires Omega(n/log(2) n) integer variables. By a polyhedral reduction we obtain an analogous result for n-item knapsack problems. In both cases, this improves the previously known bounds of Omega(root n/log n) by Cevallos et al. (in Proceedings of the twe...
-
作者：Balas, Egon; Kazachkov, Aleksandr M.
作者单位：Carnegie Mellon University; State University System of Florida; University of Florida
摘要：We introduce V-polyhedral disjunctive cuts (VPCs) to generate valid inequalities from general disjunctions for a mixed-integer linear program. While optimization solvers critically rely on cuts, they only deploy limited families derivable from weak disjunctions, as the typical cut-generating linear program needs a costly higher-dimensional representation. The VPC framework mitigates this through a polar perspective to more efficiently use deeper, multiterm disjunctions, which partition the fea...
-
作者：Zhu, Landi; Gurbuzbalaban, Mert; Ruszczynski, Andrzej
作者单位：Rutgers University System; Rutgers University New Brunswick
摘要：We consider a distributionally robust stochastic optimization problem where the ambiguity sets are implicitly defined by the dual representation of the mean-semideviation risk measure. Utilizing the specific form of this risk measure, we reformulate the problem as a stochastic two-level composition optimization problem. In this setting, we consider a single time-scale algorithm, involving two versions of the inner function value tracking: linearized tracking of a continuously differentiable lo...
-
作者：Zhang, Liang; He, Niao; Muehlebach, Michael
作者单位：Swiss Federal Institutes of Technology Domain; ETH Zurich; Max Planck Society
摘要：Variational inequality problems are recognized for their broad applications across various fields including machine learning and operations research. First-order methods have emerged as the standard approach for solving these problems due to their simplicity and scalability. However, they typically rely on projection or linear minimization oracles to navigate the feasible set, which becomes computationally expensive in practical scenarios featuring multiple functional constraints. Existing eff...
-
作者：Del Pia, Alberto; Khajavirad, Aida
作者单位：University of Wisconsin System; University of Wisconsin Madison; University of Wisconsin System; University of Wisconsin Madison; Lehigh University
-
作者：Berczi, Kristof; Chandrasekaran, Karthekeyan; Kiraly, Tamas; Kulkarni, Shubhang
作者单位：Eotvos Lorand University; Eotvos Lorand University; University of Illinois System; University of Illinois Urbana-Champaign
摘要：We consider hypergraph network design problems where the goal is to construct a hypergraph that satisfies certain connectivity requirements. For graph network design problems where the goal is to construct a graph that satisfies certain connectivity requirements, the number of edges in every feasible solution is at most quadratic in the number of vertices. In contrast, for hypergraph network design problems, we might have feasible solutions in which the number of hyperedges is exponential in t...
-
作者：Majthoub Almoghrabi, Mohammed; Skutella, Martin; Warode, Philipp
作者单位：Technical University of Berlin; Humboldt University of Berlin
摘要：An unsplittable multiflow routes the demand of each commodity along a single path from its source to its sink node. As our main result, we prove that in series-parallel digraphs, any given multiflow can be expressed as a convex combination of unsplittable multiflows, where the total flow on any arc deviates from the given flow by less than the maximum demand of any commodity. This result confirms a 25-year-old conjecture by Goemans for single-source unsplittable flows, as well as a stronger re...
-
作者：Liberti, Leo; Sager, Sebastian; Wiegele, Angelika
作者单位：Institut Polytechnique de Paris; Ecole Polytechnique; Otto von Guericke University; University of Klagenfurt
