-
作者：Bruggmann, Simon; Zenklusen, Rico
作者单位：Swiss Federal Institutes of Technology Domain; ETH Zurich
摘要：Relaxation and rounding approaches became a standard and extremely versatile tool for constrained submodular function maximization. One of the most common rounding techniques in this context are contention resolution schemes. Such schemes round a fractional point by first rounding each coordinate independently, and then dropping some elements to reach a feasible set. Also the second step, where elements are dropped, is typically randomized. This leads to an additional source of randomization w...
-
作者：Driggs, Derek; Ehrhardt, Matthias J.; Schonlieb, Carola-Bibiane
作者单位：University of Cambridge; University of Bath
摘要：Variance reduction is a crucial tool for improving the slow convergence of stochastic gradient descent. Only a few variance-reduced methods, however, have yet been shown to directly benefit from Nesterov's acceleration techniques to match the convergence rates of accelerated gradient methods. Such approaches rely on negative momentum, a technique for further variance reduction that is generally specific to the SVRG gradient estimator. In this work, we show for the first time that negative mome...
-
作者：Friedland, Shmuel; Lasserre, Jean-Bernard; Lim, Lek-Heng; Nie, Jiawang
作者单位：University of Illinois System; University of Illinois Chicago; University of Illinois Chicago Hospital; Centre National de la Recherche Scientifique (CNRS); University of Chicago; University of California System; University of California San Diego
-
作者：Barak, Boaz; Moitra, Ankur
作者单位：Massachusetts Institute of Technology (MIT); Massachusetts Institute of Technology (MIT)
摘要：In the noisy tensor completion problem we observe m entries (whose location is chosen uniformly at random) from an unknown n(1) x n(2) x n(3) tensor T. We assume that T is entry-wise close to being rank r. Our goal is to fill in its missing entries using as few observations as possible. Let n = max(n(1), n(2), n(3)). We show that if m greater than or similar to n(3/2)r then there is a polynomial time algorithm based on the sixth level of the sum-of-squares hierarchy for completing it. Our esti...
-
作者：Ahmed, Shabbir; Cabral, Filipe Goulart; Paulo da Costa, Bernardo Freitas
作者单位：University System of Georgia; Georgia Institute of Technology; Universidade Federal do Rio de Janeiro
摘要：We propose a new algorithm for solving multistage stochastic mixed integer linear programming (MILP) problems with complete continuous recourse. In a similar way to cutting plane methods, we construct nonlinear Lipschitz cuts to build lower approximations for the non-convex cost-to-go functions. An example of such a class of cuts are those derived using Augmented Lagrangian Duality for MILPs. The family of Lipschitz cuts we use is MILP representable, so that the introduction of these cuts does...
-
作者：Kiszka, Adriana; Wozabal, David
作者单位：Technical University of Munich
摘要：In this paper, we propose a semi-metric for Markov processes that allows to bound optimal values of linear Markovian stochastic optimization problems. Similar to existing notions of distance for general stochastic processes, our distance is based on transportation metrics. As opposed to the extant literature, the proposed distance is problem specific, i.e., dependent on the data of the problem whose objective value we want to bound. As a result, we are able to consider problems with randomness...
-
作者：Blekherman, Grigoriy; Dey, Santanu S.; Molinaro, Marco; Sun, Shengding
作者单位：University System of Georgia; Georgia Institute of Technology; Pontificia Universidade Catolica do Rio de Janeiro
摘要：While semidefinite programming (SDP) problems are polynomially solvable in theory, it is often difficult to solve large SDP instances in practice. One technique to address this issue is to relax the global positive-semidefiniteness (PSD) constraint and only enforce PSD-ness on smaller k x k principal submatrices-we call this the sparse SDP relaxation. Surprisingly, it has been observed empirically that in some cases this approach appears to produce bounds that are close to the optimal objectiv...
-
作者：Bourdin, Loic; Dhar, Gaurav
作者单位：Universite de Limoges; Centre National de la Recherche Scientifique (CNRS)
摘要：In the present paper we derive a Pontryagin maximum principle for general nonlinear optimal sampled-data control problems in the presence of running inequality state constraints. We obtain, in particular, a nonpositive averaged Hamiltonian gradient condition associated with an adjoint vector being a function of bounded variation. As a well known challenge, theoretical and numerical difficulties may arise due to the possible pathological behavior of the adjoint vector (jumps and singular part l...
-
作者：Wang, Alex L.; Kilinc-Karzan, Fatma
作者单位：Carnegie Mellon University
摘要：We consider the generalized trust region subproblem (GTRS) ofminimizing a nonconvex quadratic objective over a nonconvex quadratic constraint. Alifting of this problem recasts the GTRS as minimizing a linear objective subject to two nonconvex quadratic constraints. Our first main contribution is structural: we give an explicit description of the convex hull of this nonconvex set in terms of the generalized eigenvalues of an associated matrix pencil. This result may be of interest in building r...
-
作者：Johnstone, Patrick R.; Eckstein, Jonathan
作者单位：Rutgers University System; Rutgers University New Brunswick
摘要：This work is concerned with the classical problem of finding a zero of a sum of maximal monotone operators. For the projective splitting framework recently proposed by Combettes and Eckstein, we show how to replace the fundamental subproblem calculation using a backward step with one based on two forward steps. The resulting algorithms have the same kind of coordination procedure and can be implemented in the same block-iterative and highly flexible manner, but may perform backward steps on so...
