-
作者：Maehara, Takanori; Nakashima, So; Yamaguchi, Yutaro
作者单位：RIKEN; University of Tokyo; Kyushu University
摘要：We consider a problem of maximizing a monotone DR-submodular function under multiple order-consistent knapsack constraints on a distributive lattice. Because a distributive lattice is used to represent a dependency constraint, the problem can represent a dependency constrained version of a submodular maximization problem on a set. We propose a (1-1/e)-approximation algorithm for this problem. To achieve this result, we generalize the continuous greedy algorithm to distributive lattices: We cho...
-
作者：Quoc Tran-Dinh; Pham, Nhan H.; Phan, Dzung T.; Nguyen, Lam M.
作者单位：University of North Carolina; University of North Carolina Chapel Hill; International Business Machines (IBM); IBM USA
摘要：We introduce a new approach to develop stochastic optimization algorithms for a class of stochastic composite and possibly nonconvex optimization problems. The main idea is to combine a variance-reduced estimator and an unbiased stochastic one to create a new hybrid estimator which trades-off the variance and bias, and possesses useful properties for developing new algorithms. We first introduce our hybrid estimator and investigate its fundamental properties to form a foundational theory for a...
-
作者：Lan, Guanghui
作者单位：University System of Georgia; Georgia Institute of Technology
摘要：Stochastic dual dynamic programming is a cutting plane type algorithm for multi-stage stochastic optimization originated about 30 years ago. In spite of its popularity in practice, there does not exist any analysis on the convergence rates of this method. In this paper, we first establish the number of iterations, i.e., iteration complexity, required by a basic dual dynamic programming method for solving single-scenario multi-stage optimization problems, by introducing novel mathematical tools...
-
作者：Dowson, O.; Morton, D. P.; Downward, A.
作者单位：Northwestern University; University of Auckland
摘要：We propose an algorithm for solving a class of bi-objective multistage stochastic linear programs. We show that the cost-to-go functions are saddle functions, and we exploit this structure, developing a new variant of the stochastic dual dynamic programming algorithm. Our algorithm is implemented in the open-source stochastic programming solver SDDP.jl. We apply our algorithm to a hydro-thermal scheduling problem using data from the Brazilian Interconnected Power System. We also propose and im...
-
作者：Shi, Xueyu; Prokopyev, Oleg A.; Zeng, Bo
作者单位：Pennsylvania Commonwealth System of Higher Education (PCSHE); University of Pittsburgh
摘要：We study the polyhedral structure of a mixed 0-1 set arising from the submodular maximization problem, given by P = ((w, x) is an element of R x (0, 1)(n) : w <= f (x), x is an element of X), where submodular function f (x) is represented by a concave function composed with an affine function, and X is the feasible region of binary variables x. For X = (0, 1)(n), two families of facet-defining inequalities are proposed for the convex hull of P through restriction and lifting using submodular i...
-
作者：Lozano, Leonardo; Smith, J. Cole
作者单位：Clemson University; Clemson University
摘要：We consider a special class of two-stage stochastic integer programming problems with binary variables appearing in both stages. The class of problems we consider constrains the second-stage variables to belong to the intersection of sets corresponding to first-stage binary variables that equal one. Our approach seeks to uncover strong dual formulations to the second-stage problems by transforming them into dynamic programming (DP) problems parameterized by first-stage variables. We demonstrat...
-
作者：Del Pia, Alberto; Ma, Mingchen
作者单位：University of Wisconsin System; University of Wisconsin Madison; University of Wisconsin System; University of Wisconsin Madison; University of Wisconsin System; University of Wisconsin Madison
摘要：A classic result by Cook, Gerards, Schrijver, and Tardos provides an upper bound of n Delta on the proximity of optimal solutions of an Integer Linear Programming problem and its standard linear relaxation. In this bound, n is the number of variables and Delta denotes the maximum of the absolute values of the subdeterminants of the constraint matrix. Hochbaum and Shanthikumar, and Werman and Magagnosc showed that the same upper bound is valid if a more general convex function is minimized, ins...
-
作者：Dragomir, Radu-Alexandru; Taylor, Adrien B.; D'Aspremont, Alexandre; Bolte, Jerome
作者单位：Universite de Toulouse; Universite Toulouse 1 Capitole; Universite PSL; Ecole Normale Superieure (ENS); Inria; Universite PSL; Ecole Normale Superieure (ENS); Universite PSL; Ecole Normale Superieure (ENS); Centre National de la Recherche Scientifique (CNRS); Universite PSL; Ecole Normale Superieure (ENS); Centre National de la Recherche Scientifique (CNRS); CNRS - Institute for Information Sciences & Technologies (INS2I); Universite de Toulouse; Universite Toulouse 1 Capitole; Toulouse School of Economics
摘要：We provide a lower bound showing that the O(1/k) convergence rate of the NoLips method (a.k.a. Bregman Gradient or Mirror Descent) is optimal for the class of problems satisfying the relative smoothness assumption. This assumption appeared in the recent developments around the Bregman Gradient method, where acceleration remained an open issue. The main inspiration behind this lower bound stems from an extension of the performance estimation framework of Drori and Teboulle (Mathematical Program...
-
作者：Rodriguez-Heck, Elisabeth; Stickler, Karl; Walter, Matthias; Weltge, Stefan
作者单位：RWTH Aachen University; University of Twente; Technical University of Munich
摘要：The Nemhauser-Trotter theorem states that the standard linear programming (LP) formulation for the stable set problem has a remarkable property, also known as (weak) persistency: for every optimal LP solution that assigns integer values to some variables, there exists an optimal integer solution in which these variables retain the same values. While the standard LP is defined by only non-negativity and edge constraints, a variety of other LP formulations have been studied and one may wonder wh...
-
作者：Wang, Alex L.; Kilinc-Karzan, Fatma
作者单位：Carnegie Mellon University
摘要：Quadratically constrained quadratic programs (QCQPs) are a fundamental class of optimization problems well-known to be NP-hard in general. In this paper we study conditions under which the standard semidefinite program (SDP) relaxation of a QCQP is tight. We begin by outlining a general framework for proving such sufficient conditions. Then using this framework, we show that the SDP relaxation is tight whenever the quadratic eigenvalue multiplicity, a parameter capturing the amount of symmetry...
