Article Contents
Article Contents

# A full-Newton step interior-point algorithm for symmetric cone convex quadratic optimization

• In this paper, we present a full-Newton step primal-dual interior-point algorithm for solving symmetric cone convex quadratic optimization problem, where the objective function is a convex quadratic function and the feasible set is the intersection of an affine subspace and a symmetric cone lies in Euclidean Jordan algebra. The search directions of the algorithm are obtained from the modification of NT-search direction in terms of the quadratic representation in Euclidean Jordan algebra. We prove that the algorithm has a quadratical convergence result. Furthermore, we present the complexity analysis for the algorithm and obtain the complexity bound as $\left\lceil 2\sqrt{r}\log\frac{\mu^0 r}{\epsilon}\right\rceil$, where $r$ is the rank of Euclidean Jordan algebras where the symmetric cone lies in.
Mathematics Subject Classification: 17C99, 90C25, 90C51.

 Citation:

•  [1] K. M. Anstreicher, D. den Hertog, C. Roos and T. Terlaky, A long-step barrier method for convex quadratic programming, Algorithmica, 10 (1993), 365-382.doi: 10.1007/BF01769704. [2] Y. Q. Bai, M. El Ghami and C. Roos, A comparative study of kernel function for primal-dual interior-point algorithms in linear optimization, SIAM J. Optim., 15 (2004), 101-128.doi: 10.1137/S1052623403423114. [3] S. Boyd and L. Vandenberghe, "Convex Optimization," Cambridge University Press, 2004. [4] J. Faraut and A. Korányi, "Analysis on Symmetric Cones," Oxford Mathematical Monographs, Oxford Science Publications, The Clarendon Press, Oxford University Press, New York, 1994. [5] L. Faybusovich, Linear systems in Jordan algebras and primal-dual interior-point algorithms, Special issue dedicated to William B. Gragg (Monterey, CA, 1996), J. Comput. Appl. Math., 86 (1997), 149-175.doi: 10.1016/S0377-0427(97)00153-2. [6] L. Faybusovich, A Jordan-algebraic approach to potential-reduction algorithms, Math. Z., 239 (2002), 117-129.doi: 10.1007/s002090100286. [7] R. D. C. Monteiro and I. Adler, Interior path following primal-dual algorithms, II: Convex quadratic programming, Math. Program., Ser. A, 44 (1989), 43-66. [8] Y. E. Nesterov and M. J. Todd, Self-scaled barriers and interior-point methods for convex programming, Math. Oper. Res., 22 (1997), 1-42.doi: 10.1287/moor.22.1.1. [9] J. Peng, C. Roos and T. Terlaky, "Self-regularity: A New Paradigm for Primal-Dual Interior-Point Algorithms," Princeton Series in Applied Mathematics, Princeton University Press, Princeton, NJ, 2002. [10] C. Roos, T. Terlaky and J.-Ph. Vial, "Theory and Algorithms for Linear Optimization. An Interior Point Approach," Wiley-Interscience Series in Discrete Mathematics and Optimization, John Wiley & Sons, Ltd., Chichester, 1997. [11] S. H. Schmieta and F. Alizadeh, Extension of primal-dual interior point algorithms to symmetric cones, Math. Program, Ser. A, 96 (2003), 409-438. [12] Changjun Yu, Kok Lay Teo, Liangsheng Zhang and Yanqin Bai, A new exact penalty function method for continuous inequality constrained optimization problems, Journal of Industrial and Management Optimization, 4 (2010), 895-910. [13] M. V. C. Vieira, "Jordan Algebraic Approach to Symmetric Optimization," Ph.D thesis, Delft University of Technology, 2007.