Optimization Online


Multiple cuts in separating plane algorithms

Evgeni Alekseevich Nurminski (nurminskiy.ea***at***dvfu.ru)

Abstract: 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.

Keywords: convex optimization, conjugate function, cutting plane, separating plane, center of gravity algorithm

Category 1: Convex and Nonsmooth Optimization (Convex Optimization )

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


Entry Submitted: 07/12/2016
Entry Accepted: 07/12/2016
Entry Last Modified: 08/29/2016

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society