conjugate gradient

A Sparse Interior Point Method for Linear Programs arising in Discrete Optimal Transport

  • Filippo Zanetti
  • Jacek Gondzio
    • Categories Convex Optimization, Linear Programming, Transportation Tags , , , ,

    Discrete Optimal Transport problems give rise to very large linear programs (LP) with a particular structure of the constraint matrix. In this paper we present an interior point method (IPM) specialized for the LP originating from the Kantorovich Optimal Transport problem. Knowing that optimal solutions of such problems display a high degree of sparsity, we … Read more

    Nonlinear conjugate gradient for smooth convex functions

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

    The method of nonlinear conjugate gradients (NCG) is widely used in practice for unconstrained optimization, but it satisfies weak complexity bounds at best when applied to smooth convex functions. In contrast, Nesterov’s accelerated gradient (AG) method is optimal up to constant factors for this class. However, when specialized to quadratic function, conjugate gradient is optimal … Read more