-
作者：Jiang, Rujun; Li, Xudong
作者单位：Fudan University
摘要：In this paper, we study the local variational geometry of the optimal solution set of the trust region subproblem (TRS), which minimizes a general, possibly nonconvex, quadratic function over the unit ball. Specifically, we demonstrate that a Holderian error bound holds globally for the TRS with modulus 1/4, and the Kurdyka-Lojasiewicz (KL) inequality holds locally for the TRS with a KL exponent 3/4 at any optimal solution. We further prove that, unless in a special case, the Holderian error b...
-
作者：Ni, Guyan; Li, Ying
作者单位：National University of Defense Technology - China
摘要：In this paper, we establish an equivalence relation between partially symmetric tensors and homogeneous polynomials, prove that every partially symmetric tensor has a partially symmetric canonical polyadic (CP)-decomposition, and present three semidefinite relaxation algorithms. The first algorithm is used to check whether there exists a positive partially symmetric real CP-decomposition for a partially symmetric real tensor and give a decomposition if it has. The second algorithm is used to c...
-
作者：Giesecke, Kay; Shkolnik, Alexander
作者单位：Stanford University; University of California System; University of California Santa Barbara
摘要：Stochastic point process models of event timing are common in many areas, including finance, insurance, and reliability. Monte Carlo simulation is often used to perform computations for these models. The standard sampling algorithm, which is based on a time-change argument, is widely applicable but generates biased simulation estimators. This article develops and analyzes a change of probability measure that can reduce or even eliminate the bias without restricting the scope of the algorithm. ...
-
作者：Benjamin, Bachi; Shiran, Rachmilevitch
作者单位：University of Haifa
摘要：Myerson proved that every linear and weakly Paretian choice function is utilitarian. We revisit his model and result for the two-person case and supplement it with an only if direction. That is, we characterize the class of linear and weakly Paretian two-person choice functions. It turns out that these are the utilitarian functions with an egalitarian tie-breaking.
-
作者：Gfrerer, Helmut; Ye, Jane J.; Zhou, Jinchuan
作者单位：Johannes Kepler University Linz; University of Victoria; Shandong University of Technology
摘要：In this paper, we study second-order optimality conditions for nonconvex setconstrained optimization problems. For a convex set-constrained optimization problem, it is well known that second-order optimality conditions involve the support function of the second-order tangent set. In this paper, we propose two approaches for establishing second-order optimality conditions for the nonconvex case. In the first approach, we extend the concept of the support function so that it is applicable to gen...
-
作者：Badenbroek, Riley; de Klerk, Etienne
作者单位：Erasmus University Rotterdam - Excl Erasmus MC; Erasmus University Rotterdam; Tilburg University
摘要：We develop a short-step interior point method to optimize a linear function over a convex body assuming that one only knows a membership oracle for this body. The approach is based a sketch of a universal interior point method using the so-called entropic barrier. It is well known that the gradient and Hessian of the entropic barrier can be approximated by sampling from Boltzmann-Gibbs distributions and the entropic barrier was shown to be self-concordant. The analysis of our algorithm uses pr...
-
作者：Ghuge, Rohan; Nagarajan, Viswanath
作者单位：University of Michigan System; University of Michigan
摘要：We consider the following general network design problem. The input is an asymmetric metric (V, c), root r is an element of V, monotone submodular function f: 2(V) -> R+, and budget B. The goal is to find an r-rooted arborescence T of cost at most B that maximizes f(T). Our main result is a simple quasi-polynomial time O(log k/log log k)-approximation algorithm for this problem, in which k <= |V| is the number of vertices in an optimal solution. As a consequence, we obtain an O(log (2)k/log lo...
-
作者：Bayraktar, Erhan; Cecchin, Alekos; Cohen, Asaf; Delarue, Francois
作者单位：University of Michigan System; University of Michigan; Institut Polytechnique de Paris; ENSTA Paris; Ecole Polytechnique; Universite Cote d'Azur; Centre National de la Recherche Scientifique (CNRS)
摘要：Forcing finite state mean field games by a relevant form of common noise is a subtle issue, which has been addressed only recently. Among others, one possible way is to subject the simplex valued dynamics of an equilibrium by a so-called Wright-Fisher noise, very much in the spirit of stochastic models in population genetics. A key feature is that such a random forcing preserves the structure of the simplex, which is nothing but, in this setting, the probability space over the state space of t...
-
作者：Wang, Weina; Maguluri, Siva Theja; Srikant, R.; Ying, Lei
作者单位：Carnegie Mellon University; University System of Georgia; Georgia Institute of Technology; University of Illinois System; University of Illinois Urbana-Champaign; University of Illinois System; University of Illinois Urbana-Champaign; University of Michigan System; University of Michigan
摘要：We consider a connection-level model proposed by Massoulie ' and Roberts for bandwidth sharing among file transfer flows in a communication network. We study weighted proportionally fair sharing policies and establish explicit-form bounds on the weighted sum of the expected numbers of flows on different routes in heavy traffic. The bounds are linear in the number of critically loaded links in the network, and they hold for a class of phase-type file-size distributions; that is, the bounds are ...
-
作者：Pennanen, Teemu
作者单位：University of London; King's College London
摘要：This paper proposes a simple descriptive model of discrete-time double auction markets for divisible assets. As in the classical models of exchange economies, we consider a finite set of agents described by their initial endowments and preferences. Instead of the classical Walrasian-type market models, however, we assume that all trades take place in a centralized double auction where the agents communicate through sealed limit orders for buying and selling. We find that, under nonstrategic bi...
