Convex nondifferentiable optimization: a survey focused on the analytic center cutting plane method. (English) Zbl 1065.90060

Summary: 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.


90C25 Convex programming
49J52 Nonsmooth analysis
90-02 Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut


Full Text: DOI


[1] Becker R., Acta Numerica 2001 pp 1– (2001)
[2] Björck A., An Optimal Control Approach to Error Control and Mesh Adaptation in Finite Element Methods (1996)
[3] Bramble J.H., Math. Comp. 50 pp 1– (1988)
[4] Conn A.R., Mathematical Programming 50 pp 177– (1991) · Zbl 0737.90062
[5] Dennis J.E., Classics Appl. Math. 16, in: Numerical methods for unconstrained optimization and nonlinear equations (1996) · Zbl 0847.65038
[6] Griewank A., Encyclopedia of Optimization (2001)
[7] Griewank A., Evaluating derivatives, principles and techniques of algorithmic differentiation. Number 19 in Frontiers in Appl. Math (2000) · Zbl 0958.65028
[8] Griewank A., SIAM Journal of Numerical Analysis 24 pp 684– (1987) · Zbl 0627.65067
[9] Griewank A., Maintaining factorized KKT systems subject to rank-one updates of Hessians and Jacobians (2002) · Zbl 1196.90130
[10] Nash S.G., Linear and nonlinear programming. McGraw-Hill Series in Industrial Engineering and Management Science (1996)
[11] Naumann U., Efficient calculation of Jacobian matrices by optimized application of the chain rule to computational graphs (1999) · Zbl 0932.65019
[12] Nocedal J., Numerical optimization. Springer Series in Operation Research (1999) · Zbl 0930.65067
[13] Powell M.J.D., Nonlinear Programming pp 27– (1978)
[14] Powell M.J.D., Numerical Methods for Nonlinear Algebraic Equations pp 77– (1970)
[15] Wagner M., Mathematical Programming 87 pp 317– (2000)
[16] Zulehner W., AMS Mathematics of Computation 71 (238) pp 479– (2000) · Zbl 0996.65038
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.