Download the paper, pdf.
John E. Mitchell
Department of Mathematical Sciences
Rensselaer Polytechnic Institute
Troy, NY 12180 USA
mitchj@rpi.edu
Srini Ramaswamy
Derivatives Strategy
JPMorgan,
270 Park Ave.,
New York, NY
Journal of Optimization Theory and Applications, Volume 125, Number 2, May 2005, pages 431-451.
Abstract:
We study the issue of updating the analytic center after multiple cutting planes have been added through the analytic center of the current polytope in Euclidean n-space. This is an important issue that arises at every `stage' in a cutting plane algorithm. If q cuts are to be added, with q no larger than n, we show that we can use a `Selective Orthonormalization' procedure to modify the cuts before adding them --- it is then easy to identify a direction for an affine step into the interior of the new polytope, and the next analytic center is then found in $O(q \log q)$\ Newton steps. Further, we show that multiple cut variants with selective orthonormalization of standard interior point cutting plane algorithms have the same complexity as the original algorithms.Download the paper, pdf.
Return to my list of papers.