Abstract
In this paper we propose primal-dual interior-point algorithms for semidefinite optimization problems based on a new kernel function with a trigonometric barrier term. We show that the iteration bounds are \(O(\sqrt{n}\log(\frac{n}{\epsilon}))\) for small-update methods and \(O(n^{\frac{3}{4}}\log(\frac{n}{\epsilon}))\) for large-update, respectively. The resulting bound is better than the classical kernel function. For small-update, the iteration complexity is the best known bound for such methods.
Similar content being viewed by others
References
Bai, Y.Q., El Ghami, M., Roos, C.: A comparative study of kernel functions for primal-dual interior-point algorithms in linear optimization. SIAM J. Optim. 15(1), 101–128 (2004)
Bai, Y.Q., Guo, J., Roos, C.: A new kernel function yielding the best known iteration bounds for primal-dual interior-point algorithms. Acta Math. Sin., Engl. Ser. 25(12), 2169–2178 (2009)
Bai, Y.Q., Roos, C.: A polynomial-time algorithm for linear optimization based a new simple kernel function. Optim. Methods Softw. 18(6), 631–646 (2003)
Bai, Y.Q., Lesaja, G., Roos, C., Wang, G.Q., El Ghami, M.: A class of large-update and small-update primal-dual interior-point algorithms for linear optimization. J. Optim. Theory Appl. 138(3), 341–359 (2008)
Bai, Y.Q., El Ghami, M., Roos, C.: A new efficient large-update primal-dual interior-point method based on a finite barrier. SIAM J. Optim. 13(3), 766–782 (2003)
Bai, Y.Q., El Ghami, M., Roos, C.: Kernel function based algorithms for semidefinite optimization. Int. J. RAIRO-Oper. Res. 43(2), 189–199 (2009)
De Klerk, E.: Aspects of Semidefinite Programming. Applied Optimization, vol. 65. Kluwer Academic, Dordrecht (2002)
El Ghami, M., Guennoun, Z.A., Bouali, S., Steihaug, T.: Interior-point methods for linear optimization based on a kernel function with trigonmetric barrier term. J. Comput. Appl. Math. (2011). doi:10.1016/j.cam.2011.05.036
El Ghami, M., Steihaug, T., Roos, C.: A generic primal-dual IPMS for semidefinite based on kernel functions. Optim. Methods Softw. 25(3), 387–403 (2010)
Helmberg, C.: Simedefinite programming for combinatorial optimization. Technical Report 00-34, Konrad-Zuse-Zentrum für Informationstechink Berlin, Takustrabe 7, D-14195 Berlin (2000)
Horn, R.A., Johnson, C.R.: Topics in Matrix Analysis. Cambridge University Press, Cambridge (1991)
Karmarkar, N.K.: A new polynomial-time algorithm for linear programming. Combinatorica 4, 375–395 (1984)
Kojima, M., Shida, M., Hara, S.: Interior point methods for the monotone semidefinite linear complementarity problem in symmetric matrices. SIAM J. Optim. 7, 86–125 (1997)
Mitrinović, D.S.: Analytic Inequalities. Springer, New York (1970)
Nesterov, Y.E., Todd, M.J.: Self-scaled barriers and interior-point methods for convex programming. Math. Oper. Res. 22(1), 1–42 (1997)
Nesterov, Y.E., Nemirovskii, A.S.: Interior point polynomial algorithms in convex programming. In: SIAM Stud. Appl. Math., vol. 13. SIAM, Philadelphia (1994)
Peng, J., Roos, C., Terlaky, T.: Self-regular functions and new search directions for linear and semidefinite optimization. Math. Program. 93(1), 129–171 (2002)
Peng, J., Roos, C., Terlaky, T.: Self-Regularity: A New Paradigm for Primal-Dual Interior-Point Algorithms. Princeton University Press, Princeton (2002)
Peng, J., Roos, C., Terlaky, T.: A new class of polynomial primal-dual methods for linear and semidefinite optimization. Eur. J. Oper. Res. 143, 234–256 (2002)
Qian, Z.G., Bai, Y.Q., Wang, G.Q.: Complexity analysis of interior-point algorithm based on a new kernel function for semidefinite optimization. J. Shanghai Univ. (Engl Ed). 12(5), 388–394 (2008)
Roos, C., Terlaky, T., Vial, J.-Ph.: Theory and Algorithms for Linear Optimization. An Interior-Point Approach. Wiley, Chichester (1997)
Todd, M.J.: A study of search directions in primal-dual interior-point methods for semidefinite programming. Optim. Methods Softw. 11, 1–46 (1999)
Wang, G.Q., Bai, Y.Q.: Primal-dual interior-point algorithm for convex quadratic semi-definite optimization. Nonlinear Anal. 71, 3389–3402 (2009)
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. Algorithms 4(4), 409–433 (2005)
Wolkowicz, H., Saigal, R., Vandenberghe, L.: Handbook of Semidefinite Programming, Theory, Algorithm, and Applications. Kluwer Academic, Dordrecht (2000)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Kheirfam, B. Primal-dual interior-point algorithm for semidefinite optimization based on a new kernel function with trigonometric barrier term. Numer Algor 61, 659–680 (2012). https://doi.org/10.1007/s11075-012-9557-y
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11075-012-9557-y
Keywords
- Kernel function
- Interior-point algorithm
- Semidefinite optimization
- Polynomial complexity
- Primal-dual method