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

Yanqin Bai; Lipu Zhang

doi:10.3934/jimo.2011.7.891

Article Contents

2011, Volume 7, Issue 4: 891-906. Doi: 10.3934/jimo.2011.7.891

This issue Previous Article Optimal fleet composition via dynamic programming and golden section search Next Article An integrated approach for selection of service vendors in service supply chain

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

Received: October 31, 2009

Revised: April 30, 2011

Published: September 2011

Abstract Related Papers Cited by

Abstract

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:

Mathematics Subject Classification: 17C99, 90C25, 90C51.

Citation:

Related Papers

Cited by

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