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

Abstract

top
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( n log n ε ), which is best-known bound so far.

How to cite

top

Bai, 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
  1. M. Achache, A new primal-dual path-following method for convex quadratic programming. Comput. Appl. Math.25 (2006) 97–110.  Zbl1213.90187
  2. 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).  
  3. 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
  4. 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
  5. 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
  6. Z. Darvay, New interior-point algorithms in linear optimization. Adv. Model. Optim.5 (2003) 51–92.  Zbl1136.90509
  7. R.A. Horn and R.J. Charles, Topics in Matrix Analysis. Cambridge University Press, UK (1991).  Zbl0729.15001
  8. R.A. Horn and C.R. Johnson, Matrix analysis. Cambridge University Press (1990).  Zbl0704.15002
  9. E. de Klerk, Aspects of Semidefinite Programming: Interior Point Algorithms and Selected Applications. Kluwer Academic Publishers, Dordrecht, The Netherlands (2002).  Zbl0991.90098
  10. 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
  11. 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
  12. 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
  13. 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
  14. 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
  15. K.C. Toh, Inexact Primal-Dual Path-Following Algorithms for a Convex Quadratic SDP. Math. Program.112 (2008) 221–254.  Zbl1136.90027
  16. 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
  17. 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
  18. 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
  19. 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
  20. 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
  21. H. Wolkowicz, R. Saigal and L. Vandenberghe, Handbook of Semidefinite Programming, Theory, Algorithms, and Applications. Kluwer Academic Publishers, Dordrecht, The Netherlands (2000).  Zbl0951.90001
  22. 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 ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.