Skip to main content
SpringerLink
Log in

Primal-Dual Path-Following Algorithms for Determinant Maximization Problems With Linear Matrix Inequalities

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

Abstract

Primal-dual path-following algorithms are considered for determinant maximization problem (maxdet-problem). These algorithms apply Newton's method to a primal-dual central path equation similar to that in semidefinite programming (SDP) to obtain a Newton system which is then symmetrized to avoid nonsymmetric search direction. Computational aspects of the algorithms are discussed, including Mehrotra-type predictor-corrector variants. Focusing on three different symmetrizations, which leads to what are known as the AHO, H..K..M and NT directions in SDP, numerical results for various classes of maxdet-problem are given. The computational results show that the proposed algorithms are efficient, robust and accurate.

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, J.-P.A. Haeberly, and M. Overton, “Primal-dual interior-point methods for semidefinite programming: Convergence results, stability and numerical results,” SIAM J. Optimization, vol. 8, pp. 746-768, 1998.

    Google Scholar 

  2. F. Alizadeh, J.-P.A. Haeberly, and M. Overton, “Complementarity and nondegeneracy in semidefinite programming,” Math. Programming, vol. 77, pp. 111-128, 1997.

    Google Scholar 

  3. S. Boyd, L. El Ghaoui, E. Feron, and V. Balakrishnan, “Linear matrix inequalities in system and control theory,” vol. 15 of Studies in Applied Mathematics, SIAM, Philadelphia, PA, 1994.

    Google Scholar 

  4. K. Fujisawa, M. Kojima, and K. Nakata, “Exploiting sparsity in primal-dual interior-point methods for semidefinite programming,” Mathematical Programming, vol. 79, pp. 235-253, 1997.

    Google Scholar 

  5. K. Fujisawa, M. Kojima, and K. Nakata, “SDPA (semidefinite programming algorithm)—User's manual,” Research Report, Department of Mathematical and Computing Science, Tokyo Institute of Technology, Tokyo.

  6. D. Goldfarb and K. Scheinberg, “Interior point trajectories in semidefinite programming,” manuscript, 1996.

  7. C. Helmberg, F. Rendl, R. Vanderbei, and H. Wolkowicz, “An interior-point method for semidefinite programming,” SIAM J. Optimization, vol. 6, pp. 342-361, 1996.

    Google Scholar 

  8. M. Kojima, S. Shindoh, and S. Hara, “Interior-point methods for the monotone linear complementarity problem in symmetric matrices,” SIAM J. Optimization, vol. 7, pp. 86-125, 1997.

    Google Scholar 

  9. C.-J. Lin and R. Saigal, “An infeasible start predictor-corrector method for semi-definite linear programming,” manuscript, Department of Industrial and Operations Engineering, University of Michigan, December, 1995.

  10. R.D.C. Monteiro, “Primal-dual path following algorithms for semidefinite programming,” SIAM J. Optimization, vol. 7, pp. 663-678, 1997.

    Google Scholar 

  11. R.D.C. Monteiro and Y. Zhang, “A unified analysis of path-following primal-dual interior-point algorithms for semidefinite programming,” Mathematical Programming, vol. 81, pp. 281-299, 1998.

    Google Scholar 

  12. Y. Nesterov and A. Nemirovsky, “Interior-Point Polynomial Algorithms in Convex Programming,” vol. 13 of Studies in Applied Mathematics, SIAM: Philadelphia, PA, 1994.

    Google Scholar 

  13. Y. Nesterov and M.J. Todd, “Primal-dual interior-point methods for self-scaled cones,” SIAM J. Optimization, vol. 8, pp. 324-364, 1998.

    Google Scholar 

  14. Y. Saad, “Iterative Methods for Sparse Linear Systems,” PWS Publishing Company: Boston, MA, 1996.

    Google Scholar 

  15. M.J. Todd, K.C. Toh, and R.H. Tütüncü, “On the Nesterov-Todd direction in semidefinite programming,” SIAM J. Optimization vol. 8, pp. 769-796, 1998.

    Google Scholar 

  16. K.C. Toh, “Search directions for primal-dual interior point methods in semidefinite programming,” Technical Report 722, Department of Mathematics, National University of Singapore, Singapore, July, 1997. Revised in March 1998.

    Google Scholar 

  17. K.C. Toh, “A note on the condition number of the Jacobian associated with the AHO direction for solving maxdet-problem,” manuscript in preparation.

  18. L. Vandenberghe and S. Boyd, “Semidefinite programming,” SIAM Review, vol. 38, pp. 49-95, 1996.

    Google Scholar 

  19. L. Vandenberghe, S. Boyd, and S.-P. Wu, “Determinant maximization with linear matrix inequality equalities,” SIAM J. Matrix Analysis and Applications, vol. 19, pp. 499-533, 1998.

    Google Scholar 

  20. Y. Zhang, “On extending some primal-dual interior-point algorithms from linear programming to semidefinite programming,” SIAM J. Optimization, vol. 8, pp. 365-386, 1998.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Mathematics, National University of Singapore, 10 Kent Ridge Crescent, Singapore, 119260

    Kim-Chuan Toh

Authors
  1. Kim-Chuan Toh
    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

Toh, KC. Primal-Dual Path-Following Algorithms for Determinant Maximization Problems With Linear Matrix Inequalities. Computational Optimization and Applications 14, 309–330 (1999). https://doi.org/10.1023/A:1026400522929

Download citation

  • Issue Date:

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

Search

Navigation