Mathematics of Operations Research

最新文章

• A Momentum-Based Linearized Augmented Lagrangian Method for Nonconvex Constrained Stochastic Optimization AI翻译
  作者：Shi, Qiankun; Wang, Xiao; Wang, Hao
  作者单位：Sun Yat Sen University; ShanghaiTech University
  摘要：Nonconvex constrained stochastic optimization has emerged in many important application areas. Subject to general functional constraints, it minimizes the sum of an expectation function and a nonsmooth regularizer. Main challenges arise because of the stochasticity in the random integrand and the possibly nonconvex functional constraints. To address these issues, we propose a momentum-based linearized augmented Lagrangian method (MLALM). MLALM adopts a single-loop framework and incorporates a ...
• Convergence of Sinkhorn's Algorithm for Entropic Martingale Optimal Transport Problem AI翻译
  作者：Chen, Fan; Conforti, Giovanni; Ren, Zhenjie; Wang, Xiaozhen
  作者单位：Shanghai Jiao Tong University; University of Padua; Universite PSL; Universite Paris-Dauphine
  摘要：In this paper, we study the entropic martingale optimal transport (EMOT) problem on R. The investigation of the EMOT problem arises in the calibration problem of the stochastic volatility models, where martingale constraints reflect no-arbitrage pricing conditions under the risk-neutral measure, as originally proposed by Henry-Laborde`re. We first establish the dual formulation of the EMOT problem and prove that Sinkhorn's algorithm achieves an exponential convergence rate under mild condition...
• Algorithms for Budget-Constrained D-Optimal Design AI翻译
  作者：Wang, Jiaqi; Xie, Weijun; Ryzhov, Ilya O.
  作者单位：University System of Georgia; Georgia Institute of Technology; University System of Maryland; University of Maryland College Park
  摘要：D-optimal experimental design is a classical statistical problem in which one chooses a collection of data vectors, from some available large pool, in order to maximize a measure of predictive quality. In the classical formulation, the only constraint is on the cardinality of the collection, that is, the number of vectors chosen. We study a more general budget-constrained variant in which vectors have heterogeneous costs, and develop four new algorithms (two deterministic and two randomized) w...
• Online Allocation of Reusable Resources in Nonstationary Environments AI翻译
  作者：Zhang, Xilin; Cheung, Wang Chi
  作者单位：National University of Singapore
  摘要：We study a general reusable resource allocation model under both model uncertainty and nonstationarity. Our study involves a set of heterogeneous customers who arrive sequentially at the decision maker's (DM's) platform, each associated with a different customer type. Each arriving customer's type is drawn from an unknown and time-varying probability distribution. Upon observing the customer's type, the DM selects an allocation decision that generates a random amount of reward and occupies ran...
• Equilibrium Transport with Time-Inconsistent Costs AI翻译
  作者：Bayraktar, Erhan; Han, Bingyan
  作者单位：University of Michigan System; University of Michigan; Hong Kong University of Science & Technology (Guangzhou)
  摘要：Given two probability measures on sequential data, we investigate the transport problem with time-inconsistent preferences in a discrete-time setting. Motivating examples are nonlinear objectives, state-dependent costs, and regularized optimal transport with general f-divergence. Under the bicausal constraint, we introduce the concept of equilibrium transport. Existence is proved in the semidiscrete Markovian case and the continuous non-Markovian case with strict quasiconvexity, whereas unique...
• Probabilistic Analysis of Edge Elimination for Euclidean TSP AI翻译
  作者：Zhong, Xianghui
  作者单位：University of Bonn
  摘要：One way to speed up the calculation of optimal traveling salesman problem tours in practice is eliminating edges that are certainly not in the optimal tour as a preprocessing step. In order to do so, several edge elimination approaches have been proposed in the past. In this work, we investigate two of them in the scenario where the input consists of n independently distributed random points in the two-dimensional unit square with density function bounded from above and below by arbitrary posi...
• Square-Root Regret Bounds for Continuous-Time Episodic Markov Decision Processes AI翻译
  作者：Gao, Xuefeng; Zhou, Xunyu
  作者单位：Chinese University of Hong Kong; Columbia University
  摘要：We study reinforcement learning for continuous-time Markov decision processes (MDPs) in the finite-horizon episodic setting. In contrast to discrete-time MDPs, the intertransition times of a continuous-time MDP are exponentially distributed with rate parameters depending on the state-action pair at each transition. We present a learning algorithm based on the methods of value iteration and upper confidence bound. We derive an upper bound on the worst case expected regret for the proposed algor...
• Denoising Diffusion Probabilistic Models Are Optimally Adaptive to Unknown Low Dimensionality AI翻译
  作者：Huang, Zhihan; Wei, Yuting; Chen, Yuxin
  作者单位：University of Pennsylvania
  摘要：The denoising diffusion probabilistic model (DDPM) has emerged as a mainstream generative model in generative artificial intelligence. Although sharp convergence guarantees have been established for the DDPM, the iteration complexity is, in general, proportional to the ambient data dimension, resulting in overly conservative theory that fails to explain its practical efficiency. This has motivated the recent work to investigate how the DDPM can achieve sampling speed-ups through automatic expl...
• Fair and Efficient Multi-resource Allocation for Cloud Computing: Beyond Dominant Resource Fairness AI翻译
  作者：Bei, Xiaohui; Li, Zihao; Luo, Junjie
  作者单位：Nanyang Technological University; National University of Singapore; Beijing Jiaotong University
  摘要：We study the problem of allocating multiple types of resources to agents with Leontief preferences. The classic Dominant Resource Fairness (DRF) mechanism satisfies several desired fairness and incentive properties, but is known to have poor performance in terms of social welfare approximation ratio. In this work, we propose a new approximation ratio measure, called fair-ratio, which is defined as the worst-case ratio between the optimal social welfare (resp. utilization) among all fair alloca...
• Robust Solutions to a System of Stochastic Vertical Linear Complementarity Problems AI翻译
  作者：Zha, Xiao; Allen-Zhao, Zhihua; Chen, Xiaojun
  作者单位：Hong Kong Polytechnic University; Xidian University
  摘要：We propose a stochastic minimization model to find a robust solution of a system of stochastic vertical linear complementarity problems. This model aims to minimize a risk function under stochastic vertical linear complementarity constraints. We reformulate the model with a finite support set as a linearly constrained piecewise smooth minimization problem by a penalty method. We prove the existence of exact penalty parameters regarding global and local minimizers. We define a smoothing functio...