-
作者：Baraldi, Robert J. J.; Kouri, Drew P. P.
作者单位：United States Department of Energy (DOE); Sandia National Laboratories
摘要：Many applications require minimizing the sum of smooth and nonsmooth functions. For example, basis pursuit denoising problems in data science require minimizing a measure of data misfit plus an l(1)-regularizer. Similar problems arise in the optimal control of partial differential equations (PDEs) when sparsity of the control is desired. We develop a novel trust-region method to minimize the sum of a smooth nonconvex function and a nonsmooth convex function. Our method is unique in that it per...
-
作者：Angelidakis, Haris; Hyatt-Denesik, Dylan; Sanita, Laura
作者单位：Eindhoven University of Technology
摘要：Many network design problems deal with the design of low-cost networks that are resilient to the failure of their elements (such as nodes or links). One such problem is Connectivity Augmentation, with the goal of cheaply increasing the (edge- or node)connectivity of a given network from a value k to k + 1. The problem is NP-hard for k >= 1, and the most studied setting focuses on the case of edge-connectivity with k = 1. In this work, we give a 1.892-approximation algorithm for the NP-hard pro...
-
作者：Guenin, Bertrand; Heo, Cheolwon
作者单位：University of Waterloo
摘要：Even-cycle matroids are elementary lifts of graphic matroids and even-cut matroids are elementary lifts of cographic matroids. We present a polynomial algorithm to check if a binary matroid is an even-cycle matroid and we present a polynomial algorithm to check if a binary matroid is an even-cut matroid. These two algorithms rely on a polynomial algorithm (to be described in a pair of follow-up papers) to check if a binary matroid is pinch-graphic.
-
作者：Dey, Santanu S.; Molinaro, Marco; Wang, Guanyi
作者单位：University System of Georgia; Georgia Institute of Technology; Pontificia Universidade Catolica do Rio de Janeiro
摘要：Sparse principal component analysis with global support (SPCAgs), is the problem of finding the top-r leading principal components such that all these principal components are linear combinations of a common subset of at most k variables. SPCAgs is a popular dimension reduction tool in statistics that enhances interpretability compared to regular principal component analysis (PCA). Methods for solving SPCAgs in the literature are either greedy heuristics (in the special case of r = 1) with gua...
-
作者：Legault, Robin; Cote, Jean-Francois; Gendron, Bernard
作者单位：Laval University; Universite de Montreal; Universite de Montreal
摘要：The single-sink fixed-charge transportation problem is known to have many applications in the area of manufacturing and transportation as well as being an important subproblem of the fixed-charge transportation problem. However, even the best algorithms from the literature do not fully leverage the structure of this problem, to the point of being surpassed by modern general-purpose mixed-integer programming solvers for large instances. We introduce a novel reformulation of the problem and stud...
-
作者：Royset, Johannes O.
作者单位：United States Department of Defense; United States Navy; Naval Postgraduate School
摘要：Approximations of optimization problems arise in computational procedures and sensitivity analysis. The resulting effect on solutions can be significant, with even small approximations of components of a problem translating into large errors in the solutions. We specify conditions under which approximations are well behaved in the sense of minimizers, stationary points, and level-sets and this leads to a framework of consistent approximations. The framework is developed for a broad class of co...
-
作者：Juditsky, Anatoli; Kwon, Joon; Moulines, Eric
作者单位：Communaute Universite Grenoble Alpes; Universite Grenoble Alpes (UGA); AgroParisTech; INRAE; Universite Paris Saclay; Institut Polytechnique de Paris; Ecole Polytechnique
摘要：We introduce and analyze a new family of first-order optimization algorithms which generalizes and unifies both mirror descent and dual averaging. Within the framework of this family, we define new algorithms for constrained optimization that combines the advantages of mirror descent and dual averaging. Our preliminary simulation study shows that these new algorithms significantly outperform available methods in some situations.
-
作者：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...
-
作者：Bertsimas, Dimitris; Cory-Wright, Ryan; Pauphilet, Jean
作者单位：Massachusetts Institute of Technology (MIT); Imperial College London; International Business Machines (IBM); IBM USA; University of London; London Business School
-
作者：Na, Sen; Anitescu, Mihai; Kolar, Mladen
作者单位：University of California System; University of California Berkeley; United States Department of Energy (DOE); Argonne National Laboratory; University of Chicago
摘要：We study nonlinear optimization problems with a stochastic objective and deterministic equality and inequality constraints, which emerge in numerous applications including finance, manufacturing, power systems and, recently, deep neural networks. We propose an active-set stochastic sequential quadratic programming (StoSQP) algorithm that utilizes a differentiable exact augmented Lagrangian as the merit function. The algorithm adaptively selects the penalty parameters of the augmented Lagrangia...
