-
作者：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...
-
作者：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...
-
作者：Morshed, Md Sarowar; Islam, Md Saiful; Noor-E-Alam, Md.
作者单位：Northeastern University
摘要：Randomized Kaczmarz, Motzkin Method and Sampling Kaczmarz Motzkin (SKM) algorithms are commonly used iterative techniques for solving a system of linear inequalities (i.e., Ax <= b). As linear systems of equations represent a modeling paradigm for solving many optimization problems, these randomized and iterative techniques are gaining popularity among researchers in different domains. In this work, we propose a Generalized Sampling Kaczmarz Motzkin (GSKM) method that unifies the iterative met...
-
作者：Huang, Wen; Wei, Ke
作者单位：Xiamen University; Fudan University
摘要：In the Euclidean setting the proximal gradient method and its accelerated variants are a class of efficient algorithms for optimization problems with decomposable objective. In this paper, we develop a Riemannian proximal gradient method (RPG) and its accelerated variant (ARPG) for similar problems but constrained on a manifold. The global convergence of RPG is established under mild assumptions, and the O(1/k) is also derived for RPG based on the notion of retraction convexity. If assuming th...
-
作者：Muir, Christopher; Toriello, Alejandro
作者单位：University System of Georgia; Georgia Institute of Technology
摘要：We propose a dynamic version of the classical node packing problem, also called the stable set or independent set problem. The problem is defined by a node set, a node weight vector, and an edge probability vector. For every pair of nodes, an edge is present or not according to an independent Bernoulli random variable defined by the corresponding entry in the probability vector. At each step, the decision maker selects an available node that maximizes the expected weight of the final packing, ...
-
作者：Molybog, Igor; Sojoudi, Somayeh; Lavaei, Javad
作者单位：University of California System; University of California Berkeley
摘要：In this work, we study the optimization landscape of the non-convex matrix sensing problem that is known to have many local minima in the worst case. Since the existing results are related to the notion of restricted isometry property (RIP) that cannot directly capture the underlying structure of a given problem, they can hardly be applied to real-world problems where the amount of data is not exorbitantly high. To address this issue, we develop the notion of kernel structure property to obtai...
