A descent method with linear programming subproblems for nondifferentiable convex optimization

Most of the descent methods developed so far suffer from the computational burden due to a sequence of constrained quadratic subproblems which are needed to obtain a descent direction. In this paper the authors present a class of proximal-type descent methods with a new direction-finding subproblem. Especially, two of them have a linear programming subproblem instead of a quadratic subproblem. Computational experience of these two methods has been performed on two well-known test problems. The results show that these methods are another very promising approach for nondifferentiable convex optimization.