-
作者：Guo, Lei; Deng, Zhibin
作者单位：East China University of Science & Technology; Chinese Academy of Sciences; University of Chinese Academy of Sciences, CAS
摘要：We propose a new augmented Lagrangian (AL) method for solving the mathematical program with complementarity constraints (MPCC), where the complementarity constraints are left out of the AL function and treated directly. Two observations motivate us to propose this method: The AL subproblems are closer to the original problem in terms of the constraint structure; and the AL subproblems can be solved efficiently by a nonmonotone projected gradient method, in which we have closed-form solutions a...
-
作者：Zhao, Renbo
作者单位：Massachusetts Institute of Technology (MIT)
摘要：We develop stochastic first-order primal-dual algorithms to solve a class of convex-concave saddle-point problems. When the saddle function is strongly convex in the primal variable, we develop the first stochastic restart scheme for this problem. When the gradient noises obey sub-Gaussian distributions, the oracle complexity of our restart scheme is strictly better than any of the existing methods, even in the deterministic case. Furthermore, for each problem parameter of interest, whenever t...
-
作者：Blanchet, Jose; Murthy, Karthyek; Zhang, Fan
作者单位：Stanford University; Singapore University of Technology & Design
摘要：We consider optimal transport-based distributionally robust optimization (DRO) problems with locally strongly convex transport cost functions and affine decision rules. Under conventional convexity assumptions on the underlying loss function, we obtain structural results about the value function, the optimal policy, and the worst-case optimal transport adversarial model. These results expose a rich structure embedded in the DRO problem (e.g., strong convexity even if the non-DRO problem is not...
-
作者：Basei, Matteo; Cao, Haoyang; Guo, Xin
作者单位：University of California System; University of California Berkeley; Electricite de France (EDF); Alan Turing Institute
摘要：We consider a general class of nonzero-sum N-player stochastic games with impulse controls, where players control the underlying dynamics with discrete interventions. We adopt a verification approach and provide sufficient conditions for the Nash equilibria (NEs) of the game. We then consider the limiting situation when N goes to infinity, that is, a suitable mean-field game (MFG) with impulse controls. We show that under appropriate technical conditions, there exists a unique NE solution to t...
-
作者：Gutekunst, Samuel C.; Williamson, David P.
作者单位：Bucknell University; Bucknell University; Cornell University
摘要：The traveling salesman problem (TSP) is a fundamental problem in combinatorial optimization. Several semidefinite programming relaxations have been proposed recently that exploit a variety of mathematical structures including, for example, algebraic connectivity, permutation matrices, and association schemes. The main results of this paper are twofold. First, de Klerk and Sotirov [de Klerk E, Sotirov R (2012) Improved semidefinite programming bounds for quadratic assignment problems with suita...
-
作者：Klimm, Max; Schuetz, Andreas
作者单位：Technical University of Berlin
摘要：This paper studies the existence of pure Nash equilibria in atomic congestion games with different user classes where the cost of each resource depends on the aggregated demand of each class. A set of cost functions is called consistent for this class if all games with cost functions from the set have a pure Nash equilibrium. We give a complete characterization of consistent sets of cost functions showing that the only consistent sets of cost functions are sets of certain affine functions and ...
-
作者：Perez-Salazar, Sebastian; Singh, Mohit; Toriello, Alejandro
作者单位：University System of Georgia; Georgia Institute of Technology
摘要：Motivated by bursty bandwidth allocation and by the allocation of virtual machines to servers in the cloud, we consider the online problem of packing items with random sizes into unit-capacity bins. Items arrive sequentially, but on arrival, an item's actual size is unknown; only its probabilistic information is available to the decision maker. Without knowing this size, the decision maker must irrevocably pack the item into an available bin or place it in a new bin. Once packed in a bin, the ...
-
作者：Amarante, Massimiliano
作者单位：Universite de Montreal; Universite de Montreal
摘要：After showing, by means of a series of examples, that paradigms alternative to the Bayesian one obtain by simply replacing the notion of approximation associated with the latter, the paper presents a unified framework for theories of decision making and inference. Given a statistical model, the algebra of bounded random variables on the sample space is mapped homomorphically into an algebra of operators on a certain Hilbert space. Then, the choice of a norm or a divergence function on the latt...
-
作者：Puha, Amber L.; Ward, Amy R.
作者单位：California State University System; California State University San Marcos; University of Chicago
摘要：We describe a fluid model with time-varying input that approximates a multiclass many-server queue with general reneging distribution and multiple customer classes (specifically, the multiclass G/GI/N+GI queue). The system dynamics depend on the policy, which is a rule for determining when to serve a given customer class. The class of admissible control policies are those that are head-of-the-line (HL) and nonanticipating. For a sequence of many-server queues operating under admissible HL cont...
-
作者：Bai, Kuang; Ye, Jane J.
作者单位：Hong Kong Polytechnic University; University of Victoria
摘要：The bilevel program is an optimization problem in which the constraint involves solutions to a parametric optimization problem. It is well known that the value function reformulation provides an equivalent single-level optimization problem, but it results in a non-smooth optimization problem that never satisfies the usual constraint qualification, such as the Mangasarian-Fromovitz constraint qualification (MFCQ). In this paper, we show that even the first order sufficient condition for metric ...
