Abstract
We describe a method for solving the maximum likelihood estimate problem of a mixing distribution, based on an interior cutting plane algorithm with cuts through analytic centers. From increasingly refined discretized statistical problem models we construct a sequence of inner non-linear problems and solve them approximately applying a primal-dual algorithm to the dual formulation. Refining the statistical problem is equivalent to adding cuts to the inner problems.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
I.D. Coope and G.A. Watson, “A projected Lagrangian algorithm for semi-infinite programming,” Mathematical Programming, vol. 32, pp. 337–356, 1985.
J.-L. Goffin, Z.Q. Luo, and Y. Ye, “Complexity analysis of an interior cutting plane method for convex feasibility problems,” SIAM J. Optim., vol. 6, pp. 638–652, 1996.
J.-L. Goffin and J.-P. Vial, “Shallow, deep and very deep cuts in the analytic center cutting plane method.” Mathematical Programming, vol. 84, pp. 89–103, 1999.
J.-L. Goffin and J.-P. Vial, “Multiple cuts in the analytic center cutting plane method,” SIAM J. Optim., vol. 11, pp. 266–288, 1999.
C.C. Gonzaga, “Path following methods for linear programming,” SIAM Review, vol. 34, pp. 167–224, 1992.
D. den Hertog, Interior Point Approach to Linear, Quadratic and Convex Programming, Algorithms and Complexity, Kluwer Academic Publishers: Doordrecht, The Netherlands, 1994.
M. Kojima, S. Mizuno, and A. Yoshise, “A primal-dual interior point algorithm for linear programming,” in Progress in Mathematical Programming: Interior Point and Related Methods, N. Megiddo (Ed.), Springer Verlag: New York, 1989, pp. 29–47.
M.L. Lesperance and J.D. Kalbfleisch, “An algorithm for computing the non parametric MLE of a mixing distribution,” Journal of the American Statistical Association, vol. 87, no. 417, pp. 120–126, 1992.
B.G. Lindsay, “The geometry of mixture likelihoods: A general theory,” The Annals of Statistics, vol. 11, no. 1, pp. 86–94, 1983.
B.G. Lindsay, Mixture Models: Theory, Geometry and Applications, Institute of Mathematical Statistics, Hayward, California, and American Statistical Association: Alexandria, VA, 1995.
J.E. Mitchell and J. Todd, “Solving combinatorial optimization problems using Karmarkar's algorithm,” Mathematical Programming, vol. 56, pp. 245–284, 1992.
F.S. Mokhtarian and J.-L. Goffin, “A nonlinear analytic center cuting plane method for a class of convex programming problems,” SIAM J. Optim., vol. 8, pp. 1108–1131, 1998.
G. Sonnevend, “An analytic center for polyhedra and new classes of global algorithms for liner (smooth, convex) programming” in Lecture Notes Control Inform. Sci., Springer Verlag: New York, NY, 1985, pp. 866–876.
T. Terlaky and J.-Ph. Vial, “Computing maximum likelihood estimators of convex density functions,” SIAM J. Sci. Comput., vol. 19, no. 2, pp. 675–694, 1998.
M.J. Todd, “Potential-reduction methods in mathematical programming,” Mathematical Programming, vol. 76, pp. 3–45, 1996.
S. Wright, Primal-Dual Interior-Point Methods, SIAM Publications: Philadelphia 1997.
Y. Ye, “Complexity analysis of the analytic center cutting plane method that uses multiple cuts,” Mathematical Programming, vol. 78, pp. 85–104, 1997.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Raupp, F., Gonzaga, C. A Center Cutting Plane Algorithm for a Likelihood Estimate Problem. Computational Optimization and Applications 21, 277–300 (2002). https://doi.org/10.1023/A:1013725219527
Issue Date:
DOI: https://doi.org/10.1023/A:1013725219527