-
作者：Adly, Samir; Attouch, Hedy
作者单位：Universite de Limoges; Centre National de la Recherche Scientifique (CNRS); Universite de Montpellier
摘要：In aHilbert spaceH, we introduce a newclass of first-order algorithms which naturally occur as discrete temporal versions of an inertial differential inclusion jointly involving viscous friction and dry friction. The function f : H -> Rto be minimized is supposed to be differentiable (not necessarily convex), and enters the algorithm via its gradient. The dry friction damping function phi : H -> R+ is convex with a sharp minimum at the origin, (typically phi(x) = r parallel to x parallel to wi...
-
作者：Bodur, Merve; Ahmed, Shabbir; Boland, Natashia; Nemhauser, George L.
作者单位：University of Toronto; University System of Georgia; Georgia Institute of Technology
摘要：We consider integer programming (IP) problems consisting of (possibly a large number of) subsystems and a small number of coupling constraints that link variables from different subsystems. Such problems are called loosely coupled or nearly decomposable. In this paper, we exploit the idea of resource-directive decomposition to reformulate the problem so that it can be decomposed into a resource-directive master problem and a set of multiobjective programming subproblems. Recent methods develop...
-
作者：Dash, Sanjeeb; Gunluk, Oktay; Lee, Dabeen
作者单位：International Business Machines (IBM); IBM USA; Cornell University; Institute for Basic Science - Korea (IBS)
摘要：Many practical integer programming problems involve variables with one or two-sided bounds. Dunkel and Schulz (A refined Gomory-Chvatal closure for polytopes in the unit cube, , 2012) considered a strengthened version of Chvatal-Gomory (CG) inequalities that use 0-1 bounds on variables, and showed that the set of points in a rational polytope that satisfy all these strengthened inequalities is a polytope. Recently, we generalized this result by considering strengthened CG inequalities that use...
-
作者：Yang, Minghan; Milzarek, Andre; Wen, Zaiwen; Zhang, Tong
作者单位：Peking University; The Chinese University of Hong Kong, Shenzhen; Shenzhen Research Institute of Big Data; Shenzhen Institute of Artificial Intelligence & Robotics for Society; Peking University; Hong Kong University of Science & Technology
摘要：In this paper, a novel stochastic extra-step quasi-Newton method is developed to solve a class of nonsmooth nonconvex composite optimization problems. We assume that the gradient of the smooth part of the objective function can only be approximated by stochastic oracles. The proposed method combines general stochastic higher order steps derived from an underlying proximal type fixed-point equation with additional stochastic proximal gradient steps to guarantee convergence. Based on suitable bo...
-
作者：Hwang, Hark-Chin
作者单位：Kyung Hee University
摘要：In this paper, we consider the subcontracting and single-item lot-sizing problem with constant capacities, which is uncapacitated in subcontracting but capacitated in production. For a holistic understanding of the problem, an infinite-period model is proposed. Such a model provides a unified view of a capacitated lot-sizing problem. The usefulness of the infinite-period model is shown by the principle that the firm's production schedule drives the subcontractor's supply schedule. For efficien...
-
作者：Wang, Alex L.; Kilinc-Karzan, Fatma
作者单位：Carnegie Mellon University
摘要：We consider the generalized trust region subproblem (GTRS) ofminimizing a nonconvex quadratic objective over a nonconvex quadratic constraint. Alifting of this problem recasts the GTRS as minimizing a linear objective subject to two nonconvex quadratic constraints. Our first main contribution is structural: we give an explicit description of the convex hull of this nonconvex set in terms of the generalized eigenvalues of an associated matrix pencil. This result may be of interest in building r...
-
作者：Johnstone, Patrick R.; Eckstein, Jonathan
作者单位：Rutgers University System; Rutgers University New Brunswick
摘要：This work is concerned with the classical problem of finding a zero of a sum of maximal monotone operators. For the projective splitting framework recently proposed by Combettes and Eckstein, we show how to replace the fundamental subproblem calculation using a backward step with one based on two forward steps. The resulting algorithms have the same kind of coordination procedure and can be implemented in the same block-iterative and highly flexible manner, but may perform backward steps on so...
-
作者：Zhang, Junyu; Xiao, Lin
作者单位：Princeton University; Facebook Inc
摘要：We consider the problem of minimizing composite functions of the form f(g(x))+h(x), where f and h are convex functions (which can be nonsmooth) and g is a smooth vector mapping. In addition, we assume that g is the average of finite number of component mappings or the expectation over a family of random component mappings. We propose a class of stochastic variance-reduced prox-linear algorithms for solving such problems and bound their sample complexities for finding an epsilon-stationary poin...
-
作者：Jansen, Klaus; Klein, Kim-Manuel; Maack, Marten; Rau, Malin
作者单位：University of Kiel; Communaute Universite Grenoble Alpes; Universite Grenoble Alpes (UGA)
摘要：Integer linear programs of configurations, or configuration IPs, are a classical tool in the design of algorithms for scheduling and packing problems where a set of items has to be placed in multiple target locations. Herein, a configuration describes a possible placement on one of the target locations, and the IP is used to choose suitable configurations covering the items. We give an augmented IP formulation, which we call the module configuration IP. It can be described within the framework...
-
作者：Yue, Man-Chung; Kuhn, Daniel; Wiesemann, Wolfram
作者单位：Hong Kong Polytechnic University; Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne; Imperial College London
摘要：Wasserstein balls, which contain all probability measures within a pre-specified Wasserstein distance to a reference measure, have recently enjoyed wide popularity in the distributionally robust optimization and machine learning communities to formulate and solve data-driven optimization problems with rigorous statistical guarantees. In this technical note we prove that the Wasserstein ball is weakly compact under mild conditions, and we offer necessary and sufficient conditions for the existe...
