2023

最新文章

• Pure characteristics demand models and distributionally robust mathematical programs with stochastic complementarity constraints AI翻译
  作者：Jiang, Jie; Chen, Xiaojun
  作者单位：Chongqing University; Hong Kong Polytechnic University
  摘要：We formulate pure characteristics demand models under uncertainties of probability distributions as distributionally robust mathematical programs with stochastic complementarity constraints (DRMP-SCC). For any fixed first-stage variable and a random realization, the second-stage problem of DRMP-SCC is a monotone linear complementarity problem (LCP). To deal with ambiguity of probability distributions of the involved random variables in the stochastic LCP, we use the distributionally robust app...
• On the optimality of pseudo-polynomial algorithms for integer programming AI翻译
  作者：Fomin, Fedor, V; Panolan, Fahad; Ramanujan, M. S.; Saurabh, Saket
  作者单位：University of Bergen; Indian Institute of Technology System (IIT System); Indian Institute of Technology (IIT) - Hyderabad; University of Warwick; Homi Bhabha National Institute; Institute of Mathematical Sciences (IMSc) India
  摘要：In the classic Integer Programming Feasibility (IPF) problem, the objective is to decide whether, for a given m x n matrix A and an m-vector b = (b(1) ..... b(m) ), there is a non-negative integer n-vector x such that Ax = b. Solving (IPF) is an important step in numerous algorithms and it is important to obtain an understanding of the precise complexity of this problem as a function of natural parameters of the input. The classic pseudo-polynomial time algorithm of Papadimitriou [J. ACM 1981]...
• Affine-invariant contracting-point methods for Convex Optimization AI翻译
  作者：Doikov, Nikita; Nesterov, Yurii
  摘要：In this paper, we develop new affine-invariant algorithms for solving composite convex minimization problems with bounded domain. We present a general framework of Contracting-Point methods, which solve at each iteration an auxiliary subproblem restricting the smooth part of the objective function onto contraction of the initial domain. This framework provides us with a systematic way for developing optimization methods of different order, endowed with the global complexity bounds. We show tha...
• Implications, conflicts, and reductions for Steiner trees AI翻译
  作者：Rehfeldt, Daniel; Koch, Thorsten
  作者单位：Zuse Institute Berlin; Technical University of Berlin
  摘要：The Steiner tree problem in graphs (SPG) is one of the most studied problems in combinatorial optimization. In the past 10 years, there have been significant advances concerning approximation and complexity of the SPG. However, the state of the art in (practical) exact solution of the SPG has remained largely unchallenged for almost 20 years. While the DIMACS Challenge 2014 and the PACE Challenge 2018 brought renewed interest into Steiner tree problems, even the best new SPG solvers cannot mat...
• Multicriteria cuts and size-constrained k-cuts in hypergraphs AI翻译
  作者：Beideman, Calvin; Chandrasekaran, Karthekeyan; Xu, Chao
  作者单位：University of Illinois System; University of Illinois Urbana-Champaign
  摘要：We address counting and optimization variants of multicriteria global min-cut and size-constrained min-k-cut in hypergraphs. 1. For an r-rank n-vertex hypergraph endowed with t hyperedge-cost functions, we show that the number of multiobjective min-cuts is O(r2(tr) n(3t-1)). In particular, this shows that the number of parametric min-cuts in constant rank hypergraphs for a constant number of criteria is strongly polynomial, thus resolving an open question by Aissi et al. (Math Program 154(1-2)...
• Inexact accelerated high-order proximal-point methods AI翻译
  作者：Nesterov, Yurii
  摘要：In this paper, we present a new framework of bi-level unconstrained minimization for development of accelerated methods in Convex Programming. These methods use approximations of the high-order proximal points, which are solutions of some auxiliary parametric optimization problems. For computing these points, we can use different methods, and, in particular, the lower-order schemes. This opens a possibility for the latter methods to overpass traditional limits of the Complexity Theory. As an e...
• Global convergence of the gradient method for functions definable in o-minimal structures AI翻译
  作者：Josz, Cedric
  作者单位：Columbia University
  摘要：We consider the gradient method with variable step size for minimizing functions that are definable in o-minimal structures on the real field and differentiable with locally Lipschitz gradients. We prove that global convergence holds if continuous gradient trajectories are bounded, with the minimum gradient norm vanishing at the rate o(1/k) if the step sizes are greater than a positive constant. If additionally the gradient is continuously differentiable, all saddle points are strict, and the ...
• Efficient joint object matching via linear programming AI翻译
  作者：De Rosa, Antonio; Khajavirad, Aida
  作者单位：University System of Maryland; University of Maryland College Park; Lehigh University
  摘要：Joint object matching, also known as multi-image matching, namely, the problem of finding consistent partial maps among all pairs of objects within a collection, is a crucial task in many areas of computer vision. This problem subsumes bipartite graph matching and graph partitioning as special cases and is NP-hard, in general. We develop scalable linear programming (LP) relaxations with theoretical performance guarantees for joint object matching. We start by proposing a new characterization o...
• Strong valid inequalities for a class of concave submodular minimization problems under cardinality constraints AI翻译
  作者：Yu, Qimeng; Kucukyavuz, Simge
  作者单位：Northwestern University
  摘要：We study the polyhedral convex hull structure of a mixed-integer set which arises in a class of cardinality-constrained concave submodular minimization problems. This class of problems has an objective function in the form of f (alpha(T)x), where f is a univariate concave function, a is a non-negative vector, and x is a binary vector of appropriate dimension. Such minimization problems frequently appear in applications that involve risk-aversion or economies of scale. We propose three classes ...
• Probability maximization via Minkowski functionals: convex representations and tractable resolution AI翻译
  作者：Bardakci, I. E.; Jalilzadeh, A.; Lagoa, C.; Shanbhag, U., V
  作者单位：Bartin University; University of Arizona; Pennsylvania Commonwealth System of Higher Education (PCSHE); Pennsylvania State University; Pennsylvania State University - University Park
  摘要：In this paper, we consider the maximizing of the probability P { zeta vertical bar zeta is an element of K(x) } over a closed and convex set chi, a special case of the chance-constrained optimization problem. Suppose K(x) (sic) { zeta is an element of K vertical bar c(x, zeta) >= 0}, and zeta is uniformly distributed on a convex and compact set K and c(x, zeta) is defined as either c(x, zeta) (sic) 1 - vertical bar zeta(T)x vertical bar(m) where m >= 0 (Setting A) or c(x, zeta) (sic) Tx - zeta...