-
作者：Dussault, Jean-Pierre; Frappier, Mathieu; Gilbert, Jean Charles
作者单位：University of Sherbrooke; University of Sherbrooke
摘要：The semismooth Newton method is a very efficient approach for computing a zero of a large class of nonsmooth equations. When the initial iterate is sufficiently close to a regular zero and the function is strongly semismooth, the generated sequence converges quadratically to that zero, while the iteration only requires to solve a linear system. If the first iterate is far away from a zero, however, it is difficult to force its convergence using linesearch or trust regions because a semismooth ...
-
作者：Huang, Kun; Pu, Shi; Nedic, Angelia
作者单位：The Chinese University of Hong Kong, Shenzhen; Arizona State University; Arizona State University-Tempe
摘要：In this paper, we introduce an accelerated distributed stochastic gradient method with momentum for solving the distributed optimization problem, where a group of n agents collaboratively minimize the average of the local objective functions over a connected network. The method, termed Distributed Stochastic Momentum Tracking (DSMT), is a single-loop algorithm that utilizes the momentum tracking technique as well as the Loopless Chebyshev Acceleration (LCA) method. We show that DSMT can asympt...
-
作者：Diouane, Youssef; Habiboullah, Mohamed Laghdaf; Orban, Dominique
作者单位：Universite de Montreal; Polytechnique Montreal; Universite de Montreal; Polytechnique Montreal
摘要：We extend traditional complexity analyses of trust-region methods for unconstrained, possibly nonconvex, optimization. Whereas most complexity analyses assume uniform boundedness of the model Hessians, we work with potentially unbounded model Hessians. Boundedness is not guaranteed in practical implementations, in particular ones based on quasi-Newton updates such as PSB, BFGS and SR1. Our analysis is conducted for a family of trust-region methods that includes most known methods as special ca...
-
作者：Faenza, Yuri; Stein, Cliff; Wan, Jia
作者单位：Columbia University; Massachusetts Institute of Technology (MIT)
摘要：Gale and Shapley's stability criterion enjoys a rich mathematical structure, which propelled its application in various settings. Although immensely popular, the approach by Gale and Shapley cannot encompass all the different features that arise in applications, motivating the search for alternative solution concepts. We investigate alternatives that rely on the concept of internal stability, a notion introduced for abstract games by von Neumann and Morgenstern and motivated by the need of fin...
-
作者：Doikov, Nikita; Grapiglia, Geovani Nunes
作者单位：Cornell University
摘要：In this work, we propose a method for minimizing non-convex functions with Lipschitz continuous pth-order derivatives, starting from p >= 1 . The method, however, only requires derivative information up to order (p-1) , since the pth-order derivatives are approximated via finite differences. To ensure oracle efficiency, instead of recomputing a finite-difference approximation of the pth-order derivative at every iteration, we attempt to reuse each approximation for m consecutive iterations bef...
-
作者：Del Pia, Alberto; Khajavirad, Aida
作者单位：University of Wisconsin System; University of Wisconsin Madison; University of Wisconsin System; University of Wisconsin Madison; Lehigh University
摘要：We consider the multilinear polytope, defined as the convex hull of the feasible region of a lifted binary polynomial optimization problem. We define a relaxation in an extended space for this polytope, which we call the complete edge relaxation. The complete edge relaxation is stronger than several well-known relaxations of the multilinear polytope, including the standard linearization, the flower relaxation, and the intersection of all possible recursive McCormick relaxations. In addition, f...
-
作者：Morton, David P.; Dowson, Oscar; Pagnoncelli, Bernardo K.
作者单位：Northwestern University; SKEMA Business School; Universite Cote d'Azur
摘要：We study a class of multi-stage stochastic programs, which incorporate modeling features from Markov decision processes (MDPs). This class includes structured MDPs with continuous action and state spaces. We extend policy graphs to include decision-dependent uncertainty for one-step transition probabilities as well as a limited form of statistical learning. We focus on the expressiveness of our modeling approach, illustrating ideas with a series of examples of increasing complexity. As a solut...
-
作者：Rodrigues, Barbara; Carvalho, Margarida; Anjos, Miguel F.; Sugishita, Nagisa
作者单位：University of Edinburgh; University of Edinburgh; Heriot Watt University; Universite de Montreal; Universite de Montreal; Universite de Montreal; Polytechnique Montreal
摘要：Bilevel optimization has garnered growing interest over the past decade. However, little attention has been paid to detecting and dealing with unboundedness in these problems, with most research assuming a bounded high-point relaxation. In this paper, we address unboundedness in bilevel and multilevel optimization by studying its computational complexity. We show that deciding whether an optimistic linear bilevel problem is unbounded is strongly NP-complete, even without coupling constraints. ...
-
作者：Van Dyk, Madison; Klause, Kim; Koenemann, Jochen; Megow, Nicole
作者单位：University of Bremen; University of Waterloo
摘要：Modern parcel logistic networks are designed to ship demand between given origin, destination pairs of nodes in an underlying directed network. Efficiency dictates that volume needs to be consolidated at intermediate nodes in typical hub-and-spoke fashion. In practice, such consolidation requires parcel sortation. In this work, we propose a mathematical model for the physical requirements, and limitations of parcel sortation. We then show that it is NP-hard to determine whether a feasible sort...
-
作者：Yoon, TaeHo; Ryu, Ernest K.; Grimmer, Benjamin
作者单位：Johns Hopkins University; University of California System; University of California Los Angeles
摘要：For nonexpansive fixed-point problems, Halpern's method with optimal parameters, its so-called H-dual algorithm, and in fact, an infinite family of algorithms containing them, all exhibit the exact minimax optimal convergence rate. In this work, we provide a characterization of the complete, exhaustive family of distinct algorithms using predetermined step-sizes, represented as lower triangular H-matrices, which attain the same optimal convergence rate. The characterization is based on polynom...
