-
作者：Lan, Guanghui
作者单位：University System of Georgia; Georgia Institute of Technology
摘要：We present new policy mirror descent (PMD) methods for solving reinforcement learning (RL) problems with either strongly convex or general convex regularizers. By exploring the structural properties of these overall highly nonconvex problems we show that the PMD methods exhibit fast linear rate of convergence to the global optimality. We develop stochastic counterparts of these methods, and establish an O(1/epsilon) (resp., O(1/epsilon(2))) sampling complexity for solving these RL problems wit...
-
作者：Murray, Riley; Naumann, Helen; Theobald, Thorsten
作者单位：University of California System; University of California Berkeley; California Institute of Technology; Goethe University Frankfurt
摘要：Conditional Sums-of-AM/GM-Exponentials (conditional SAGE) is a decomposition method to prove nonnegativity of a signomial or polynomial over some subset X of real space. In this article, we undertake the first structural analysis of conditional SAGE signomials for convex sets X. We introduce the X-circuits of a finite subset A subset of R-n, which generalize the simplicial circuits of the affine-linear matroid induced by A to a constrained setting. The X-circuits serve as the main tool in our ...
-
作者：Boob, Digvijay; Deng, Qi; Lan, Guanghui
作者单位：University System of Georgia; Georgia Institute of Technology; Shanghai University of Finance & Economics
摘要：Functional constrained optimization is becoming more and more important in machine learning and operations research. Such problems have potential applications in risk-averse machine learning, semisupervised learning and robust optimization among others. In this paper, we first present a novel Constraint Extrapolation (ConEx) method for solving convex functional constrained problems, which utilizes linear approximations of the constraint functions to define the extrapolation (or acceleration) s...
-
作者：Helou, Elias S.; Santos, Sandra A.; Simoes, Lucas E. A.
作者单位：Universidade de Sao Paulo; Universidade Estadual de Campinas
摘要：The solution of bilevel optimization problems with possibly nondifferentiable upper objective functions and with smooth and convex lower-level problems is discussed. A new approximate one-level reformulation for the original problem is introduced. An algorithm based on this reformulation is developed that is proven to converge to a solution of the bilevel problem. Each iteration of the algorithm depends on the solution of a nonsmooth optimization problem and its implementation leverages recent...
-
作者：Aprile, Manuel; Drescher, Matthew; Fiorini, Samuel; Huynh, Tony
作者单位：University of Padua; Universite Libre de Bruxelles; Monash University
摘要：We give the first 2-approximation algorithm for the cluster vertex deletion problem. This approximation factor is tight, since approximating the problem within any constant factor smaller than 2 is UGC-hard. Our algorithm combines previous approaches, based on the local ratio technique and the management of twins, with a novel construction of a good cost function on the vertices at distance at most 2 from any vertex of the input graph. As an additional contribution, we also study cluster verte...
-
作者：Chandra, Ashish; Tawarmalani, Mohit
作者单位：Purdue University System; Purdue University
摘要：This paper develops various optimization techniques to estimate probability of events where the optimal value of a convex program, satisfying certain structural assumptions, exceeds a given threshold. First, we relate the search of affine/polynomial policies for the robust counterpart to existing relaxation hierarchies in MINLP (Lasserre in Proceedings of the international congress of mathematicians (ICM 2018), 2019; Sherali and Adams in A reformulation-linearization technique for solving disc...
-
作者：Wei, Linchuan; Gomez, Andres; Kucukyavuz, Simge
作者单位：Northwestern University; University of Southern California
摘要：Motivated by modern regression applications, in this paper, we study the convexification of a class of convex optimization problems with indicator variables and combinatorial constraints on the indicators. Unlike most of the previous work on convexification of sparse regression problems, we simultaneously consider the nonlinear non-separable objective, indicator variables, and combinatorial constraints. Specifically, we give the convex hull description of the epigraph of the composition of a o...
-
作者：Klein, Kim-Manuel
作者单位：University of Kiel
摘要：We consider so called 2-stage stochastic integer programs (IPs) and their generalized form, so calledmulti-stage stochastic IPs. A2-stage stochastic IP is an integer program of the form max{c(T) x vertical bar Ax = b, l <= x <= u, x epsilon Z(s+nt)} where the constraint matrix A epsilon Z(rnxs+nt) consists roughly of n repetitions of a matrix A epsilon Z(rxs) on the vertical line and n repetitions of a matrix B epsilon Z(rxt) on the diagonal. In this paper we improve upon an algorithmic result...
-
作者：Attouch, Hedy; Chbani, Zaki; Fadili, Jalal; Riahi, Hassan
作者单位：Centre National de la Recherche Scientifique (CNRS); Universite de Montpellier; Cadi Ayyad University of Marrakech; Universite de Caen Normandie; Centre National de la Recherche Scientifique (CNRS)
摘要：In a Hilbert space setting, for convex optimization, we analyze the convergence rate of a class of first-order algorithms involving inertial features. They can be interpreted as discrete time versions of inertial dynamics involving both viscous and Hessian-driven dampings. The geometrical damping driven by the Hessian intervenes in the dynamics in the form del(2) f (x(t)).x(t). By treating this term as the time derivative of del f (x(t)), this gives, in discretized form, first-order algorithms...
-
作者：Abdi, Ahmad; Cornuejols, Gerard; Huynh, Tony; Lee, Dabeen
作者单位：University of London; London School Economics & Political Science; Carnegie Mellon University; Monash University; Institute for Basic Science - Korea (IBS)
摘要：A clutter is k-wise intersecting if every k members have a common element, yet no element belongs to all members. We conjecture that, for some integer k >= 4, every k-wise intersecting clutter is non-ideal. As evidence for our conjecture, we prove it for k = 4 for the class of binary clutters. Two key ingredients for our proof are Jaeger's 8-flow theorem for graphs, and Seymour's characterization of the binary matroids with the sums of circuits property. As further evidence for our conjecture,...
