-
作者：von Stengel, Bernhard
作者单位：University of London; London School Economics & Political Science
摘要：The minimax theorem for zero-sum games is easily proved from the strong duality theorem of linear programming. For the converse direction, the standard proof by Dantzig is known to be incomplete. We explain and combine classical theorems about solving linear equations with nonnegative variables to give a correct alternative proof more directly than Adler. We also extend Dantzig's game so that any max-min strategy gives either an optimal LP solution or shows that none exists.
-
作者：Pichler, Alois; Schlotter, Ruben
作者单位：Technische Universitat Chemnitz
摘要：This paper extends dynamic control problems from a risk-neutral to a risk-averse setting. We establish a limit for consecutive risk-averse decision making by consistently and adequately nesting coherent risk measures. This approach provides a new perspective on multistage optimal control problems in continuous time. For the limiting case, we elaborate a new dynamic programming principle, which is risk averse, and give risk-averse Hamilton-Jacobi-Bellman equations by generalizing the infinitesi...
-
作者：Garg, Jugal; Hoefer, Martin; Mehlhorn, Kurt
作者单位：University of Illinois System; University of Illinois Urbana-Champaign; Goethe University Frankfurt; Max Planck Society
摘要：We study linear Fisher markets with satiation. In these markets, sellers have earning limits, and buyers have utility limits. Beyond applications in economics, they arise in the context of maximizing Nash social welfare when allocating indivisible items to agents. In contrast to markets with either earning or utility limits, markets with both limits have not been studied before. They turn out to have fundamentally different properties. In general, the existence of competitive equilibria is not...
-
作者：Hallak, Nadav; Teboulle, Marc
作者单位：Technion Israel Institute of Technology; Tel Aviv University
摘要：This paper develops a novel adaptive, augmented, Lagrangian-based method to address the comprehensive class of nonsmooth, nonconvex models with a nonlinear, functional composite structure in the objective. The proposed method uses an adaptive mechanism for the update of the feasibility penalizing elements, essentially turning our multiplier type method into a simple alternating minimization procedure based on the augmented Lagrangian function from some iteration onward. This allows us to avoid...
-
作者：Hu, Mingshang; Ji, Shaolin; Xue, Xiaole
作者单位：Shandong University; Shandong University
摘要：In this paper, we propose a general modeling framework for optimal control of stochastic fully coupled forward-backward linear quadratic (FBLQ) problems with indefinite control weight costs that stem from rational expectations models. We propose a new decoupling technique to obtain the optimal feedback control, which is accompanied by one kind of non-Riccati-type ordinary differential equation (ODE). By applying the completion-of-squares method, we prove the existence of the solutions for the ...
-
作者：Kerdreux, Thomas; Colin, Igor; d'Aspremont, Alexandre
作者单位：Centre National de la Recherche Scientifique (CNRS); CNRS - Institute for Information Sciences & Technologies (INS2I); Universite PSL; Ecole Normale Superieure (ENS); Huawei Technologies
摘要：The Shapley-Folkman theorem shows that Minkowski averages of uniformly bounded sets tend to be convex when the number of terms in the sum becomes much larger than the ambient dimension. In optimization, Aubin and Ekeland show that this produces an a priori bound on the duality gap of separable nonconvex optimization problems involving finite sums. This bound is highly conservative and depends on unstable quantities; we relax it in several directions to show that nonconvexity can have a much mi...
-
作者：Kushnir, Alexey; Krishnamoorthy, Vinod
作者单位：Carnegie Mellon University; Carnegie Mellon University
摘要：We prove that supply correspondences are characterized by two properties: the law of supply and being homogeneous of degree zero.
-
作者：Walton, Neil; Denisov, Denis
作者单位：Durham University
摘要：We consider a policy gradient algorithm applied to a finite-arm bandit problem with Bernoulli rewards. We allow learning rates to depend on the current state of the algorithm rather than using a deterministic time-decreasing learning rate. The state of the algorithm forms a Markov chain on the probability simplex. We apply Foster-Lyapunov techniques to analyze the stability of this Markov chain. We prove that, if learning rates are well-chosen, then the policy gradient algorithm is a transient...
-
作者：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...
