-
作者：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 ...
-
作者：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...
-
作者：Kleer, Pieter
作者单位：Tilburg University
摘要：Logit dynamics is a form of randomized game dynamics in which players have a bias toward strategic deviations that give a higher improvement in cost. It is used extensively in practice. In congestion (or potential) games, the dynamics converge to the so-called Gibbs distribution over the set of all strategy profiles when interpreted as a Markov chain. In general, logit dynamics can converge slowly to the Gibbs distribution, but beyond that, not much is known about its algorithmic aspects, nor ...
-
作者：Dadush, Daniel; Koh, Zhuan Khye; Natura, Bento; Vegh, Laszlo A.
作者单位：University of London; London School Economics & Political Science
摘要：We present an accelerated or look-ahead version of the Newton-Dinkelbach method, a well-known technique for solving fractional and parametric optimization problems. This acceleration halves the Bregman divergence between the current iterate and the optimal solution within every two iterations. Using the Bregman divergence as a potential in conjunction with combinatorial arguments, we obtain strongly polynomial algorithms in three applications domains. (i) For linear fractional combinatorial op...
-
作者：Cao, Haoyang; Dianetti, Jodi; Ferrari, Giorgio
作者单位：Institut Polytechnique de Paris; ENSTA Paris; Ecole Polytechnique; University of Bielefeld
摘要：We study stationary mean field games with singular controls in which the representative player interacts with a long-time weighted average of the population through a discounted and ergodic performance criteria. This class of games finds natural applications in the context of optimal productivity expansion in dynamic oligopolies. We prove the existence and uniqueness of the mean field equilibria, which are completely characterized through nonlinear equations. Furthermore, we relate the mean fi...
-
作者：Cassel, Asaf; Mannor, Shie; Zeevi, Assaf
作者单位：Tel Aviv University; Technion Israel Institute of Technology; Technion Israel Institute of Technology; Columbia University; Columbia University
摘要：The stochastic multiarmed bandit (MAB) problem is a common model for sequential decision problems. In the standard setup, a decision maker has to choose at every instant between several competing arms; each of them provides a scalar random variable, referred to as a reward. Nearly all research on this topic considers the total cumulative reward as the criterion of interest. This work focuses on other natural objectives that cannot be cast as a sum over rewards but rather, more involved functio...
-
作者：Garber, Dan; Kaplan, Atara
作者单位：Technion Israel Institute of Technology
摘要：Convex optimization over the spectrahedron, that is, the set of all real n x n positive semidefinite matrices with unit trace, has important applications in machine learning, signal processing, and statistics, mainly as a convex relaxation for optimization problems with low-rank matrices. It is also one of the most prominent examples in the theory of first order methods for convex optimization in which non-Euclidean methods can be significantly preferable to their Euclidean counterparts. In pa...
-
作者：Rhee, Chang-Han; Glynn, Peter W.
作者单位：Northwestern University; Stanford University
摘要：We consider a family of Markov chains whose transition dynamics are affected by model parameters. Understanding the parametric dependence of (complex) performance measures of such Markov chains is often of significant interest. The derivatives and their continuity of the performance measures w.r.t. the parameters play important roles, for example, in numerical optimization of the performance measures, and quantification of the uncertainties in the performance measures when there are uncertaint...
-
作者：Lin, Tianyi; Jordan, Michael I.
作者单位：University of California System; University of California Berkeley; University of California System; University of California Berkeley
摘要：We propose and analyze a new dynamical system with a closed-loop control law in a Hilbert space H, aiming to shed light on the acceleration phenomenon for monotone inclusion problems, which unifies a broad class of optimization, saddle point, and variational inequality (VI) problems under a single framework. Given an operator A : H paired right arrows H that is maximal monotone, we propose a closed-loop control system that is governed by the operator I - (I + lambda(t)A)(-1), where a feedback ...
-
作者：Braun, Alexander; Kesselheim, Thomas
作者单位：University of Bonn
摘要：We design novel mechanisms for welfare maximization in two-sided markets. That is, there are buyers willing to purchase items and sellers holding items initially, both acting rationally and strategically in order to maximize utility. Our mechanisms are designed based on a powerful correspondence between two-sided markets and prophet inequalities. They satisfy individual rationality, dominant-strategy incentive compatibility, and budget balance constraints and give constant factor approximation...
