Using selective orthonormalization to update the analytic center after the addition of multiple cuts

John E Mitchell (mitchjrpi.edu)
Srinivasan Ramaswamy (srini_ramswamyyahoo.com)

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.

Keywords: Cutting plane, analytic center, selective orthonormalization, linear programming, convex programming

Category 1: Convex and Nonsmooth Optimization (Convex Optimization )

Category 2: Convex and Nonsmooth Optimization (Nonsmooth Optimization )

Category 3: Integer Programming (Cutting Plane Approaches )

Citation: Department of Mathematical Sciences, Rensselaer Polytechnic Institute, Troy, NY 12180 USA. http://www.rpi.edu/~mitchj/papers/selorth.html

Download: [Postscript][PDF]

Entry Submitted: 10/29/2002
Entry Accepted: 10/30/2002
Entry Last Modified: 10/29/2002

Modify/Update this entry