Skip to main content
Springer Nature Link
Log in

A new second-order Mehrotra-type predictor-corrector algorithm for SDO

  • Mathematics
  • Published:
Wuhan University Journal of Natural Sciences

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Karmarkar N K. A new polynomial-time algorithm for linear programming [J]. Combinatorica, 1984, 4: 373–395.

    Article  Google Scholar 

  2. Mehrotra S. On the implementation of a primal-dual interior point method [J]. SIAM Journal on Optimization, 1992, 2: 575–601.

    Article  Google Scholar 

  3. Salahi M, Peng J, Terlaky T. On Mehrotra-type predictor-corrector algorithms [J]. SIAM Journal on Optimization, 2007, 18(4): 1377–1397.

    Article  Google Scholar 

  4. Salahi M. A finite termination Mehrotra-type predictor-corrector algorithm [J]. Applied Mathematics and Computation, 2007, 190: 1740–1746.

    Article  Google Scholar 

  5. Salahi M, Mahdavi-Amiri N. Polynomial time second order Mehrotra-type predictor-corrector algorithms [J]. Applied Mathematics and Computation, 2006, 183: 646–658.

    Article  Google Scholar 

  6. Salahi M. New barrier parameter updating technique in Mehrotra-type algorithm [J]. Bulletin of the Iranian Mathematical Society, 2010, 36: 99–108.

    Google Scholar 

  7. Alizadeh F. Interior point methods in semidefinite programming with applications to combinatorial optimization[J]. SIAM Journal on Optimization, 1995, 5: 13–51.

    Article  Google Scholar 

  8. Nesterov Y E, Nemirovsky A S. Interior Point Methods in Convex Programming: Theory and Applications [M]. Philadelphia: SIAM, 1994.

    Google Scholar 

  9. Ye Y. A class of projective transformations for linear programming [J]. SIAM Journal on Computing, 1990, 19: 457–466.

    Article  Google Scholar 

  10. 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.

    Google Scholar 

  11. 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.

    Article  Google Scholar 

  12. Horn R A, Charles R J. Matrix Analysis [M]. Cambridge: Cambridge University Press, 1986.

    Google Scholar 

  13. Nesterov Y E, Todd M J. Primal-dual interior-point methods for self-scaled cones [J]. SIAM Journal on Optimization, 1998, 8: 324–364.

    Article  Google Scholar 

  14. Koulaei M H, Terlaky T. On the Extension of a Mehrotra-Type Algorithm for Semidefinite Optimization [R]. Ontario: McMaster University, 2007.

    Google Scholar 

  15. 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

    Article  Google Scholar 

  16. Zhang M W. A second order Mehrotra-type predictor corrector algorithm for semidefinite optimization [J]. Journal of Systems Science Complexity, 2012, 25: 1108–1121.

    Article  Google Scholar 

  17. 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.

    Article  Google Scholar 

  18. 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.

    Google Scholar 

  19. Klerk D E. Aspects of Semidefinite Programming: Interior Point Algorithms and Selected Applications [M]. Dordrecht: Kluwer Academic Publishers, 2002.

    Book  Google Scholar 

  20. 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.

    Article  Google Scholar 

  21. Monteiro R D C. Primal-dual path-following algorithms for semidefenite programming [J]. SIAM Journal on Optimization, 1997, 7: 663–678.

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. College of Science, China Three Gorges University, Yichang 443002, Hubei, China

    Fangyan Huang & Mingwang Zhang

  2. College of Economics and Management, China Three Gorges University, Yichang 443002, Hubei, China

    Zhengwei Huang

Authors
  1. Fangyan Huang
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Mingwang Zhang
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Zhengwei Huang
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Mingwang Zhang.

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

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

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

Download citation

  • Received:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11859-016-1144-y

Key words

CLC number

Search

Navigation