Multiple cuts in separating plane algorithms

This paper presents an extended version of the separation plane algorithm for subgradient-based finite-dimensional nondifferentiable convex optimization. The extension introduces additional cuts for epigraph of the conjugate of objective function which improve the convergence of the algorithm. The case of affine cuts is considered in more details and it is shown that it requires solution of an auxiliary convex subproblem the dimensionality of which depends on the number of additional cuts and can be kept arbitrary low. Therefore algorithm can make use of the efficient algorithms of low-dimensional nondifferentiable convex optimization which overcome known computational complexity bounds for the general case.