Smoothing Technique and its Applications in Semidefinite Optimization

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 Ο(1/ε) , where ε is the required absolute accuracy of the problem. In the second case, the number of iterations is bounded by (4/δ)√((1+δ)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.

• metadata
• References
• relations

Document type	Article de périodique (Journal article) – Article de recherche
Publication date	2007
Language	Anglais
Journal information	"Mathematical Programming" - Vol. 110, no. 2, p. 245-259 (Juillet 2007)
Peer reviewed	yes
Publisher	Springer (Heidelberg, Germany)
issn	0025-5610
e-issn	1436-4646
Publication status	Publié
Affiliations	UCL - EUEN/CORE - Center for operations research and econometrics UCL - FSA/INMA - Département d'ingénierie mathématique
Keywords	Convex optimization ; Non-smooth optimization ; Complexity theory ; Black-box model ; Optimal methods ; Structural optimization ; Smoothing technique
Links	http://hdl.handle.net/2078.1/23745[Handle] https://doi.org/10.1007/s10107-006-0001-8[DOI]

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 Adrian S., Sendov Hristo S., Twice Differentiable Spectral Functions, 10.1137/s089547980036838x
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
7. Nesterov Yurii, Introductory Lectures on Convex Optimization, ISBN:9781461346913, 10.1007/978-1-4419-8853-9
8. Nesterov Yu. (2005) Smooth minimization of non-smooth functions. Mathematical programming, 103(1): 127–152
9. Nesterov Yu. (2005) Excessive gap technique in nonsmooth convex minimization. SIAM J Optim 16(1): 235–249
10. Nesterov, Yu. Unconstrained convex minimization in relative scale. CORE Discussion Paper 2003/96 (2003)

See also
	[boreal:4801]	Smoothing technique and its applications in semidefinite optimization