-
作者：Berahas, Albert S.; Curtis, Frank E.; Zhou, Baoyu
作者单位：Lehigh University
摘要：A displacement aggregation strategy is proposed for the curvature pairs stored in a limited-memory BFGS (a.k.a. L-BFGS) method such that the resulting (inverse) Hessian approximations are equal to those that would be derived from a full-memory BFGS method. This means that, if a sufficiently large number of pairs are stored, then an optimization algorithm employing the limited-memory method can achieve the same theoretical convergence properties as when full-memory (inverse) Hessian approximati...
-
作者：Yuan, Chenyang; Parrilo, Pablo A.
作者单位：Massachusetts Institute of Technology (MIT)
摘要：We study the convex relaxation of a polynomial optimization problem, maximizing a product of linear forms over the complex sphere. We show that this convex program is also a relaxation of the permanent of Hermitian positive semidefinite (HPSD) matrices. By analyzing a constructive randomized rounding algorithm, we obtain an improved multiplicative approximation factor to the permanent of HPSD matrices, as well as computationally efficient certificates for this approximation. We also propose an...
-
作者：Correa, Jose R.; Munoz, Felipe T.
作者单位：Universidad de Chile; Universidad del Bio-Bio
摘要：We study the worst-case performance guarantee of locally optimal solutions for the problem of minimizing the total weighted and unweighted completion time on parallel machine environments. Our method makes use of a mapping that maps a schedule into an inner product space so that the norm of the mapping is closely related to the cost of the schedule. We apply the method to study the most basic local search heuristics for scheduling, namely jump and swap, and establish their worst-case performan...
-
作者：Candogan, Utkan Onur; Chandrasekaran, Venkat
作者单位：California Institute of Technology; California Institute of Technology
摘要：The edit distance between two graphs is a widely used measure of similarity that evaluates the smallest number of vertex and edge deletions/insertions required to transform one graph to another. It is NP-hard to compute in general, and a large number of heuristics have been proposed for approximating this quantity. With few exceptions, these methods generally provide upper bounds on the edit distance between two graphs. In this paper, we propose a new family of computationally tractable convex...
-
作者：Grimm, Veronika; Nowak, Daniel; Schewe, Lars; Schmidt, Martin; Schwartz, Alexandra; Zoettl, Gregor
作者单位：University of Erlangen Nuremberg; Technical University of Darmstadt; University of Edinburgh; Universitat Trier; Technische Universitat Dresden; Technical University of Darmstadt
摘要：While single-level Nash equilibrium problems are quite well understood nowadays, less is known about multi-leader multi-follower games. However, these have important applications, e.g., in the analysis of electricity and gas markets, where often a limited number of firms interacts on various subsequent markets. In this paper, we consider a special class of two-level multi-leader multi-follower games that can be applied, e.g., to model strategic booking decisions in the European entry-exit gas ...
-
作者：Frascaria, Dario; Olver, Neil
作者单位：Vrije Universiteit Amsterdam; University of London; London School Economics & Political Science; Centrum Wiskunde & Informatica (CWI)
摘要：Flows over time have received substantial attention from both an optimization and (more recently) a game-theoretic perspective. In this model, each arc has an associated delay for traversing the arc, and a bound on the rate of flow entering the arc; flows are time-varying. We consider a setting which is very standard within the transportation economic literature, but has received little attention from an algorithmic perspective. The flow consists of users who are able to choose their route but...
-
作者：Camlibel, Kanat; Iannelli, Luigi; Tanwani, Aneel
作者单位：University of Groningen; University of Sannio; Universite de Toulouse; Centre National de la Recherche Scientifique (CNRS)
摘要：This article studies the solutions of time-dependent differential inclusions which is motivated by their utility in optimization algorithms and the modeling of physical systems. The differential inclusion is described by a time-dependent set-valued mapping having the property that, for a given time instant, the set-valued mapping describes a maximal monotone operator. By successive application of a proximal operator, we construct a sequence of functions parameterized by the sampling time that ...
-
作者：Hirai, Hiroshi; Iwamasa, Yuni
作者单位：University of Tokyo; Kyoto University
摘要：In this paper, we consider the problem of computing the rank of a block-structured symbolic matrix (a generic partitioned matrix) A = (A(alpha beta)x(alpha beta)), where A(alpha beta) is a 2 x 2 matrix over a field F and x(alpha beta) is an indeterminate for alpha = 1, 2, ..., mu and beta = 1, 2, ..., v. This problem can be viewed as an algebraic generalization of the bipartite matching problem and was considered by Iwata and Murota (SIAM J Matrix Anal Appl 16(3):719-734, 1995). Recent interes...
-
作者：Hartmann, Tim A.; Lendl, Stefan; Woeginger, Gerhard J.
作者单位：RWTH Aachen University; Graz University of Technology
摘要：We study a continuous facility location problem on undirected graphs where all edges have unit length and where the facilities may be positioned on the vertices as well as on interior points of the edges. The goal is to cover the entire graph with a minimum number of facilities with covering range delta > 0. In other words, we want to position as few facilities as possible subject to the condition that every point on every edge is at distance at most delta from one of these facilities. We inve...
-
作者：Kolobov, Victor I.; Reich, Simeon; Zalas, Rafal
作者单位：Technion Israel Institute of Technology; Technion Israel Institute of Technology
摘要：We propose finitely convergent methods for solving convex feasibility problems defined over a possibly infinite pool of constraints. Following other works in this area, we assume that the interior of the solution set is nonempty and that certain overrelaxation parameters form a divergent series. We combine our methods with a very general class of deterministic control sequences where, roughly speaking, we require that sooner or later we encounter a violated constraint if one exists. This requi...
