Mathematical Programming

最新文章

• Distributionally robust expectation inequalities for structured distributions AI翻译
  作者：Van Parys, Bart P. G.; Goulart, Paul J.; Morari, Manfred
  作者单位：Massachusetts Institute of Technology (MIT); University of Oxford; University of Pennsylvania
  摘要：Quantifying the risk of unfortunate events occurring, despite limited distributional information, is a basic problem underlying many practical questions. Indeed, quantifying constraint violation probabilities in distributionally robust programming or judging the risk of financial positions can both be seen to involve risk quantification under distributional ambiguity. In this work we discuss worst-case probability and conditional value-at-risk problems, where the distributional information is ...
• Sample average approximation with sparsity-inducing penalty for high-dimensional stochastic programming AI翻译
  作者：Liu, Hongcheng; Wang, Xue; Yao, Tao; Li, Runze; Ye, Yinyu
  作者单位：State University System of Florida; University of Florida; Pennsylvania Commonwealth System of Higher Education (PCSHE); Pennsylvania State University; Pennsylvania State University - University Park; Pennsylvania Commonwealth System of Higher Education (PCSHE); Pennsylvania State University; Pennsylvania State University - University Park; Stanford University
  摘要：The theory on the traditional sample average approximation (SAA) scheme for stochastic programming (SP) dictates that the number of samples should be polynomial in the number of problem dimensions in order to ensure proper optimization accuracy. In this paper, we study a modification to the SAA in the scenario where the global minimizer is either sparse or can be approximated by a sparse solution. By making use of a regularization penalty referred to as the folded concave penalty (FCP), we sho...
• An algorithm for nonsmooth optimization by successive piecewise linearization AI翻译
  作者：Fiege, Sabrina; Walther, Andrea; Griewank, Andreas
  作者单位：University of Paderborn; Universidad Yachay Tech
  摘要：We present an optimization method for Lipschitz continuous, piecewise smooth (PS) objective functions based on successive piecewise linearization. Since, in many realistic cases, nondifferentiabilities are caused by the occurrence of abs(), max(), and min(), we concentrate on these nonsmooth elemental functions. The method's idea is to locate an optimum of a PS objective function by explicitly handling the kink structure at the level of piecewise linear models. This piecewise linearization can...
• Convergence of inertial dynamics and proximal algorithms governed by maximally monotone operators AI翻译
  作者：Attouch, Hedy; Peypouquet, Juan
  作者单位：Universite de Montpellier; Universidad Tecnica Federico Santa Maria; Centre National de la Recherche Scientifique (CNRS); CNRS - National Institute for Mathematical Sciences (INSMI); Universidad de Chile; Universidad de Chile; Centre National de la Recherche Scientifique (CNRS); CNRS - National Institute for Mathematical Sciences (INSMI)
  摘要：We study the behavior of the trajectories of a second-order differential equation with vanishing damping, governed by the Yosida regularization of a maximally monotone operator with time-varying index, along with a new Regularized Inertial Proximal Algorithm obtained by means of a convenient finite-difference discretization. These systems are the counterpart to accelerated forward-backward algorithms in the context of maximally monotone operators. A proper tuning of the parameters allows us to...
• Learning in games with continuous action sets and unknown payoff functions AI翻译
  作者：Mertikopoulos, Panayotis; Zhou, Zhengyuan
  作者单位：Communaute Universite Grenoble Alpes; Institut National Polytechnique de Grenoble; Universite Grenoble Alpes (UGA); Centre National de la Recherche Scientifique (CNRS); Inria; Stanford University
  摘要：This paper examines the convergence of no-regret learning in games with continuous action sets. For concreteness, we focus on learning via dual averaging, a widely used class of no-regret learning schemes where players take small steps along their individual payoff gradients and then mirror the output back to their action sets. In terms of feedback, we assume that players can only estimate their payoff gradients up to a zero-mean error with bounded variance. To study the convergence of the ind...
• Quadratic optimization with orthogonality constraint: explicit Lojasiewicz exponent and linear convergence of retraction-based line-search and stochastic variance-reduced gradient methods AI翻译
  作者：Liu, Huikang; So, Anthony Man-Cho; Wu, Weijie
  作者单位：Chinese University of Hong Kong; Chinese University of Hong Kong
  摘要：The problem of optimizing a quadratic form over an orthogonality constraint (QP-OC for short) is one of the most fundamental matrix optimization problems and arises in many applications. In this paper, we characterize the growth behavior of the objective function around the critical points of the QP-OC problem and demonstrate how such characterization can be used to obtain strong convergence rate results for iterative methods that exploit the manifold structure of the orthogonality constraint ...
• Exploiting problem structure in optimization under uncertainty via online convex optimization AI翻译
  作者：Nam Ho-Nguyen; Kilinc-Karzan, Fatma
  作者单位：Carnegie Mellon University
  摘要：In this paper, we consider two paradigms that are developed to account for uncertainty in optimization models: robust optimization (RO) and joint estimation-optimization (JEO). We examine recent developments on efficient and scalable iterative first-order methods for these problems, and show that these iterative methods can be viewed through the lens of online convex optimization (OCO). The standard OCO framework has seen much success for its ability to handle decision-making in dynamic, uncer...
• Routing optimization with time windows under uncertainty AI翻译
  作者：Zhang, Yu; Baldacci, Roberto; Sim, Melvyn; Tang, Jiafu
  作者单位：Southwestern University of Finance & Economics - China; National University of Singapore; University of Bologna; National University of Singapore; Dongbei University of Finance & Economics
  摘要：We study an a priori Traveling Salesman Problem with Time Windows (tsptw) in which the travel times along the arcs are uncertain and the goal is to determine within a budget constraint, a route for the service vehicle in order to arrive at the customers' locations within their stipulated time windows as well as possible. In particular, service at customer's location cannot commence before the beginning of the time window and any arrival after the end of the time window is considered late and c...
• Oracle complexity of second-order methods for smooth convex optimization AI翻译
  作者：Arjevani, Yossi; Shamir, Ohad; Shiff, Ron
  作者单位：Weizmann Institute of Science
  摘要：Second-order methods, which utilize gradients as well as Hessians to optimize a given function, are of major importance in mathematical optimization. In this work, we prove tight bounds on the oracle complexity of such methods for smooth convex functions, or equivalently, the worst-case number of iterations required to optimize such functions to a given accuracy. In particular, these bounds indicate when such methods can or cannot improve on gradient-based methods, whose oracle complexity is m...
• A new use of Douglas-Rachford splitting for identifying infeasible, unbounded, and pathological conic programs AI翻译
  作者：Liu, Yanli; Ryu, Ernest K.; Yin, Wotao
  作者单位：University of California System; University of California Los Angeles
  摘要：In this paper, we present a method for identifying infeasible, unbounded, and pathological conic programs based on Douglas-Rachford splitting. When an optimization program is infeasible, unbounded, or pathological, the iterates of Douglas-Rachford splitting diverge. Somewhat surprisingly, such divergent iterates still provide useful information, which our method uses for identification. In addition, for strongly infeasible problems the method produces a separating hyperplane and informs the us...