-
作者：Jin, Qing; Georghiou, Angelos; Vayanos, Phebe; Hanasusanto, Grani A.
作者单位：University of Southern California; University of Southern California; University of Cyprus; University of Southern California; University of Illinois System; University of Illinois Urbana-Champaign
摘要：We study two-stage distributionally robust optimization (DRO) problems with decision-dependent information discovery (DDID) wherein (a portion of) the uncertain parameters are revealed only if an (often costly) investment is made at the first stage. This class of problems finds many important applications in selection problems (e.g., in hiring, project portfolio optimization, or optimal sensor location). Despite the wide applicability of the problem, it has not been previously studied. We prop...
-
作者：Chen, Lin; Lian, Jiayi; Mao, Yuchen; Zhang, Guochuan
作者单位：Zhejiang University
摘要：We investigate pseudo-polynomial time algorithms for Subset Sum. Given a multi-set X consisting of n positive integers and a target t, Subset Sum asks whether some subset of X sums to t. Bringmann proposed an O(n +t)-time algorithm [Bringmann SODA'17].An open question has naturally arisen: can Subset Sum be solved in O(n+ w)time? Here w is the largest integer in X. We make progress towards resolving the open question by proposing an O(n + root wt)-time algorithm.
-
作者：Brosch, Daniel; Puges, Diane
作者单位：University of Klagenfurt
摘要：The inducibility of a graph represents its maximum density as an induced subgraph over all possible sequences of graphs of size growing to infinity. This invariant of graphs has been extensively studied since its introduction in 1975 by Pippenger and Golumbic. In 2017, Czabarka, Sz & eacute;kely and Wagner extended this notion to leaf-labeled rooted binary trees, which are objects widely studied in the field of phylogenetics. They obtain the first results and bounds for the densities and induc...
-
作者：Jin, Qiujiang; Jiang, Ruichen; Mokhtari, Aryan
作者单位：University of Texas System; University of Texas Austin
摘要：In this paper, we explore the non-asymptotic global convergence rates of the Broyden-Fletcher-Goldfarb-Shanno (BFGS) method implemented with exact line search. Notably, due to Dixon's equivalence result, our findings are also applicable to other quasi-Newton methods in the convex Broyden class employing exact line search, such as the Davidon-Fletcher-Powell (DFP) method. Specifically, we focus on problems where the objective function is strongly convex with Lipschitz continuous gradient and He...
-
作者：Catanzaro, Daniele; Pesenti, Raffaele; Sapucaia, Allan; Wolsey, Laurence
作者单位：Universite Catholique Louvain; Universita Ca Foscari Venezia
摘要：Path-Length Matrices (PLMs) form a tree encoding scheme that is often used in the context of optimization problems defined over Unrooted Binary Trees (UBTs). Determining the conditions that a symmetric integer matrix of order n >= 3 must satisfy to encode the PLM of a UBT with n leaves is central to these applications. Here, we show that a certain subset of known necessary conditions is also sufficient to characterize the set Theta(n) of PLMs induced by the set of UBTs with n leaves. We also i...
-
作者：Luner, Alan; Grimmer, Benjamin
作者单位：Johns Hopkins University
摘要：We extend recent computer-assisted design and analysis techniques for first-order optimization over structured functions-known as performance estimation-to apply to structured sets. We prove interpolation theorems for smooth and strongly convex sets with interior point conditions and bounded diameter, showing a wide range of extremal questions amount to structured mathematical programs. Prior function interpolation theorems are recovered as a limit of our set interpolation theory. Our theory p...
-
作者：Fang, Yuchen; Lavaei, Javad; Na, Sen
作者单位：University of California System; University of California Berkeley; University of California System; University of California Berkeley; University System of Georgia; Georgia Institute of Technology
摘要：In this paper, we consider nonlinear optimization problems with a stochastic objective and deterministic equality constraints. We propose a Trust-Region Stochastic Sequential Quadratic Programming (TR-SSQP) method and establish its high-probability iteration complexity bounds for identifying first- and second-order & varepsilon;\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage...
-
作者：Kukharenko, Kirill; Sanita, Laura
作者单位：Otto von Guericke University; Bocconi University
摘要：The simplex algorithm is one of the most popular algorithms to solve linear programs (LPs). Starting at an extreme point solution of an LP, it performs a sequence of basis exchanges (called pivots) that allows one to move to a better extreme point along an improving edge-direction of the underlying polyhedron. A key issue in the simplex algorithm's performance is degeneracy, which may lead to a (potentially long) sequence of basis exchanges which do not change the current extreme point solutio...
-
作者：Zhou, Jinling; Liu, Xin; Nie, Jiawang; Tang, Xindong
作者单位：Xiangtan University; Chinese Academy of Sciences; Academy of Mathematics & System Sciences, CAS; Chinese Academy of Sciences; University of Chinese Academy of Sciences, CAS; University of California System; University of California San Diego; Hong Kong Baptist University
摘要：This paper studies how to compute global minimizers of the cubic-quartic regularization (CQR) problem where f0 is a constant, g is an n-dimensional vector, H is an n-by-n symmetric matrix, and & Vert;s & Vert; denotes the Euclidean norm of s. The parameter sigma is nonnegative while beta can have any sign. The CQR problem arises as a critical subproblem for getting efficient regularization methods for solving unconstrained nonlinear optimization. Its properties are recently well studied by Car...
-
作者：Xiao, Nachuan; Hu, Xiaoyin; Toh, Kim-Chuan
作者单位：The Chinese University of Hong Kong, Shenzhen; Shenzhen University; National University of Singapore; National University of Singapore
摘要：In this paper, we focus on providing convergence guarantees for stochastic subgradient methods in minimizing nonsmooth nonconvex functions. We first investigate the global stability of a general framework for stochastic subgradient methods, where the corresponding differential inclusion admits a coercive Lyapunov function. We prove that, for any sequence of sufficiently small stepsizes and approximation parameters, coupled with sufficiently controlled noises, the iterates are uniformly bounded...
