Mathematics of Operations Research

最新文章

• (No-)Betting Pareto Optima Under Rank-Dependent Utility AI翻译
  作者：Beissner, Patrick; Boonen, Tim; Ghossoub, Mario
  作者单位：Australian National University; University of Hong Kong; University of Waterloo
  摘要：In a pure-exchange economy with no aggregate uncertainty, we characterize in closed form and full generality Pareto-optimal allocations between two agents who maximize (nonconcave) rank-dependent utilities (RDU). We then derive a necessary and sufficient condition for Pareto optima to be no-betting allocations (i.e., deterministic allocations or full insurance allocations). This condition depends only on the probability weighting functions of the two agents and not on their (concave) utility o...
• An Stochastic Differential Equation Perspective on Stochastic Convex Optimization AI翻译
  作者：Maule, Rodrigo; Fadili, Jalal; Attouch, Hedy
  作者单位：Universite de Caen Normandie; Centre National de la Recherche Scientifique (CNRS); Centre National de la Recherche Scientifique (CNRS); Universite de Montpellier
  摘要：In this paper, we analyze the global and local behavior of gradient-like flows under stochastic errors toward the aim of solving convex optimization problems with noisy gradient input. We first study the unconstrained differentiable convex case, using a stochastic differential equation where the drift term is minus the gradient of the objective function and the diffusion term is either bounded or square-integrable. In this context, under Lipschitz continuity of the gradient, our first main res...
• Secretaries with Advice br AI翻译
  作者：Dutting, Paul; Lattanzi, Silvio; Leme, Renato Paes; Vassilvitskii, Sergei
  作者单位：Alphabet Inc.; Google Incorporated; Alphabet Inc.; Google Incorporated
  摘要：The secretary problem is probably the purest model of decision making under uncertainty. In this paper, we ask which advice we can give the algorithm to improve its suc-cess probability. We propose a general model that unifies a broad range of problems: from the classic secretary problem with no advice to the variant where the quality of a secretary is drawn from a known distribution and the algorithm learns each candidate's quality on arrival, more modern versions of advice in the form of sam...
• Limit Theorems for Default Contagion and Systemic Risk AI翻译
  作者：Amini, Hamed; Cao, Zhongyuan; Sulemb, Agnes
  作者单位：State University System of Florida; University of Florida; Universite PSL; Universite Paris-Dauphine
  摘要：We consider a general tractable model for default contagion and systemic risk in a heterogeneous financial network subjected to an exogenous macroeconomic shock. We show that under certain regularity assumptions, the default cascade model can be transformed into a death process problem represented by a balls-and-bins model. We state various limit theorems regarding the final size of default cascades. Under appropriate assumptions on the degree and threshold distributions, we prove that the fin...
• A Stochastic Sequential Quadratic Optimization Algorithm for Nonlinear-Equality-Constrained Optimization with Rank-Deficient Jacobians AI翻译
  作者：Berahas, Albert S.; Curtis, Frank E.; O'Neill, Michael J.; Robinson, Daniel P.
  作者单位：University of Michigan System; University of Michigan; Lehigh University; University of North Carolina; University of North Carolina Chapel Hill; University of North Carolina School of Medicine
  摘要：A sequential quadratic optimization algorithm is proposed for solving smooth nonlinear-equality-constrained optimization problems in which the objective function is defined by an expectation. The algorithmic structure of the proposed method is based on a step decomposition strategy that is known in the literature to be widely effective in practice, wherein each search direction is computed as the sum of a normal step (toward linearized feasibility) and a tangential step (toward objective decre...
• Zero-Sum Games and Linear Programming Duality br AI翻译
  作者：von Stengel, Bernhard
  作者单位：University of London; London School Economics & Political Science
  摘要：The minimax theorem for zero-sum games is easily proved from the strong duality theorem of linear programming. For the converse direction, the standard proof by Dantzig is known to be incomplete. We explain and combine classical theorems about solv-ing linear equations with nonnegative variables to give a correct alternative proof more directly than Adler. We also extend Dantzig's game so that any max-min strategy gives either an optimal LP solution or shows that none exists
• Joint Mixability and Notions of Negative Dependence AI翻译
  作者：Koike, Takaaki; Lin, Liyuan; Wang, Ruodu
  作者单位：Hitotsubashi University; University of Waterloo
  摘要：A joint mix (JM) is a random vector with a constant component-wise sum. The dependence structure of a joint mix minimizes some common objectives, such as the variance of the component-wise sum, and it is regarded as a concept of extremal negative dependence. In this paper, we explore the connection between the joint mix structure and popular notions of negative dependence in statistics, such as negative correlation dependence, negative orthant dependence, and negative association. A joint mix ...
• Inner Moreau Envelope of Nonsmooth Conic Chance-Constrained Optimization Problems AI翻译
  作者：van Ackooij, Wim; Perez-Aros, Pedro; Soto, Claudia; Vilches, Emilio
  作者单位：Electricite de France (EDF); Universidad de O'Higgins; Universidad de Chile
  摘要：Optimization problems with uncertainty in the constraints occur in many applications. Particularly, probability functions present a natural form to deal with this situation. Nevertheless, in some cases, the resulting probability functions are nonsmooth, which motivates us to propose a regularization employing the Moreau envelope of a scalar representation of the vector inequality. More precisely, we consider a probability function that covers most of the general classes of probabilistic constr...
• Stochastic Subgradient Descent Escapes Active Strict Saddles on Weakly Convex Functions AI翻译
  作者：Bianchi, Pascal; Hachem, Walid; Schechtman, Sholom
  作者单位：IMT - Institut Mines-Telecom; Institut Polytechnique de Paris; Telecom Paris; Universite Gustave-Eiffel; Centre National de la Recherche Scientifique (CNRS)
  摘要：In nonsmooth stochastic optimization, we establish the nonconvergence of the stochastic subgradient descent (SGD) to the critical points recently called active strict saddles by Davis and Drusvyatskiy. Such points lie on a manifold M, where the function f has a direction of second-order negative curvature. Off this manifold, the norm of the Clarke subdifferential of f is lower-bounded. We require two conditions on f. The first assumption is a Verdier stratification condition, which is a refine...
• Naive Feature Selection: A Nearly Tight Convex Relaxation for Sparse Naive Bayes AI翻译
  作者：Askari, Armin; d'Aspremont, Alexandre; El Ghaoui, Laurent
  作者单位：University of California System; University of California Berkeley; Centre National de la Recherche Scientifique (CNRS); Universite PSL; Ecole Normale Superieure (ENS)
  摘要：Because of its linear complexity, naive Bayes classification remains an attractive supervised learning method, especially in very large-scale settings. We propose a sparse version of naive Bayes, which can be used for feature selection. This leads to a combinatorial maximum-likelihood problem, for which we provide an exact solution in the case of binary data, or a bound in the multinomial case. We prove that our convex relaxation bounds become tight as the marginal contribution of additional f...