3期

最新文章

• Quantile Optimization via Multiple-Timescale Local Search for Black-Box Functions AI翻译
  作者：Hu, Jiaqiao; Song, Meichen; Fu, Michael C.
  作者单位：State University of New York (SUNY) System; Stony Brook University; University System of Maryland; University of Maryland College Park; University System of Maryland; University of Maryland College Park
  摘要：We consider quantile optimization of black-box functions that are estimated with noise. We propose two new iterative three-timescale local search algorithms. The first algorithm uses an appropriately modified finite-difference-based gradient estimator that requires 2d + 1 samples of the black-box function per iteration of the algorithm, where d is the number of decision variables (dimension of the input vector). For higher-dimensional problems, this algorithm may not be practical if the black-...
• Designing Service Menus for Bipartite Queueing Systems AI翻译
  作者：Caldentey, Rene; Hillas, Lisa Aoki; Gupta, Varun
  作者单位：University of Chicago; University of Auckland; Northwestern University
  摘要：We consider a multiclass, multiserver queueing system, in which customers of different types have heterogeneous preferences over the many servers available. The goal of the service provider is to design a menu of service classes that balances two competing objectives: (1) maximize customers' average matching reward and (2) minimize customers' average waiting time. A service class corresponds to a single queue served by a subset of servers under a first come, first served-assign longest idle se...
• Optimal Diagonal Preconditioning AI翻译
  作者：Qu, Zhaonan; Gao, Wenzhi; Hinder, Oliver; Ye, Yinyu; Zhou, Zhengyuan
  作者单位：Stanford University; Stanford University; Stanford University; Pennsylvania Commonwealth System of Higher Education (PCSHE); University of Pittsburgh; New York University
  摘要：Preconditioning has long been a staple technique in optimization, often applied to reduce the condition number of a matrix and speed up the convergence of algorithms. Although there are many popular preconditioning techniques in practice, most lack guarantees on reductions in condition number, and the degree to which we can improve over existing heuristic preconditioners remains an important question. In this paper, we study the problem of optimal diagonal preconditioning that achieves maximal...
• Robust CARA Optimization AI翻译
  作者：Chen, Li; Sim, Melvyn
  作者单位：University of Sydney; National University of Singapore
  摘要：We propose robust optimization models and their tractable approximations that cater for ambiguity -averse decision makers whose underlying risk preferences are consistent with constant absolute risk aversion (CARA). Specifically, we focus on maximizing the worst -case expected exponential utility where the underlying uncertainty is generated from a set of stochastically independent factors with ambiguous marginals. To obtain computationally tractable formulations, we propose a hierarchy of app...
• Stochastic Optimization Approaches for an Operating Room and Anesthesiologist Scheduling Problem AI翻译
  作者：Tsang, Man Yiu; Shehadeh, Karmel S.; Curtis, Frank E.; Hochman, Beth R.; Brentjens, Tricia E.
  作者单位：Lehigh University; Columbia University; NewYork-Presbyterian Hospital; Columbia University; NewYork-Presbyterian Hospital
  摘要：We propose combined allocation, assignment, sequencing, and scheduling problems under uncertainty involving multiple operation rooms (ORs), anesthesiologists, and surgeries as well as methodologies for solving such problems. Specifically, given sets of ORs, regular anesthesiologists, on -call anesthesiologists, and surgeries, our methodologies solve the following decision -making problems simultaneously: (1) an allocation problem that decides which ORs to open and which on -call anesthesiologi...
• When Does the Gittins Policy Have Asymptotically Optimal Response Time Tail in the M/G/1? AI翻译
  作者：Scully, Ziv; van Kreveld, Lucas
  作者单位：Cornell University; Eindhoven University of Technology
  摘要：We consider scheduling in the M/G/1 queue with unknown job sizes. It is known that the Gittins policy minimizes mean response time in this setting. However, the behavior of the tail of response time under Gittins is poorly understood, even in the largeresponse -time limit. Characterizing Gittins's asymptotic tail behavior is important because if Gittins has optimal tail asymptotics, then it simultaneously provides optimal mean response time and good tail performance. In this work, we give the ...
• Data-Driven Compositional Optimization in Misspecified Regimes AI翻译
  作者：Yang, Shuoguang; Fang, Ethan X.; Shanbhag, Uday V.
  作者单位：Hong Kong University of Science & Technology; Duke University; Pennsylvania Commonwealth System of Higher Education (PCSHE); Pennsylvania State University; Pennsylvania State University - University Park
  摘要：As systems grow in size, scale, and intricacy, the challenges of misspecification become even more pronounced. In this paper, we focus on parametric misspecification in regimes complicated by risk and nonconvexity. When this misspecification may be resolved via a parallel learning process, we develop data -driven schemes for resolving a broad class of misspecified stochastic compositional optimization problems. Notably, this rather broad class of compositional problems can contend with challen...
• Column-Randomized Linear Programs: Performance Guarantees and Applications AI翻译
  作者：Akchen, Yi-Chun; Misic, Velibor V.
  作者单位：University of London; University College London; University of California System; University of California Los Angeles
  摘要：We propose a randomized method for solving linear programs with a large number of columns but a relatively small number of constraints. Because enumerating all the columns is usually unrealistic, such linear programs are commonly solved by column generation, which is often still computationally challenging because of the intractability of the subproblem in many applications. Instead of iteratively introducing one column at a time as in column generation, our proposed method involves sampling a...
• An Exact Solution to Wordle AI翻译
  作者：Bertsimas, Dimitris; Paskov, Alex
  作者单位：Massachusetts Institute of Technology (MIT)
  摘要：In this paper, we propose and scale a framework based on exact dynamic programming to solve the game of Wordle, which has withstood many attempts to be solved by a variety of methods ranging from reinforcement learning to information theory. First, we derive a mathematical model of the game, present the resultant Bellman equation, and outline a series of optimizations to make this approach tractable. We then outline how to extend the framework to solve variants of the game-such as Wordle Hard ...
• Data-Driven Minimax Optimization with Expectation Constraints AI翻译
  作者：Yang, Shuoguang; Li, Xudong; Lan, Guanghui
  作者单位：Hong Kong University of Science & Technology; Fudan University; University System of Georgia; Georgia Institute of Technology
  摘要：Attention to data-driven optimization approaches, including the well-known stochastic gradient descent method, has grown significantly over recent decades, but data driven constraints have rarely been studied because of the computational challenges of projections onto the feasible set defined by these hard constraints. In this paper, we focus on the nonsmooth convex-concave stochastic minimax regime and formulate the data-driven constraints as expectation constraints. The minimax expectation c...