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.
Similar content being viewed by others
References
Helmberg, C., Rendl, F. A spectral bundle method for semidenite programming. In: Technical Report SC 97-37, Konrad-Zuse-Zentrum fur Informationstechnik Berlin 1997
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
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
Lewis A.S., Sendov H.S. (2001) Twice differentiable spectral functions. SIMAX 23(2): 368–386
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
Nemirovskii A.S., Yudin D.B. (1983) Problem complexity and method efficiency in optimization. Wiley, New York
Nesterov Yu. (2004) Introductory lectures on convex optimization. A basic course. Kluwer, Boston
Nesterov Yu. (2005) Smooth minimization of non-smooth functions. Mathematical programming, 103(1): 127–152
Nesterov Yu. (2005) Excessive gap technique in nonsmooth convex minimization. SIAM J Optim 16(1): 235–249
Nesterov, Yu. Unconstrained convex minimization in relative scale. CORE Discussion Paper 2003/96 (2003)
Author information
Authors and Affiliations
Corresponding author
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
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
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10107-006-0001-8
Keywords
- Convex optimization
- Non-smooth optimization
- Complexity theory
- Black-box model
- Optimal methods
- Structural optimization
- Smoothing technique