User menu

Accès à distance ? S'identifier sur le proxy UCLouvain

Complexity of the primal-dual path-following. Algorithms for the weighted determinant maximization problems with linear matrix inequalities in the narrow neighborhood

Primary tabs

Xia, Yu [UCL]

Weighted determinant maximization with linear matrix inequality constraints (maxdet-problem) is a generalization of the semidefinite programming. We give a polynomial-time complexity analysis for the path-following interior-point short-step and predictor-corrector methods for the maxdet-problem based on symmetric Newton equations for certain classes of scaling matrices.

Document type Article de périodique (Journal article)
Publication date 2008
Language Anglais
Journal information "Optimization Methods and Software" - Vol. 23, no. 3, p. 421-440 (Juin 2008)
Peer reviewed yes
Publisher Taylor & Francis Ltd. (Abingdon, United Kingdom)
issn 1055-6788
Publication status Publié
Affiliation UCL - EUEN/CORE - Center for operations research and econometrics
Keywords Interior-point method ; Determinant maximization ; Semidefinite programming ; Path-following algorithm ; Complexity
Links
  1. Alizadeh Farid, Interior Point Methods in Semidefinite Programming with Applications to Combinatorial Optimization, 10.1137/0805002
  2. Alizadeh Farid, Haeberly Jean-Pierre A., Overton Michael L., Primal-Dual Interior-Point Methods for Semidefinite Programming: Convergence Rates, Stability and Numerical Results, 10.1137/s1052623496304700
  3. Fushiki Tadayoshi, Horiuchi Shingo, Tsuchiya Takashi, A Maximum Likelihood Approach to Density Estimation with Semidefinite Programming, 10.1162/neco.2006.18.11.2777
  4. Graña Drummond L. M., Peterzil Y., THE CENTRAL PATH IN SMOOTH CONVEX SEMIDEFINITE PROGRAMS, 10.1080/02331930290019396
  5. Mizuno Shinji, Todd Michael J., Ye Yinyu, On Adaptive-Step Primal-Dual Interior-Point Algorithms for Linear Programming, 10.1287/moor.18.4.964
  6. Monteiro R., Ser. Oper. Res. Management Sci, 267 (2000)
  7. Muramatsu M., On a Commutative Class of Search Directions for Linear Programming over Symmetric Cones, 10.1023/a:1017920200889
  8. Nesterov Yu. E., Todd M. J., Self-Scaled Barriers and Interior-Point Methods for Convex Programming, 10.1287/moor.22.1.1
  9. Nesterov Yu. E., Todd M. J., Primal-Dual Interior-Point Methods for Self-Scaled Cones, 10.1137/s1052623495290209
  10. Toh Kim-Chuan, 10.1023/a:1026400522929
  11. Toh K. C., Todd M. J., Tütüncü R. H., SDPT3 — A Matlab software package for semidefinite programming, Version 1.3, 10.1080/10556789908805762
  12. Tsuchiya T., Pac. J. Optim., 3, 165 (2007)
  13. Vandenberghe Lieven, Boyd Stephen, Wu Shao-Po, Determinant Maximization with Linear Matrix Inequality Constraints, 10.1137/s0895479896303430
  14. Xia, Y. The maxdet problem – algorithm and applications in machine learning. Proceedings of the 18th RAMP Symposium. The Operations Research Society of Japan. Vol. 10,
Bibliographic reference Xia, Yu. Complexity of the primal-dual path-following. Algorithms for the weighted determinant maximization problems with linear matrix inequalities in the narrow neighborhood. In: Optimization Methods and Software, Vol. 23, no. 3, p. 421-440 (Juin 2008)
Permanent URL http://hdl.handle.net/2078.1/23649