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.
Citation
Department of Mathematical Sciences, Rensselaer Polytechnic Institute, Troy, NY 12180 USA. http://www.rpi.edu/~mitchj/papers/selorth.html