-
作者：Lei, Jinlong; Shanbhag, Uday, V; Pang, Jong-Shi; Sen, Suvrajeet
作者单位：Pennsylvania Commonwealth System of Higher Education (PCSHE); Pennsylvania State University; Pennsylvania State University - University Park; University of Southern California
摘要：In this paper, we consider a stochastic Nash game in which each player minimizes a parameterized expectation-valued convex objective function. In deterministic regimes, proximal best-response (BR) schemes have been shown to be convergent under a suitable spectral property associated with the proximal BR map. However, a direct application of this scheme to stochastic settings requires obtaining exact solutions to stochastic optimization problems at each iteration. Instead, we propose an inexact...
-
作者：Moriguchi, Satoko; Murota, Kazuo; Tamura, Akihisa; Tardella, Fablo
作者单位：Tokyo Metropolitan University; Keio University; Sapienza University Rome
摘要：For a function defined on the integer lattice, we consider discrete versions of midpoint convexity, which offer a unifying framework for discrete convexity of functions, including integral convexity, L-(sic)-convexity, and submodularity. By considering discrete midpoint convexity for all pairs at l(infinity)-distance equal to 2 or not smaller than 2, we identify new classes of discrete convex functions, called locally and globally discrete midpoint convex functions. These functions enjoy nice ...
-
作者：Balkanski, Eric; Leme, Renato Paes
作者单位：Harvard University; Alphabet Inc.; Google Incorporated
摘要：Gross substitutability is a central concept in economics and is connected to important notions in discrete convex analysis, number theory, and the analysis of greedy algorithms in computer science. Many different characterizations are known for this class, but providing a constructive description remains a major open problem. The construction problem asks how to construct all gross substitutes from a class of simpler functions using a set of operations. Because gross substitutes are a natural ...
-
作者：Guasoni, Paolo; Meireles-Rodrigues, Andrea A.
作者单位：Boston University; Dublin City University; University of York - UK
摘要：This paper finds optimal portfolios for the reference-dependent preferences by Koszegi and Rabin with piecewise linear gain-loss utility in a one-period model with a safe and a risky asset. If the return of the risky asset is highly dispersed relative to its potential gains, two personal equilibria arise, one of them including risky investments and the other one only safe holdings. In the same circumstances, the risky personal equilibrium entails market participation that decreases with loss a...
-
作者：Frangioni, Antonio; Gentile, Claudio; Hungerford, James
作者单位：University of Pisa; Consiglio Nazionale delle Ricerche (CNR); Istituto di Analisi dei Sistemi ed Informatica Antonio Ruberti (IASI-CNR)
摘要：We study the problem of decomposing the Hessian matrix of a mixed integer convex quadratic program (MICQP) into the sum of positive semidefinite 2 x 2 matrices. Solving this problem enables the use of perspective reformulation techniques for obtaining strong lower bounds for MICQPs with semicontinuous variables but a nonseparable objective function. An explicit formula is derived for constructing 2 x 2 decompositions when the underlying matrix is weakly scaled diagonally dominant, and necessar...
-
作者：Etessami, Kousha; Stewart, Alistair; Yannakakis, Mihalis
作者单位：University of Edinburgh; University of Southern California; Columbia University
摘要：We show that one can compute the least nonnegative solution (also known as the least fixed point) for a system of probabilistic min (max) polynomial equations, to any desired accuracy epsilon > 0 in time polynomial in both the encoding size of the system and in log(1/epsilon). These are Bellman optimality equations for important classes of infinite-state Markov decision processes (MDPs), including branching MDPs (BMDPs), which generalize classic multitype branching stochastic processes. We thu...
-
作者：Aravkin, Aleksandr; Davis, Damek
作者单位：University of Washington; University of Washington Seattle; Cornell University
摘要：In this paper, we show how to transform any optimization problem that arises from fitting a machine learning model into one that (1) detects and removes contaminated data from the training set while (2) simultaneously fitting the trimmed model on the uncontaminated data that remains. To solve the resulting nonconvex optimization problem, we introduce a fast stochastic proximal-gradient algorithm that incorporates prior knowledge through nonsmooth regularization. For data sets of size n, our ap...
