Abstract
A large-update primal-dual interior-point algorithm is presented for solving second order cone programming. At each iteration, the iterate is always following the usual wide neighborhood \(\mathcal {N}_\infty^-(\tau)\), but not necessary staying within it. However, it must stay within a wider neighborhood \(\mathcal {N}(\tau,\beta)\). We show that the method has \(O(\sqrt{r}L)\) iteration complexity bound which is the best bound of wide neighborhood algorithm for second-order cone programming.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Rangarajan, B.K.: Polynomial Convergence of Infeasible-Interior-Point Methods over Symmetric Cones. SIAM J. OPTIM. 16(4), 1211–1229 (2006)
Alizadeh, F., Goldfarb, D.: Second-order cone programming. Math. Program. 95, 3–51 (2003)
Peng, J.M., Roos, C., Terlaky, T.: Self-regular functions and new search directions for linear and semidefinite optimization. Math. Program. Ser. A 93, 129–171 (2002)
Toh, K.C., Tütüncü, R.H., Todd, M.J.: SDPT3 Version 3.02-A MATLAB software for semidefinite-quadratic-linear programming (2002)
Todd, M.J., Toh, K.C., Tütüncü, R.H.: On the Nesterov-Todd direction in semidefinite programming. SIAM Journal on Optimization 8, 769–796 (1998)
Shivaswamy, P.K., Bhattacharyya, C., Smola, A.J.: Second Order Cone Programming Approaches for Handling Missing and Uncertain Data. Journal of Machine Learning Research 7, 1283–1314 (2006)
Monteiro, R.D.C., Zhang, Y.: A unified analysis for a class of long-step primal-dual path-following interior-point algorithms for semidefinie programming. Math. Program. 81, 281–299 (1998)
Debnath, R., Muramatsu, M., Takahashi, H.: An Efficient Support Vector Machine Learning Method with Second-Order Cone Programming for Large-Scale Problems. Applied Intelligence 23, 219–239 (2005)
Nesterov, Y.E., Todd, M.J.: Primal-dual Interior-point Methods for Self-scaled Cones. SIAM J. OPTIM. 8(2), 324–364 (1998)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Fang, L., He, G., Feng, Z., Wang, Y. (2010). A Large-Update Primal-Dual Interior-Point Method for Second-Order Cone Programming. In: Zhang, L., Lu, BL., Kwok, J. (eds) Advances in Neural Networks - ISNN 2010. ISNN 2010. Lecture Notes in Computer Science, vol 6063. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-13278-0_14
Download citation
DOI: https://doi.org/10.1007/978-3-642-13278-0_14
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-13277-3
Online ISBN: 978-3-642-13278-0
eBook Packages: Computer ScienceComputer Science (R0)