##
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