-
作者：Koh, Zhuan Khye; Sanita, Laura
作者单位：University of London; London School Economics & Political Science; University of Waterloo; Eindhoven University of Technology
摘要：Cooperative games form an important class of problems in game theory, where a key goal is to distribute a value among a set of players who are allowed to cooperate by forming coalitions. An outcome of the game is given by an allocation vector that assigns a value share to each player. A crucial aspect of such games is submodularity (or convexity). Indeed, convex instances of cooperative games exhibit several nice properties, e.g. regarding the existence and computation of allocations realizing...
-
作者：Zhang, Hui
作者单位：National University of Defense Technology - China
摘要：This paper reveals that a common and central role, played in many error bound (EB) conditions and a variety of gradient-type methods, is a residual measure operator. On one hand, by linking this operator with other optimality measures, we define a group of abstract EB conditions, and then analyze the interplay between them; on the other hand, by using this operator as an ascent direction, we propose an abstract gradient-type method, and then derive EB conditions that are necessary and sufficie...
-
作者：Della Croce, Federico; Scatamacchia, Rosario
作者单位：Polytechnic University of Turin; Consiglio Nazionale delle Ricerche (CNR); Istituto di Elettronica e di Ingegneria dell'Informazione e delle Telecomunicazioni (IEIIT-CNR)
摘要：We consider the bilevel knapsack problem with interdiction constraints, an extension of the classic 0-1 knapsack problem formulated as a Stackelberg game with two agents, a leader and a follower, that choose items from a common set and hold their own private knapsacks. First, the leader selects some items to be interdicted for the follower while satisfying a capacity constraint. Then the follower packs a set of the remaining items according to his knapsack constraint in order to maximize the p...
-
作者：Serra, Thiago; Hooker, J. N.
作者单位：Carnegie Mellon University
摘要：It is often useful in practice to explore near-optimal solutions of an integer programming problem. We show how all solutions within a given tolerance of the optimal value can be efficiently and compactly represented in a weighted decision diagram. The structure of the diagram facilitates rapid processing of a wide range of queries about the near-optimal solution space, as well as reoptimization after changes in the objective function. We also exploit the paradoxical fact that the diagram can ...
-
作者：Ahmadi, Amir Ali; Hall, Georgina
作者单位：Princeton University; INSEAD Business School
摘要：It has recently been shown that the problem of testing global convexity of polynomials of degree four is strongly NP-hard, answering an open question of N.Z. Shor. This result is minimal in the degree of the polynomial when global convexity is of concern. In a number of applications however, one is interested in testing convexity only over a compact region, most commonly a box (i.e., a hyper-rectangle). In this paper, we show that this problem is also strongly NP-hard, in fact for polynomials ...
-
作者：Perez, Guillaume; Barlaud, Michel; Fillatre, Lionel; Regin, Jean-Charles
作者单位：Cornell University; Centre National de la Recherche Scientifique (CNRS); Universite Cote d'Azur
摘要：We propose in this paper a new method processing the projection of an arbitrary size vector onto the probabilistic simplex or the l(1) ball. Our method merges two principles. The first one is an original search of the projection using a bucket algorithm. The second one is a filtering, on the fly, of the values that cannot be part of the projection. The combination of these two principles offers a simple and efficient algorithm whose worst-case complexity is linear with respect to the vector si...
-
作者：Lan, Guanghui; Lee, Soomin; Zhou, Yi
作者单位：University System of Georgia; Georgia Institute of Technology
摘要：We present a new class of decentralized first-order methods for nonsmooth and stochastic optimization problems defined over multiagent networks. Considering that communication is a major bottleneck in decentralized optimization, our main goal in this paper is to develop algorithmic frameworks which can significantly reduce the number of inter-node communications. Our major contribution is to present a new class of decentralized primal-dual type algorithms, namely the decentralized communicatio...
-
作者：Gratton, S.; Royer, C. W.; Vicente, L. N.
作者单位：Universite de Toulouse; University of Wisconsin System; University of Wisconsin Madison; Universidade de Coimbra
摘要：In order to be provably convergent towards a second-order stationary point, optimization methods applied to nonconvex problems must necessarily exploit both first and second-order information. However, as revealed by recent complexity analyses of some of these methods, the overall effort to reach second-order points is significantly larger when compared to the one of approaching first-order ones. On the other hand, there are other algorithmic schemes, initially designed with first-order conver...
-
作者：Godsil, Chris; Roberson, David E.; Rooney, Brendan; Samal, Robert; Varvitsiotis, Antonios
作者单位：University of Waterloo; Technical University of Denmark; Korea Advanced Institute of Science & Technology (KAIST); Charles University Prague; Nanyang Technological University
摘要：A vector t-coloring of a graph is an assignment of real vectors p(1), ... , p(n) to its vertices such that p(i)(T) p(i) = t - 1, for all i = 1, ... , n and p(i)(T) p(j) <= -1, whenever i and j are adjacent. The vector chromatic number of G is the smallest number t >= 1 for which a vector t-coloring of G exists. For a graph H and a vector t-coloring p(1), ... , p(n) of G, the map taking (i, l) is an element of V(G) x V(H) to p(i) is a vector t-coloring of the categorical product G x H. It follo...
-
作者：Rockafellar, R. Tyrrell; Sun, Jie
作者单位：University of Washington; University of Washington Seattle; Curtin University
摘要：Lagrangian variational inequalities feature both primal and dual elements in expressing first-order conditions for optimality in a wide variety of settings where multipliers in a very general sense need to be brought in. Their stochastic version relates to problems of stochastic programming and covers not only classical formats with inequality constraints but also composite models with nonsmooth objectives. The progressive hedging algorithm, as a means of solving stochastic programming problem...
