Skip to main content
SpringerLink
Log in

A Computational Study of the Homogeneous Algorithm for Large-scale Convex Optimization

  • Published:
Computational Optimization and Applications Aims and scope Submit manuscript

Abstract

Recently the authors have proposed a homogeneous and self-dual algorithm for solving the monotone complementarity problem (MCP) [5]. The algorithm is a single phase interior-point type method; nevertheless, it yields either an approximate optimal solution or detects a possible infeasibility of the problem. In this paper we specialize the algorithm to the solution of general smooth convex optimization problems, which also possess nonlinear inequality constraints and free variables. We discuss an implementation of the algorithm for large-scale sparse convex optimization. Moreover, we present computational results for solving quadratically constrained quadratic programming and geometric programming problems, where some of the problems contain more than 100,000 constraints and variables. The results indicate that the proposed algorithm is also practically efficient.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. F. Alizadeh, "Interior point methods in semidefinite programming with applications to combinatorial optimization," SIAM J. on Optim., vol. 5, no.1, 1995.

  2. E.D. Andersen, "Finding all linearly dependent rows in large-scale linear programming," Optimization Methods and Software, vol. 6, pp. 219-227, 1995.

    Google Scholar 

  3. E.D. Andersen and K.D. Andersen, "Presolving in linear programming," Math. Programming, vol. 71, no.2, pp. 221-245, 1995.

    Google Scholar 

  4. E.D. Andersen and X. Xu, "The QMPS format for quadratically constrained optimization problems," Technical Report, Department of Management, Odense University, Denmark, 1996. Available from: http://www.ou.dk/busieco/man/faculty/eda.html.

    Google Scholar 

  5. E.D. Andersen and Y. Ye, "On a homogeneous algorithm for the monotone complementarity problem," Technical Report, Department of Management Sciences, The University of Iowa, 1995. Revised November 1996, to appear in Mathematical Programming.

  6. E.D. Andersen and Y. Ye, "On a homogeneous algorithm for a monotone complementarity problem with nonlinear equality constraints,” in Complementarity and Variational Problems: State of the Art, M.C. Ferris and J.S. Pang (Eds.), SIAM: Philadelphia, PA, USA, 1997.

    Google Scholar 

  7. K.D. Andersen, "Minimizing a sum of norms (Large-scale solutions of symmetric positive definite linear systems)," Ph.D. Thesis, Odense University, 1995.

  8. K. Anstreicher and J.-P. Vial, "On the convergence of an infeasible primal-dual interior-point method for convex programming," Optimization Methods and Software, vol. 3, pp. 273-283, 1994.

    Google Scholar 

  9. O. Bahn, J.L. Goffin, J.-Ph. Vial, and O. Du Merle, "Experimental behaviour of an interior point cutting plane algorithm for convex programming: An application to geometric programming," Discrete Appl. Math., vol. 49, pp. 2-23, 1994.

    Google Scholar 

  10. D.P. Baron, "Quadratic programming with quadratic constraints," Naval Res. Logist. Quart., vol. 19, pp. 253-260, 1972.

    Google Scholar 

  11. M.S. Bazaraa, H.D. Sherali, and C.M. Shetty, Nonlinear Programming: Theory and Algorithms, 2nd edition, John Wiley and Sons: New York, 1993.

    Google Scholar 

  12. C. Beightler and D.T. Phillips, Applied Geometric Programming, John Wiley and Sons: New York, 1976.

    Google Scholar 

  13. A. Ben-Tal and A. Nemirovskii, "Potential reduction polynomial time method for truss topology design," SIAM J. on Optim., vol. 4, no.3, 1994.

  14. K.M. Bretthauer and B. Shetty, "The nonlinear resource allocation problem," Oper. Res., vol. 43, no.4, pp. 670-683, 1995.

    Google Scholar 

  15. R.W. Cottle, J.-S. Pang, and R.E. Stone, "The linear complementarity problem," Computer Science and Scientific Computing, Academic Press: San Diego, 1992.

    Google Scholar 

  16. E. de Klerk, C. Roos, and T. Terlaky, "Initialization in semidefinite programming via a self-dual skew-symmetric embedding," Technical Report 96-10, Faculty of Mathematics and Informatics, Delft University of Technology, 1996.

  17. R.S. Dembo, "Second-order algorithms for posynomial geometric programming dual, Part I: Analysis," Math. Programming, vol. 17, pp. 156-175, 1979.

    Google Scholar 

  18. D. den Hertog, J. Kaliski, C. Roos, and T. Terlaky, "A logarithmic barrier cutting plane method for convex programming," in Annals of Operations Research, I. Maros and G. Mitra (Eds.), Baltzer Science Publishers: Amsterdam, The Netherlands, vol. 58, pp. 69-98, 1995.

    Google Scholar 

  19. J.E. Dennis, Jr. and R.B. Schnabel, "Numerical methods for unconstrained optimization and nonlinear equations," Prentice-Hall, Inc.: Englewood Cliffs, NJ 07632, USA, 1983.

    Google Scholar 

  20. R.J. Duffin, E.L. Peterson, and C. Zener, Geometric Programming, John Wiley and Sons: New York, 1969.

    Google Scholar 

  21. E. Phan-huy-Hao, "Quadratically constrained quadratic programming: Some applications and a method for solution," Zeitschrift für Operations Research, vol. 26, pp. 105-119, 1982.

    Google Scholar 

  22. A.S. El-Bakry, R.A. Tapia, T. Tsuchiya, and Y. Zhang, "On the formulation and theory of the primal-dual Newton interior-point method for nonlinear programming," J. Optim. Theory Appl., vol. 89, no.3, pp. 507-541, 1996.

    Google Scholar 

  23. A.V. Fiacco and G.P. McCormick, Nonlinear Programming: Sequential Unconstrained Minimization Techniques, John Wiley and Sons: New York, 1968.

    Google Scholar 

  24. R.W. Freund and F. Jarre, "A QMR-based interior-point algorithm for solving linear programs," Math. Programming, vol. 76, no.1, pp. 183-210, 1997.

    Google Scholar 

  25. P.E. Gill, W. Murray, M.A. Saunders, J.A. Tomlin, and M.H. Wright, "On the projected Newton barrier methods for linear programming and an equivalence to Karmarkar’s projective method," Math. Programming, vol. 36, pp. 183-209, 1986.

    Google Scholar 

  26. J.-L. Goffin, J. Gondzio, R. Sarkissian, and J.-P. Vial, "Solving nonlinear multicommodity flow problems by the analytic center cutting plane method," Math. Programming, vol. 76, no.1, pp. 131-154, 1997.

    Google Scholar 

  27. J. Gondzio, R. Sarkissian, and J.-P. Vial, "Using an interior point method for the master problem in a decomposition approach," Technical Report 1995. 30, Logilab, HEC Geneva, Section of Management Studies, University of Geneva, 1995. To appear in European Journal of Operations Research.

  28. O. Güler, "Existence of interior points and interior paths in nonlinear monotone complementarity problems," Math. Oper. Res., vol. 18, pp. 148-162, 1993.

    Google Scholar 

  29. F. Jarre, "On the convergence of the method of analytic centers when applied to convex quadratic programs," Math. Programming, vol. 49, pp. 341-358, 1991.

    Google Scholar 

  30. F. Jarre, M. Kocvara, and J. Zowe, "Interior point methods for mechanical design problems," Technical Report 173, Institut für Angewandte Mathematik, Universität Erlangen-Nürnburg, 1996.

  31. N. Karmarkar, "A polynomial-time algorithm for linear programming," Combinatorica, vol. 4, pp. 373-395, 1984.

    Google Scholar 

  32. M. Kojima, N. Megiddo, and S. Mizuno, "A primal-dual infeasible-interior-point algorithm for linear programming," Math. Programming, vol. 61, pp. 263-280, 1993.

    Google Scholar 

  33. M. Kojima, S. Mizuno, and A. Yoshise, "A primal-dual interior point algorithm for linear proramming," in Progress in Mathematical Programming: Interior-Point Algorithms and Related Methods, N. Megiddo (Ed.), Springer Verlag: Berlin, 1989, pp. 29-47.

    Google Scholar 

  34. K.O. Kortanek, F. Potra, and Y. Ye, "On some efficient interior point methods for nonlinear convex programming," Linear Algebra Appl., vol. 152, pp. 169-189, 1991.

    Google Scholar 

  35. K.O. Kortanek and X. Xu, "Numerical experiments with XGP: An optimizer for geometric programming and some comparisons with other solvers," Technical Report, Department of Management Sciences, The University of Iowa, 1995.

  36. K.O. Kortanek, X. Xu, and Y. Ye, "An infeasible interior-point algorithm for solving primal and dual geometric programs," Math. Programming, vol. 76, no.1, pp. 155-181, 1997.

    Google Scholar 

  37. I.J. Lustig, R.E. Marsten, and D.F. Shanno, "Interior point methods for linear programming: Computational state of the art," ORSA J. on Comput., vol. 6, no.1, pp. 1-15, 1994.

    Google Scholar 

  38. S. Mehrotra, "On the implementation of a primal-dual interior point method," SIAM J. on Optim., vol. 2, no.4, pp. 575-601, 1992.

    Google Scholar 

  39. S. Mehrotra and J. Sun, "A method of analytic centers for quadratically constrained convex quadratic programming," SIAM J. Numer. Anal., vol. 28, no.2, pp. 529-544, 1991.

    Google Scholar 

  40. Y. Nesterov and A. Nemirovskii, Interior-Point Polynomial Algorithms in Convex Programming, 1st edition, SIAM: Philadelphia, PA, 1994.

    Google Scholar 

  41. Y. Nesterov and M. Todd, "Self-scaled barries and interior point methods for convex programming," Technical Report, CORE, Lovain-la-Neuve, 1994. Discussion paper 9462.

  42. F.A. Potra and R. Sheng, "Homogeneous interior-point algorithms for semidefinite programming," Technical Report 82/1995, Department of Mathematics, The University of Iowa, 1995.

  43. L. Vandenberghe and S. Boyd, "Semidefinite programming," SIAM Rev., vol. 38, no.1, pp. 49-95, 1996.

    Google Scholar 

  44. R.J. Vanderbei, "Symmetric quasi-definite matrices," SIAM J. on Optim., vol. 5, no.1, 1995.

  45. R.J. Vanderbei and T.J. Carpenter, "Symmetric indefinite systems for interior point methods," Math. Programming, vol. 58, pp. 1-32, 1993.

    Google Scholar 

  46. J.-P. Vial, "Computational experience with a primal-dual algorithm for smooth convex programming," Optimization Methods and Software, vol. 3, pp. 273-283, 1994.

    Google Scholar 

  47. X. Xu, P.-F. Hung, and Y. Ye, "A simplified homogeneous and self-dual linear programming algorithm and its implementation," Annals of Operations Research, vol. 62, pp. 151-171, 1996.

    Google Scholar 

  48. G. Xue and Y. Ye, "An efficient algorithm for minimizing a sum of Euclidean norms with applications," Technical Report, Department of Computer Science and Electrical Engineering, The University of Vermont, June 1995. University of Vermont Research Report, CSEE/955/01-01, to appear in SIAM J. on Optimization.

  49. H. Yamashita and H. Yabe, "Superlinear and quadratic convergence of some primal-dual interior point methods for constrained optimization," Math. Programming, vol. 75, no.3, pp. 377-397, 1996.

    Google Scholar 

  50. Y. Ye, M.J. Todd, and S. Mizuno, "An O(√nL)-iteration homogeneous and self-dual linear programming algorithm," Math. Oper. Res., vol. 19, pp. 53-67, 1994.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Management, Odense University, Campusvej 55, DK-5230, Odense M, Denmark

    Erling D. Andersen

  2. Department of Management Sciences, The University of Iowa, Iowa City, Iowa, 52242, USA

    Yinyu Ye

Authors
  1. Erling D. Andersen
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Yinyu Ye
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Andersen, E.D., Ye, Y. A Computational Study of the Homogeneous Algorithm for Large-scale Convex Optimization. Computational Optimization and Applications 10, 243–269 (1998). https://doi.org/10.1023/A:1018369223322

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1023/A:1018369223322

Search

Navigation