-
作者：Liberti, Leo; Sager, Sebastian; Wiegele, Angelika
作者单位：Institut Polytechnique de Paris; Ecole Polytechnique; Otto von Guericke University; University of Klagenfurt
-
作者：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...
-
作者：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...
-
作者：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
-
作者：Kober, Stefan
作者单位：Universite Libre de Bruxelles
摘要：Integer programs (IPs) on constraint matrices with bounded subdeterminants are conjectured to be solvable in polynomial time. We give a strongly polynomial-time algorithm to solve IPs where the constraint matrix has bounded subdeterminants and at most two non-zeros per row after removing a constant number of rows and columns. This result extends the work by Fiorini, Joret, Weltge & Yuditsky (J. ACM 72(1), 1-50 (2025)) by allowing for additional, unifying constraints and variables. Further, we ...
-
作者：Gess, Benjamin; Kassing, Sebastian
作者单位：University of Wuppertal; Technical University of Berlin; Max Planck Society
摘要：We prove explicit bounds on the exponential rate of convergence for the momentum stochastic gradient descent scheme (MSGD) for arbitrary, fixed hyperparameters (learning rate, friction parameter) and its continuous-in-time counterpart in the context of non-convex optimization. The results are shown for objective functions satisfying a local Polyak-& Lstrok;ojasiewicz inequality and under assumptions on the variance of MSGD that are satisfied in overparametrized settings. Moreover, we analyze t...
