-
作者：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...
-
作者：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...
-
作者：Lin, Tianyi; Jordan, Michael, I
作者单位：University of California System; University of California Berkeley; University of California System; University of California Berkeley
摘要：We provide a control-theoretic perspective on optimal tensor algorithms for minimizing a convex function in a finite-dimensional Euclidean space. Given a function Phi : R-d -> R that is convex and twice continuously differentiable, we study a closed-loop control system that is governed by the operators del Phi and del(2)Phi together with a feedback control law lambda(.) satisfying the algebraic equation lambda(t))(p) parallel to del Phi(x(t))parallel to(p-1) = theta for some theta is an elemen...
-
作者：Karimi, Mehdi; Tuncel, Levent
作者单位：University of Waterloo
摘要：We study the geometry of convex optimization problems given in a Domain-Driven form and categorize possible statuses of these problems using duality theory. Our duality theory for the Domain-Driven form, which accepts both conic and non-conic constraints, lets us determine and certify statuses of a problem as rigorously as the best approaches for conic formulations (which have been demonstrably very efficient in this context). We analyze the performance of a class of infeasible-start primal-du...
-
作者：Adjiashvili, David; Hommelsheim, Felix; Muhlenthaler, Moritz
作者单位：Swiss Federal Institutes of Technology Domain; ETH Zurich; Dortmund University of Technology; Communaute Universite Grenoble Alpes; Institut National Polytechnique de Grenoble; Universite Grenoble Alpes (UGA); Centre National de la Recherche Scientifique (CNRS)
摘要：We introduce and study the problem Flexible Graph Connectivity, which in contrast to many classical connectivity problems features a non-uniform failure model. We distinguish between safe and unsafe resources and postulate that failures can only occur among the unsafe resources. Given an undirected edge-weighted graph and a set of unsafe edges, the task is to find a minimum-cost subgraph that remains connected after removing at most k unsafe edges. We give constant-factor approximation algorit...
