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]

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

[2]

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
[3]

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
[4]

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
[5]

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
[6]

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
[7]

Sohana Jahan. Discriminant analysis of regularized multidimensional scaling. Numerical Algebra, Control & Optimization, 2021, 11 (2) : 255-267. doi: 10.3934/naco.2020024
[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]

Qiang Guo, Dong Liang. An adaptive wavelet method and its analysis for parabolic equations. Numerical Algebra, Control & Optimization, 2013, 3 (2) : 327-345. doi: 10.3934/naco.2013.3.327
[10]

Martial Agueh, Reinhard Illner, Ashlin Richardson. Analysis and simulations of a refined flocking and swarming model of Cucker-Smale type. Kinetic & Related Models, 2011, 4 (1) : 1-16. doi: 10.3934/krm.2011.4.1
[11]

Rui Hu, Yuan Yuan. Stability, bifurcation analysis in a neural network model with delay and diffusion. Conference Publications, 2009, 2009 (Special) : 367-376. doi: 10.3934/proc.2009.2009.367
[12]

Seung-Yeal Ha, Shi Jin. Local sensitivity analysis for the Cucker-Smale model with random inputs. Kinetic & Related Models, 2018, 11 (4) : 859-889. doi: 10.3934/krm.2018034
[13]

Israa Mohammed Khudher, Yahya Ismail Ibrahim, Suhaib Abduljabbar Altamir. Individual biometrics pattern based artificial image analysis techniques. Numerical Algebra, Control & Optimization, 2021  doi: 10.3934/naco.2020056
[14]

Jiangxing Wang. Convergence analysis of an accurate and efficient method for nonlinear Maxwell's equations. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2429-2440. doi: 10.3934/dcdsb.2020185
[15]

Dan Wei, Shangjiang Guo. Qualitative analysis of a Lotka-Volterra competition-diffusion-advection system. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2599-2623. doi: 10.3934/dcdsb.2020197
[16]

Hailing Xuan, Xiaoliang Cheng. Numerical analysis and simulation of an adhesive contact problem with damage and long memory. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2781-2804. doi: 10.3934/dcdsb.2020205
[17]

Carlos Fresneda-Portillo, Sergey E. Mikhailov. Analysis of Boundary-Domain Integral Equations to the mixed BVP for a compressible stokes system with variable viscosity. Communications on Pure & Applied Analysis, 2019, 18 (6) : 3059-3088. doi: 10.3934/cpaa.2019137
[18]

Xiaoyi Zhou, Tong Ye, Tony T. Lee. Designing and analysis of a Wi-Fi data offloading strategy catering for the preference of mobile users. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021038
[19]

John Leventides, Costas Poulios, Georgios Alkis Tsiatsios, Maria Livada, Stavros Tsipras, Konstantinos Lefcaditis, Panagiota Sargenti, Aleka Sargenti. Systems theory and analysis of the implementation of non pharmaceutical policies for the mitigation of the COVID-19 pandemic. Journal of Dynamics & Games, 2021  doi: 10.3934/jdg.2021004

2019 Impact Factor: 1.366

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences