Mathematics of Operations Research

最新文章

• Fair Congested Assignment AI翻译
  作者：Bogomolnaia, Anna; Moulin, Herve
  作者单位：University of Glasgow; Centre National de la Recherche Scientifique (CNRS)
  摘要：We must assign n agents to m posts subject to negative congestion; what assignment is fair and efficient? If congestion is anonymous (each agent adds one unit), it is always possible to assign each agent to one of the agent's top n out of the n x m feasible allocations. This ordinal interpretation of ex ante fairness can be adjusted if congestion is weighted (agent-specific). An assignment is competitive if I don't want to move to an empty post or to an occupied one at its current congestion l...
• Inexact Bregman Proximal Gradient Method and Its Inertial Variant with Absolute and Partial Relative Stopping Criteria AI翻译
  作者：Yang, Lei; Toh, Kim-Chuan
  作者单位：Sun Yat Sen University; National University of Singapore
  摘要：The Bregman proximal gradient method (BPGM), which uses the Bregman distance as a proximity measure in the iterative scheme, has recently been redeveloped for minimizing convex composite problems without the global Lipschitz gradient continuity assumption. This makes the BPGM appealing for a wide range of applications, and hence, it has received growing attention in recent years. However, most existing convergence results are obtained only under the assumption that the involved subproblems are...
• Convergence of Augmented Lagrangian Methods for Composite Optimization Problems AI翻译
  作者：Hang, Nguyen Thi Van; Sarabi, Ebrahim
  作者单位：Nanyang Technological University; Vietnam Academy of Science & Technology (VAST); University System of Ohio; Miami University
  摘要：Local convergence analysis of the augmented Lagrangian method (ALM) is established for a large class of composite optimization problems with nonunique Lagrange multipliers under a second-order sufficient condition. We present a new second-order variational property called the semistability of second subderivatives and demonstrate that it is widely satisfied for numerous classes of functions, which is important for applications in constrained and composite optimization problems. Using the latte...
• On Interim Envy-Free Allocation Lotteries AI翻译
  作者：Caragiannis, Ioannis; Kanellopoulos, Panagiotis; Kyropoulou, Maria
  作者单位：Aarhus University; University of Essex
  摘要：With very few exceptions, recent research in fair division has mostly focused on deterministic allocations. Deviating from this trend, we study the fairness notion of interim envy-freeness (iEF) for lotteries over allocations, which serves as a sweet spot between the too-stringent notion of ex post envy-freeness and the very weak notion of ex ante envy freeness. Our analysis relates iEF to other fairness notions as well and reveals trade-offs between iEF and efficiency. Even though several of ...
• Exactness and Effective Degree Bound of Lasserre's Relaxation for Polynomial Optimization over Finite Variety AI翻译
  作者：Hua, Zheng; Qu, Zheng
  作者单位：University of Hong Kong; Shenzhen University
  摘要：In this paper, we address the effective degree bound problem for Lasserre's hierarchy of moment-sum-of-squares (SOS) relaxations in polynomial optimization involving n variables. We assume that the first n equality constraint polynomials g1, ... ,gn do not share any nontrivial common complex zero locus at infinity and that the optimal solutions are nonsingular. Under these conditions, we derive an effective degree bound for the exactness of Lasserre's hierarchy. Importantly, the assumption of ...
• Riemannian Anderson Mixing Methods for Minimizing C2 Functions on Riemannian Manifolds AI翻译
  作者：Li, Zanyu; Bao, Chenglong
  作者单位：Tsinghua University; Tsinghua University; Yanqi Lake Beijing Institute of Mathematical Sciences & Applications
  摘要：Anderson mixing (AM) method is a popular approach for accelerating fixedpoint iterations by leveraging historical information from previous steps. In this paper, we introduce the Riemannian Anderson mixing (RAM) method, an extension of AM to Riemannian manifolds, and analyze its local linear convergence under reasonable assumptions. Unlike other extrapolation-based algorithms on Riemannian manifolds, RAM does not require computing the inverse retraction or inverse exponential mapping and has a...
• Variational Inequalities on Unbounded Domains for Zero-Sum Singular Controller vs. Stopper Games AI翻译
  作者：Bovo, Andrea; De Angelis, Tiziano; Issoglio, Elena
  作者单位：University of Turin; University of Turin
  摘要：We study a class of zero-sum games between a singular controller and a stopper over a finite-time horizon. The underlying process is a multidimensional (locally nondegenerate) controlled stochastic differential equation (SDE) evolving in an unbounded domain. We prove that such games admit a value and provide an optimal strategy for the stopper. The value of the game is shown to be the maximal solution in a suitable Sobolev class of a variational inequality of min-max type with an obstacle cons...
• On the Equivalence of Zero-Sum Games and Conic Programs AI翻译
  作者：Dimou, Nikos
  作者单位：University of North Carolina; University of North Carolina Chapel Hill; University of North Carolina School of Medicine
  摘要：We prove the almost equivalence of the minimax theorem and the strong duality theorem for a large class of games and conic programs. The previous fundamental results on the equivalence of linear programming and two-player zero-sum games with simplex strategy sets are extended to Banach spaces, and a comprehensive framework unifying two-player zero-sum games and conic linear programs is established. Specifically, we show that, for every zero-sum game with a bilinear payoff function and strategy...
• Unichain and Aperiodicity Are Sufficient for Asymptotic Optimality of Average-Reward Restless Bandits AI翻译
  作者：Hong, Yige; Xie, Qiaomin; Chen, Yudong; Wang, Weina
  作者单位：Carnegie Mellon University; University of Wisconsin System; University of Wisconsin Madison; University of Wisconsin System; University of Wisconsin Madison
  摘要：We consider the infinite-horizon, average-reward restless bandit problem in discrete time. We propose a new class of policies that are designed to drive a progressively larger subset of arms toward the optimal distribution. We show that our policies are root ffiffififfi asymptotically optimal with an O(1= N ) optimality gap for an N-armed problem, assuming only a unichain and aperiodicity assumption. Our approach departs from most existing work that focuses on index or priority policies, which...
• Network Revenue Management with Nonparametric Demand Learning: √T-Regret and Polynomial Dimension Dependency AI翻译
  作者：Miao, Sentao; Wang, Yining
  作者单位：University of Colorado System; University of Colorado Boulder
  摘要：This paper studies the classic price-based network revenue management (NRM) problem with demand learning. The retailer dynamically decides prices of n products over a finite selling season (of length T) subject to m resource constraints, with the purpose of maximizing the cumulative revenue. In this paper, we focus on a nonparametric demand model with some mild technical assumptions which are satisfied by most of the commonly used demand functions. We propose a robust ellipsoid method adapted ...