American Institute of Mathematical Sciences

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

An efficient algorithm for convex quadratic semi-definite optimization

Lipu Zhang 1, , Yinghong Xu 2, and  Zhengjing Jin 3,

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.
Keywords: complexity analysis., Convex quadratic semi-definite optimization, interior point algorithm.
Mathematics Subject Classification: 65K05; 90C51.
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-110. doi: 10.1590/S0101-82052006000100005.  Google Scholar

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

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

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

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

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

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

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

[9]

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

[10]

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

[11]

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

[12]

M. El Ghami, "New Primal-Dual Interior-Point Methods Based on Kernel Functions," Ph.D Thesis, Delft University of Technology, 2005. Google Scholar

[13]

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

[14]

R. Horn and C. Johnson, "Topics in Matrix Analysis," Cambridge Univ Pr, Cambridge, 1994.  Google Scholar

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

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

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

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

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

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

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

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

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

[24]

J. Peng, C. Roos and T. Terlaky, "Self-Regularity: A New Paradigm for Primal-Dual Interior-Point Algorithms," Princeton Univ Pr, NJ, 2002.  Google Scholar

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

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

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

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

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

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

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

[32]

H. Wolkowicz, R. Saigal and L. Vandenberghe, "Handbook of Semidefinite Programming: Theory, Algorithms and Applications," Kluwer Academic Publishers, Boston, MA, 2000.  Google Scholar

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

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

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-110. doi: 10.1590/S0101-82052006000100005.  Google Scholar

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

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

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

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

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

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

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

[9]

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

[10]

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

[11]

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

[12]

M. El Ghami, "New Primal-Dual Interior-Point Methods Based on Kernel Functions," Ph.D Thesis, Delft University of Technology, 2005. Google Scholar

[13]

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

[14]

R. Horn and C. Johnson, "Topics in Matrix Analysis," Cambridge Univ Pr, Cambridge, 1994.  Google Scholar

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

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

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

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

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

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

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

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

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

[24]

J. Peng, C. Roos and T. Terlaky, "Self-Regularity: A New Paradigm for Primal-Dual Interior-Point Algorithms," Princeton Univ Pr, NJ, 2002.  Google Scholar

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

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

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

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

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

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

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

[32]

H. Wolkowicz, R. Saigal and L. Vandenberghe, "Handbook of Semidefinite Programming: Theory, Algorithms and Applications," Kluwer Academic Publishers, Boston, MA, 2000.  Google Scholar

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

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

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

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

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

Stephane Chretien, Paul Clarkson. A fast algorithm for the semi-definite relaxation of the state estimation problem in power grids. Journal of Industrial & Management Optimization, 2020, 16 (1) : 431-443. doi: 10.3934/jimo.2018161
[6]

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

Yi Xu, Jinjie Liu, Liqun Qi. A new class of positive semi-definite tensors. Journal of Industrial & Management Optimization, 2020, 16 (2) : 933-943. doi: 10.3934/jimo.2018186
[8]

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

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

Monika Eisenmann, Etienne Emmrich, Volker Mehrmann. Convergence of the backward Euler scheme for the operator-valued Riccati differential equation with semi-definite data. Evolution Equations & Control Theory, 2019, 8 (2) : 315-342. doi: 10.3934/eect.2019017
[11]

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

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

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

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

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

Adil Bagirov, Sona Taheri, Soodabeh Asadi. A difference of convex optimization algorithm for piecewise linear regression. Journal of Industrial & Management Optimization, 2019, 15 (2) : 909-932. doi: 10.3934/jimo.2018077
[17]

Yong Wang, Wanquan Liu, Guanglu Zhou. An efficient algorithm for non-convex sparse optimization. Journal of Industrial & Management Optimization, 2019, 15 (4) : 2009-2021. doi: 10.3934/jimo.2018134
[18]

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

Xiaojin Zheng, Zhongyi Jiang. Tighter quadratically constrained convex reformulations for semi-continuous quadratic programming. Journal of Industrial & Management Optimization, 2021, 17 (5) : 2331-2343. doi: 10.3934/jimo.2020071
[20]

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

 Impact Factor: 

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences | Privacy Policy