-
作者：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 ...
-
作者：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...
-
作者：Kiessling, David; Leyffer, Sven; Vanaret, Charlie
作者单位：KU Leuven; United States Department of Energy (DOE); Argonne National Laboratory; Zuse Institute Berlin
摘要：We consider nonlinearly constrained optimization problems and discuss a generic double-loop framework consisting of basic algorithmic ingredients that unifies a broad range of nonlinear optimization solvers. This framework has been implemented in the open-source solver Uno, a Swiss Army knife-like C++ optimization framework that unifies many nonlinearly constrained nonconvex optimization solvers. We illustrate the framework with a sequential quadratic programming (SQP) algorithm that maintains...
-
作者：Doikov, Nikita
作者单位：Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne
摘要：We study the composite convex optimization problems with a quasi-self-concordant smooth component. This problem class naturally interpolates between classic self-concordant functions and functions with Lipschitz continuous Hessian. Previously, the best complexity bounds for this problem class were associated with trust-region schemes and implementations of a ball optimization oracle. In this paper, we show that for minimizing quasi-self-concordant functions we can use instead the basic Newton ...
-
作者：Nie, Jiawang; Qu, Zheng; Tang, Xindong; Zhang, Linghao
作者单位：University of California System; University of California San Diego; Hong Kong Polytechnic University; Hong Kong Baptist University
摘要：This paper studies the sparse Moment-SOS hierarchy of relaxations for solving sparse polynomial optimization problems. We show that this sparse hierarchy is tight if and only if the objective can be written as a sum of sparse nonnegative polynomials, each of which belongs to the sum of the ideal and quadratic module generated by the corresponding sparse constraints. Based on this characterization, we give several sufficient conditions for the sparse Moment-SOS hierarchy to be tight. In particu...
-
作者：Chua, Chek Beng
作者单位：Nanyang Technological University
摘要：We study the Carath & eacute;odory number of homogeneous convex cones via their spectrahedral representations. A characterization of homogeneous convex cones whose ranks match their Carath & eacute;odory numbers is given. This characterization is then used to show that a homogeneous convex cone is selfdual if and only if its rank matches the Carath & eacute;odory numbers of both its closure and its dual cone. It is further used to show that the only sparse spectrahedral cones that are homogene...
