[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

A Variant of the Dual Simplex Method for a Linear Semidefinite Programming Problem

  • Published:
Proceedings of the Steklov Institute of Mathematics Aims and scope Submit manuscript

Abstract

A linear semidefinite programming problem in the standard statement is considered, and a variant of the dual simplex method is proposed for its solution. This variant generalizes the corresponding method used for linear programming problems. The transfer from an extreme point of the feasible set to another extreme point is described. The convergence of the method is proved.

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
£29.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 includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. I. I. Eremin, Theory of Linear Optimization (Izd. Ekaterinburg, Yekaterinburg, 1999) [in Russian].

    Google Scholar 

  2. F. P. Vasil’ev and A. Yu. Ivanitskii, Linear Programming (Faktorial, Moscow, 2008) [in Russian].

    MATH  Google Scholar 

  3. L. Vandenberghe and S. Boyd, “Semidefinite programming,” SIAM Rev. 38 (1), 49–95 (1996).

    MathSciNet  MATH  Google Scholar 

  4. Handbook of Semidefinite Programming, Ed. by H. Wolkowicz, R. Saigal, and L. Vandenberghe (Kluwer Acad., Dordrecht, 2000).

    MATH  Google Scholar 

  5. J. B. Lasserre, “Linear programming with positive semi-definite matrices,” Math. Probl. Engineering 2, 499–522 (1996).

    Article  MATH  Google Scholar 

  6. G. Pataki, “Cone-LP’s and semidefinite programs: Geometry and a simplex-type method,” in Proceedings of the 5th International Conference on Integer Programming and Combinatorial Optimization, Vancouver, Canada, 1996, pp. 162–174.

    Chapter  Google Scholar 

  7. A. I. Kosolap, “The simplex method for semidefinite programming problems,” Vestn. Donetsk. Nats. Univ., Ser. Estestv. Nauki, No. 2, pp. 365–369 (2009).

    Google Scholar 

  8. V. G. Zhadan, “On a variant of the simplex method for a linear semidefinite programming problem,” Trudy Inst. Mat. Mekh. UrO RAN 21 (3), 117–127 (2015).

    MathSciNet  Google Scholar 

  9. J. R. Magnus and H. Neudecker, Matrix Differential Calculus with Applications in Statistics and Econometrics (Wiley, Chichester, 1999; Fizmatlit, Moscow, 2002).

    MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Dorodnitsyn Computing Center of the Russian Academy of Sciences, Moscow, 119333, Russia

    V. G. Zhadan

Authors
  1. V. G. Zhadan
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to V. G. Zhadan.

Additional information

Original Russian Text © V.G. Zhadan, 2016, published in Trudy Instituta Matematiki i Mekhaniki UrO RAN, 2016, Vol. 22, No. 3.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Zhadan, V.G. A Variant of the Dual Simplex Method for a Linear Semidefinite Programming Problem. Proc. Steklov Inst. Math. 299 (Suppl 1), 246–256 (2017). https://doi.org/10.1134/S0081543817090267

Download citation

  • Received:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1134/S0081543817090267

Keywords

Search

Navigation