# American Institute of Mathematical Sciences

October  2011, 7(4): 891-906. doi: 10.3934/jimo.2011.7.891

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

 1 Department of Mathematics, Shanghai University, 99, Shangda Road, 200444, Shanghai 2 Department of Mathematics, Shanghai University, Shanghai 200444, China

Received  November 2009 Revised  May 2011 Published  August 2011

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.
Citation: Yanqin Bai, Lipu Zhang. A full-Newton step interior-point algorithm for symmetric cone convex quadratic optimization. Journal of Industrial & Management Optimization, 2011, 7 (4) : 891-906. doi: 10.3934/jimo.2011.7.891
##### References:
 [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. doi: 10.1007/BF01769704. Google Scholar [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. doi: 10.1137/S1052623403423114. Google Scholar [3] S. Boyd and L. Vandenberghe, "Convex Optimization,", Cambridge University Press, (2004). Google Scholar [4] J. Faraut and A. Korányi, "Analysis on Symmetric Cones,", Oxford Mathematical Monographs, (1994). Google Scholar [5] L. Faybusovich, Linear systems in Jordan algebras and primal-dual interior-point algorithms,, Special issue dedicated to William B. Gragg (Monterey, 86 (1997), 149. doi: 10.1016/S0377-0427(97)00153-2. Google Scholar [6] L. Faybusovich, A Jordan-algebraic approach to potential-reduction algorithms,, Math. Z., 239 (2002), 117. doi: 10.1007/s002090100286. Google Scholar [7] R. D. C. Monteiro and I. Adler, Interior path following primal-dual algorithms, II: Convex quadratic programming,, Math. Program., 44 (1989), 43. Google Scholar [8] Y. E. Nesterov and M. J. Todd, Self-scaled barriers and interior-point methods for convex programming,, Math. Oper. Res., 22 (1997), 1. doi: 10.1287/moor.22.1.1. Google Scholar [9] J. Peng, C. Roos and T. Terlaky, "Self-regularity: A New Paradigm for Primal-Dual Interior-Point Algorithms,", Princeton Series in Applied Mathematics, (2002). Google Scholar [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, (1997). Google Scholar [11] S. H. Schmieta and F. Alizadeh, Extension of primal-dual interior point algorithms to symmetric cones,, Math. Program, 96 (2003), 409. Google Scholar [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. Google Scholar [13] M. V. C. Vieira, "Jordan Algebraic Approach to Symmetric Optimization,", Ph.D thesis, (2007). Google Scholar

show all references

##### References:
 [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. doi: 10.1007/BF01769704. Google Scholar [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. doi: 10.1137/S1052623403423114. Google Scholar [3] S. Boyd and L. Vandenberghe, "Convex Optimization,", Cambridge University Press, (2004). Google Scholar [4] J. Faraut and A. Korányi, "Analysis on Symmetric Cones,", Oxford Mathematical Monographs, (1994). Google Scholar [5] L. Faybusovich, Linear systems in Jordan algebras and primal-dual interior-point algorithms,, Special issue dedicated to William B. Gragg (Monterey, 86 (1997), 149. doi: 10.1016/S0377-0427(97)00153-2. Google Scholar [6] L. Faybusovich, A Jordan-algebraic approach to potential-reduction algorithms,, Math. Z., 239 (2002), 117. doi: 10.1007/s002090100286. Google Scholar [7] R. D. C. Monteiro and I. Adler, Interior path following primal-dual algorithms, II: Convex quadratic programming,, Math. Program., 44 (1989), 43. Google Scholar [8] Y. E. Nesterov and M. J. Todd, Self-scaled barriers and interior-point methods for convex programming,, Math. Oper. Res., 22 (1997), 1. doi: 10.1287/moor.22.1.1. Google Scholar [9] J. Peng, C. Roos and T. Terlaky, "Self-regularity: A New Paradigm for Primal-Dual Interior-Point Algorithms,", Princeton Series in Applied Mathematics, (2002). Google Scholar [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, (1997). Google Scholar [11] S. H. Schmieta and F. Alizadeh, Extension of primal-dual interior point algorithms to symmetric cones,, Math. Program, 96 (2003), 409. Google Scholar [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. Google Scholar [13] M. V. C. Vieira, "Jordan Algebraic Approach to Symmetric Optimization,", Ph.D thesis, (2007). Google Scholar
 [1] Behrouz Kheirfam, Guoqiang Wang. An infeasible full NT-step interior point method for circular optimization. Numerical Algebra, Control & Optimization, 2017, 7 (2) : 171-184. doi: 10.3934/naco.2017011 [2] Yu-Lin Chang, Chin-Yu Yang. Some useful inequalities via trace function method in Euclidean Jordan algebras. Numerical Algebra, Control & Optimization, 2014, 4 (1) : 39-48. doi: 10.3934/naco.2014.4.39 [3] Shuang Chen, Li-Ping Pang, Dan Li. An inexact semismooth Newton method for variational inequality with symmetric cone constraints. Journal of Industrial & Management Optimization, 2015, 11 (3) : 733-746. doi: 10.3934/jimo.2015.11.733 [4] Yinghong Xu, Lipu Zhang, Jing Zhang. A full-modified-Newton step infeasible interior-point algorithm for linear optimization. Journal of Industrial & Management Optimization, 2016, 12 (1) : 103-116. doi: 10.3934/jimo.2016.12.103 [5] Li-Xia Liu, Sanyang Liu, Chun-Feng Wang. Smoothing Newton methods for symmetric cone linear complementarity problem with the Cartesian $P$/$P_0$-property. Journal of Industrial & Management Optimization, 2011, 7 (1) : 53-66. doi: 10.3934/jimo.2011.7.53 [6] Behrouz Kheirfam. A full Nesterov-Todd step infeasible interior-point algorithm for symmetric optimization based on a specific kernel function. Numerical Algebra, Control & Optimization, 2013, 3 (4) : 601-614. doi: 10.3934/naco.2013.3.601 [7] Golamreza Zamani Eskandani, Hamid Vaezi. Hyers--Ulam--Rassias stability of derivations in proper Jordan $CQ^{*}$-algebras. Discrete & Continuous Dynamical Systems - A, 2011, 31 (4) : 1469-1477. doi: 10.3934/dcds.2011.31.1469 [8] M. P. de Oliveira. On 3-graded Lie algebras, Jordan pairs and the canonical kernel function. Electronic Research Announcements, 2003, 9: 142-151. [9] Xin-He Miao, Jein-Shan Chen. Error bounds for symmetric cone complementarity problems. Numerical Algebra, Control & Optimization, 2013, 3 (4) : 627-641. doi: 10.3934/naco.2013.3.627 [10] Yuan Shen, Lei Ji. Partial convolution for total variation deblurring and denoising by new linearized alternating direction method of multipliers with extension step. Journal of Industrial & Management Optimization, 2019, 15 (1) : 159-175. doi: 10.3934/jimo.2018037 [11] Peng Guo, Wenming Cheng, Yi Wang. A general variable neighborhood search for single-machine total tardiness scheduling problem with step-deteriorating jobs. Journal of Industrial & Management Optimization, 2014, 10 (4) : 1071-1090. doi: 10.3934/jimo.2014.10.1071 [12] Behrouz Kheirfam. A weighted-path-following method for symmetric cone linear complementarity problems. Numerical Algebra, Control & Optimization, 2014, 4 (2) : 141-150. doi: 10.3934/naco.2014.4.141 [13] Yi Zhang, Liwei Zhang, Jia Wu. On the convergence properties of a smoothing approach for mathematical programs with symmetric cone complementarity constraints. Journal of Industrial & Management Optimization, 2018, 14 (3) : 981-1005. doi: 10.3934/jimo.2017086 [14] Liping Tang, Xinmin Yang, Ying Gao. Higher-order symmetric duality for multiobjective programming with cone constraints. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-12. doi: 10.3934/jimo.2019033 [15] Matthias Gerdts, Stefan Horn, Sven-Joachim Kimmerle. Line search globalization of a semismooth Newton method for operator equations in Hilbert spaces with applications in optimal control. Journal of Industrial & Management Optimization, 2017, 13 (1) : 47-62. doi: 10.3934/jimo.2016003 [16] Yanhong Yuan, Hongwei Zhang, Liwei Zhang. A smoothing Newton method for generalized Nash equilibrium problems with second-order cone constraints. Numerical Algebra, Control & Optimization, 2012, 2 (1) : 1-18. doi: 10.3934/naco.2012.2.1 [17] Leong-Kwan Li, Sally Shao. Convergence analysis of the weighted state space search algorithm for recurrent neural networks. Numerical Algebra, Control & Optimization, 2014, 4 (3) : 193-207. doi: 10.3934/naco.2014.4.193 [18] Ming-Jong Yao, Yu-Chun Wang. Theoretical analysis and a search procedure for the joint replenishment problem with deteriorating products. Journal of Industrial & Management Optimization, 2005, 1 (3) : 359-375. doi: 10.3934/jimo.2005.1.359 [19] Juan Pablo Cárdenas, Gerardo Vidal, Gastón Olivares. Complexity, selectivity and asymmetry in the conformation of the power phenomenon. Analysis of Chilean society. Networks & Heterogeneous Media, 2015, 10 (1) : 167-194. doi: 10.3934/nhm.2015.10.167 [20] Ai-Li Yang, Yu-Jiang Wu. Newton-MHSS methods for solving systems of nonlinear equations with complex symmetric Jacobian matrices. Numerical Algebra, Control & Optimization, 2012, 2 (4) : 839-853. doi: 10.3934/naco.2012.2.839

2018 Impact Factor: 1.025

## Metrics

• PDF downloads (4)
• HTML views (0)
• Cited by (5)

## Other articlesby authors

• on AIMS
• on Google Scholar

[Back to Top]