-
作者：Pantuso, Giovanni; Hewitt, Mike
作者单位：University of Copenhagen; Loyola University Chicago
摘要：In this paper we extend the well-known L-Shaped method to solve two-stage stochastic programming problems with decision-dependent uncertainty. The method is based on a novel, unifying, formulation and on distribution-specific optimality and feasibility cuts for both linear and integer stochastic programs. Extensive tests on three production planning problems illustrate that the method is extremely effective on large-scale instances.
-
作者：Shen, Han; Xiao, Quan; Chen, Tianyi
作者单位：Rensselaer Polytechnic Institute
摘要：Bilevel optimization enjoys a wide range of applications in emerging machine learning and signal processing problems such as hyper-parameter optimization, image reconstruction, meta-learning, adversarial training, and reinforcement learning. However, bilevel optimization problems are traditionally known to be difficult to solve. Recent progress on bilevel algorithms mainly focuses on bilevel optimization problems through the lens of the implicit-gradient method, where the lower-level objective...
-
作者：Zhang, Junyu
作者单位：National University of Singapore
摘要：We investigate stochastic Bregman proximal gradient (SBPG) methods for minimizing a finite-sum nonconvex function Psi(x):=1n & sum;i=1nfi(x)+phi(x)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\Psi (x):=\frac{1}{n}\sum _{i=1}<^>nf_i(x)+\phi (x)$$\end{document}, where phi\documentclass[12pt]{minimal} \usepackage{a...
-
作者：Bennouna, Amine; Van Parys, Bart P. G.
作者单位：Northwestern University; Massachusetts Institute of Technology (MIT); Centrum Wiskunde & Informatica (CWI)
摘要：We study the problem of designing optimal learning and decision-making formulations when only historical data is available. Prior work typically commits to a particular class of data-driven formulation and subsequently tries to establish out-of-sample performance guarantees. Following (Van Parys et al. From data to decisions: Distributionally robust optimization is optimal. Management Science 2020) we take here the opposite approach. We define first a sensible yardstick with which to measure t...
-
作者：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...
-
作者：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...
-
作者：Ghadiri, Mehrdad; Santiago, Richard; Shepherd, Bruce
作者单位：Massachusetts Institute of Technology (MIT); Swiss Federal Institutes of Technology Domain; ETH Zurich; University of British Columbia
摘要：The multilinear framework for submodular maximization was developed to achieve a tight 1-1/e\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$1-1/e$$\end{document} approximation for maximizing a monotone submodular function subject to a matroid constraint, including as special case the submodular welfare problem. The...
-
作者：Goujaud, Baptiste; Taylor, Adrien; Dieuleveut, Aymeric
作者单位：Institut Polytechnique de Paris; Ecole Polytechnique; Centre National de la Recherche Scientifique (CNRS); Universite PSL; Inria; Ecole Normale Superieure (ENS)
摘要：In this work, we show that the heavy-ball (HB\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\operatorname {HB}$$\end{document}) method provably does not reach an accelerated convergence rate on smooth strongly convex problems. More specifically, we show that for any condition number and any choice of algorithmic p...
