An interior point subgradient method for linearly constrained nondifferentiable convex programming

J.B.G. Frenk, J.F. Sturm, S. Zhang

We propose in this paper an algorithm for solving linearly constrained nondifferentiable convex programming problems. This algorithm combines the ideas of the affine scaling method with the subgradient method. It is a generalization of the dual and interior point method for min-max problems proposed by Sturm and Zhang \cite{SZ95}. In the new method, the search direction is obtained by projecting in a scaled space a subgradient of the objective function with a logarithmic barrier term. The stepsize choice is analogous to the stepsize choice in the usual subgradient method. Convergence of the method is established.

Report 9612/A, Econometric Institute, Erasmus University Rotterdam.