A predictor-corrector path-following algorithm for symmetric optimization based on Darvay's technique
DOI:
https://doi.org/10.2298/YJOR120904016KKeywords:
symmetric cone optimization, interior-point method, predictor-corrector method, polynomial complexityAbstract
In this paper, we present a predictor-corrector path-following interior-point algorithm for symmetric cone optimization based on Darvay's technique. Each iteration of the algorithm contains a predictor step and a corrector step based on a modification of the Nesterov and Todd directions. Moreover, we show that the algorithm is well defined and that the obtained iteration bound is o(√rlogrμ/ε), where r is the rank of Euclidean Jordan algebra.References
Darvay, Z., “New interior point algorithms in linear programming”, Adv. Model. Optim., 5(1) (2003) 51-92.
Wang, G.Q., Bai, Y.Q., “A new full Nesterov–Todd step primal–dual path-following interior point algorithm for symmetric optimization”, J. Optim. Theory Appl., DOI 10.1007/s10957-012-0013-x.
Faraut, J., Korányi, A., Analysis on symmetric cones, Oxford Mathematical Monographs, The Clarendon Press Oxford University Press, Oxford Science Publications, New York, (1994).
Faybusovich, L., “Linear systems in Jordan algebras and primal-dual interior-point algorithms”, J. Comput. Appl. Math., 86 (1997) 149-175.
Gu, G., Zangiabadi, M., Roos, C., “Full Nesterov-Todd step infeasible interior-point method for symmetric optimization”, European J. Oper. Res., 214(3) (2011) 473-484.
Ills, T., Nagy, M., “A Mizuno-Todd-Ye type predictor-corrector algorithm for sufficient linear complementarity problems”, European J. Oper. Res., 181 (2007) 1097-1111.
Mizuno, S., Todd, M.J., Ye, Y., “On adaptive-step primal-dual interior point algorithms for linear programming”, Math. Oper. Res., 18 (1993) 964-981.
Monteiro, R. D. C., Zhang, Y., “A unified analysis for a class of path-following primal-dual interior-point algorithms for semidefinite programming”, Math. Program., 8 (1998) 281-299.
Nesterov, Y.E., Nemirovskii, A.S., Interior Point Polynomial Algorithms in Convex Programming, in: SIAM Stud. Appl. Math., Philadelphia, SIAM, 13, 1994.
Nesterov, Y.E., Todd, M.J., “Self-scaled barriers and interior-point methods for convex programming”, Math. Oper. Res., 22(1) (1997) 1-42.
Roos, C., “A full-Newton step $O(n)$ infeasible interior-point algorithm for linear optimization”, SIAM J. Optim., 16(4) (2006) 1110-1136.
Schmieta, S.H., Alizadeh, F., “Extension of primal-dual interior-point algorithm to symmetric cones”, Math. Program., 96(3) (2003) 409-438.
Sonnevend, G., Stoer, G., Zhao, G., “On the complexity of following the central path of linear programs by linear extrapolation”, Methods Oper. Res., 63, (1989) 19-31.
Sturm, J.F., “Similarity and other spectral relations for symmetric cones”, Algebra Appl., 312(1-3) (2000) 135-154.
Vieira, M.V.C., “Jordan algebraic approach to symmetric optimization”, Ph.D thesis, Electrical Engineering, Mathematics and Computer Science, Delft University of Technology, The Netherlands, 2007.
Ye, Y., Anstreicher, K., “On quadratic and √ convergence of a predictor-corrector algorithm for LCP”, Math. Program., 62 (1993) 537-551.
Downloads
Published
Issue
Section
License
Copyright (c) 2014 YUJOR
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
