-
作者：Briceno-Arias, Luis M.; Combettes, Patrick L.
作者单位：Universidad Tecnica Federico Santa Maria; North Carolina State University
摘要：We introduce a framework based on Rockafellar's perturbation theory to analyze and solve general nonsmooth convex minimization and monotone inclusion problems involving nonlinearly composed functions as well as linear compositions. Such problems have been investigated only from a primal perspective and only for nonlinear compositions of smooth functions in finite-dimensional spaces in the absence of linear compositions. In the context of Banach spaces, the proposed perturbation analysis serves...
-
作者：Kizilkale, Can; Vohra, Rakesh
作者单位：University of California System; University of California Berkeley; United States Department of Energy (DOE); Lawrence Berkeley National Laboratory; University of Pennsylvania; University of Pennsylvania
摘要：Trades based on bilateral (indivisible) contracts can be represented by a network. Vertices correspond to agents, whereas arcs represent the nonprice elements of a bilateral contract. Given prices for each arc, agents choose the incident arcs that maximize their utility. We enlarge the model to allow for polymatroidal constraints on the set of contracts that may be traded, which can be interpreted as modeling limited one-for-one substitution. We show that, for two-sided markets, there exists a...
-
作者：Caldentey, Rene; Giloni, Avi; Hurvich, Clifford; Zhang, Yichen
作者单位：University of Chicago; Yeshiva University; New York University; Purdue University System; Purdue University
摘要：We study the interplay between inventory replenishment policies and information sharing in the context of a two-tier supply chain with a single supplier and a single retailer serving an independent and identically distributed Gaussian market demand. We investigate how the retailer's inventory policy impacts the supply chain's cumulative expected long-term average inventory costs C in two extreme information-sharing cases: (a) full information sharing and (b) no information sharing. To find the...
-
作者：Eckstein, Stephan; Nutz, Marcel
作者单位：Swiss Federal Institutes of Technology Domain; ETH Zurich; Columbia University; Columbia University
摘要：We study the convergence of divergence-regularized optimal transport as the reg-ularization parameter vanishes. Sharp rates for general divergences including relative entropy or Lp regularization, general transport costs, and multimarginal problems are obtained. A novel methodology using quantization and martingale couplings is suitable for noncompact marginals and achieves, in particular, the sharp leading-order term of entropically regularized 2-Wasserstein distance for marginals with a fini...
-
作者：Eden, Alon; Feldman, Michal; Fiat, Amos; Goldner, Kira; Karlin, Anna R.
作者单位：Hebrew University of Jerusalem; Tel Aviv University; Boston University; University of Washington; University of Washington Seattle
摘要：. We study combinatorial auctions with interdependent valuations, where each agent i has a private signal si that captures her private information and the valuation func-tion of every agent depends on the entire signal profile, s(s1,:::,sn). The literature in eco-nomics shows that the interdependent model gives rise to strong impossibility results and identifies assumptions under which optimal solutions can be attained. The computer sci-ence literature provides approximation results for simple...
-
作者：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 remaining time first scheduling algorithm. In case of a tie, processor sharing is utilized. 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 approximation ...
-
作者：Branzei, Simina; Sandomirskiy, Fedor
作者单位：Purdue University System; Purdue University; California Institute of Technology
摘要：We study the problem of allocating divisible bads (chores) among multiple agents with additive utilities when monetary transfers are not allowed. The competitive rule is known for its remarkable fairness and efficiency properties in the case of goods. This rule was extended to chores by Bogomolnaia, Moulin, Sandomirskiy, and Yanovskaya. For both goods and chores, the rule produces Pareto optimal and envy-free allocations. In the case of goods, the outcome of the competitive rule can be easily ...
-
作者：Csoka, Peter; Heringsc, Jean-Jacques
作者单位：Corvinus University Budapest; Tilburg University
摘要：We study bankruptcy problems in financial networks in the presence of general bankruptcy laws. The set of clearing payment matrices is shown to be a lattice, which guarantees the existence of a greatest clearing payment and a least clearing payment. Multiplicity of clearing payment matrices is both a theoretical and a practical concern. We present a new condition for uniqueness that generalizes all the existing conditions proposed in the literature. Our condition depends on the decomposition o...
-
作者：Li, Jiaxiang; Ma, Shiqian; Srivastava, Tejes
作者单位：University of Minnesota System; University of Minnesota Twin Cities; Rice University; University of Chicago
摘要：We consider a class of Riemannian optimization problems where the objective is the sum of a smooth function and a nonsmooth function considered in the ambient space. This class of problems finds important applications in machine learning and statistics, such as sparse principal component analysis, sparse spectral clustering, and orthogonal dictionary learning. We propose a Riemannian alternating direction method of multipliers (ADMM) to solve this class of problems. Our algorithm adopts easily...
-
作者：Charisopoulos, Vasileios; Davis, Damek
作者单位：Cornell University
摘要：Subgradient methods comprise a fundamental class of nonsmooth optimization algorithms. Classical results show that certain subgradient methods converge sublinearly for general Lipschitz convex functions and converge linearly for convex functions that grow sharply away from solutions. Recent work has moreover extended these results to certain nonconvex problems. In this work, we seek to improve the complexity of these algorithms by asking the following question. Is it possible to design a super...
