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

[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 (n3 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.

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.

[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 (n3 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.

[1]

Ayache Benhadid, Fateh Merahi. Complexity analysis of an interior-point algorithm for linear optimization based on a new parametric kernel function with a double barrier term. Numerical Algebra, Control and Optimization, 2022  doi: 10.3934/naco.2022003
[2]

Yanqin Bai, Lipu Zhang. A full-Newton step interior-point algorithm for symmetric cone convex quadratic optimization. Journal of Industrial and Management Optimization, 2011, 7 (4) : 891-906. doi: 10.3934/jimo.2011.7.891
[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 and Management Optimization, 2016, 12 (1) : 317-336. doi: 10.3934/jimo.2016.12.317
[4]

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

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 and Optimization, 2015, 5 (1) : 37-46. doi: 10.3934/naco.2015.5.37
[6]

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

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

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

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 and Optimization, 2015, 5 (2) : 101-113. doi: 10.3934/naco.2015.5.101
[10]

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

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 and Control Theory, 2019, 8 (2) : 315-342. doi: 10.3934/eect.2019017
[12]

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 and Optimization, 2013, 3 (4) : 665-680. doi: 10.3934/naco.2013.3.665
[13]

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

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

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

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

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

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

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

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

 Impact Factor: 

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy