A Newton-CG Augmented Lagrangian Method for Semidefinite Programming
We consider a Newton-CG augmented Lagrangian method for solving semidefinite programming (SDP) problems from the perspective of approximate semismooth Newton methods. In order to analyze the rate of convergence of our proposed method, we characterize the Lipschitz continuity of the corresponding sol...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Society for Industrial and Applied Mathematics
2010
|
| Online Access: | http://hdl.handle.net/1721.1/58308 |
| _version_ | 1826210667903844352 |
|---|---|
| author | Toh, Kim Chuan Zhao, Xin-Yuan Sun, Defeng |
| author2 | Singapore-MIT Alliance in Research and Technology (SMART) |
| author_facet | Singapore-MIT Alliance in Research and Technology (SMART) Toh, Kim Chuan Zhao, Xin-Yuan Sun, Defeng |
| author_sort | Toh, Kim Chuan |
| collection | MIT |
| description | We consider a Newton-CG augmented Lagrangian method for solving semidefinite programming (SDP) problems from the perspective of approximate semismooth Newton methods. In order to analyze the rate of convergence of our proposed method, we characterize the Lipschitz continuity of the corresponding solution mapping at the origin. For the inner problems, we show that the positive definiteness of the generalized Hessian of the objective function in these inner problems, a key property for ensuring the efficiency of using an inexact semismooth Newton-CG method to solve the inner problems, is equivalent to the constraint nondegeneracy of the corresponding dual problems. Numerical experiments on a variety of large-scale SDP problems with the matrix dimension n up to 4,110 and the number of equality constraints m up to 2,156,544 show that the proposed method is very efficient. We are also able to solve the SDP problem fap36 (with n=4,110 and m=1,154,467) in the Seventh DIMACS Implementation Challenge much more accurately than in previous attempts. |
| first_indexed | 2024-09-23T14:53:16Z |
| format | Article |
| id | mit-1721.1/58308 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T14:53:16Z |
| publishDate | 2010 |
| publisher | Society for Industrial and Applied Mathematics |
| record_format | dspace |
| spelling | mit-1721.1/583082022-09-29T11:14:36Z A Newton-CG Augmented Lagrangian Method for Semidefinite Programming A NEWTON-CG AUGMENTED LAGRANGIAN METHOD FOR SEMIDEFINITE PROGRAMMING Toh, Kim Chuan Zhao, Xin-Yuan Sun, Defeng Singapore-MIT Alliance in Research and Technology (SMART) Toh, Kim-Chuan Toh, Kim Chuan We consider a Newton-CG augmented Lagrangian method for solving semidefinite programming (SDP) problems from the perspective of approximate semismooth Newton methods. In order to analyze the rate of convergence of our proposed method, we characterize the Lipschitz continuity of the corresponding solution mapping at the origin. For the inner problems, we show that the positive definiteness of the generalized Hessian of the objective function in these inner problems, a key property for ensuring the efficiency of using an inexact semismooth Newton-CG method to solve the inner problems, is equivalent to the constraint nondegeneracy of the corresponding dual problems. Numerical experiments on a variety of large-scale SDP problems with the matrix dimension n up to 4,110 and the number of equality constraints m up to 2,156,544 show that the proposed method is very efficient. We are also able to solve the SDP problem fap36 (with n=4,110 and m=1,154,467) in the Seventh DIMACS Implementation Challenge much more accurately than in previous attempts. 2010-09-03T17:49:02Z 2010-09-03T17:49:02Z 2010-01 2008-03 Article http://purl.org/eprint/type/JournalArticle 1052-6234 1095-7189 http://hdl.handle.net/1721.1/58308 Zhao, Xin-Yuan, Defeng Sun, and Kim-Chuan Toh. "A Newton-CG Augmented Lagrangian Method for Semidefinite Programming." SIAM J. Optim. Volume 20, Issue 4, pp. 1737-1765 (2010) ©2010 Society for Industrial and Applied Mathematics. en_US http://dx.doi.org/10.1137/080718206 SIAM Journal on Optimization Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. application/pdf Society for Industrial and Applied Mathematics SIAM |
| spellingShingle | Toh, Kim Chuan Zhao, Xin-Yuan Sun, Defeng A Newton-CG Augmented Lagrangian Method for Semidefinite Programming |
| title | A Newton-CG Augmented Lagrangian Method for Semidefinite Programming |
| title_full | A Newton-CG Augmented Lagrangian Method for Semidefinite Programming |
| title_fullStr | A Newton-CG Augmented Lagrangian Method for Semidefinite Programming |
| title_full_unstemmed | A Newton-CG Augmented Lagrangian Method for Semidefinite Programming |
| title_short | A Newton-CG Augmented Lagrangian Method for Semidefinite Programming |
| title_sort | newton cg augmented lagrangian method for semidefinite programming |
| url | http://hdl.handle.net/1721.1/58308 |
| work_keys_str_mv | AT tohkimchuan anewtoncgaugmentedlagrangianmethodforsemidefiniteprogramming AT zhaoxinyuan anewtoncgaugmentedlagrangianmethodforsemidefiniteprogramming AT sundefeng anewtoncgaugmentedlagrangianmethodforsemidefiniteprogramming AT tohkimchuan newtoncgaugmentedlagrangianmethodforsemidefiniteprogramming AT zhaoxinyuan newtoncgaugmentedlagrangianmethodforsemidefiniteprogramming AT sundefeng newtoncgaugmentedlagrangianmethodforsemidefiniteprogramming |