-
作者：Uchoa, Eduardo; Sadykov, Ruslan
作者单位：Universidade Federal Fluminense
摘要：This article probes the origins of the Column Generation technique. It begins with Kantorovich's classic 1939 work, correcting widespread misconceptions about his contributions to the Cutting Stock Problem. It then brings to light Kantorovich and Zalgaller's lesser-known 1951 book, which is revealed to contain a complete Column Generation algorithm. The article also places these contributions in the context of the turbulent USSR's political and ideological environment, essential for a deeper u...
-
作者：Li, Xiang; Shen, Zebang; Zhang, Liang; He, Niao
作者单位：Swiss Federal Institutes of Technology Domain; ETH Zurich
摘要：Continuous-time approximation of Stochastic Gradient Descent (SGD) is a crucial tool to study its escaping behaviors from stationary points. However, existing stochastic differential equation (SDE) models fail to fully capture these behaviors, even for simple quadratic objectives. Built on a novel stochastic backward error analysis framework, we derive the Hessian-Aware Stochastic Modified Equation (HA-SME), an SDE that incorporates Hessian information of the objective function into both its d...
-
作者：Ranjan, Vinit; Stellato, Bartolomeo
作者单位：Princeton University
摘要：We introduce a numerical framework to verify the finite step convergence of first-order methods for parametric convex quadratic optimization. We formulate the verification problem as a mathematical optimization problem where we maximize a performance metric (e.g., fixed-point residual at the last iteration) subject to constraints representing proximal algorithm steps (e.g., linear system solutions, projections, or gradient steps). Our framework is highly modular because we encode a wide range ...
-
作者：Kang, Sumin; Bansal, Manish
作者单位：Virginia Polytechnic Institute & State University
摘要：In this paper, we study distributionally risk-receptive and distributionally robust (or risk-averse) multistage stochastic mixed-integer programs (denoted by DRR- and DRO-MSIPs). We present cutting plane-based and reformulation-based approaches for solving DRR- and DRO-MSIPs without and with decision-dependent uncertainty to optimality. We show that these approaches are finitely convergent with probability one. Furthermore, we introduce generalizations of DRR- and DRO-MSIPs by presenting multi...
-
作者：Wirth, Elias; Pena, Javier; Pokutta, Sebastian
作者单位：Technical University of Berlin; Carnegie Mellon University
-
作者：Vaisbourd, Yakov; Choksi, Rustum; Goodwin, Ariel; Hoheisel, Tim; Schonlieb, Carola-Bibiane
作者单位：McGill University; University of Cambridge
摘要：We explore a method of statistical estimation called Maximum Entropy on the Mean (MEM) which is based on an information-driven criterion that quantifies the compliance of a given point with a reference prior probability measure. At the core of this approach lies the MEM function which is a partial minimization of the Kullback-Leibler divergence over a linear constraint. In many cases, it is known that this function admits a simpler representation (known as the Cram & eacute;r rate function). V...
-
作者：Shao, Shuai; Zivny, Stanislav
作者单位：Chinese Academy of Sciences; University of Science & Technology of China, CAS; Hefei National Laboratory; University of Oxford
摘要：General factors generalize the concept of graph matchings and have been extensively studied in combinatorial optimization. Given a graph G where each vertex v is assigned a set pi(v) of feasible degrees (called a degree constraint), the general factor problem seeks a (spanning) subgraph F of G such that degF(v)is an element of pi(v) for all v of G. When all degree constraints are symmetric Delta -matroids, the problem is solvable in polynomial-time. The weighted general factor problem further ...
-
作者：Diouane, Youssef; Fomeni, Franklin Djeumou; Hertz, Alain; Orban, Dominique; Paquette, Courtney
作者单位：Universite de Montreal; Polytechnique Montreal; Universite de Montreal; Polytechnique Montreal; McGill University
-
作者：Hyatt-Denesik, Dylan; Ameli, Afrouz Jabal; Sanita, Laura
作者单位：Eindhoven University of Technology; Bocconi University
摘要：This paper addresses a graph optimization problem, called the Witness Tree problem, which seeks a spanning tree of a graph minimizing a certain non-linear objective function. This problem is of interest because it plays a crucial role in the analysis of the best approximation algorithms for two fundamental network design problems: Steiner Tree and Node-Tree Augmentation. We will show how a wiser choice of witness trees leads to an improved approximation for Node-Tree Augmentation, and for Stei...
-
作者：Xie, Zhonglin; Yin, Wotao; Wen, Zaiwen
作者单位：Peking University; Peking University; Peking University
摘要：Recent years have seen a growing interest in understanding acceleration methods through the lens of ordinary differential equations (ODEs). Despite the theoretical advancements, translating the rapid convergence observed in continuous-time models to discrete-time iterative methods poses significant challenges. In this paper, we present a comprehensive framework integrating the inertial systems with Hessian-driven damping (ISHD) and learning-based approaches for developing optimization methods ...
