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.
Similar content being viewed by others
References
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.
F. Alizadeh, J.-P.A. Haeberly, and M. Overton, “Complementarity and nondegeneracy in semidefinite programming,” Math. Programming, vol. 77, pp. 111-128, 1997.
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.
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.
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.
D. Goldfarb and K. Scheinberg, “Interior point trajectories in semidefinite programming,” manuscript, 1996.
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.
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.
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.
R.D.C. Monteiro, “Primal-dual path following algorithms for semidefinite programming,” SIAM J. Optimization, vol. 7, pp. 663-678, 1997.
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.
Y. Nesterov and A. Nemirovsky, “Interior-Point Polynomial Algorithms in Convex Programming,” vol. 13 of Studies in Applied Mathematics, SIAM: Philadelphia, PA, 1994.
Y. Nesterov and M.J. Todd, “Primal-dual interior-point methods for self-scaled cones,” SIAM J. Optimization, vol. 8, pp. 324-364, 1998.
Y. Saad, “Iterative Methods for Sparse Linear Systems,” PWS Publishing Company: Boston, MA, 1996.
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.
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.
K.C. Toh, “A note on the condition number of the Jacobian associated with the AHO direction for solving maxdet-problem,” manuscript in preparation.
L. Vandenberghe and S. Boyd, “Semidefinite programming,” SIAM Review, vol. 38, pp. 49-95, 1996.
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.
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.
Author information
Authors and Affiliations
Rights 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
Issue Date:
DOI: https://doi.org/10.1023/A:1026400522929