Abstract
In this paper, we propose a full Nesterov-Todd (NT) step infeasible interior-point algorithm for convex quadratic symmetric cone optimization based on Euclidean Jordan algebra. The algorithm uses only one feasibility step in each main iteration. The complexity result coincides with the best-known iteration bound for infeasible interior-point methods.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Bai, Y.Q., Zhang, L.P.: A full-Newton step interior-point algorithm for symmetric cone convex quadratic optimization. J. Ind. Manag. Optim. 7(4), 891–906 (2011)
Faraut, J., Kornyi, A.: Analysis on Symmetric Cones, Oxford Mathematical Monographs. The Clarendon Press Oxford University Press, New York (1994)
Faybusovich, L.: A Jordan-algebraic approach to potential-reduction algorithms. Mathematicsche Zeitschrift 239(1), 117–129 (2002)
Faybusovich, L.: Linear systems in Jordan algebras and primal-dual interior-point algorithms. J. Comput. Appl. Math. 86, 149–175 (1997)
Kheirfam, B., Mahdavi-Amiri, N.: A full Nesterov-Todd step infeasible interior-point algorithm for symmetric cone linear complementarity problem. Bull. Iranian Math. Soc. 40(3), 541–564 (2014)
Kheirfam, B.: A new complexity analysis for full-Newton step infeasible interior-point algorithm for horizontal linear complementarity problems. J. Optim. Theory Appl. 161(3), 853–869 (2014)
Kheirfam, B.: A new infeasible interior-point method based on Darvay’s technique for symmetric optimization. Ann. Oper. Res. 211(1), 209–224 (2013)
Kheirfam, B.: A full Nesterov-Todd step infeasible interior-point algorithm for symmetric optimization based on a specific kernel function, Numer. Algebra Control Optim. 3(4), 601–614 (2013)
Kheirfam, B.: A full step infeasible interior-point method for Cartesian P ∗(κ)-SCLCP. Optim. Lett. 10(3), 591–603 (2016)
Kheirfam, B.: An improved full-Newton step O(n) infeasible interior-point method for horizontal linear complementarity problem. Numer. Algorithms. 71(3), 491–503 (2016)
Kheirfam, B.: A corrector-predictor path-following method for convex quadratic symmetric cone optimization. J. Optim. Theory Appl. 164(1), 246–260 (2015)
Kojima, M., Megiddo, N., Mizuno, S.: A primal-dual infeasible-interior-point algorithm for linear programming. Math. Program. 61, 263–280 (1993)
Li, L., Toh, K.C.: A polynomial-time inexact interior-point method for convex quadratic symmetric cone programming. J. Math. Indus. 2, 199–212 (2010B)
Lustig, I.J.: Feasibility issues in a primal-dual interior-point methods for linear programming. Math. Progrem. 49, 145–162 (1990)
Maros, I., Meszaros, C.: Departmental Technical Report DOC 97/6, Department of Computing, Imperial College, London, U.K., A repository of convex quadratic programming problems
Nesterov, Y.E., Todd, M.J.: Self-scaled barriers and interior-point methods for convex programming. Math. Oper. Res. 22, 1–42 (1997)
Rangarajan, B.K.: Polynomial convergence of infeasible interior-point methods over symmetric cones. SIAM J. Optim. 16(4), 1211–1229 (2006)
Roos, C.: A full-Newton step O(n) infeasible interior-point algorithm for linear optimization. SIAM J. Optim. 16, 1110–1138 (2006)
Roos, C.: An improved and simplified full-Newton step O(n) infeasible interior-point method for linear optimization. SIAM J. Optim. 25(1), 102–114 (2015)
Roos, C., Terlaky, T., Vial, J-Ph: Theory and Algorithms for Linear Optimization. An Interior-Point Approach. Wiley, Chichester (1997)
Schmieta, S.H., Alizadeh, F.: Extension of primal-dual interior-point algorithm to symmetric cones. Math. Program. 96(3), 409–438 (2003)
Sturm, J.F.: Similarity and other spectral relations for symmetric cones. Linear Algebra Appl. 312(1-3), 135–154 (2000)
Wang, G.Q., Zhang, Z.H., Zhu, D.T.: On extending primal-dual interior-point method for linear optimization to convex quadratic symmetric cone optimization. Numer. Funct. Anal. Optim. 34(5), 576–603 (2013)
Wang, G.Q., Yu, C.J., Teo, K.L.: A new full Nesterov-Todd step feasible interior-point method for convex quadratic symmetric cone optimization. Appl. Math. Comput. 221, 329–343 (2013)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Kheirfam, B. An infeasible full-NT step interior point algorithm for CQSCO. Numer Algor 74, 93–109 (2017). https://doi.org/10.1007/s11075-016-0140-9
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11075-016-0140-9
Keywords
- Convex quadratic symmetric cone optimization
- Interior-point method
- Infeasible method
- Euclidean Jordan algebra
- Polynomial complexity