-
作者：Cui, Xingbang; Zhang, Liping
作者单位：Tsinghua University
摘要：The progressive hedging algorithm (PHA) is an effective solution method for solving monotone stochastic variational inequalities (SVIs). However, this validity is based on the assumption of global maximal monotonicity. In this paper, we propose a localized PHA for solving nonmonotone SVIs and show that its validity is based on the weaker assumption of locally elicitable maximal monotonicity. Furthermore, we prove that such assumption holds when the mapping involved in the SVI is locally elicit...
-
作者：Yu, Huizhen
作者单位：University of Alberta
摘要：This paper concerns discrete-time infinite-horizon stochastic control systems with Borel state and action spaces and universally measurable policies. We study optimization problems on strategic measures induced by the policies in these systems. The results are then applied to risk-neutral and risk-sensitive Markov decision processes to establish the measurability of the optimal value functions and the existence of universally measurable, randomized or nonrandomized, e-optimal policies, for a v...
-
作者：Birgin, Ernesto G.; Gardenghi, John L.; Laurain, Antoine
作者单位：Universidade de Sao Paulo; Universidade de Brasilia; University of Duisburg Essen
摘要：The problem of covering a two-dimensional bounded set with a fixed number of minimum-radius identical disks is studied in the present work. Bounds on the optimal radius are obtained for a certain class of nonsmooth domains, and an asymptotic expansion of the bounds as the number of disks goes to infinity is provided. The proof is based on the approximation of the set to be covered by hexagonal honeycombs and on the thinnest covering property of the regular hexagonal lattice arrangement in the ...
-
作者：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...
-
作者：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...
-
作者：Biro, Peter; Klijn, Flip; Klimentova, Xenia; Viana, Ana
作者单位：Corvinus University Budapest; Consejo Superior de Investigaciones Cientificas (CSIC); Barcelona School of Economics; INESC TEC; Instituto Politecnico do Porto
摘要：In a housing market of Shapley and Scarf, each agent is endowed with one indivisible object and has preferences over all objects. An allocation of the objects is in the (strong) core if there exists no (weakly) blocking coalition. We show that, for strict preferences, the unique strong core allocation respects improvement-if an agent's object becomes more desirable for some other agents, then the agent's allotment in the unique strong core allocation weakly improves. We extend this result to w...
-
作者：Baldwin, Elizabeth; Goldberg, Paul W.; Klemperer, Paul; Lock, Edwin
作者单位：University of Oxford; University of Oxford
摘要：This paper develops algorithms to solve strong-substitutes product-mix auctions: it finds competitive equilibrium prices and quantities for agents who use this auction's bidding language to truthfully express their strong-substitutes preferences over an arbitrary number of goods, each of which is available in multiple discrete units. Our use of the bidding language and the information it provides contrasts with existing algorithms that rely on access to a valuation or demand oracle. We compute...
-
作者：Milz, Johannes; Surowiec, Thomas M.
作者单位：University System of Georgia; Georgia Institute of Technology
摘要：Optimal values and solutions of empirical approximations of stochastic optimization problems can be viewed as statistical estimators of their true values. From this perspective, it is important to understand the asymptotic behavior of these estimators as the sample size goes to infinity. This area of study has a long tradition in stochastic programming. However, the literature is lacking consistency analysis for problems in which the decision variables are taken from an infinite-dimensional sp...
-
作者：Brustle, Johannes; Correa, Jose; Duetting, Paul; Verdugo, Victor
作者单位：University of London; London School Economics & Political Science; Universidad de Chile; Alphabet Inc.; Google Incorporated; Universidad de O'Higgins
摘要：We study the competition complexity of dynamic pricing relative to the optimal auction in the fundamental single-item setting. In prophet inequality terminology, we compare the expected reward Am(F) achievable by the optimal online policy on m independent and identically distributed (i.i.d.) random variables distributed according to F to the expected maximum Mn(F)of n i.i.d. draws from F. We ask how big m has to be to ensure that (1 + epsilon)Am(F) >_ Mn(F) for all F. We resolve this question ...
-
作者：Naegele, Martin; Santiago, Richard; Zenklusen, Rico
作者单位：University of Bonn
摘要：A long-standing open question in integer programming is whether integer programs with constraint matrices with bounded subdeterminants are efficiently solvable. An important special case thereof are congruency-constrained integer programs min{c(inverted perpendicular)x : Tx <= b, gamma(inverted perpendicular)x = r (mod m), x is an element of Z(n)} with a totally unimodular constraint matrix T. Such problems are shown to be polynomial-time solvable for m = 2, which led to an efficient algorithm...
