Abstract
Interior-point methods (IPMs) for semidefinite optimization (SDO) have been studied intensively, due to their polynomial complexity and practical efficiency. Recently, J. Peng et al. introduced so-called self-regular kernel (and barrier) functions and designed primal-dual interior-point algorithms based on self-regular proximities for linear optimization (LO) problems. They also extended the approach for LO to SDO. In this paper we present a primal-dual interior-point algorithm for SDO problems based on a simple kernel function which was first presented at the Proceedings of Industrial Symposium and Optimization Day, Australia, November 2002; the function is not self-regular. We derive the complexity analysis for algorithms based on this kernel function, both with large- and small-updates. The complexity bounds are \(\mathrm{O}(qn)\log\frac{n}{\epsilon}\) and \(\mathrm{O}(q^{2}\sqrt{n})\log\frac{n}{\epsilon}\) , respectively, which are as good as those in the linear case.
Similar content being viewed by others
References
Alizadeh, F., Haeberly, J. A. and Overton, M.: A new primal-dual interior-point method for semidefinite programming, in J. G. Lewis (ed.), Proceedings of the fifth SIAM Conference on Applied Linear Algebra, SIAM, 1994, pp. 113???117.
Andersen, E. D., Gondzio, J., M??sz??ros, Cs. and Xu, X.: Implementation of interior point methods for large scale linear programming, in T. Terlaky (ed.), Interior Point Methods of Mathematical Programming, Kluwer Academic Publishers, The Netherlands, 1996, pp. 189???252.
Bai, Y. Q. and Roos, C.: A primal-dual interior-point method based on a new kernel function with linear growth rate, in Proceedings of Industrial Optimization Symposium and Optimization Day, Australia, November 2002.
Bai, Y. Q., Ghami, M. El. and Roos, C.: A comparative study of kernel functions for primal-dual interior-point algorithms in linear optimization, SIAM J. Optim. 18 (2004), 101???128.
Ben-Tal, A. and Nemirovski, A.: Lectures on Modern Convex Optimization: Analysis, Algorithm, and Engineering Applications, MPS-SIAM Series on Optimization, Vol. 02, SIAM, Philadelphia, PA, 2001.
Helmberg, C., Rendl, F., Vanderbei, R. J. and Wolkowicz, H.: An interior-point method for semidefinite programming, SIAM J. Optim. 6 (1996), 342???361.
Horn, R. A. and Johnson, C. R.: Topics in Matrix Analysis, Cambridge University Press, 1991.
Kojima, M., Mizuno, S. and Yoshise, A.: Interior-point methods for the monotone semidefinite linear complementarity problem in symmetric matrices, SIAM J. Optim. 7 (1997), 342???361.
L??tkepohl, H.: Handbook of Matrices, Wiley, 1996.
Megiddo, N.: Pathways to the optimal set in linear programming, in N. Megiddo (ed.), Progress in Mathematical Programming: Interior Point and Related Methods, Springer-Verlag, New York, 1989, pp. 131???158. Identical version in: Proceedings of the 6th Mathematical Programming Symposium of Japan, Nagoya, Japan, 1986, pp. 1???35.
Monteiro, R. D. C.: Primal-dual path-following algorithms for semidefinite programming, SIAM J. Optim. 7 (1997), 663???678.
Nesterov, Yu. E. and Todd, M. J.: Self-scaled barries and interior-point methods for convex programming, Math. Oper. Res. 22(1) (1997), 1???42.
Nesterov, Yu. E. and Todd, M. J.: Primal-dual interior-point methods for self-scaled cones, SIAM J. Optim. 8(2) (1998), 324???364 (electronic).
Peng, P., Roos, C. and Terlaky, T.: Self-regular functions and new search directions for linear and semidefinite optimization, Math. Programming 93 (2002), 129???171.
Peng, J., Roos, C. and Terlaky, T.: Self-Regularity: A New Paradigm for Primal-Dual Interior-Point Algorithms, Princeton University Press, 2002.
Roos, C., Terlaky, T. and Vial, J.-Ph.: Theory and Algorithms for Linear Optimization. An Interior-Point Approach, Wiley, Chichester, UK, 1997.
Sonnevend, G.: An ???analytic center??? for polyhedrons and new classes of global algorithms for linear (smooth, convex) programming, in A. Pr??kopa, J. Szelezs??n and B. Strazicky (eds), System Modelling and Optimization: Proceedings of the 12th IFIP-Conference held in Budapest, Hungary, September 1985, Lecture Notes in Control and Inform. Sci. 84, Springer-Verlag, Berlin, 1986, pp. 866???876.
Wolkowicz, H., Saigal, R. and Vandenberghe, L.: Handbook of Semidefinite Programming, Theory, Algorithms, and Applications, Kluwer Academic Publishers, 2000.
Author information
Authors and Affiliations
Corresponding author
Additional information
Mathematics Subject Classifications (2000)
90C22, 90C31.
Rights and permissions
About this article
Cite this article
Wang, G.Q., Bai, Y.Q. & Roos, C. Primal-Dual Interior-Point Algorithms for Semidefinite Optimization Based on a Simple Kernel Function. J Math Model Algor 4, 409–433 (2005). https://doi.org/10.1007/s10852-005-3561-3
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10852-005-3561-3