Convex nondifferentiable optimization: a survey
focussed on the analytic center cutting plane method
Jean-Louis Goffin and Jean-Philippe Vial
We present a survey of nondifferentiable optimization problems and methods with
special focus on the analytic center cutting plane method. We propose a
self-contained convergence analysis, that uses the formalism of the
theory of self-concordant functions, but for the main results, we give direct
proofs based on the properties of the logarithmic function. We also provide an
in depth analysis of two extensions that are very relevant to practical problems:
the case of multiple cuts and the case of deep cuts.
We further examine extensions to problems including feasible sets partially
described by an explicit barrier function, and to the case of nonlinear cuts.
Finally, we review several implementation issues and discuss some applications.
Logilab Technical Report 99.02,
Department of Management Studies, University of Geneva, Switzerland, February,