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.  
  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.  
  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.  
  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.  
  6. Z. Darvay, New interior-point algorithms in linear optimization. Adv. Model. Optim.5 (2003) 51–92.  
  7. R.A. Horn and R.J. Charles, Topics in Matrix Analysis. Cambridge University Press, UK (1991).  
  8. R.A. Horn and C.R. Johnson, Matrix analysis. Cambridge University Press (1990).  
  9. E. de Klerk, Aspects of Semidefinite Programming: Interior Point Algorithms and Selected Applications. Kluwer Academic Publishers, Dordrecht, The Netherlands (2002).  
  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.  
  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.  
  12. Y.E. Nesterov and M.J. Todd, Primal-dual interior-point methods for self-scaled cones. SIAM J. Optim.8 (1998) 324–364.  
  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.  
  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.  
  15. K.C. Toh, Inexact Primal-Dual Path-Following Algorithms for a Convex Quadratic SDP. Math. Program.112 (2008) 221–254.  
  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.  
  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.  
  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.  
  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.  
  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.  
  21. H. Wolkowicz, R. Saigal and L. Vandenberghe, Handbook of Semidefinite Programming, Theory, Algorithms, and Applications. Kluwer Academic Publishers, Dordrecht, The Netherlands (2000).  
  22. Y. Zhang, On extending some primal-dual interior-point algorithms from linear programming to semidefinite programming. SIAM J. Optim.8 (1998) 365–386.  

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.