-
作者：Sheriff, Mohammed Rayyan; Esfahani, Peyman Mohajerin
作者单位：Delft University of Technology
摘要：This article focuses on a class of distributionally robust optimization (DRO) problems where, unlike the growing body of the literature, the objective function is potentially nonlinear in the distribution. Existing methods to optimize nonlinear functions in probability space use the Frechet derivatives, which present both theoretical and computational challenges. Motivated by this, we propose an alternative notion for the derivative and corresponding smoothness based on Gateaux (G)-derivative ...
-
作者：Goyens, Florentin; Royer, Clement W.
作者单位：Centre National de la Recherche Scientifique (CNRS); Universite PSL; Universite Paris-Dauphine
摘要：The difficulty of minimizing a nonconvex function is in part explained by the presence of saddle points. This slows down optimization algorithms and impacts worst-case complexity guarantees. However, many nonconvex problems of interest possess a favorable structure for optimization, in the sense that saddle points can be escaped efficiently by appropriate algorithms. This strict saddle property has been extensively used in data science to derive good properties for first-order algorithms, such...
-
作者：Lewis, A. S.; Tian, Tonghua
作者单位：Cornell University
摘要：A central tool for understanding first-order optimization algorithms is the Kurdyka-& Lstrok;ojasiewicz inequality. Standard approaches to such methods rely crucially on this inequality to leverage sufficient decrease conditions involving gradients or subgradients. However, the KL property fundamentally concerns not subgradients but rather slope, a purely metric notion. By highlighting this view, and avoiding any use of subgradients, we present a simple and concise complexity analysis for firs...
-
作者：Munoz, Gonzalo; Paat, Joseph; Serrano, Felipe
作者单位：Universidad de Chile; University of British Columbia
摘要：The intersection cut framework was introduced by Balas in 1971 as a method for generating cutting planes in integer optimization. In this framework, one uses a full-dimensional convex S-free set, where S is the feasible region of the integer program, to derive a cut separating S from a non-integral vertex of a linear relaxation of S. Among all S-free sets, it is the inclusion-wise maximal ones that yield the strongest cuts. Recently, this framework has been extended beyond the integer case in ...
-
作者：Dadush, Daniel; Eisenbrand, Friedrich; Rothvoss, Thomas
作者单位：Centrum Wiskunde & Informatica (CWI); Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne; University of Washington; University of Washington Seattle
摘要：Approximate integer programming is the following: For a given convex body K subset of R-n, either determine whether K boolean AND Z(n) is empty, or find an integer point in the convex body 2 . (K-c)+c which is K, scaled by 2 from its center of gravity c. Approximate integer programming can be solved in time 2(O(n)) while the fastest known methods for exact integer programming run in time 2(O(n)) . n(n). So far, there are no efficient methods for integer programming known that are based on appr...
-
作者：Gerstbrein, Matthew; Sanita, Laura; Verberk, Lucy
作者单位：University of Waterloo; Bocconi University; Eindhoven University of Technology
摘要：An edge-weighted, vertex-capacitated graph G is called stable if the value of a maximum-weight capacity-matching equals the value of a maximum-weight fractional capacity-matching. Stable graphs play a key role in characterizing the existence of stable solutions for popular combinatorial games that involve the structure of matchings in graphs, such as network bargaining games and cooperative matching games. The vertex-stabilizer problem asks to compute a minimum number of players to block (i.e....
-
作者：Zheng, Da Wei; Henzinger, Monika
作者单位：University of Illinois System; University of Illinois Urbana-Champaign; Institute of Science & Technology - Austria
摘要：We present an auction algorithm using multiplicative instead of constant weight updates to compute a (1-epsilon)-approximate maximum weight matching (MWM) in a bipartite graph with n vertices and m edges in time O(m epsilon(-1)), beating the running time of the fastest known approximation algorithm of Duan and Pettie [JACM '14] that runs in O(m epsilon(-1)log epsilon(-1)). Our algorithm is very simple and it can be extended to give a dynamic data structure that maintains a (1-epsilon)-approxim...
-
作者：Brun, Matthew; Perini, Tyler; Sinha, Saumya; Schaefer, Andrew J.
作者单位：Massachusetts Institute of Technology (MIT); University of Minnesota System; University of Minnesota Twin Cities; Rice University
摘要：This paper investigates the potential of Lagrangian relaxations to generate quality bounds on non-dominated images of multiobjective integer programs (MOIPs). Under some conditions on the relaxed constraints, we show that a set of Lagrangian relaxations can provide bounds that coincide with every bound generated by the convex hull relaxation. We also provide a guarantee of the relative quality of the Lagrangian bound at unsupported solutions. These results imply that, if the relaxed feasible r...
-
作者：Marumo, Naoki; Takeda, Akiko
作者单位：University of Tokyo; RIKEN
摘要：We propose a new first-order method for minimizing nonconvex functions with Lipschitz continuous gradients and H & ouml;lder continuous Hessians. The proposed algorithm is a heavy-ball method equipped with two particular restart mechanisms. It finds a solution where the gradient norm is less than epsilon \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\od...
-
作者：Laemmel, Sebastian; Shikhman, Vladimir
作者单位：Technische Universitat Chemnitz
摘要：We extend the convergence analysis of the Scholtes-type regularization method for cardinality-constrained optimization problems. Its behavior is clarified in the vicinity of saddle points, and not just of minimizers as it has been done in the literature before. This becomes possible by using as an intermediate step the recently introduced regularized continuous reformulation of a cardinality-constrained optimization problem. We show that the Scholtes-type regularization method is well-defined ...
