-
作者：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...
-
作者：Mulansky, Bernd; Potschka, Andreas
作者单位：TU Clausthal
-
作者：Laude, Emanuel; Patrinos, Panagiotis
作者单位：KU Leuven
摘要：This paper studies a novel algorithm for nonconvex composite minimization which can be interpreted in terms of dual space nonlinear preconditioning for the classical proximal gradient method. The proposed scheme can be applied to additive composite minimization problems whose smooth part exhibits an anisotropic descent inequality relative to a reference function. It is proved that the anisotropic descent property is closed under pointwise average if the Bregman distance generated by the conjug...
-
作者：Jin, Billy; Klein, Nathan; Williamson, David P.
作者单位：Purdue University System; Purdue University; Boston University; Cornell University
摘要：A long-standing conjecture for the traveling salesman problem (TSP) states that the integrality gap of the standard linear programming relaxation of the TSP (sometimes called the Subtour LP or the Held-Karp bound) is at most 4/3 for symmetric instances of the TSP obeying the triangle inequality; that is, the cost of an optimal tour is at most 4/3 times the value of the value of the corresponding linear program. There is a variety of evidence in support of the conjecture (see, for instance, Goe...
-
作者：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. ...
-
作者：Chekuri, Chandra; Jain, Rhea
作者单位：University of Illinois System; University of Illinois Urbana-Champaign
摘要：The Survivable Network Design problem (SNDP) is a well-studied problem, (partly) motivated by the design of networks that are robust to faults under the assumption that any subset of edges up to a specific number can fail. We consider non-uniform fault models where the subset of edges that fail can be specified in different ways. We consider three models: the flexible graph connectivity model (Adjiashvili, D.: Fault-tolerant shortest paths - beyond the uniform failure model (unpublished).) (Ad...
