Smoothing technique and its applications in semidefinite optimization

Yurii Nesterov

No 2004073, LIDAM Discussion Papers CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE)

Abstract: In this paper we extend the smoothing technique [7], [9] 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 Lipshitz constants for some natural approximations of maximal eigenvalue and the spectral radius of symmetric matrices. We analyze the complexity of the problem-oriented gradient-type schemes onto 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/E), where E is the required absolute accuracy of the problem. In the second case, the number of iterations is bounded by 4/[delta] sq.(1 + [delta])r ln r, where [delta] 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.

Keywords: convex optimization; non-smooth optimization; complexity theory; black-box model; optimal methods; structural optimization; smoothing technique (search for similar items in EconPapers)
Date: 2004-11
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://sites.uclouvain.be/core/publications/coredp/coredp2004.html (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:cor:louvco:2004073

Access Statistics for this paper

More papers in LIDAM Discussion Papers CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE) Voie du Roman Pays 34, 1348 Louvain-la-Neuve (Belgium). Contact information at EDIRC.
Bibliographic data for series maintained by Alain GILLIS ().