TY - JOUR
T1 - The spectral bundle method with second-order information
AU - Helmberg, C.
AU - Overton, M. L.
AU - Rendl, F.
N1 - Funding Information:
This work was supported by the National Science Foundation [grant number DMS-1016325].
PY - 2014/7/4
Y1 - 2014/7/4
N2 - The spectral bundle (SB) method was introduced by Helmberg and Rend [A spectral bundle method for semidefinite programming. SIAM J. Optim. 10 (2000), pp. 673-696] to solve a class of eigenvalue optimization problems that is equivalent to the class of semidefinite programs with the constant trace property. We investigate the feasibility and effectiveness of including full or partial second-order information in the SB method, building on work of Overton [On minimizing the maximum eigenvalue of a symmetric matrix. SIAM J. Matrix Anal. Appl. 9(2) (1988), pp. 256-268] and Overton and Womersley [Second derivatives for optimizing eigenvalues of symmetric matrices. SIAM J. Matrix Anal. Appl. 16 (1995), pp. 697-718]. We propose several variations that include second-order information in the SB method and describe efficient implementations. One of these, namely diagonal scaling based on a low-rank approximation of the second-order model for max, improves the standard SB method both with respect to accuracy requirements and computation time.
AB - The spectral bundle (SB) method was introduced by Helmberg and Rend [A spectral bundle method for semidefinite programming. SIAM J. Optim. 10 (2000), pp. 673-696] to solve a class of eigenvalue optimization problems that is equivalent to the class of semidefinite programs with the constant trace property. We investigate the feasibility and effectiveness of including full or partial second-order information in the SB method, building on work of Overton [On minimizing the maximum eigenvalue of a symmetric matrix. SIAM J. Matrix Anal. Appl. 9(2) (1988), pp. 256-268] and Overton and Womersley [Second derivatives for optimizing eigenvalues of symmetric matrices. SIAM J. Matrix Anal. Appl. 16 (1995), pp. 697-718]. We propose several variations that include second-order information in the SB method and describe efficient implementations. One of these, namely diagonal scaling based on a low-rank approximation of the second-order model for max, improves the standard SB method both with respect to accuracy requirements and computation time.
KW - bundle methods
KW - eigenvalue optimization
KW - semidefinite optimization
UR - http://www.scopus.com/inward/record.url?scp=84894081904&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84894081904&partnerID=8YFLogxK
U2 - 10.1080/10556788.2013.858155
DO - 10.1080/10556788.2013.858155
M3 - Article
AN - SCOPUS:84894081904
SN - 1055-6788
VL - 29
SP - 855
EP - 876
JO - Optimization Methods and Software
JF - Optimization Methods and Software
IS - 4
ER -