-
作者：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.
-
作者：Munoz, Gonzalo; Paat, Joseph; Xavier, Alinson S.
作者单位：Universidad de O'Higgins; University of British Columbia; United States Department of Energy (DOE); Argonne National Laboratory
摘要：A branch-and-bound (BB) tree certifies a dual bound on the value of an integer program. In this work, we introduce the tree compression problem (TCP): Given a BB treeTthat certifies a dual bound, can we obtain a smaller tree with the same (or stronger) bound by either (1) applying a different disjunction at some node inTor (2) removing leaves fromT? We believe such post-hoc analysis of BB trees may assist in identifying helpful general disjunctions in BB algorithms. We initiate our study by co...
-
作者：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...
-
作者：De Loera, Jesus A.; Marsters, Brittney; Xu, Luze; Zhang, Shixuan
作者单位：University of California System; University of California Davis; Texas A&M University System; Texas A&M University College Station
摘要：We investigate the semigroup of integer points inside a convex cone. We extend classical results in integer linear programming to integer conic programming. We show that the semigroup associated with nonpolyhedral cones can sometimes have a notion of finite generating set with the help of a group action. We show this is true for the cone of positive semidefinite matrices (PSD) and the second-order cone (SOC). Both cones have a finite generating set of integer points, similar in spirit to Hilbe...
-
作者：Cartis, Coralia; Zhu, Wenqi
作者单位：University of Oxford
摘要：High-order tensor methods for solving both convex and nonconvex optimization problems have recently generated significant research interest, due in part to the natural way in which higher derivatives can be incorporated into adaptive regularization frameworks, leading to algorithms with optimal global rates of convergence and local rates that are faster than Newton's method. On each iteration, to find the next solution approximation, these methods require the unconstrained local minimization o...
-
作者：Au, Yu Hin; Tuncel, Levent
作者单位：University of Saskatchewan; University of Waterloo
摘要：We study the lift-and-project rank of the stable set polytopes of graphs with respect to the Lov & aacute;sz-Schrijver SDP operator LS+\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\,\textrm{LS}\,}}_+$$\end{document}, with a particular focus on finding and characterizing the smallest graphs with a given LS+\doc...
-
作者：Luke, D. Russell
作者单位：University of Gottingen
摘要：We present a Markov-chain analysis of blockwise-stochastic algorithms for solving partially block-separable optimization problems. Our main contributions to the extensive literature on these methods are statements about the Markov operators and distributions behind the iterates of stochastic algorithms, and in particular the regularity of Markov operators and rates of convergence of the distributions of the corresponding Markov chains. This provides a detailed characterization of the moments o...
-
作者：Au, Yu Hin; Tuncel, Levent
作者单位：University of Saskatchewan; University of Waterloo
摘要：We study the lift-and-project rank of the stable set polytopes of graphs with respect to the Lov & aacute;sz-Schrijver SDP operator LS+\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\,\textrm{LS}\,}}_+$$\end{document}. In particular, we focus on a search for relatively small graphs with high LS+\documentclass[12...
-
作者：Lasserre, Jean B.
作者单位：Centre National de la Recherche Scientifique (CNRS); Universite de Toulouse; Universite Toulouse 1 Capitole; Toulouse School of Economics
摘要：Given two measures mu,nu\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mu ,\nu $$\end{document} on Rd\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \...
-
作者：Kilinc-Karzan, Fatma; Sun, Shengding
作者单位：Carnegie Mellon University; University of Cambridge
摘要：We study quadratic programs with m ball constraints, and the strength of a lifted convex relaxation for it recently proposed by Burer (2024). Burer shows this relaxation is exact when m=2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$m=2$$\end{document}. For general m, Burer (2024) provides numerical evidence that...
