A Nonlinear Analytic Center Cutting Plane Method for a Class of Convex Programming Problems

F. Sharifi Mokhtarian and J.-L. Goffin

A cutting plane algorithm for minimizing a convex function subject to constraints define d by a separation oracle is presented. The algorithm is based on approximate analytic cen ters. The nonlinearity of the objective function is taken into account, yet the feasible region is approximated by a containing polytope. This containing polytope is regularly updated either by adding a new cut at or by shifting an existing cut to the test point. In the first phase of the algorithm, the test point is an approximate analytic center of a containing polytope. In the second phase, it becomes an approximate analytic center of the intersection of a containing polytope and a level set of the nonlinear objective function. We prove that the algorithm converges and establish its complexity. In the case where the oracle generates a finite number of cuts, the algorithm is polynomial in this number, while it is a polynomial approximation scheme (in the dimension of the space) in the case where the oracle can generate an infinite number of cuts.

GERAD Technical Report G-96-53 November 1996

Contact: goffin@management.mcgill.ca