American Institute of Mathematical Sciences

Advanced
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

Yanqin Bai 1, and  Lipu Zhang 2,

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.
Keywords: complexity analysis., Euclidean Jordan algebras, full-Newton step, NT-search direction, symmetric cone.
Mathematics Subject Classification: 17C99, 90C25, 90C5.
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]

Jie Li, Xiangdong Ye, Tao Yu. Mean equicontinuity, complexity and applications. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 359-393. doi: 10.3934/dcds.2020167
[2]

Agnaldo José Ferrari, Tatiana Miguel Rodrigues de Souza. Rotated $ A_n $-lattice codes of full diversity. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020118
[3]

Hua Chen, Yawei Wei. Multiple solutions for nonlinear cone degenerate elliptic equations. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020272
[4]

Min Chen, Olivier Goubet, Shenghao Li. Mathematical analysis of bump to bucket problem. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5567-5580. doi: 10.3934/cpaa.2020251
[5]

Qianqian Han, Xiao-Song Yang. Qualitative analysis of a generalized Nosé-Hoover oscillator. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020346
[6]

Laurence Cherfils, Stefania Gatti, Alain Miranville, Rémy Guillevin. Analysis of a model for tumor growth and lactate exchanges in a glioma. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020457
[7]

Vieri Benci, Sunra Mosconi, Marco Squassina. Preface: Applications of mathematical analysis to problems in theoretical physics. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020446
[8]

Lei Liu, Li Wu. Multiplicity of closed characteristics on $ P $-symmetric compact convex hypersurfaces in $ \mathbb{R}^{2n} $. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020378
[9]

Yining Cao, Chuck Jia, Roger Temam, Joseph Tribbia. Mathematical analysis of a cloud resolving model including the ice microphysics. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 131-167. doi: 10.3934/dcds.2020219
[10]

Jianquan Li, Xin Xie, Dian Zhang, Jia Li, Xiaolin Lin. Qualitative analysis of a simple tumor-immune system with time delay of tumor action. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020341
[11]

A. M. Elaiw, N. H. AlShamrani, A. Abdel-Aty, H. Dutta. Stability analysis of a general HIV dynamics model with multi-stages of infected cells and two routes of infection. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020441

2019 Impact Factor: 1.366

Tools

Metrics

  • PDF downloads (24)
  • HTML views (0)
  • Cited by (6)

Other articles
by authors

[Back to Top]

Copyright © 2020 American Institute of Mathematical Sciences