Month: May 2016

A unified convergence bound for conjugate gradient and accelerated gradient

  • Sahar Karimi
  • Stephen A. Vavasis
    • Categories Convex Optimization Tags , ,

    Nesterov’s accelerated gradient method for minimizing a smooth strongly convex function $f$ is known to reduce $f(\x_k)-f(\x^*)$ by a factor of $\eps\in(0,1)$ after $k\ge O(\sqrt{L/\ell}\log(1/\eps))$ iterations, where $\ell,L$ are the two parameters of smooth strong convexity. Furthermore, it is known that this is the best possible complexity in the function-gradient oracle model of computation. The … Read more

    A Polyhedral Study on Chance Constrained Program with Random Right-Hand Side

  • Kai Huang
  • Bo Zeng
  • Ming Zhao
    • Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches, Stochastic Programming Tags , , , , ,

    The essential structure of the mixed–integer programming formulation for chance–constrained program (CCP) is the intersection of multiple mixing sets with a $0-1$ knapsack. To improve our computational capacity on CCP, an underlying substructure, the (single) mixing set with a $0-1$ knapsack, has received substantial attentions recently. In this study, we consider a CCP problem with … Read more