Abstract
In Zhang’s recent works, a second-order Mehrotra-type predictor-corrector algorithm for linear optimization was extended to semidefinite optimization and derived that the algorithm for semidefinite optimization had O(n 3/2log(X 0)T•S 0/ε) iteration complexity based on the NT direction as Newton search direction. In this paper, we extend the second-order Mehrotra-type predictor-corrector algorithm for linear optimization to semidefinite optimization and discuss the polynomial convergence of the algorithm by modifying the corrector direction and new iterates. It is proved that the iteration complexity is reduced to O(nlogX 0•S 0/ε), which coincides with the currently best iteration bound of Mehrotra-type predictor-corrector algorithm for semidefinite optimization.
Similar content being viewed by others
References
Karmarkar N K. A new polynomial-time algorithm for linear programming [J]. Combinatorica, 1984, 4: 373–395.
Mehrotra S. On the implementation of a primal-dual interior point method [J]. SIAM Journal on Optimization, 1992, 2: 575–601.
Salahi M, Peng J, Terlaky T. On Mehrotra-type predictor-corrector algorithms [J]. SIAM Journal on Optimization, 2007, 18(4): 1377–1397.
Salahi M. A finite termination Mehrotra-type predictor-corrector algorithm [J]. Applied Mathematics and Computation, 2007, 190: 1740–1746.
Salahi M, Mahdavi-Amiri N. Polynomial time second order Mehrotra-type predictor-corrector algorithms [J]. Applied Mathematics and Computation, 2006, 183: 646–658.
Salahi M. New barrier parameter updating technique in Mehrotra-type algorithm [J]. Bulletin of the Iranian Mathematical Society, 2010, 36: 99–108.
Alizadeh F. Interior point methods in semidefinite programming with applications to combinatorial optimization[J]. SIAM Journal on Optimization, 1995, 5: 13–51.
Nesterov Y E, Nemirovsky A S. Interior Point Methods in Convex Programming: Theory and Applications [M]. Philadelphia: SIAM, 1994.
Ye Y. A class of projective transformations for linear programming [J]. SIAM Journal on Computing, 1990, 19: 457–466.
Alizadeh F, Haeberly J A, Overton M. Primal-dual interior-point methods for semidefinite programming: Convergence rates, stability and numerical results [J]. SIAM Journal on Optimization, 1994.
Helmberg C, Rendl F, Vanderbei R J, et al. An interior-point method for semidefinite programming [J]. SIAM Journal on Optimization, 1996, 6(2): 342–361.
Horn R A, Charles R J. Matrix Analysis [M]. Cambridge: Cambridge University Press, 1986.
Nesterov Y E, Todd M J. Primal-dual interior-point methods for self-scaled cones [J]. SIAM Journal on Optimization, 1998, 8: 324–364.
Koulaei M H, Terlaky T. On the Extension of a Mehrotra-Type Algorithm for Semidefinite Optimization [R]. Ontario: McMaster University, 2007.
Liu C H, Liu H W, Liu X Z. Polynomial convergence of second-order mehrotra-type predictor-corrector algorithms over symmetric cones [J]. Journal of Optimization Theory and Applications, 2012, 154: 949–965
Zhang M W. A second order Mehrotra-type predictor corrector algorithm for semidefinite optimization [J]. Journal of Systems Science Complexity, 2012, 25: 1108–1121.
Zhang Y. On extending some primal-dual interior-point algorithms from linear programming to semidefinite programming [J]. SIAM Journal on Optimization, 1998, 8: 365–386.
Monteiro R D C, Zhang Y. A unified analysis for a class of long-step primal-dual path-following interior-point algorithms for semidefinite programming [J]. Mathematical Programming, 1998, 81: 281–299.
Klerk D E. Aspects of Semidefinite Programming: Interior Point Algorithms and Selected Applications [M]. Dordrecht: Kluwer Academic Publishers, 2002.
Kojima M, Shindoh S, Hara S. Interior point methods for the monotone semidefinite linear complementarity problem in symmetric matrices [J]. SIAM Journal on Optimization, 1997, 7: 86–125.
Monteiro R D C. Primal-dual path-following algorithms for semidefenite programming [J]. SIAM Journal on Optimization, 1997, 7: 663–678.
Author information
Authors and Affiliations
Corresponding author
Additional information
Foundation item: Supported by the National Natural Science Foundation of China (71471102)
Biography: HUANG Fangyan, female, Master candidate, research direction: optimization theory and application.
Rights and permissions
About this article
Cite this article
Huang, F., Zhang, M. & Huang, Z. A new second-order Mehrotra-type predictor-corrector algorithm for SDO. Wuhan Univ. J. Nat. Sci. 21, 99–109 (2016). https://doi.org/10.1007/s11859-016-1144-y
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11859-016-1144-y