-
作者：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...
-
作者：Klep, Igor; Magron, Victor; Povh, Janez
作者单位：University of Ljubljana; Centre National de la Recherche Scientifique (CNRS); University of Ljubljana
摘要：This article focuses on optimization of polynomials in noncommuting variables, while taking into account sparsity in the input data. A converging hierarchy of semidefinite relaxations for eigenvalue and trace optimization is provided. This hierarchy is a noncommutative analogue of results due to Lasserre (SIAM J Optim 17(3):822-843, 2006) and Waki et al. (SIAM J Optim 17(1):218-242, 2006). The Gelfand-Naimark-Segal construction is applied to extract optimizers if flatness and irreducibility co...
-
作者：Bhaskara, Aditya; Chen, Aidao; Perreault, Aidan; Vijayaraghavan, Aravindan
作者单位：Utah System of Higher Education; University of Utah; Northwestern University
摘要：Smoothed analysis is a powerful paradigm in overcoming worst-case intractability in high-dimensional data analysis and unsupervised learning. While polynomial time smoothed analysis guarantees have been obtained for worst-case intractable problems like tensor decomposition and learning mixtures of Gaussians, such guarantees have been hard to obtain for several other important problems in data analysis. A core technical challenge in analyzing algorithms is obtaining lower bounds on the least si...
-
作者：Henrion, R.; Roemisch, W.
作者单位：Leibniz Association; Weierstrass Institute for Applied Analysis & Stochastics; Humboldt University of Berlin
摘要：Scenarios are indispensable ingredients for the numerical solution of stochastic programs. Earlier approaches to optimal scenario generation and reduction are based on stability arguments involving distances of probability measures. In this paper we review those ideas and suggest to make use of stability estimates based only on problem specific data. For linear two-stage stochastic programs we show that the problem-based approach to optimal scenario generation can be reformulated as best appro...
-
作者：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...
