Optimization Online


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

John E Mitchell (mitchj***at***rpi.edu)
Srinivasan Ramaswamy (srini_ramswamy***at***yahoo.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

  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 Programming Society