Smoothing technique and its applications in semidefinite optimization
(2004)
Files
dp2004_73.pdf
Open Access - Adobe PDF
- 175.94 KB
Details
- Authors
- 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.
- Affiliations
Citations
Nesterov, Y. (2004). Smoothing technique and its applications in semidefinite optimization (CORE Discussion Papers 2004/73).