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( log ), which is best-known bound so far.
Mots-clés : convex quadratic semidefinite optimization, interior-point algorithm, small-update method, iteration bound, polynomial-time
@article{RO_2010__44_3_251_0, author = {Bai, Y. Q. and Wang, F. Y. and Luo, X. W.}, title = {A polynomial-time interior-point algorithm for convex quadratic semidefinite optimization}, journal = {RAIRO - Operations Research - Recherche Op\'erationnelle}, pages = {251--265}, publisher = {EDP-Sciences}, volume = {44}, number = {3}, year = {2010}, doi = {10.1051/ro/2010016}, mrnumber = {2762796}, zbl = {1203.90178}, language = {en}, url = {http://www.numdam.org/articles/10.1051/ro/2010016/} }
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 - Recherche Opérationnelle PY - 2010 SP - 251 EP - 265 VL - 44 IS - 3 PB - EDP-Sciences UR - http://www.numdam.org/articles/10.1051/ro/2010016/ DO - 10.1051/ro/2010016 LA - en ID - RO_2010__44_3_251_0 ER -
%0 Journal Article %A Bai, Y. Q. %A Wang, F. Y. %A Luo, X. W. %T A polynomial-time interior-point algorithm for convex quadratic semidefinite optimization %J RAIRO - Operations Research - Recherche Opérationnelle %D 2010 %P 251-265 %V 44 %N 3 %I EDP-Sciences %U http://www.numdam.org/articles/10.1051/ro/2010016/ %R 10.1051/ro/2010016 %G en %F RO_2010__44_3_251_0
Bai, Y. Q.; Wang, F. Y.; Luo, X. W. A polynomial-time interior-point algorithm for convex quadratic semidefinite optimization. RAIRO - Operations Research - Recherche Opérationnelle, Tome 44 (2010) no. 3, pp. 251-265. doi : 10.1051/ro/2010016. http://www.numdam.org/articles/10.1051/ro/2010016/
[1] A new primal-dual path-following method for convex quadratic programming. Comput. Appl. Math. 25 (2006) 97-110.
,[2] 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).
and ,[3] Solving Euclidean distance matrix completion problems via semidefinite programming. Comp. Optim. Appl. 12 (1999) 13C30. | Zbl
, and ,[4] 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. | Zbl
and ,[5] Ghami, A comparative study of kernel functions for primal-dual interior-point algorithms in linear optimization. SIAM J. Optim. 15 (2004) 101-128. | Zbl
, and .[6] New interior-point algorithms in linear optimization. Adv. Model. Optim. 5 (2003) 51-92. | Zbl
,[7] Topics in Matrix Analysis. Cambridge University Press, UK (1991). | Zbl
and ,[8] Matrix analysis. Cambridge University Press (1990). | Zbl
and ,[9] Aspects of Semidefinite Programming: Interior Point Algorithms and Selected Applications. Kluwer Academic Publishers, Dordrecht, The Netherlands (2002). | Zbl
,[10] Reduction of Monotone Linear Complemen-tarity Problems over Cones to Linear Programs over Cones. Acta Mathematica Vietnamica 22 (1997) 147-157. | Zbl
, and ,[11] Interior-point methods for the monotone linear complementarity problem in symmetric matrices. SIAM J. Optim. 7 (1997) 86-125. | Zbl
, and ,[12] Primal-dual interior-point methods for self-scaled cones. SIAM J. Optim. 8 (1998) 324-364. | Zbl
and ,[13] A Potential Reduction Algorithm for an Extended SDP. Science In China (Series A) 43 (2000) 35-46. | Zbl
and ,[14] A Predictor-Corrector Algorithm for QSDP Combining and Newton Centering Steps. Ann. Oper. Res. 103 (2001) 115-133. | Zbl
and ,[15] Inexact Primal-Dual Path-Following Algorithms for a Convex Quadratic SDP. Math. Program. 112 (2008) 221-254. | Zbl
,[16] Inexact primal-dual path-following algorithms for a special class of convex quadratic SDP and related problems. Pac. J. Optim. 3 (2007) 135-164. | Zbl
, and ,[17] Self-regular functions and new search directions for linear and semidefinite optimization. Math. Program. 93 (2002) 129-171. | Zbl
, and ,[18] A new primal-dual path-following interior-point algorithm for semidefinite optimization. J. Math. Anal. Appl. 353 (2009) 339-349. | Zbl
and ,[19] Primal-dual interior point algorithm for convex quadratic semi-definite optimization. Nonlinear Anal. 71 (2009) 3389-3402. | Zbl
and ,[20] Primal-dual interior-point algorithms for semidefinite optimization based on a simple kernel function. J. Math. Model. Algorithms 4 (2005) 409-433. | Zbl
, and ,[21] Handbook of Semidefinite Programming, Theory, Algorithms, and Applications. Kluwer Academic Publishers, Dordrecht, The Netherlands (2000). | Zbl
, and ,[22] On extending some primal-dual interior-point algorithms from linear programming to semidefinite programming. SIAM J. Optim. 8 (1998) 365-386. | Zbl
,Cité par Sources :