-
作者：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...
