-
作者：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...
-
作者：Bienstock, Daniel; Chen, Chen; Munoz, Gonzalo
作者单位：Columbia University; University System of Ohio; Ohio State University; Universidad de O'Higgins
摘要：This paper introduces cutting planes that involve minimal structural assumptions, enabling the generation of strong polyhedral relaxations for a broad class of problems. We consider valid inequalities for the set S boolean AND P, where S is a closed set, and P is a polyhedron. Given an oracle that provides the distance from a point to S, we construct a pure cutting plane algorithm which is shown to converge if the initial relaxation is a polyhedron. These cuts are generated from convex forbidd...
-
作者：Hosseini, Reshad; Sra, Suvrit
作者单位：University of Tehran; Institute for Research in Fundamental Sciences IPM; Massachusetts Institute of Technology (MIT)
摘要：We consider maximum likelihood estimation for Gaussian Mixture Models (Gmm s). This task is almost invariably solved (in theory and practice) via the Expectation Maximization (EM) algorithm. EM owes its success to various factors, of which is its ability to fulfill positive definiteness constraints in closed form is of key importance. We propose an alternative to EM grounded in the Riemannian geometry of positive definite matrices, using which we cast Gmm parameter estimation as a Riemannian o...
-
作者：Naegele, Martin; Zenklusen, Rico
作者单位：Swiss Federal Institutes of Technology Domain; ETH Zurich
摘要：Minimum cut problems are among the most classical problems in Combinatorial Optimization and are used in a wide set of applications. Some of the best-known efficiently solvable variants include global mininmum cuts, minimum s-t cuts, and minimum odd cuts in undirected graphs. We study a problem class that can be seen to generalize the above variants, namely finding congruency-constrained minimum cuts, i.e., we consider cuts whose number of vertices is congruent to r modulo m, for some integers...
