An Interior Point Method for Solving Semidefinite Programs Using Cutting Planes and Weighted Analytic Centers
We investigate solving semidefinite programs (SDPs) with an interior point method called SDP-CUT, which utilizes weighted analytic centers and cutting plane constraints. SDP-CUT iteratively refines the feasible region to achieve the optimal solution. The algorithm uses Newton’s method to compute the...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2012-01-01
|
| Series: | Journal of Applied Mathematics |
| Online Access: | http://dx.doi.org/10.1155/2012/946893 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832552400749068288 |
|---|---|
| author | John Machacek Shafiu Jibrin |
| author_facet | John Machacek Shafiu Jibrin |
| author_sort | John Machacek |
| collection | DOAJ |
| description | We investigate solving semidefinite programs (SDPs) with an interior point method called SDP-CUT, which utilizes weighted analytic centers and cutting plane constraints. SDP-CUT iteratively refines
the feasible region to achieve the optimal solution. The algorithm uses Newton’s method to compute the weighted analytic center. We investigate different stepsize determining techniques. We found that using
Newton's method with exact line search is generally the best implementation of the algorithm. We have also compared our algorithm to the SDPT3 method and found that SDP-CUT initially gets into the neighborhood of the optimal solution in less iterations on all our test problems. SDP-CUT also took less iterations to reach optimality on many of the problems. However, SDPT3 required less iterations on most
of the test problems and less time on all the problems. Some theoretical properties of the convergence of SDP-CUT are also discussed. |
| format | Article |
| id | doaj-art-e097bd13246f4e21aaba210170d8b624 |
| institution | Kabale University |
| issn | 1110-757X 1687-0042 |
| language | English |
| publishDate | 2012-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | Journal of Applied Mathematics |
| spelling | doaj-art-e097bd13246f4e21aaba210170d8b6242025-02-03T05:58:54ZengWileyJournal of Applied Mathematics1110-757X1687-00422012-01-01201210.1155/2012/946893946893An Interior Point Method for Solving Semidefinite Programs Using Cutting Planes and Weighted Analytic CentersJohn Machacek0Shafiu Jibrin1Department of Computer Science and Engineering, University of Minnesota, Minneapolis, MN 55455, USADepartment of Mathematics and Statistics, Northern Arizona University, Flagstaff, Arizona 86011-5717, USAWe investigate solving semidefinite programs (SDPs) with an interior point method called SDP-CUT, which utilizes weighted analytic centers and cutting plane constraints. SDP-CUT iteratively refines the feasible region to achieve the optimal solution. The algorithm uses Newton’s method to compute the weighted analytic center. We investigate different stepsize determining techniques. We found that using Newton's method with exact line search is generally the best implementation of the algorithm. We have also compared our algorithm to the SDPT3 method and found that SDP-CUT initially gets into the neighborhood of the optimal solution in less iterations on all our test problems. SDP-CUT also took less iterations to reach optimality on many of the problems. However, SDPT3 required less iterations on most of the test problems and less time on all the problems. Some theoretical properties of the convergence of SDP-CUT are also discussed.http://dx.doi.org/10.1155/2012/946893 |
| spellingShingle | John Machacek Shafiu Jibrin An Interior Point Method for Solving Semidefinite Programs Using Cutting Planes and Weighted Analytic Centers Journal of Applied Mathematics |
| title | An Interior Point Method for Solving Semidefinite Programs Using Cutting Planes and Weighted Analytic Centers |
| title_full | An Interior Point Method for Solving Semidefinite Programs Using Cutting Planes and Weighted Analytic Centers |
| title_fullStr | An Interior Point Method for Solving Semidefinite Programs Using Cutting Planes and Weighted Analytic Centers |
| title_full_unstemmed | An Interior Point Method for Solving Semidefinite Programs Using Cutting Planes and Weighted Analytic Centers |
| title_short | An Interior Point Method for Solving Semidefinite Programs Using Cutting Planes and Weighted Analytic Centers |
| title_sort | interior point method for solving semidefinite programs using cutting planes and weighted analytic centers |
| url | http://dx.doi.org/10.1155/2012/946893 |
| work_keys_str_mv | AT johnmachacek aninteriorpointmethodforsolvingsemidefiniteprogramsusingcuttingplanesandweightedanalyticcenters AT shafiujibrin aninteriorpointmethodforsolvingsemidefiniteprogramsusingcuttingplanesandweightedanalyticcenters AT johnmachacek interiorpointmethodforsolvingsemidefiniteprogramsusingcuttingplanesandweightedanalyticcenters AT shafiujibrin interiorpointmethodforsolvingsemidefiniteprogramsusingcuttingplanesandweightedanalyticcenters |