A Polynomial Cutting Surfaces Algorithm for the Convex Feasibility Problem Defined by Self-Concordant Inequalities
Tóm tắt
Consider a nonempty convex set in ℝm which is defined by a finite number of smooth convex inequalities and which admits a self-concordant logarithmic barrier. We study the analytic center based column generation algorithm for the problem of finding a feasible point in this set. At each iteration the algorithm computes an approximate analytic center of the set defined by the inequalities generated in the previous iterations. If this approximate analytic center is a solution, then the algorithm terminates; otherwise either an existing inequality is shifted or a new inequality is added into the system. As the number of iterations increases, the set defined by the generated inequalities shrinks and the algorithm eventually finds a solution of the problem. The algorithm can be thought of as an extension of the classical cutting plane method. The difference is that we use analytic centers and “convex cuts” instead of arbitrary infeasible points and linear cuts. In contrast to the cutting plane method, the algorithm has a polynomial worst case complexity of O(Nlog 1/ε) on the total number of cuts to be used, where N is the number of convex inequalities in the original problem and ε is the maximum common slack of the original inequality system.
Tài liệu tham khảo
K. Afkhamie, Z.-Q. Luo, and K.M. Wong, “Interior point column generation algorithms for adaptive filtering,” Manuscript, Communications Research Laboratory, McMaster University, Hamilton, Ontario, Canada, 1997.
A. Altman and K.C. Kiwiel, “A note on some analytic center cutting plane methods for convex feasibility and minimization problems,” Systems Research Institute, Newelska 6, 01-447, Warsaw, Poland, June 1994.
D.S. Atkinson and P.M.Vaidya, “Acutting plane algorithm for convex programming that uses analytic centers,” Mathematical Programming, vol. 69, pp. 1–44, 1995.
O. Bahn, O. Du Merle, J.-L. Goffin, and J.-P. Vial, “Experimental behavior of an interior point cutting plane algorithm for convex programming: an application to geometric programming,” Discrete Applied Mathematics, vol. 49, pp. 3–23, 1994.
O. Bahn, O. Du Merle, J.-L. Goffin, and J.-P. Vial, “A cutting plane method from analytic centers for stochastic programming,” Mathematical Programming, vol. 69, pp. 45–74, 1995.
D. den Hertog, F. Jarre, C. Roos, and T. Terlaky, “A sufficient condition for self-concordance, with application to some classes of structured convex programming problems,” Mathematical Programming, vol. 69, pp. 75–88, 1995.
J.-L. Goffin, Z.-Q. Luo, and Y. Ye, “Complexity analysis of an interior cutting plane method for convex feasibility problems,” SIAM J. Optimization, vol. 6, pp. 638–652, 1996.
J.-L. Goffin, Z.-Q. Luo, and Y. Ye, “On the complexity of a column generation algorithm for convex or quasiconvex feasibility problems,” in Large Scale Optimization: State of the Art, W.W. Hager, D.W. Hearn, and P.M. Pardalos, (Eds.), Kluwer Academic Publishers B.V., 1994, pp. 182-189.
J.-L. Goffin and J.-P. Vial, “Shallow, deep and very deep cuts in the analutic center cutting plane method,” Logilab Technical Report 96.1, University of Geneva, Switzerland, 1996.
F. Jarre, The Method of Analytic Centers for Smooth Convex Programs, Ph.D. Thesis, Institut für Angwandte Mathematik und Statistik, Universität Würtzburg, Germany, 1989.
Z.-Q. Luo, “Analysis of a cutting plane method that uses weighted analytic center and multiple cuts,” SIAM Journal on Optimization, vol. 7, pp. 697–716, 1997.
Z.-Q. Luo and J. Sun, “An analytic center based column generation algorithm for the convex quadratic feasibility problem,” SIAM J. Optimization, vol. 9, no. 1, pp. 217–235, 1998.
S. Mehrotra and J. Sun, “An interior point algorithm for solving smooth convex programs based on Newton's method,” Contemporary Mathematics, vol. 114, pp. 265–284, 1990.
S. Mehrotra and J. Sun, “On computing the center of a convex quadratically constrained set,” Mathematical Programming, vol. 50, pp. 81–89, 1991.
Y. Nesterov, “Cutting plane algorithms from analytic centers: efficiency estimates,” Mathematical Programming, vol. 69, pp. 149–176, 1995.
Y. Nesterov and A. Nemirovskii, Interior-Point Polynomial Algorithms in Convex Programming, SIAM Studies in Applied Mathematics, Philadelphia, USA, 1993.
M.L. Overton, “A quadratically convergent method for minimizing a sum of euclidean norms,” Mathematical Programming, vol. 27, pp. 34–63, 1983.
G. Sonnevend, “New algorithms in convex programming based on a notion of 'centre' (for systems of analytic inequalities) and on rational extrapolation,” in Trends in Mathematical Optimization: Proceedings of the 4th French-German Conference on Optimization in Irsee, K.H. Hoffmann, J.B. Hiriat-Urruty, C. Lemarechal, and J. Zowe, (Eds.), Germany, 1986.
Y. Ye, “A potential reduction algorithm allowing column generation,” SIAM Journal on Optimization, vol. 2, pp. 7–20, 1992.
Y. Ye, “Complexity analysis of the analytic center cutting plane method that uses multiple cuts,” Mathematical Programming, vol. 78, pp. 85–104, 1997.