SMOOTH OPTIMIZATION WITH APPROXIMATE GRADIENT

被引：99

作者：

D'Aspremont, Alexandre ^{[1
]}

机构：

[1] Princeton Univ, ORFE Dept, Princeton, NJ 08544 USA

来源：

SIAM JOURNAL ON OPTIMIZATION | 2008年 / 19卷 / 03期

关键词：

smooth optimization; first-order methods; semidefinite programming;

D O I：

10.1137/060676386

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

We show that the optimal complexity of Nesterov's smooth first-order optimization algorithm is preserved when the gradient is computed only up to a small, uniformly bounded error. In applications of this method to semidefinite programs, this means in some instances computing only a few leading eigenvalues of the current iterate instead of a full matrix exponential, which significantly reduces the method's computational cost. This also allows sparse problems to be solved efficiently using sparse maximum eigenvalue packages.

引用

页码：1171 / 1183

页数：13

共 19 条

[1] Broad patterns of gene expression revealed by clustering analysis of tumor and normal colon tissues probed by oligonucleotide arrays [J].

Alon, U ;

Barkai, N ;

Notterman, DA ;

Gish, K ;

Ybarra, S ;

Mack, D ;

Levine, AJ .

PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA, 1999, 96 (12) :6745-6750

[2] Non-euclidean restricted memory level method for large-scale convex optimization [J].

Ben-Tal, A ;

Nemirovski, A .

MATHEMATICAL PROGRAMMING, 2005, 102 (03) :407-456

[3] A direct formulation for sparse PCA using semidefinite programming [J].

d'Aspremont, Alexandre ;

El Ghaoui, Laurent ;

Jordan, Michael I. ;

Lanckriet, Gert R. G. .

SIAM REVIEW, 2007, 49 (03) :434-448

[4] Patterns in eigenvalues: The 70th Josiah Willard Gibbs Lecture [J].

Diaconis, P .

BULLETIN OF THE AMERICAN MATHEMATICAL SOCIETY, 2003, 40 (02) :155-178

[5]

Golub G.H., 1990, MATRIX COMPUTATION

[6] A spectral bundle method for semidefinite programming [J].

Helmberg, C ;

Rendl, F .

SIAM JOURNAL ON OPTIMIZATION, 2000, 10 (03) :673-696

[7]

Hiriart-Urruty J. B., 1996, CONVEX ANAL MINIMIZA, V305

[8]

LEHOUCQ RB, 1998, ARPACK SOLUTION LARG

[9]

Lewis A. S., 1996, Acta Numerica, V5, P149, DOI 10.1017/S0962492900002646

[10]

Marenko VA., 1967, MATH USSR SB, V1, P457, DOI [DOI 10.1070/SM1967V001N04ABEH001994, 10.1070/SM1967v001n04ABEH001994, 10.1070/sm1967v001n04abeh001994]

← 1 2 →