Towards a practical volumetric cutting plane method for convex programming

Authors
Anstreicher, KM
Citation
Km. Anstreicher, Towards a practical volumetric cutting plane method for convex programming, SIAM J OPTI, 9(1), 1998, pp. 190-206
Citations number
22
Categorie Soggetti
Mathematics
Journal title
SIAM JOURNAL ON OPTIMIZATION
ISSN journal
10526234 → ACNP
Volume
9
Issue
1
Year of publication
1998
Pages
190 - 206
Database
ISI
SICI code
1052-6234(199812)9:1<190:TAPVCP>2.0.ZU;2-#
Abstract
We consider the volumetric cutting plane method for finding a point in a co nvex set C subset of R-n that is characterized by a separation oracle. We p rove polynomiality of the algorithm with each added cut placed directly thr ough the current point and show that this "central cut" version of the meth od can be implemented using no more than 25n constraints at any time.