Nothing Special   »   [go: up one dir, main page]

Skip to main content
Log in

Smoothing Technique and its Applications in Semidefinite Optimization

  • Published:
Mathematical Programming Submit manuscript

Abstract

In this paper we extend the smoothing technique (Nesterov in Math Program 103(1): 127–152, 2005; Nesterov in Unconstrained convex mimimization in relative scale, 2003) onto the problems of semidefinite optimization. For that, we develop a simple framework for estimating a Lipschitz constant for the gradient of some symmetric functions of eigenvalues of symmetric matrices. Using this technique, we can justify the Lipschitz constants for some natural approximations of maximal eigenvalue and the spectral radius of symmetric matrices. We analyze the efficiency of the special gradient-type schemes on the problems of minimizing the maximal eigenvalue or the spectral radius of the matrix, which depends linearly on the design variables. We show that in the first case the number of iterations of the method is bounded by \(O({1}/{\epsilon})\), where \(\epsilon\) is the required absolute accuracy of the problem. In the second case, the number of iterations is bounded by \({({4}/{\delta})} \sqrt{(1 + \delta) r\, \ln r }\), where δ is the required relative accuracy and r is the maximal rank of corresponding linear matrix inequality. Thus, the latter method is a fully polynomial approximation scheme.

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

Access this article

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.

Similar content being viewed by others

References

  1. Helmberg, C., Rendl, F. A spectral bundle method for semidenite programming. In: Technical Report SC 97-37, Konrad-Zuse-Zentrum fur Informationstechnik Berlin 1997

  2. Helmberg, C., Oustry, F. Bundle methods to minimize the maximum eigenvalue function. In: Vandenberghe, R. Saigal, H. Wolkovicz, (eds.) Hanbook on semidefinite programming. Theory, algorithms and applications. Kluwer Dordrecht 1999

  3. Lemarechal, C., Oustry, F. Nonsmooth algorithms to solve semidefinite programs. In: El Ghaoui, L. Niculescu S.I. (eds.) Recent advances on LMI methods in control. Advances in design and control series. SIAM 1999

  4. Lewis A.S., Sendov H.S. (2001) Twice differentiable spectral functions. SIMAX 23(2): 368–386

    MATH  MathSciNet  Google Scholar 

  5. Nayakkankuppam, M.V., Tymofejev, Y. A parallel implementation of the spectral bundle method for large-scale semidefinite programs. In: Proceedings of the 8th SIAM conference on applied linear algebra, Williamsburg (VA) 2003

  6. Nemirovskii A.S., Yudin D.B. (1983) Problem complexity and method efficiency in optimization. Wiley, New York

    Google Scholar 

  7. Nesterov Yu. (2004) Introductory lectures on convex optimization. A basic course. Kluwer, Boston

    MATH  Google Scholar 

  8. Nesterov Yu. (2005) Smooth minimization of non-smooth functions. Mathematical programming, 103(1): 127–152

    Article  MATH  MathSciNet  Google Scholar 

  9. Nesterov Yu. (2005) Excessive gap technique in nonsmooth convex minimization. SIAM J Optim 16(1): 235–249

    Article  MATH  MathSciNet  Google Scholar 

  10. Nesterov, Yu. Unconstrained convex minimization in relative scale. CORE Discussion Paper 2003/96 (2003)

Download references

Author information

Authors and Affiliations

Authors

Corresponding author

Correspondence to Yurii Nesterov.

Additional information

The research results presented in this paper have been supported by a grant “Action de recherche concertè ARC 04/09-315” from the “Direction de la recherche scientifique - Communautè française de Belgique”. The scientific responsibility rests with the authors.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Nesterov, Y. Smoothing Technique and its Applications in Semidefinite Optimization. Math. Program. 110, 245–259 (2007). https://doi.org/10.1007/s10107-006-0001-8

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10107-006-0001-8

Keywords

Mathematics Subject Classification (1991)

Navigation