A method for convex minimization based on translated first-order approximations (Q1681778)

The paper considers the unconstrained minimization of a real-valued function that is assumed to be convex and not necessarily smooth. A method is presented based on a convex, piecewise affine model of the objective function, and it does not necessarily minorize the objective function. The method generates a possible displacement from the current point on the basis of information gathered from many subgradients. The convergence of the proposed method is established. Numerical results are reported on 48 randomly generated instances of a multicommodity min-cost network flow problem characterized by fixed costs on the arcs.