-
作者：Black, Alexander E.
作者单位：Bowdoin College
摘要：The existence of a pivot rule for the simplex method that guarantees a polynomial run-time is a longstanding, fundamental open problem in the theory of linear programming. The most popular pivot rule for theoretical analysis is the shadow pivot rule, which solves a linear program by projecting the feasible region onto a polygon. It has been shown to perform in expected polynomial time on uniformly random instances and in smoothed analysis. In practice, the pivot rule of choice is the steepest ...
-
作者：Upadhyaya, Manu; Latafat, Puya; Giselsson, Pontus
作者单位：Lund University; IMT School for Advanced Studies Lucca
摘要：We develop a Lyapunov-based analysis of Korpelevich's extragradient method and show that it achieves an o(1/k) last-iterate convergence rate of the constructed Lyapunov function. This Lyapunov function simultaneously upper bounds several standard measures of optimality, which allows our analysis to sharpen existing last-iterate convergence guarantees for these measures. Moreover, the same analysis enables the design of a class of flexible extensions of the extragradient method in which extragr...
-
作者：Li, Yongchun; Xie, Weijun
作者单位：University System of Georgia; Georgia Institute of Technology
摘要：A Low-rank Spectral Optimization Problem (LSOP) minimizes a linear objective function subject to multiple two-sided linear inequalities intersected with a low-rank and spectral constrained domain. Although solving LSOP is generally NP-hard, its partial convexification (i.e., replacing the domain with its convex hull), termed LSOP-R, is often tractable and yields a high-quality solution. This motivates us to study the strength of LSOP-R. Specifically, we derive rank bounds for any extreme point...
-
作者：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...
-
作者：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...
