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]

Algorithmica, 10 (1993), 365-382. doi: 10.1007/BF01769704.  Google Scholar

[2]

SIAM J. Optim., 15 (2004), 101-128. doi: 10.1137/S1052623403423114.  Google Scholar

[3]

Cambridge University Press, 2004. Google Scholar

[4]

Oxford Mathematical Monographs, Oxford Science Publications, The Clarendon Press, Oxford University Press, New York, 1994.  Google Scholar

[5]

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.  Google Scholar

[6]

Math. Z., 239 (2002), 117-129. doi: 10.1007/s002090100286.  Google Scholar

[7]

Math. Program., Ser. A, 44 (1989), 43-66.  Google Scholar

[8]

Math. Oper. Res., 22 (1997), 1-42. doi: 10.1287/moor.22.1.1.  Google Scholar

[9]

Princeton Series in Applied Mathematics, Princeton University Press, Princeton, NJ, 2002.  Google Scholar

[10]

Wiley-Interscience Series in Discrete Mathematics and Optimization, John Wiley & Sons, Ltd., Chichester, 1997.  Google Scholar

[11]

Math. Program, Ser. A, 96 (2003), 409-438.  Google Scholar

[12]

Journal of Industrial and Management Optimization, 4 (2010), 895-910. Google Scholar

[13]

Ph.D thesis, Delft University of Technology, 2007. Google Scholar

show all references

References:
[1]

Algorithmica, 10 (1993), 365-382. doi: 10.1007/BF01769704.  Google Scholar

[2]

SIAM J. Optim., 15 (2004), 101-128. doi: 10.1137/S1052623403423114.  Google Scholar

[3]

Cambridge University Press, 2004. Google Scholar

[4]

Oxford Mathematical Monographs, Oxford Science Publications, The Clarendon Press, Oxford University Press, New York, 1994.  Google Scholar

[5]

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.  Google Scholar

[6]

Math. Z., 239 (2002), 117-129. doi: 10.1007/s002090100286.  Google Scholar

[7]

Math. Program., Ser. A, 44 (1989), 43-66.  Google Scholar

[8]

Math. Oper. Res., 22 (1997), 1-42. doi: 10.1287/moor.22.1.1.  Google Scholar

[9]

Princeton Series in Applied Mathematics, Princeton University Press, Princeton, NJ, 2002.  Google Scholar

[10]

Wiley-Interscience Series in Discrete Mathematics and Optimization, John Wiley & Sons, Ltd., Chichester, 1997.  Google Scholar

[11]

Math. Program, Ser. A, 96 (2003), 409-438.  Google Scholar

[12]

Journal of Industrial and Management Optimization, 4 (2010), 895-910. Google Scholar

[13]

Ph.D thesis, Delft University of Technology, 2007. Google Scholar

[1]

Xiaoni Chi, Zhongping Wan, Zijun Hao. A full-modified-Newton step $ O(n) $ infeasible interior-point method for the special weighted linear complementarity problem. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021082
[2]

Li Chu, Bo Wang, Jie Zhang, Hong-Wei Zhang. Convergence analysis of a smoothing SAA method for a stochastic mathematical program with second-order cone complementarity constraints. Journal of Industrial & Management Optimization, 2021, 17 (4) : 1863-1886. doi: 10.3934/jimo.2020050
[3]

Zehui Jia, Xue Gao, Xingju Cai, Deren Han. The convergence rate analysis of the symmetric ADMM for the nonconvex separable optimization problems. Journal of Industrial & Management Optimization, 2021, 17 (4) : 1943-1971. doi: 10.3934/jimo.2020053
[4]

Stephen Doty and Anthony Giaquinto. Generators and relations for Schur algebras. Electronic Research Announcements, 2001, 7: 54-62.

[5]

Valery Y. Glizer. Novel Conditions of Euclidean space controllability for singularly perturbed systems with input delay. Numerical Algebra, Control & Optimization, 2021, 11 (2) : 307-320. doi: 10.3934/naco.2020027
[6]

Xiaochen Mao, Weijie Ding, Xiangyu Zhou, Song Wang, Xingyong Li. Complexity in time-delay networks of multiple interacting neural groups. Electronic Research Archive, , () : -. doi: 10.3934/era.2021022
[7]

Jie-Wen He, Chi-Chon Lei, Chen-Yang Shi, Seak-Weng Vong. An inexact alternating direction method of multipliers for a kind of nonlinear complementarity problems. Numerical Algebra, Control & Optimization, 2021, 11 (3) : 353-362. doi: 10.3934/naco.2020030
[8]

Fatemeh Abtahi, Zeinab Kamali, Maryam Toutounchi. The BSE concepts for vector-valued Lipschitz algebras. Communications on Pure & Applied Analysis, 2021, 20 (3) : 1171-1186. doi: 10.3934/cpaa.2021011
[9]

Krzysztof A. Krakowski, Luís Machado, Fátima Silva Leite. A unifying approach for rolling symmetric spaces. Journal of Geometric Mechanics, 2021, 13 (1) : 145-166. doi: 10.3934/jgm.2020016
[10]

Jérôme Ducoat, Frédérique Oggier. On skew polynomial codes and lattices from quotients of cyclic division algebras. Advances in Mathematics of Communications, 2016, 10 (1) : 79-94. doi: 10.3934/amc.2016.10.79
[11]

Mohammed Abdelghany, Amr B. Eltawil, Zakaria Yahia, Kazuhide Nakata. A hybrid variable neighbourhood search and dynamic programming approach for the nurse rostering problem. Journal of Industrial & Management Optimization, 2021, 17 (4) : 2051-2072. doi: 10.3934/jimo.2020058
[12]

Hong-Yi Miao, Li Wang. Preconditioned inexact Newton-like method for large nonsymmetric eigenvalue problems. Numerical Algebra, Control & Optimization, 2021  doi: 10.3934/naco.2021012
[13]

Hong Seng Sim, Wah June Leong, Chuei Yee Chen, Siti Nur Iqmal Ibrahim. Multi-step spectral gradient methods with modified weak secant relation for large scale unconstrained optimization. Numerical Algebra, Control & Optimization, 2018, 8 (3) : 377-387. doi: 10.3934/naco.2018024
[14]

Zheng Chang, Haoxun Chen, Farouk Yalaoui, Bo Dai. Adaptive large neighborhood search Algorithm for route planning of freight buses with pickup and delivery. Journal of Industrial & Management Optimization, 2021, 17 (4) : 1771-1793. doi: 10.3934/jimo.2020045
[15]

Kazeem Olalekan Aremu, Chinedu Izuchukwu, Grace Nnenanya Ogwo, Oluwatosin Temitope Mewomo. Multi-step iterative algorithm for minimization and fixed point problems in p-uniformly convex metric spaces. Journal of Industrial & Management Optimization, 2021, 17 (4) : 2161-2180. doi: 10.3934/jimo.2020063
[16]

Yishui Wang, Dongmei Zhang, Peng Zhang, Yong Zhang. Local search algorithm for the squared metric $ k $-facility location problem with linear penalties. Journal of Industrial & Management Optimization, 2021, 17 (4) : 2013-2030. doi: 10.3934/jimo.2020056
[17]

Pablo D. Carrasco, Túlio Vales. A symmetric Random Walk defined by the time-one map of a geodesic flow. Discrete & Continuous Dynamical Systems, 2021, 41 (6) : 2891-2905. doi: 10.3934/dcds.2020390
[18]

Reza Mazrooei-Sebdani, Zahra Yousefi. The coupled 1:2 resonance in a symmetric case and parametric amplification model. Discrete & Continuous Dynamical Systems - B, 2021, 26 (7) : 3737-3765. doi: 10.3934/dcdsb.2020255
[19]

Min Li. A three term Polak-Ribière-Polyak conjugate gradient method close to the memoryless BFGS quasi-Newton method. Journal of Industrial & Management Optimization, 2020, 16 (1) : 245-260. doi: 10.3934/jimo.2018149
[20]

Jan Prüss, Laurent Pujo-Menjouet, G.F. Webb, Rico Zacher. Analysis of a model for the dynamics of prions. Discrete & Continuous Dynamical Systems - B, 2006, 6 (1) : 225-235. doi: 10.3934/dcdsb.2006.6.225

2019 Impact Factor: 1.366

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences