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.  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., (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.  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.  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.  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.  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.  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.  doi: 10.1023/A:1026583532263.  Google Scholar

[9]

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

[10]

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

[11]

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

[12]

M. El Ghami, "New Primal-Dual Interior-Point Methods Based on Kernel Functions,", Ph.D Thesis, (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.  doi: 10.1007/BF01588795.  Google Scholar

[14]

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

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

[26]

J. Sun, On methods for solving nonlinear semidefinite optimization problems,, Numerical Algebra, 1 (2011), 1.  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.  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.   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.  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, 71 (2009), 3389.   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.  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, (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.  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.  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.  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., (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.  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.  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.  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.  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.  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.  doi: 10.1023/A:1026583532263.  Google Scholar

[9]

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

[10]

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

[11]

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

[12]

M. El Ghami, "New Primal-Dual Interior-Point Methods Based on Kernel Functions,", Ph.D Thesis, (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.  doi: 10.1007/BF01588795.  Google Scholar

[14]

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

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

[26]

J. Sun, On methods for solving nonlinear semidefinite optimization problems,, Numerical Algebra, 1 (2011), 1.  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.  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.   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.  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, 71 (2009), 3389.   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.  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, (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.  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.  doi: [10.1080/00207160.2011.597503.  Google Scholar

[1]

Zi Xu, Siwen Wang, Jinjin Huang. An efficient low complexity algorithm for box-constrained weighted maximin dispersion problem. Journal of Industrial & Management Optimization, 2021, 17 (2) : 971-979. doi: 10.3934/jimo.2020007

[2]

Wolfgang Riedl, Robert Baier, Matthias Gerdts. Optimization-based subdivision algorithm for reachable sets. Journal of Computational Dynamics, 2021, 8 (1) : 99-130. doi: 10.3934/jcd.2021005

[3]

Haodong Yu, Jie Sun. Robust stochastic optimization with convex risk measures: A discretized subgradient scheme. Journal of Industrial & Management Optimization, 2021, 17 (1) : 81-99. doi: 10.3934/jimo.2019100

[4]

Mohammed Abdulrazaq Kahya, Suhaib Abduljabbar Altamir, Zakariya Yahya Algamal. Improving whale optimization algorithm for feature selection with a time-varying transfer function. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 87-98. doi: 10.3934/naco.2020017

[5]

Guo Zhou, Yongquan Zhou, Ruxin Zhao. Hybrid social spider optimization algorithm with differential mutation operator for the job-shop scheduling problem. Journal of Industrial & Management Optimization, 2021, 17 (2) : 533-548. doi: 10.3934/jimo.2019122

[6]

Hedy Attouch, Aïcha Balhag, Zaki Chbani, Hassan Riahi. Fast convex optimization via inertial dynamics combining viscous and Hessian-driven damping with time rescaling. Evolution Equations & Control Theory, 2021  doi: 10.3934/eect.2021010

[7]

Xin Zhao, Tao Feng, Liang Wang, Zhipeng Qiu. Threshold dynamics and sensitivity analysis of a stochastic semi-Markov switched SIRS epidemic model with nonlinear incidence and vaccination. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2021010

[8]

Jie Li, Xiangdong Ye, Tao Yu. Mean equicontinuity, complexity and applications. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 359-393. doi: 10.3934/dcds.2020167

[9]

Fioralba Cakoni, Pu-Zhao Kow, Jenn-Nan Wang. The interior transmission eigenvalue problem for elastic waves in media with obstacles. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020075

[10]

Xiaofeng Ren, David Shoup. The impact of the domain boundary on an inhibitory system: Interior discs and boundary half discs. Discrete & Continuous Dynamical Systems - A, 2020, 40 (6) : 3957-3979. doi: 10.3934/dcds.2020048

[11]

Peng Luo. Comparison theorem for diagonally quadratic BSDEs. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020374

[12]

Ugo Bessi. Another point of view on Kusuoka's measure. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020404

[13]

Huu-Quang Nguyen, Ya-Chi Chu, Ruey-Lin Sheu. On the convexity for the range set of two quadratic functions. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020169

[14]

Wei-Chieh Chen, Bogdan Kazmierczak. Traveling waves in quadratic autocatalytic systems with complexing agent. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020364

[15]

Angelica Pachon, Federico Polito, Costantino Ricciuti. On discrete-time semi-Markov processes. Discrete & Continuous Dynamical Systems - B, 2021, 26 (3) : 1499-1529. doi: 10.3934/dcdsb.2020170

[16]

Christian Beck, Lukas Gonon, Martin Hutzenthaler, Arnulf Jentzen. On existence and uniqueness properties for solutions of stochastic fixed point equations. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020320

[17]

Gang Luo, Qingzhi Yang. The point-wise convergence of shifted symmetric higher order power method. Journal of Industrial & Management Optimization, 2021, 17 (1) : 357-368. doi: 10.3934/jimo.2019115

[18]

Sabira El Khalfaoui, Gábor P. Nagy. On the dimension of the subfield subcodes of 1-point Hermitian codes. Advances in Mathematics of Communications, 2021, 15 (2) : 219-226. doi: 10.3934/amc.2020054

[19]

Balázs Kósa, Karol Mikula, Markjoe Olunna Uba, Antonia Weberling, Neophytos Christodoulou, Magdalena Zernicka-Goetz. 3D image segmentation supported by a point cloud. Discrete & Continuous Dynamical Systems - S, 2021, 14 (3) : 971-985. doi: 10.3934/dcdss.2020351

[20]

Djamel Aaid, Amel Noui, Özen Özer. Piecewise quadratic bounding functions for finding real roots of polynomials. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 63-73. doi: 10.3934/naco.2020015

 Impact Factor: 

Metrics

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

Other articles
by authors

[Back to Top]