-
作者：Cohen, Asaf; Sun, Chuhao
作者单位：University of Michigan System; University of Michigan
摘要：In this paper, we examine the stationary relaxed singular control problem within a multidimensional framework for a single agent as well as its mean field game equivalent. We demonstrate that optimal relaxed controls exist for two problem classes: one driven by queueing control and the other by harvesting models. These relaxed controls are defined by random measures across the state and control spaces with the state process described as a solution to the associated martingale problem. By lever...
-
作者：Sanita, Laura; Verberk, Lucy
作者单位：Bocconi University; Eindhoven University of Technology
摘要：Capacitated network bargaining games are popular combinatorial games that involve the structure of matchings in graphs. We show that it is always possible to stabilize unit weight instances of this problem (that is, ensure that they admit a stable outcome) via capacity reduction and edge removal operations without decreasing the total value that the players can get. Furthermore, for general weighted instances, we show that computing a minimum amount of vertex capacity to reduce to make an inst...
-
作者：Liu, Wei; Lin, Qihang; Xu, Yangyang
作者单位：Rensselaer Polytechnic Institute; University of Iowa
摘要：Many recent studies on first-order methods (FOMs) focus on composite nonconvex nonsmooth optimization with linear and/or nonlinear function constraints. Upper (or worst-case) complexity bounds have been established for these methods. However, little can be claimed about their optimality, as no lower bound is known except for a few special smooth nonconvex cases. In this paper, we make the first attempt to establish lower complexity bounds of FOMs for solving a class of composite nonconvex nons...
-
作者：Kijima, Shuji; Shimizu, Nobutaka; Shiraga, Takeharu
作者单位：Shiga University; Institute of Science Tokyo; Chuo University
摘要：Real networks are often dynamic. In response to it, analyses of algorithms on dynamic networks attract more and more attention in network science and engineering. Random walks on dynamic graphs have also been actively investigated for over a decade, where in most cases the edge set changes but the vertex set is static. The vertex sets are also dynamic in many real networks. Motivated by the setting of random walks on growing networks, this paper introduces a simple model of graphs with an incr...
-
作者：Xing, Jie; Ma, Jingtang; Zheng, Harry
作者单位：Guizhou University of Finance & Economics; Southwestern University of Finance & Economics - China; Imperial College London
摘要：In this paper, we study a finite horizon optimal investment stopping problem with an unobservable random variable for the return of a risky asset. Using the Bayesian filter and the dual control approach, we transform the original primal problem into a dual finite horizon optimal stopping problem, which results in the dual value function satisfying a variational inequality with two state variables. For a class of utility functions that includes power utility and non-hyperbolic absolute risk ave...
-
作者：Boros, Endre; Lee, Joonhee
作者单位：Rutgers University System; Rutgers University New Brunswick; Rutgers University System; Rutgers University New Brunswick; Pace University
摘要：Hailperin (1965) introduced a linear programming formulation to a difficult family of problems, originally proposed by Boole (1854, 1868). Hailperin's model is computationally still difficult and involves an exponential number of variables (in terms of a typical input size for Boole's problem). Numerous papers provided efficiently computable bounds for the minimum and maximum values of Hailperin's model by using aggregation that is a monotone linear mapping to a lower dimensional space. In man...
-
作者：Goodwin, Ariel; Lewis, Adrian S.; Lopez-Acedo, Genaro; Nicolae, Adriana
作者单位：Cornell University; Cornell University; University of Sevilla; Babes Bolyai University from Cluj
摘要：The classical Euclidean subgradient algorithm extends, via tangent constructions and exponential maps, to geodesically convex optimization on manifolds. General complexity analysis for manifolds with an upper curvature bound of zero, as developed by Zhang and Sra in 2016 [Zhang H, Sra S (2016) First-order methods for geodesically convex optimization. Feldman V, Rakhlin A, Shamir O, eds. Proc. 29th Conf. Learn. Theory, vol. 49 (PMLR, New York), 1617-1638] depends unavoidably on an additional lo...
-
作者：Hafalir, Isa E.; Kojima, Fuhito; Yenmez, M. Bumin; Yokote, Koji
作者单位：University of Technology Sydney; University of Tokyo; Washington University (WUSTL); Durham University; Ozyegin University; Aoyama Gakuin University
摘要：We provide optimal solutions to an institution that has distributional objectives when choosing from a set of applications based on merit (or priority). For example, in college admissions, administrators may want to admit a diverse class in addition to choosing students with the highest qualifications. We provide a family of choice rules that maximize merit subject to attaining a level of the distributional objective. We study the desirable properties of choice rules in this family and use the...
-
作者：Luner, Alan; Grimmer, Benjamin
作者单位：Johns Hopkins University
摘要：This work considers the effect of averaging, and more generally extrapolation, of the iterates of gradient descent in smooth convex optimization. After running the method, rather than reporting the final iterate, one can report either a convex combination of the iterates (averaging) or a generic combination of the iterates (extrapolation). For several common stepsize sequences, including recently developed accelerated periodically long stepsize schemes, we show averaging cannot improve gradien...
-
作者：Han, Xia; Wang, Qiuqi; Wang, Ruodu; Xia, Jianming
作者单位：Nankai University; Nankai University; University System of Georgia; Georgia State University; University of Waterloo; Chinese Academy of Sciences
摘要：In the literature on risk measures, cash subadditivity was proposed to replace cash additivity, motivated by the presence of stochastic or ambiguous interest rates and defaultable contingent claims. Cash subadditivity has been traditionally studied together with quasi-convexity, in a way similar to cash additivity with convexity. In this paper, we study cash-subadditive risk measures without quasi-convexity. One of our major results is that a general cash-subadditive risk measure can be repres...
