This paper presents an extended version of the separation plane algorithms for subgradient-based finite-dimensional nondifferentiable convex blackbox 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 overcomes known computational complexity bounds for the general case.
Citation
Nurminski, E.A.: Multiple cuts in separating planes algorithms. In: Kochetov, Y., Khachay, M., Beresnev, V., Nurminski, E., Pardalos, P. (eds) Discrete Optimization and Operations Research. 9th International Conference, DOOR 2016 Vladivostok, Russia, September 19-23, 2016. Proceedings. Lecture Notes in Computer Science, vol. 9869 pp. 430-440. Springer, Heidelberg (2016) DOI; 10.1007/978-3-319-44914-2.34