-
作者：Jang, Uijeong; Gupta, Shuvomoy Das; Ryu, Ernest K.
作者单位：University of California System; University of California Los Angeles; Rice University
摘要：The accelerated composite optimization method FISTA (Beck, Teboulle 2009) is suboptimal by a constant factor, and we present a new method OptISTA that improves FISTA by a constant factor of 2. The performance estimation problem (PEP) has recently been introduced as a new computer-assisted paradigm for designing optimal first-order methods. In this work, we present a double-function stepsize-optimization PEP methodology that poses the optimization over fixed-step first-order methods for composi...
-
作者：Buchheim, Christoph; Merkert, Maximilian
作者单位：Dortmund University of Technology; Braunschweig University of Technology
摘要：Many discrete optimal control problems feature combinatorial constraints on the possible switching patterns, a common example being minimum dwell-time constraints. After discretizing to a finite time grid, it is sometimes possible to give a description of the convex hull of feasible (finite-dimensional) binary controls via flow-based extended formulations. For example, this is the case if the feasible set can be characterized via finite-state automata. In this work, we aim to transfer such des...
-
作者：Neuwohner, Meike
作者单位：University of London; London School Economics & Political Science
摘要：The Maximum Leaf Spanning Arborescence problem (MLSA) in directed acyclic graphs (dags) is defined as follows: Given a directed acyclic graph G and a vertex r is an element of V(G) from which every other vertex is reachable, find a spanning arborescence rooted at r maximizing the number of leaves (vertices with out-degree zero). The MLSAin dags is known to be APX-hard as reported byNadine Schwartges, Spoerhase, andWolff (Approximation and OnlineAlgorithms, Springer, Berlin Heidelberg, 2012) an...
-
作者：Nuti, Pranav; Vondrak, Jan
作者单位：Stanford University
摘要：In this paper, we study contention resolution schemes for matchings. Given a fractional matching x and a random set R(x) where each edge e appears independently with probability xe\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$x_e$$\end{document}, we want to select a matching M subset of R(x)\documentclass[12pt]{m...
-
作者：Lasserre, Jean B.
作者单位：Centre National de la Recherche Scientifique (CNRS); Communaute d'universites et etablissements de Toulouse (Comue); Universite Toulouse 1 Capitole; Toulouse School of Economics
摘要：We consider the Moment-SOS hierarchy in polynomial optimization. We first provide a sufficient condition to solve the truncated K -moment problem associated with a given degree-2n pseudo-moment sequence phi n and a semi-algebraic set K subset of Rd . Namely, let 2v be the maximum degree of the polynomials that describe K . If the rank r of its associated moment matrix is less than n-v+1 , then phi n restricted to degree- 2n-1 moments, has an atomic representing measure supported on at most r p...
-
作者：Luke, D. Russell; Schultze, Steffen; Grubmuller, Helmut
作者单位：University of Gottingen
摘要：We apply a recently developed framework for analyzing the convergence of stochastic algorithms to the general problem of large-scale nonconvex composite optimization more generally, and nonconvex likelihood maximization in particular. Our theory is demonstrated on a stochastic gradient descent algorithm for determining the electron density of a molecule from random samples of its scattering amplitude. Numerical results on an idealized synthetic example provide a proof of concept. The algorithm...
-
作者：Liang, Jiaming
作者单位：University of Rochester; University of Rochester
摘要：This paper studies the primal-dual convergence and iteration-complexity of proximal bundle methods for solving nonsmooth problems with convex structures. More specifically, we develop a family of primal-dual proximal bundle methods for solving convex nonsmooth composite optimization problems and establish the iteration-complexity in terms of a primal-dual gap. We also propose a class of proximal bundle methods for solving convex-concave nonsmooth composite saddle-point problems and establish t...
-
作者：Jiang, Nan; Xie, Weijun
作者单位：University System of Georgia; Georgia Institute of Technology
摘要：Distributionally Favorable Optimization (DFO) is a framework for decision-making under uncertainty, with applications spanning various fields, including reinforcement learning, online learning, robust statistics, chance-constrained programming, and two-stage stochastic optimization without complete recourse. In contrast to the traditional Distributionally Robust Optimization (DRO) paradigm, DFO presents a unique challenge- the application of the inner infimum operator often fails to retain the...
-
作者：Weninger, Noah; Fukasawa, Ricardo
作者单位：University of Waterloo
摘要：In the minimum spanning tree (MST) interdiction problem, we are given a graph G=(V,E)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$G=(V,E)$$\end{document} with edge weights, and want to find some X subset of E\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage...
-
作者：Huang, Kun; Pu, Shi; Nedic, Angelia
作者单位：The Chinese University of Hong Kong, Shenzhen; Arizona State University-Tempe; Arizona State University; Arizona State University-Tempe
