-
作者：Fawzi, Hamza
作者单位：University of Cambridge
摘要：It is well known that state-of-the-art linear programming solvers are more efficient than their semidefinite programming counterparts and can scale to much larger problem sizes. This leads us to consider the question, how well can we approximate semidefinite programs with linear programs? In this paper, we prove lower bounds on the size of linear programs that approximate the positive semidefinite cone. Let D be the set of n x n positive semidefinite matrices of trace equal to one. We prove tw...
-
作者：Arieli, Itai; Mueller-Frank, Manuel
作者单位：Technion Israel Institute of Technology; University of Navarra; IESE Business School
摘要：This paper analyzes a sequential social learning game with a general utility function, state, and action space. We show that asymptotic learning holds for every utility function if and only if signals are totally unbounded, that is, the support of the private posterior probability of every event contains both zero and one. For the case of finitely many actions, we provide a sufficient condition for asymptotic learning depending on the given utility function. Finally, we establish that for the ...
-
作者：Kalinowski, Thomas; Mohammadian, Sogol
作者单位：University of New England; University of Newcastle
摘要：We study a certain polytope depending on a graph G and a parameter beta is an element of(0,1) that arises from embedding the Hamiltonian cycle problem in a discounted Markov decision process. Literature suggests a conjecture a lower bound on the proportion of feasible bases corresponding to Hamiltonian cycles in the set of all feasible bases. We make progress toward a proof of the conjecture by proving results about the structure of feasible bases. In particular, we prove three main results: (...
-
作者：Mehlitz, Patrick; Zemkoho, Alain B.
作者单位：Brandenburg University of Technology Cottbus; University of Southampton
摘要：This paper is concerned with the derivation of first- and second-order sufficient optimality conditions for optimistic bilevel optimization problems involving smooth functions. First-order sufficient optimality conditions are obtained by estimating the tangent cone to the feasible set of the bilevel program in terms of initial problem data. This is done by exploiting several different reformulations of the hierarchical model as a singlelevel problem. To obtain second-order sufficient optimalit...
-
作者：Bramson, Maury; D'Auria, Bernardo; Walton, Neil
作者单位：University of Minnesota System; University of Minnesota Twin Cities; Universidad Carlos III de Madrid; University of Manchester
摘要：Consider a switched queueing network with general routing among its queues. TShe MaxWeight policy assigns available service by maximizing the objective function Sigma(j)Q(j)sigma(j) among the different feasible service options, where Q(j) denotes queue size and sigma(j) denotes the amount of service to be executed at queue j. MaxWeight is a greedy policy that does not depend on knowledge of arrival rates and is straightforward to implement. These properties and its simple formulation suggest M...
-
作者：Kruk, Lukasz
作者单位：Maria Curie-Sklodowska University
摘要：We investigate minimal and locally edge minimal fluid models for real-time resource-sharing networks, which are natural counterparts of pathwise minimal and locally edge minimal performance processes for the corresponding real-time stochastic systems. The models under study arise as optimizers of appropriate idleness-based criteria within a suitable family of fluid models for a given resource-sharing network. The class of minimal fluid models is fairly general, corresponding to efficient servi...
-
作者：Boxma, Onno; Mandjes, Michel
作者单位：Eindhoven University of Technology; University of Amsterdam
摘要：The aim of this paper is to analyze a general class of storage processes, in which the rate at which the storage level increases or decreases is assumed to be an affine function of the current storage level, and, in addition, both upward and downward jumps are allowed. To do so, we first focus on a related insurance risk model, for which we determine the ruin probability at an exponentially distributed epoch jointly with the corresponding undershoot and overshoot, given that the capital level ...
-
作者：Chen, Xi; Wang, Yining; Zhou, Yuan
作者单位：New York University; State University System of Florida; University of Florida; University of Illinois System; University of Illinois Urbana-Champaign
摘要：We study the dynamic assortment planning problem, where for each arriving customer, the seller offers an assortment of substitutable products and the customer makes the purchase among offered products according to an uncapacitated multinomial logit (MNL) model. Because all the utility parameters of theMNLmodel are unknown, the seller needs to simultaneously learn customers' choice behavior and make dynamic decisions on assortments based on the current knowledge. The goal of the seller is to ma...
-
作者：Jiang, Bo; Wang, Haoyue; Zhang, Shuzhong
作者单位：Shanghai University of Finance & Economics; Massachusetts Institute of Technology (MIT); University of Minnesota System; University of Minnesota Twin Cities; Shenzhen Research Institute of Big Data; The Chinese University of Hong Kong, Shenzhen
摘要：This paper is concerned with finding an optimal algorithm for minimizing a composite convex objective function. The basic setting is that the objective is the sum of two convex functions: the first function is smooth with up to the dth-order derivative information available, and the second function is possibly nonsmooth, but its proximal tensor mappings can be computed approximately in an efficient manner. The problem is to find-in that setting-the best possible (optimal) iteration complexity ...
