-
作者：Kruk, Lukasz
作者单位：Maria Curie-Sklodowska University
摘要：A single-server queue with renewal arrivals and generally distributed independent and identically distributed service times is considered. Customers are served using the longest job first (LJF) scheduling algorithm with first in, first out being used as a tiebreaking rule. We introduce a fluid model for the evolution of a measure-valued state descriptor of this queue, and we investigate its properties. We also prove a fluid limit theorem justifying our fluid model as the first order approximat...
-
作者：Aydin, Ugur; Saldi, Naci
作者单位：University of Illinois System; University of Illinois Urbana-Champaign; Ihsan Dogramaci Bilkent University
摘要：In this paper, we investigate the robustness of stationary mean-field equilibria in the presence of model uncertainties, specifically focusing on infinite-horizon discounted cost functions. To achieve this, we initially establish convergence conditions for value iterationbased algorithms in mean-field games. Subsequently, utilizing these results, we demonstrate that the mean-field equilibrium obtained through this value iteration algorithm remains robust even in the face of system dynamics mis...
-
作者：Shin, Sungho; Na, Sen; Anitescu, Mihai
作者单位：Massachusetts Institute of Technology (MIT); University System of Georgia; Georgia Institute of Technology; United States Department of Energy (DOE); Argonne National Laboratory; University of Chicago
摘要：This article presents a regret analysis for stochastic model predictive control (SMPC) in linear systems with quadratic performance index and additive and multiplicative uncertainties. Under a finite support assumption, the problem can be cast as a finitedimensional quadratic program, but the problem becomes quickly intractable as the problem size grows exponentially in the horizon length. SMPC aims to compute approximate solutions by solving a sequence of problems with truncated prediction ho...
-
作者：Giannakopoulos, Yiannis; Melissourgos, Themistoklis; Grosz, Alexander
作者单位：University of Glasgow; Technical University of Munich; University of Essex
摘要：We propose a unifying framework for smoothed analysis of combinatorial local optimization problems and show how a variety of problems within the complexity class PLS (Polynomial Local Search) can be cast within this model. This abstraction enables identifying key structural properties, and corresponding parameters, that determine the smoothed running time of local search dynamics. Our black-box tool provides concrete bounds on the expected maximum number of steps needed until local search reac...
-
作者：Jiao, Liguo; Lee, Jae Hyoung; Pham, Tien-Son
作者单位：Northeast Normal University - China; Pukyong National University; Dalat University
摘要：We are interested in optimality conditions for semialgebraic vector optimization problems with a situation in which generalized (weakly) nondominated points do exist but are not attained as image points of (weakly) efficient solutions. To this end, cones associated with unbounded semialgebraic sets at infinity are introduced and studied. Then, optimality conditions at infinity in terms of the Newton polyhedra of the objective mappings and of the cones associated with the constraint sets at inf...
-
作者：Ma, Jianhao; Fattahi, Salar
作者单位：University of Michigan System; University of Michigan
摘要：We explore the local landscape of low-rank matrix recovery, focusing on reconstructing a d1 x d2 matrix X* with rank r from m linear measurements, some potentially noisy. When the noise is distributed according to an outlier model, minimizing a nonsmooth & ell;1-loss with a simple subgradient method can often perfectly recover the ground truth matrix X*. Given this, a natural question is what optimization property (if any) enables such learning behavior. The most plausible answer is that the g...
-
作者：Faenza, Yuri; He, Chengyue; Sethuraman, Jay
作者单位：Columbia University
摘要：Scarf's algorithm gives a pivoting procedure to find a special vertex-a dominating vertex-in a down-monotone polytope. This paper studies the behavior of Scarf's algorithm when employed to find stable matchings in bipartite graphs. First, it proves that Scarf's algorithm can be implemented to run in polynomial time, showing the first positive result on its runtime in significant settings. Second, it shows an infinite family of instances where, no matter the pivoting rule and runtime, Scarf's a...
-
作者：Wang, Xingyu; Rhee, Chang-Han
作者单位：University of Amsterdam; Northwestern University
摘要：In this paper, we address rare-event simulation for heavy-tailed Levy processes with infinite activities. The presence of infinite activities poses a critical challenge, making it impractical to simulate or store the precise sample path of the Levy process. We present a rare-event simulation algorithm that incorporates an importance sampling strategy based on heavy-tailed large deviations, the stick-breaking approximation for the extrema of Levy processes, the Asmussen-Rosinski approximation, ...
-
作者：Hofer, Felix; Soner, H. Mete
作者单位：Princeton University
摘要：We propose a new mean-field game model with two states to study synchronization phenomena, and we provide a comprehensive characterization of stationary and dynamic equilibria along with their stability properties. The game undergoes a phase transition with increasing interaction strength. In the subcritical regime, the uniform distribution, representing incoherence, is the unique and stable stationary equilibrium. Above the critical interaction threshold, the uniform equilibrium becomes unsta...
-
作者：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 ...
