An efficient algorithm for convex quadratic semi-definite optimization

Lipu Zhang; Yinghong Xu; Zhengjing Jin

doi:10.3934/naco.2012.2.129

Article Contents

2012, Volume 2, Issue 1: 129-144. Doi: 10.3934/naco.2012.2.129

This issue Previous Article A bilevel optimization approach to obtain optimal cost functions for human arm movements Next Article A class of smoothing SAA methods for a stochastic linear complementarity problem

An efficient algorithm for convex quadratic semi-definite optimization

1.
Department of Mathematics, Shanghai University, Shanghai 200444
2.
Department of Mathematics, Zhejiang Sci-Tech University, Hangzhou, 310018
3.
Department of Mathematics, Zhejiang A&F University, Hangzhou, 311300

Received: September 30, 2010

Revised: September 30, 2011

Published: February 2012

Abstract Related Papers Cited by

Abstract

We present a full-step interior-point algorithm for convex quadratic semi-definite optimization based on a simple univariate function. The algorithm uses the simple function to determine the search direction and define the neighborhood of central path. The full-step used in the algorithm has local quadratic convergence property according to the proximity function which is also constructed by the simple function. We derive the iteration complexity for the algorithm and obtain the best-known iteration bounds for convex quadratic semi-definite optimization.

Keywords:

Convex quadratic semi-definite optimization,
interior point algorithm,
complexity analysis.

Mathematics Subject Classification: 65K05; 90C51.

Citation:

Related Papers

Cited by

References

[1]	M. Achache, A new primal-dual path-following method for convex quadratic programming, Computational and Applied Mathematics, 25 (2006), 97-110.doi: 10.1590/S0101-82052006000100005.
[2]	E. Andersen, J. Gondzio, C. Mészáros and X. Xu, "Implementation of Interior Point Methods for Large Scale Linear Programming," Kluwer Acad. Publ., Dordrecht, 1996.
[3]	E. Andersen, C. Roos and T. Terlaky, On implementing a primal-dual interior-point method for conic quadratic optimization, Mathematical Programming, 95 (2003), 249-277.doi: 10.1007/s10107-002-0349-3.
[4]	P. Apkarian, D. Noll, J. Thevenet and H. Tuan, A spectral quadratic-SDP method with applications to fixed-order H2 and H∞ synthesis, European Journal of Control, 10 (2004), 527-538.doi: 10.3166/ejc.10.527-538.
[5]	Y. Bai, M. El Ghami and C. Roos, A new efficient large-update primal-dual interior-point method based on a finite barrier, SIAM Journal on Optimization, 13 (2002), 766-782.doi: 10.1137/S1052623401398132.
[6]	Y. Bai, M. El Ghami and C. Roos, A comparative study of kernel functions for primal-dual interior-point algorithms in linear optimization, SIAM Journal on Optimization, 15 (2004), 101-128.doi: 10.1137/S1052623403423114.
[7]	Y. Bai, C. Roos and M. Ghami, A primal-dual interior-point method for linear optimization based on a new proximity function, Optimization Methods and Software, 17 (2002), 985-1008.doi: 10.1080/1055678021000090024.
[8]	I. Bomze, M. Dür, E. De Klerk, C. Roos, A. Quist and T. Terlaky, On copositive programming and standard quadratic optimization problems, Journal of Global Optimization, 18 (2000), 301-320.doi: 10.1023/A:1026583532263.
[9]	Z. Darvay, A weighted-path-following method for linear optimization, Studia Universitatis Babes-Bolyai, Series Informatica, 47 (2002), 3-12.
[10]	Z. Darvay, New interior point algorithms in linear programming, Advanced Modeling and Optimization, 5 (2003), 51-92.
[11]	E. De Klerk, "Aspects of Semidefinite Programming: Interior Point Algorithms and Selected Applications," Kluwer Academic Publishers, Dordrecht, 2002.
[12]	M. El Ghami, "New Primal-Dual Interior-Point Methods Based on Kernel Functions," Ph.D Thesis, Delft University of Technology, 2005.
[13]	D. Goldfarb and S. Liu, An O (n³ L) primal interior point algorithm for convex quadratic programming, Mathematical Programming, 49 (1990), 325-340.doi: 10.1007/BF01588795.
[14]	R. Horn and C. Johnson, "Topics in Matrix Analysis," Cambridge Univ Pr, Cambridge, 1994.
[15]	M. Kojima, M. Shida and S. Shindoh, Local convergence of predictor—corrector infeasible-interior-point algorithms for SDPs and SDLCPs, Mathematical Programming, 80 (1998), 129-160.doi: 10.1007/BF01581723.
[16]	M. Kojima, S. Shindoh and S. Hara, Interior-point methods for the monotone semidefinite linear complementarity problem in symmetric matrices, SIAM Journal on Optimization, 7 (1997), 86-125.doi: 10.1137/S1052623494269035.
[17]	Y. Lu and Y. Yuan, An interior-point trust-region polynomial algorithm for convex quadratic minimization subject to general convex constraints, Optimization Methods and Software, 23 (2008), 251-258.doi: 10.1080/10556780701645057.
[18]	R. Monteiro and I. Adler, Interior path following primal-dual algorithms. Part II: Convex quadratic programming, Mathematical Programming, 44 (1989), 43-66.doi: 10.1007/BF01587076.
[19]	Y. Nesterov and M. Todd, Primal-dual interior-point methods for self-scaled cones, SIAM Journal on Optimization, 8 (1998), 324-364.doi: 10.1137/S1052623495290209.
[20]	J. Nie and Y. Yuan, A predictor-corrector algorithm for QSDP combining Dikin-Type and Newton centering steps, Annals of Operations Research, 103 (2001), 115-133.doi: 10.1023/A:1012994820412.
[21]	J. Peng, C. Roos and T. Terlaky, New complexity analysis of the primal-dual Newton method for linear optimization, Annals of Operations Research, 99(2000), 23-39.doi: 10.1023/A:1019280614748.
[22]	J. Peng, C. Roos and T. Terlaky, A new and efficient large-update interior-point method for linear optimization, Vychisl. Tekhnol., 6 (2001), 61-80.
[23]	J. Peng, C. Roos and T. Terlaky, Self-regular functions and new search directions for linear and semidefinite optimization, Mathematical Programming, 93 (2002), 129-171.doi: 10.1007/s101070200296.
[24]	J. Peng, C. Roos and T. Terlaky, "Self-Regularity: A New Paradigm for Primal-Dual Interior-Point Algorithms," Princeton Univ Pr, NJ, 2002.
[25]	J. Sturm and S. Zhang, Symmetric primal-dual path-following algorithms for semidefinite programming, Applied Numerical Mathematics, 29 (1998), 301-315.doi: 10.1016/S0168-9274(98)00099-3.
[26]	J. Sun, On methods for solving nonlinear semidefinite optimization problems, Numerical Algebra, Control and Optimization, 1 (2011), 1-14.doi: 10.3934/naco.2011.1.1.
[27]	M. Todd, K. Toh and R. Tütüncü, On the Nesterov-Todd direction in semidefinite programming, SIAM Journal on Optimization, 8 (1998), 769-796.doi: 10.1137/S105262349630060X.
[28]	K. Toh, R. Tütüncü and M. Todd, Inexact primal-dual path-following algorithms for a special class of convex quadratic SDP and related problems, Pacific J. Optimization, 3 (2007), 135-164.
[29]	G. Wang and Y. Bai, A new primal-dual path-following interior-point algorithm for semidefinite optimization, Journal of Mathematical Analysis and Applications, 353 (2009), 339-349.doi: 10.1016/j.jmaa.2008.12.016.
[30]	G. Wang and Y. Bai, Primal-dual interior-point algorithm for convex quadratic semi-definite optimization, Nonlinear Analysis: Theory, Methods & Applications, 71 (2009), 3389-3402.
[31]	G. Wang, Y. Bai, Y. Liu and M. Zhang, A new primal-dual interior-point algorithm for convex quadratic optimization, Journal of Shanghai University (English Edition), 12 (2008), 189-196.doi: 10.1007/s11741-008-0301-3.
[32]	H. Wolkowicz, R. Saigal and L. Vandenberghe, "Handbook of Semidefinite Programming: Theory, Algorithms and Applications," Kluwer Academic Publishers, Boston, MA, 2000.
[33]	Y. Zhang, On extending some primal-dual interior-point algorithms from linear programming to semidefinite programming, SIAM Journal on Optimization, 8 (1998), 365-386.doi: 10.1137/S1052623495296115.
[34]	L. Zhang and Y. Xu, A new infeasible interior-point algorithm with full step for linear optimization based on a simple function, International Journal of Computer Mathematics, 88 (2011), 3163-3185.doi: [10.1080/00207160.2011.597503.