-
作者：Coey, Chris; Kapelevich, Lea; Vielma, Juan Pablo
作者单位：Massachusetts Institute of Technology (MIT)
摘要：Spectral functions on Euclidean Jordan algebras arise frequently in convex optimization models. Despite the success of primal-dual conic interior point solvers, there has been little work on enabling direct support for spectral cones, that is, proper nonsymmetric cones defined from epigraphs and perspectives of spectral functions. We propose simple logarithmically homogeneous barriers for spectral cones and we derive efficient, numerically stable procedures for evaluating barrier oracles such ...
-
作者：Herdegen, Martin; Muhle-Karbe, Johannes; Stebeggc, Florian
作者单位：University of Warwick; Imperial College London; Columbia University
摘要：We study one-shot Nash competition between an arbitrary number of identical dealers that compete for the order flow of a client. The client trades either because of proprietary information, exposure to idiosyncratic risk, or a mix of both trading motives. When quoting their price schedules, the dealers do not know the client's type but only its distribution, and in turn choose their price quotes to mitigate between adverse selection and inventory costs. Under essentially minimal conditions, we...
-
作者：Buke, Burak; Qin, Wenyi
作者单位：University of Edinburgh; Beihang University
摘要：We consider many-server queueing systems with heterogeneous exponential servers, for which the service rate of each server is a random variable drawn from a given distribution. We develop a framework for analyzing the heavy-traffic diffusion limits of these queues using measure-valued stochastic processes. We introduce the measure-valued fairness process, which denotes the proportion of cumulative idleness experienced by servers whose rates fall in a Borel subset of the support of the service ...
-
作者：Fibich, Gadi; Golan, Amit
作者单位：Tel Aviv University
摘要：Does a new product spread faster among heterogeneous or homogeneous consumers? We analyze this question using the stochastic discrete Bass model in which consumers may differ in their individual external influence rates {p(j)} and in their individual internal influence rates {q(j)}. When the network is complete and the heterogeneity is only manifested in {p(j)} or only in {q(j)}, it always slows down the diffusion, compared with the corresponding homogeneous network. When, however, consumers a...
-
作者：Gutman, David H.; Ho-Nguyen, Nam
作者单位：Texas Tech University System; Texas Tech University; University of Sydney
摘要：We extend coordinate descent to manifold domains and provide convergence analyses for geodesically convex and nonconvex smooth objective functions. Our key insight is to draw an analogy between coordinate blocks in Euclidean space and tangent subspaces of a manifold. Hence, our method is called tangent subspace descent (TSD). The core principle behind ensuring convergence of TSD is the appropriate choice of subspace at each iteration. To this end, we propose two novel conditions, the (C, r)-no...
-
作者：Pham Duy Khanh; Mordukhovich, Boris; Vo Thanh Phat
作者单位：Wayne State University
摘要：This paper proposes and develops a new Newton-type algorithm to solve subdifferential inclusions defined by subgradients of extended real-valued prox-regular functions. The proposed algorithm is formulated in terms of the second order subdifferential of such functions that enjoy extensive calculus rules and can be efficiently computed for broad classes of extended real-valued functions. Based on this and on the metric regularity and subregularity properties of subgradient mappings, we establis...
-
作者：Belomestny, Denis; Bender, Christian; Schoenmakers, John
作者单位：University of Duisburg Essen; Saarland University; Leibniz Association; Weierstrass Institute for Applied Analysis & Stochastics
摘要：In this paper, we consider optimal stopping problems in their dual form. In this way, the optimal stopping problem can be reformulated as a problem of stochastic average approximation (SAA) that can be solved via linear programming. By randomizing the initial value of the underlying process, we enforce solutions with zero variance while preserving the linear programming structure of the problem. A careful analysis of the randomized SAA algorithm shows that it enjoys favorable properties such a...
-
作者：Ashlagi, Itai; Burq, Maximilien; Dutta, Chinmoy; Jaillet, Patrick; Saberi, Amin; Sholley, Chris
作者单位：Stanford University; Massachusetts Institute of Technology (MIT)
摘要：Consider amatching problem, in which agents arrive to amarketplace over time and leave after some time periods. Agents can only bematchedwhile present in themarketplace. Each pair of agents can yield a different match value, and a social planner seeks to maximize the total value from matches over a finite time horizon. First we study the case in which vertices arrive in an adversarial order. For the case when agents depart in the order of arrival, we provide a randomized 1/4-competitive algori...
-
作者：Zhang, Liwei; Zhang, Yule; Xiao, Xiantao; Wu, Jia
作者单位：Dalian University of Technology; Dalian Maritime University
摘要：This paper considers the problem of minimizing a convex expectation function over a closed convex set, coupled with a set of inequality convex expectation constraints. We present a new stochastic approximation proximal method of multipliers to solve this convex stochastic optimization problem. We analyze regrets of the proposed method for solving convex stochastic optimization problems. Under mild conditions, we show that this method exhibits sublinear regret for both objective reduction and c...
-
作者：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 success 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 samp...
