-
作者：Frank, Andras; Murota, Kazuo
作者单位：Eotvos Lorand University; Tokyo Metropolitan University; Research Organization of Information & Systems (ROIS); Institute of Statistical Mathematics (ISM) - Japan
摘要：This paper is concerned with algorithms and applications of decreasing minimization on an M-convex set, which is the set of integral elements of an integral base-polyhedron. Based on a recent characterization of decreasingly minimal (dec-min) elements, we develop a strongly polynomial algorithm for computing a dec-min element of an M-convex set. The matroidal feature of the set of dec-min elements makes it possible to compute a minimum cost dec-min element, as well. Our second goal is to exhib...
-
作者：Laiu, M. Paul; Tits, Andre L.
作者单位：United States Department of Energy (DOE); Oak Ridge National Laboratory; University System of Maryland; University of Maryland College Park; University System of Maryland; University of Maryland College Park
摘要：A framework is proposed for solving general convex quadratic programs (CQPs) from an infeasible starting point by invoking an existing feasible-start algorithm tailored for inequality-constrained CQPs. The central tool is an exact penalty function scheme equipped with a penalty-parameter updating rule. The feasible-start algorithm merely has to satisfy certain general requirements, and so is the updating rule. Under mild assumptions, the framework is proved to converge on CQPs with both inequa...
-
作者：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...
-
作者：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...
-
作者：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, Peng; Zhou, Zirui; So, Anthony Man-Cho
作者单位：Chinese University of Hong Kong; Huawei Technologies
摘要：Community detection in graphs that are generated according to stochastic block models (SBMs) has received much attention lately. In this paper, we focus on the binary symmetric SBM-in which a graph of n vertices is randomly generated by first partitioning the vertices into two equal-sized communities and then connecting each pair of vertices with probability that depends on their community memberships-and study the associated exact community recovery problem. Although the maximum-likelihood fo...
-
作者：Hazimeh, Hussein; Mazumder, Rahul; Saab, Ali
作者单位：Massachusetts Institute of Technology (MIT)
摘要：We consider the least squares regression problem, penalized with a combination of the l(0) and squared l(2) penalty functions (a.k.a. l(0)l(2) regularization). Recent work shows that the resulting estimators enjoy appealing statistical properties in many high-dimensional settings. However, exact computation of these estimators remains a major challenge. Indeed, modern exact methods, based on mixed integer programming (MIP), face difficulties for problems where the number of features p similar ...
