2012, 2(1): 129-144. doi: 10.3934/naco.2012.2.129

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, China

3. 

Department of Mathematics, Zhejiang A&F University, Hangzhou, 311300, China

Received  October 2010 Revised  October 2011 Published  March 2012

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.
Citation: Lipu Zhang, Yinghong Xu, Zhengjing Jin. An efficient algorithm for convex quadratic semi-definite optimization. Numerical Algebra, Control & Optimization, 2012, 2 (1) : 129-144. doi: 10.3934/naco.2012.2.129
References:
[1]

M. Achache, A new primal-dual path-following method for convex quadratic programming,, Computational and Applied Mathematics, 25 (2006), 97. 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., (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. 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. 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. 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. 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. 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. doi: 10.1023/A:1026583532263.

[9]

Z. Darvay, A weighted-path-following method for linear optimization,, Studia Universitatis Babes-Bolyai, 47 (2002), 3.

[10]

Z. Darvay, New interior point algorithms in linear programming,, Advanced Modeling and Optimization, 5 (2003), 51.

[11]

E. De Klerk, "Aspects of Semidefinite Programming: Interior Point Algorithms and Selected Applications,", Kluwer Academic Publishers, (2002).

[12]

M. El Ghami, "New Primal-Dual Interior-Point Methods Based on Kernel Functions,", Ph.D Thesis, (2005).

[13]

D. Goldfarb and S. Liu, An O (n3 L) primal interior point algorithm for convex quadratic programming,, Mathematical Programming, 49 (1990), 325. doi: 10.1007/BF01588795.

[14]

R. Horn and C. Johnson, "Topics in Matrix Analysis,", Cambridge Univ Pr, (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. 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. 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. 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. 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. 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. 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. 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.

[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. 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, (2002).

[25]

J. Sturm and S. Zhang, Symmetric primal-dual path-following algorithms for semidefinite programming,, Applied Numerical Mathematics, 29 (1998), 301. doi: 10.1016/S0168-9274(98)00099-3.

[26]

J. Sun, On methods for solving nonlinear semidefinite optimization problems,, Numerical Algebra, 1 (2011), 1. 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. 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.

[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. 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, 71 (2009), 3389.

[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. 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, (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. 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. doi: [10.1080/00207160.2011.597503.

show all references

References:
[1]

M. Achache, A new primal-dual path-following method for convex quadratic programming,, Computational and Applied Mathematics, 25 (2006), 97. 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., (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. 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. 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. 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. 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. 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. doi: 10.1023/A:1026583532263.

[9]

Z. Darvay, A weighted-path-following method for linear optimization,, Studia Universitatis Babes-Bolyai, 47 (2002), 3.

[10]

Z. Darvay, New interior point algorithms in linear programming,, Advanced Modeling and Optimization, 5 (2003), 51.

[11]

E. De Klerk, "Aspects of Semidefinite Programming: Interior Point Algorithms and Selected Applications,", Kluwer Academic Publishers, (2002).

[12]

M. El Ghami, "New Primal-Dual Interior-Point Methods Based on Kernel Functions,", Ph.D Thesis, (2005).

[13]

D. Goldfarb and S. Liu, An O (n3 L) primal interior point algorithm for convex quadratic programming,, Mathematical Programming, 49 (1990), 325. doi: 10.1007/BF01588795.

[14]

R. Horn and C. Johnson, "Topics in Matrix Analysis,", Cambridge Univ Pr, (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. 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. 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. 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. 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. 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. 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. 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.

[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. 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, (2002).

[25]

J. Sturm and S. Zhang, Symmetric primal-dual path-following algorithms for semidefinite programming,, Applied Numerical Mathematics, 29 (1998), 301. doi: 10.1016/S0168-9274(98)00099-3.

[26]

J. Sun, On methods for solving nonlinear semidefinite optimization problems,, Numerical Algebra, 1 (2011), 1. 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. 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.

[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. 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, 71 (2009), 3389.

[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. 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, (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. 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. doi: [10.1080/00207160.2011.597503.

[1]

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

[2]

Xiantao Xiao, Liwei Zhang, Jianzhong Zhang. On convergence of augmented Lagrangian method for inverse semi-definite quadratic programming problems. Journal of Industrial & Management Optimization, 2009, 5 (2) : 319-339. doi: 10.3934/jimo.2009.5.319

[3]

Yue Lu, Ying-En Ge, Li-Wei Zhang. An alternating direction method for solving a class of inverse semi-definite quadratic programming problems. Journal of Industrial & Management Optimization, 2016, 12 (1) : 317-336. doi: 10.3934/jimo.2016.12.317

[4]

Siqi Li, Weiyi Qian. Analysis of complexity of primal-dual interior-point algorithms based on a new kernel function for linear optimization. Numerical Algebra, Control & Optimization, 2015, 5 (1) : 37-46. doi: 10.3934/naco.2015.5.37

[5]

Yanqin Bai, Xuerui Gao, Guoqiang Wang. Primal-dual interior-point algorithms for convex quadratic circular cone optimization. Numerical Algebra, Control & Optimization, 2015, 5 (2) : 211-231. doi: 10.3934/naco.2015.5.211

[6]

Guoqiang Wang, Zhongchen Wu, Zhongtuan Zheng, Xinzhong Cai. Complexity analysis of primal-dual interior-point methods for semidefinite optimization based on a parametric kernel function with a trigonometric barrier term. Numerical Algebra, Control & Optimization, 2015, 5 (2) : 101-113. doi: 10.3934/naco.2015.5.101

[7]

Behrouz Kheirfam, Morteza Moslemi. On the extension of an arc-search interior-point algorithm for semidefinite optimization. Numerical Algebra, Control & Optimization, 2018, 8 (2) : 261-275. doi: 10.3934/naco.2018015

[8]

Wei Huang, Ka-Fai Cedric Yiu, Henry Y. K. Lau. Semi-definite programming based approaches for real-time tractor localization in port container terminals. Numerical Algebra, Control & Optimization, 2013, 3 (4) : 665-680. doi: 10.3934/naco.2013.3.665

[9]

Behrouz Kheirfam. A full Nesterov-Todd step infeasible interior-point algorithm for symmetric optimization based on a specific kernel function. Numerical Algebra, Control & Optimization, 2013, 3 (4) : 601-614. doi: 10.3934/naco.2013.3.601

[10]

Yinghong Xu, Lipu Zhang, Jing Zhang. A full-modified-Newton step infeasible interior-point algorithm for linear optimization. Journal of Industrial & Management Optimization, 2016, 12 (1) : 103-116. doi: 10.3934/jimo.2016.12.103

[11]

Igor Griva, Roman A. Polyak. Proximal point nonlinear rescaling method for convex optimization. Numerical Algebra, Control & Optimization, 2011, 1 (2) : 283-299. doi: 10.3934/naco.2011.1.283

[12]

Adil Bagirov, Sona Taheri, Soodabeh Asadi. A difference of convex optimization algorithm for piecewise linear regression. Journal of Industrial & Management Optimization, 2018, 13 (5) : 1-24. doi: 10.3934/jimo.2018077

[13]

Yong Wang, Wanquan Liu, Guanglu Zhou. An efficient algorithm for non-convex sparse optimization. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-13. doi: 10.3934/jimo.2018134

[14]

Zheng-Hai Huang, Shang-Wen Xu. Convergence properties of a non-interior-point smoothing algorithm for the P*NCP. Journal of Industrial & Management Optimization, 2007, 3 (3) : 569-584. doi: 10.3934/jimo.2007.3.569

[15]

Behrouz Kheirfam, Guoqiang Wang. An infeasible full NT-step interior point method for circular optimization. Numerical Algebra, Control & Optimization, 2017, 7 (2) : 171-184. doi: 10.3934/naco.2017011

[16]

Paul B. Hermanns, Nguyen Van Thoai. Global optimization algorithm for solving bilevel programming problems with quadratic lower levels. Journal of Industrial & Management Optimization, 2010, 6 (1) : 177-196. doi: 10.3934/jimo.2010.6.177

[17]

Yazheng Dang, Fanwen Meng, Jie Sun. Convergence analysis of a parallel projection algorithm for solving convex feasibility problems. Numerical Algebra, Control & Optimization, 2016, 6 (4) : 505-519. doi: 10.3934/naco.2016023

[18]

Boshi Tian, Xiaoqi Yang, Kaiwen Meng. An interior-point $l_{\frac{1}{2}}$-penalty method for inequality constrained nonlinear optimization. Journal of Industrial & Management Optimization, 2016, 12 (3) : 949-973. doi: 10.3934/jimo.2016.12.949

[19]

Meixia Li, Changyu Wang, Biao Qu. Non-convex semi-infinite min-max optimization with noncompact sets. Journal of Industrial & Management Optimization, 2017, 13 (4) : 1859-1881. doi: 10.3934/jimo.2017022

[20]

Yuan Shen, Wenxing Zhang, Bingsheng He. Relaxed augmented Lagrangian-based proximal point algorithms for convex optimization with linear constraints. Journal of Industrial & Management Optimization, 2014, 10 (3) : 743-759. doi: 10.3934/jimo.2014.10.743

 Impact Factor: 

Metrics

  • PDF downloads (2)
  • HTML views (0)
  • Cited by (3)

Other articles
by authors

[Back to Top]