Mathematical Programming

最新文章

• Convergence of the forward-backward algorithm: beyond the worst-case with the help of geometry AI翻译
  作者：Garrigos, Guillaume; Rosasco, Lorenzo; Villa, Silvia
  作者单位：Centre National de la Recherche Scientifique (CNRS); Universite Paris Cite; University of Genoa; Istituto Italiano di Tecnologia - IIT; University of Genoa
  摘要：We provide a comprehensive study of the convergence of the forward-backward algorithm under suitable geometric conditions, such as conditioning or Lojasiewicz properties. These geometrical notions are usually local by nature, and may fail to describe the fine geometry of objective functions relevant in inverse problems and signal processing, that have a nice behaviour on manifolds, or sets open with respect to a weak topology. Motivated by this observation, we revisit those geometric notions o...
• Risk-neutral PDE-constrained generalized Nash equilibrium problems AI翻译
  作者：Gahururu, Deborah B.; Hintermueller, Michael; Surowiec, Thomas M.
  作者单位：Philipps University Marburg; Leibniz Association; Weierstrass Institute for Applied Analysis & Stochastics; Humboldt University of Berlin
  摘要：A class of risk-neutral generalized Nash equilibrium problems is introduced in which the feasible strategy set of each player is subject to a common linear elliptic partial differential equation with random inputs. In addition, each player's actions are taken from a bounded, closed, and convex set on the individual strategies and a bound constraint on the common state variable. Existence of Nash equilibria and first-order optimality conditions are derived by exploiting higher integrability and...
• An exact penalty approach for optimization with nonnegative orthogonality constraints AI翻译
  作者：Jiang, Bo; Meng, Xiang; Wen, Zaiwen; Chen, Xiaojun
  作者单位：Nanjing Normal University; Massachusetts Institute of Technology (MIT); Peking University; Peking University; Hong Kong Polytechnic University
  摘要：Optimization with nonnegative orthogonality constraints has wide applications in machine learning and data sciences. It is NP-hard due to some combinatorial properties of the constraints. We first propose an equivalent optimization formulation with nonnegative and multiple spherical constraints and an additional single nonlinear constraint. Various constraint qualifications, the first- and second-order optimality conditions of the equivalent formulation are discussed. By establishing a local e...
• Nonlinear acceleration of momentum and primal-dual algorithms AI翻译
  作者：Bollapragada, Raghu; Scieur, Damien; D'Aspremont, Alexandre
  作者单位：University of Texas System; University of Texas Austin; Inria; Centre National de la Recherche Scientifique (CNRS); CNRS - Institute for Information Sciences & Technologies (INS2I); Universite PSL; Ecole Normale Superieure (ENS); Universite PSL; Ecole Normale Superieure (ENS); Centre National de la Recherche Scientifique (CNRS)
  摘要：We describe convergence acceleration schemes for multistep optimization algorithms where the underlying fixed-point operator is not symmetric. In particular, our analysis handles algorithms with momentum terms such as Nesterov's accelerated method or primal-dual methods. The acceleration technique combines previous iterates through a weighted sum, whose coefficients are computed via a simple linear system. We analyze performance in both online and offline modes, and we study in particular a va...
• Variance reduction for root-finding problems AI翻译
  作者：Davis, Damek
  作者单位：Cornell University
  摘要：Minimizing finite sums of smooth and strongly convex functions is an important task in machine learning. Recent work has developed stochastic gradient methods that optimize these sums with less computation than methods that do not exploit the finite sum structure. This speedup results from using efficiently constructed stochastic gradient estimators, which have variance that diminishes as the algorithm progresses. In this work, we ask whether the benefits of variance reduction extend to fixed ...
• The landscape of the proximal point method for nonconvex-nonconcave minimax optimization AI翻译
  作者：Grimmer, Benjamin; Lu, Haihao; Worah, Pratik; Mirrokni, Vahab
  作者单位：Johns Hopkins University; University of Chicago; Alphabet Inc.; Google Incorporated
  摘要：Minimax optimization has become a central tool in machine learning with applications in robust optimization, reinforcement learning, GANs, etc. These applications are often nonconvex-nonconcave, but the existing theory is unable to identify and deal with the fundamental difficulties this poses. In this paper, we study the classic proximal point method (PPM) applied to nonconvex-nonconcave minimax problems. We find that a classic generalization of the Moreau envelope by Attouch and Wets provide...
• Chance-constrained set covering with Wasserstein ambiguity AI翻译
  作者：Shen, Haoming; Jiang, Ruiwei
  作者单位：University of Michigan System; University of Michigan
  摘要：We study a generalized distributionally robust chance-constrained set covering problem (DRC) with a Wasserstein ambiguity set, where both decisions and uncertainty are binary-valued. We establish the NP-hardness of DRC and recast it as a two-stage stochastic program, which facilitates decomposition algorithms. Furthermore, we derive two families of valid inequalities. The first family targets the hypograph of a shifted submodular function, which is associated with each scenario of the two-stag...
• Exact solution of network flow models with strong relaxations AI翻译
  作者：de Lima, Vinicius Loti; Iori, Manuel; Miyazawa, Flavio Keidi
  作者单位：Universidade Estadual de Campinas; Universita di Modena e Reggio Emilia
  摘要：We address the solution of Mixed Integer Linear Programming (MILP) models with strong relaxations that are derived from Dantzig-Wolfe decompositions and allow a pseudo-polynomial pricing algorithm. We exploit their network-flow characterization and provide a framework based on column generation, reduced-cost variable-fixing, and a highly asymmetric branching scheme that allows us to take advantage of the potential of the current MILP solvers. We apply our framework to a variety of cutting and ...
• Linear-step solvability of some folded concave and singly-parametric sparse optimization problems AI翻译
  作者：Gomez, Andres; He, Ziyu; Pang, Jong-Shi
  作者单位：University of Southern California
  摘要：This paper studies several versions of the sparse optimization problem in statistical estimation defined by a pairwise separation objective. The sparsity (i.e., l(0)) function is approximated by a folded concave function; the pairwise separation gives rise to an objective of the Z-type. After presenting several realistic estimation problems to illustrate the Z-structure, we introduce a linear-step inner-outer loop algorithm for computing a directional stationary solution of the nonconvex nondi...
• Sum-of-squares chordal decomposition of polynomial matrix inequalities AI翻译
  作者：Zheng, Yang; Fantuzzi, Giovanni
  作者单位：University of California System; University of California San Diego; Imperial College London
  摘要：We prove decomposition theorems for sparse positive (semi)definite polynomialmatrices that can be viewed as sparsity-exploiting versions of the Hilbert-Artin, Reznick, Putinar, and Putinar-Vasilescu Positivstellensatze. First, we establish that a polynomial matrix P( x) with chordal sparsity is positive semidefinite for all x is an element of R-n if and only if there exists a sum-of-squares (SOS) polynomial sigma( x) such that s P is a sum of sparse SOS matrices. Second, we show that setting s...