Mathematics of Operations Research

最新文章

• Splitting Guarantees for Prophet Inequalities via Nonlinear Systems AI翻译
  作者：Brustle, Johannes; Perez-Salazar, Sebastian; Verdugo, Victor
  作者单位：Sapienza University Rome; Rice University; Rice University; Pontificia Universidad Catolica de Chile; Pontificia Universidad Catolica de Chile
  摘要：The prophet inequality is one of the cornerstone problems in optimal stopping theory and has become a crucial tool for designing sequential algorithms in Bayesian settings. In the i.i.d. k-selection prophet inequality problem, we sequentially observe n nonnegative random values sampled from a known distribution. Each time, a decision is made to accept or reject the value, and under the constraint of accepting at most k items. For k = 1, Hill and Kertz [Ann. Probab. 1982] provided an upper boun...
• A Riemannian Alternating Descent Ascent Algorithmic Framework for Nonconvex-Linear Minimax Problems on Riemannian Manifolds AI翻译
  作者：Xu, Meng; Jiang, Bo; Liu, Ya-Feng; So, Anthony Man-Cho
  作者单位：Chinese Academy of Sciences; Nanjing Institute of Geology & Paleontology, CAS; Academy of Mathematics & System Sciences, CAS; Chinese Academy of Sciences; University of Chinese Academy of Sciences, CAS; Nanjing Normal University; Beijing University of Posts & Telecommunications; Chinese University of Hong Kong
  摘要：In this paper, we consider a class of nonconvex-linear minimax problems on Riemannian manifolds, which find wide applications in machine learning and signal processing. For solving this class of problems, we develop a flexible Riemannian alternating descent ascent (RADA) algorithmic framework. Within this framework, we propose two easy-to-implement yet efficient algorithms that alternately perform one or multiple projected/Riemannian gradient descent steps and a proximal gradient ascent step a...
• First-Order Methods for Stochastic Variational Inequality Problems with Function Constraints AI翻译
  作者：Boob, Digvijay; Deng, Qi; Khalafi, Mohammad
  作者单位：Southern Methodist University; Shanghai Jiao Tong University
  摘要：We study monotone function-constrained variational inequalities (FCVIs) whose feasible region is the intersection of a projection-friendly set and several convex function constraints; both the operator and the constraint functions may be smooth, nonsmooth, and/or stochastic. Computing the projection operator is challenging for FCVIs. We introduce the adaptive operator extrapolation (AdOpEx) method, which employs an operator extrapolation on the Karush-Kuhn-Tucker operator of the FCVI in a smoo...
• Lipschitz Stability of Least-Squares Problems Regularized by Functions with C2-Cone Reducible Conjugates AI翻译
  作者：Cui, Ying; Hoheisel, Tim; Nghia, Tran T. A.; Sun, Defeng
  作者单位：University of California System; University of California Berkeley; McGill University; Oakland University; Hong Kong Polytechnic University
  摘要：In this paper, we study Lipschitz continuity of the solution mappings of regularized least-squares problems for which the convex regularizers have (Fenchel) conjugates that are C2-cone reducible. Our approach, by using Robinson's strong regularity on the dual problem, allows us to obtain new characterizations of Lipschitz stability that rely solely on firstorder information, thus bypassing the need to explore second-order information (curvature) of the regularizer. We show that these solution ...
• On Stability of the Scholtes Regularization for Mathematical Programs with Complementarity Constraints AI翻译
  作者：Lammel, Sebastian; Shikhman, Vladimir
  作者单位：Technische Universitat Chemnitz
  摘要：For mathematical programs with complementarity constraints (MPCC), we study the stability properties of their Scholtes regularization. Our goal is to relate nondegenerate C-stationary points of MPCC with nondegenerate Karush-Kuhn-Tucker points of the Scholtes regularization up to their topological type. As it is standard in the framework of Morse theory, the topological types are captured by the C-index and the quadratic index, respectively. It turns out that a change of the topological type f...
• AdaBB: Adaptive Barzilai-Borwein Method for Convex Optimization AI翻译
  作者：Zhou, Danqing; Ma, Shiqian; Yang, Tunfeng
  作者单位：Nanjing University; Rice University
  摘要：In this paper, we propose AdaBB, an adaptive gradient method based on the Barzilai-Borwein stepsize. The algorithm is line-search-free and parameter-free, and it essentially provides a convergent variant of the Barzilai-Borwein method for general convex optimization problems. We analyze the ergodic convergence of the objective function value and the convergence of the iterates for solving general convex optimization problems. Compared with existing works along this line of research, our algori...
• Streaming Submodular Maximization Under Matroid Constraints AI翻译
  作者：Feldman, Moran; Liu, Paul; Norouzi-Fard, Ashkan; Svensson, Ola; Zenklusen, Rico
  作者单位：University of Haifa; Stanford University; Alphabet Inc.; Google Incorporated; Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne
  摘要：Recent progress in (semi-)streaming algorithms for monotone submodular function maximization has led to tight results for a simple cardinality constraint. However, current techniques fail to give a similar understanding for natural generalizations, including matroid constraints. This paper aims at closing this gap. For a single matroid of rank k (i.e., any solution has cardinality at most k), our main results are a single-pass streaming algorithm that uses Oe(k) memory and achieves an approxim...
• Centrality in Normalized Stochastic Networks AI翻译
  作者：Mostagir, Mohamed; Siderius, James
  作者单位：University of Michigan System; University of Michigan; Dartmouth College
  摘要：In many applications, network effects are normalized: in opinion dynamics, agents take a weighted average of their friends' beliefs, or in social media models, users' adoption decisions depends on the fraction of their peers who also adopt. The outcome of these processes share a common network property: a weighted Katz-Bonacich centrality but one defined over the network's row-normalized adjacency matrix, which measures relative spillovers. This row-normalized centrality measure is well-unders...
• Coderivatives at Infinity of Set-Valued Mappings with Applications to Optimization AI翻译
  作者：Kim, Do Sang; Pham, Tien-Son; Tung, Nguyen Minh; Van Tuyen, Nguyen
  作者单位：Pukyong National University; Dalat University; Ho Chi Minh University of Banking (HUB)
  摘要：In this paper, the concept of coderivatives at infinity of set-valued mappings is introduced. Well-posedness properties at infinity of set-valued mappings as well as Mordukhovich's criterion at infinity are established. Optimality conditions at infinity in set-valued optimization are also provided. The obtained results, which give new information even in the classical cases of smooth single-valued mappings, provide complete characterizations of the properties under consideration in the setting...
• Cooperation, Correlation, and Competition in Ergodic N-Player Games and Mean-Field Games of Singular Controls: A Case Study AI翻译
  作者：Cannerozzi, Federico; Ferrari, Giorgio
  作者单位：University of Bielefeld; University of Milan
  摘要：We consider a class of N-player games and mean-field games of singular controls with ergodic performance criterion, providing a benchmark case for irreversible investment games featuring mean-field interaction and strategic complementarities. The state of each player follows a geometric Brownian motion controlled additively through a nondecreasing process, whereas agents seek to maximize a long-term average reward functional with a power-type instantaneous profit under strategic complementarit...