# A Polynomial-time Interior-point Algorithm for Convex Quadratic Semidefinite Optimization

Y. Q. Bai; F. Y. Wang; X. W. Luo

RAIRO - Operations Research (2010)

- Volume: 44, Issue: 3, page 251-265
- ISSN: 0399-0559

## Access Full Article

top## Abstract

top## How to cite

topBai, Y. Q., Wang, F. Y., and Luo, X. W.. "A Polynomial-time Interior-point Algorithm for Convex Quadratic Semidefinite Optimization." RAIRO - Operations Research 44.3 (2010): 251-265. <http://eudml.org/doc/250834>.

@article{Bai2010,

abstract = {
In this paper we propose a primal-dual interior-point algorithm for
convex quadratic semidefinite optimization problem. The search
direction of algorithm is defined in terms of a matrix function and
the iteration is generated by full-Newton step. Furthermore, we
derive the iteration bound for the algorithm with small-update
method, namely, O($\sqrt\{n\}$ log $\frac\{n\}\{\varepsilon\}$), which is
best-known bound so far.
},

author = {Bai, Y. Q., Wang, F. Y., Luo, X. W.},

journal = {RAIRO - Operations Research},

keywords = {Convex quadratic semidefinite optimization; interior-point
algorithm; small-update method; iteration bound; polynomial-time; convex quadratic semidefinite optimization; interior-point algorithm},

language = {eng},

month = {10},

number = {3},

pages = {251-265},

publisher = {EDP Sciences},

title = {A Polynomial-time Interior-point Algorithm for Convex Quadratic Semidefinite Optimization},

url = {http://eudml.org/doc/250834},

volume = {44},

year = {2010},

}

TY - JOUR

AU - Bai, Y. Q.

AU - Wang, F. Y.

AU - Luo, X. W.

TI - A Polynomial-time Interior-point Algorithm for Convex Quadratic Semidefinite Optimization

JO - RAIRO - Operations Research

DA - 2010/10//

PB - EDP Sciences

VL - 44

IS - 3

SP - 251

EP - 265

AB -
In this paper we propose a primal-dual interior-point algorithm for
convex quadratic semidefinite optimization problem. The search
direction of algorithm is defined in terms of a matrix function and
the iteration is generated by full-Newton step. Furthermore, we
derive the iteration bound for the algorithm with small-update
method, namely, O($\sqrt{n}$ log $\frac{n}{\varepsilon}$), which is
best-known bound so far.

LA - eng

KW - Convex quadratic semidefinite optimization; interior-point
algorithm; small-update method; iteration bound; polynomial-time; convex quadratic semidefinite optimization; interior-point algorithm

UR - http://eudml.org/doc/250834

ER -

## References

top- M. Achache, A new primal-dual path-following method for convex quadratic programming. Comput. Appl. Math.25 (2006) 97–110. Zbl1213.90187
- I. Adler and F. Alizadeh, Primal-dual interior point algorithms for convex quadratically constrained and semidefinite optimization problems. Technical Report RRR-111-95, Rutger Center for Operations Research, Brunswick, NJ (1995).
- A.Y. Alfakih, A. Khandani and H. Wolkowicz, Solving Euclidean distance matrix completion problems via semidefinite programming. Comp. Optim. Appl.12 (1999) 13C30. Zbl1040.90537
- Y.Q. Bai and G.Q. Wang, A new primal-dual interior-point algorithm for second-order cone optimization based on kernel function. Acta Math. Sinica (English Series)23 (2007) 2027–2042. Zbl1169.90483
- Y.Q. Bai, C. Roos and M.El. Ghami, A comparative study of kernel functions for primal-dual interior-point algorithms in linear optimization. SIAM J. Optim.15 (2004) 101–128. Zbl1077.90038
- Z. Darvay, New interior-point algorithms in linear optimization. Adv. Model. Optim.5 (2003) 51–92. Zbl1136.90509
- R.A. Horn and R.J. Charles, Topics in Matrix Analysis. Cambridge University Press, UK (1991). Zbl0729.15001
- R.A. Horn and C.R. Johnson, Matrix analysis. Cambridge University Press (1990). Zbl0704.15002
- E. de Klerk, Aspects of Semidefinite Programming: Interior Point Algorithms and Selected Applications. Kluwer Academic Publishers, Dordrecht, The Netherlands (2002). Zbl0991.90098
- M. Kojima, M. Shida and S. Shindoh, Reduction of Monotone Linear Complemen-tarity Problems over Cones to Linear Programs over Cones. Acta Mathematica Vietnamica22 (1997) 147–157. Zbl0903.90165
- M. Kojima, S. Shindoh and S. Hara, Interior-point methods for the monotone linear complementarity problem in symmetric matrices. SIAM J. Optim.7 (1997) 86–125. Zbl0872.90098
- Y.E. Nesterov and M.J. Todd, Primal-dual interior-point methods for self-scaled cones. SIAM J. Optim.8 (1998) 324–364. Zbl0922.90110
- J.W. Nie and Y.X. Yuan, A Potential Reduction Algorithm for an Extended SDP. Science In China (Series A)43 (2000) 35–46. Zbl0944.90058
- J.W. Nie and Y.X. Yuan, A Predictor-Corrector Algorithm for QSDP Combining and Newton Centering Steps. Ann. Oper. Res.103 (2001) 115–133. Zbl1169.90457
- K.C. Toh, Inexact Primal-Dual Path-Following Algorithms for a Convex Quadratic SDP. Math. Program.112 (2008) 221–254. Zbl1136.90027
- K.C. Toh, R.H. Tütüncü and M.J. Todd, Inexact primal-dual path-following algorithms for a special class of convex quadratic SDP and related problems. Pac. J. Optim.3 (2007) 135–164. Zbl1136.90026
- J. Peng, C. Roos and T. Terlaky, Self-regular functions and new search directions for linear and semidefinite optimization. Math. Program.93 (2002) 129–171. Zbl1007.90037
- G.Q. Wang and Y.Q. Bai, A new primal-dual path-following interior-point algorithm for semidefinite optimization. J. Math. Anal. Appl.353 (2009) 339–349. Zbl1172.90011
- G.Q. Wang and Y.Q. Bai, Primal-dual interior point algorithm for convex quadratic semi-definite optimization. Nonlinear Anal.71 (2009) 3389–3402. Zbl1179.65074
- G.Q. Wang, Y.Q. Bai and C. Roos, Primal-dual interior-point algorithms for semidefinite optimization based on a simple kernel function. J. Math. Model. Algorithms4 (2005) 409–433. Zbl1111.90083
- H. Wolkowicz, R. Saigal and L. Vandenberghe, Handbook of Semidefinite Programming, Theory, Algorithms, and Applications. Kluwer Academic Publishers, Dordrecht, The Netherlands (2000). Zbl0951.90001
- Y. Zhang, On extending some primal-dual interior-point algorithms from linear programming to semidefinite programming. SIAM J. Optim.8 (1998) 365–386. Zbl0913.65050

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.