Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Introduction to Semidefinite, Conic and Polynomial Optimization Read chapter Read first chapter

2012 | OriginalPaper | Chapter

15. Self-Regular Interior-Point Methods for Semidefinite Optimization

Authors : Maziar Salahi, Tamás Terlaky

Published in: Handbook on Semidefinite, Conic and Polynomial Optimization

Publisher: Springer US

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

Semidefinite optimization has an ever growing family of crucial applications, and large neighborhood interior point methods (IPMs) yield the method of choice to solve them. This chapter reviews the fundamental concepts and complexity results of Self-Regular (SR) IPMs for semidefinite optimizaion, that up to a log factor achieve the best polynomial complexity bound of small neighborhood IPMs. SR kernel functions are in the core of SR-IPMs. This chapter reviews several none SR kernel functions too. IPMs based on theses kernel functions enjoy similar iteration complexity bounds as SR-IPMs, though their complexity analysis requires additional tools.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter Positivity and Optimization: Beyond Polynomials
next chapter Elementary Optimality Conditions for Nonlinear SDPs
Footnotes
1
As we see the right hand side of the last equation in (15.11) is the negative gradient of the classical logarithmic barrier function ψ(V ) (see Definition 3 on p. 9), where
$$\psi (t) = \frac{{t}^{2} - 1} {2} -\log t.$$
 
Literature
1.
Ai, W., Zhang, S.: An \(O(\sqrt{n}L)\) iteration primal-dual path-following method, based on wide neighborhood and large updates, for monotone LCP. SIAM J. on Optimization 16, 400–417 (2005)
2.
Alizadeh, F.: Combinatorial optimization with interior-point methods and semi-definite matrices. Ph.D. Thesis, Computer Science Department, University of Minnesota, Minneapolis, MN, USA (1991)
3.
Alizadeh, F.: Interior point methods in semidefinite programming with applications to combinatorial optimization. SIAM J. on Optimization 5, 13-51 (1995)CrossRef
4.
Alizadeh, F., Haeberly, J.A., Overton, M.L.: Primal-dual interior-point methods for semidefinite programming: Convergence rates, stability and numerical results. SIAM J. on Optimization 8, 746-768 (1998)CrossRef
5.
Bellman, R., Fan, K.: On systems of linear inequalities in Hermitian matrix variables. In: Klee, V.L. (ed.) Convexity, Proceedings of Symposia in Pure Mathematics, vol. 7, pp. 1-11. American Mathematical Society, Providence, RI (1963)
6.
El Ghami, M., Bai, Y.Q., Roos, C.: Kernel-functions based algorithms for semidefinite optimization. RAIRO-Oper. Res. 43, 189–199 (2009)CrossRef
7.
El Ghami, M., Roos, C., Steihaug, T.: A generic primal-dual interior-point method for semidefinite optimization based on a new class of kernel functions. Optimization Methods and Software 25(3), 387–403 (2010)CrossRef
8.
Goemans, M.X., Williamson, D.P.: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. of the ACM 42(6), 1115-1145 (1995)CrossRef
9.
Helmberg, C., Rendl, F., Vanderbei, R.J., Wolkowicz, H.: An interior-point method for semidefinite programming. SIAM J. on Optimization 6, 342-361 (1996)CrossRef
10.
Kojima, M., Shindoh, S., Hara, S.: Interior-point methods for the monotone semidefinite linear complementarity problem in symmetric matrices. SIAM J. on Optimization 7, 86-125 (1997)CrossRef
11.
Liu, H., Liu, S., Xu, F.: A tight semidefinite relaxation of the max-cut problem. J. of Combinatorial Optimization 7, 237–245 (2004)CrossRef
12.
Nesterov, Y.E., Nemirovskii, A.S.: Interior Point Polynomial Algorithms in Convex Programming: Theory and Applications. SIAM, Philadelphia, PA (1994)CrossRef
13.
Nesterov, Y.E., Todd, M.J.: Self-scaled barriers and interior-point methods for convex programming. Mathematics of Operations Research 22, 1-42 (1997)CrossRef
14.
Nesterov, Y.E., Todd, M.J.: Primal-dual interior-point methods for self-scaled cones. SIAM J. on Optimization 8, 324–364 (1998)CrossRef
15.
Peng, J., Roos, C., Terlaky, T.: Self-regular proximities and new search directions for linear and semidefinite optimization. Mathematical Programming 93, 129–171 (2002)CrossRef
16.
Peng, J., Roos, C., Terlaky, T.: A new class of polynomial primal-dual methods for linear and semidefinite optimization. European J. Operational Research 143(2), 234–256 (2002)CrossRef
17.
Peng, J., Roos, C., Terlaky, T.: Self-Regularity: A New Paradigm of Primal-Dual Interior Point Algorithms. Princeton University Press, Princeton (2002)
18.
Peyghami, M.R.: An interior point approach for semidefinite optimization using new proximity functions. Asia-Pacific J. of Operational Research 26(3), 365–382 (2009)CrossRef
19.
Roos, C., Terlaky, T., Vial, J.P.: Interior Point Algorithms for Linear Optimization. Second ed., Springer Science (2005)
20.
Terlaky, T., Li, Y.: A new class of large neighborhood path–following interior point algorithms for semidefinite optimization with \(O\Big{(}\sqrt{n}\log \frac{\mathrm{Tr}({X}^{0}{S}^{0})} {\epsilon } \Big{)}\) iteration complexity. SIAM J. on Optimization 20(6), 2853–2875 (2010)
21.
Vandenberghe, L., Boyd, S.: Semidefinite programming. SIAM Review 38, 49–95 (1996)
22.
Wang, G.Q., Bai, Y.Q., Roos, C.: Primal-dual interior-point algorithms for semidefinite optimization based on simple kernel functions. J. of Mathematical Modelling and Algorithms 4, 409–433 (2005)CrossRef
23.
Wolkowicz, H., Saigal, R., Vandenberghe, L.: Handbook of Semidefinite Programming: Theory, Algorithms and Applications. Kluwer Academic Publishers (2000)CrossRef
24.
Zhang Y.: On extending some primal-dual interior-point algorithms from linear programming to semidefinite programming. SIAM J. on Optimization 8, 365–386 (1998)CrossRef
Metadata
Title
Self-Regular Interior-Point Methods for Semidefinite Optimization
Authors
Maziar Salahi
Tamás Terlaky
Copyright Year
2012
Publisher
Springer US
Book
Handbook on Semidefinite, Conic and Polynomial Optimization

Print ISBN: 978-1-4614-0768-3

Electronic ISBN: 978-1-4614-0769-0

Copyright Year: 2012

DOI
https://doi.org/10.1007/978-1-4614-0769-0_15