About OpenKnowledge@NAU | For NAU Authors

An interior point method for solving semidefinite programs using cutting planes and weighted analytic centers

Machacek, John and Jibrin, Shafiu (2012) An interior point method for solving semidefinite programs using cutting planes and weighted analytic centers. Journal of Applied Mathematics, 2012. ISSN 1687-0042

Available under License Creative Commons Attribution.

Download (2MB) | Preview
Publisher’s or external URL: http://dx.doi.org/10.1155/2012/946893


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.

Item Type: Article
Publisher’s Statement: © 2012 J. Machacek and S. Jibrin. Creative Commons Attribution License. Published by Hindawi Publishing Corporation.
ID number or DOI: 10.1155/2012/946893
Keywords: algorithims; feasibility; interiors-point methods; iterative methods (Mathematics); problem solving; semidefinitive programming; sets; stochastic convergence
Subjects: Q Science > QA Mathematics
NAU Depositing Author Academic Status: Faculty/Staff
Department/Unit: College of Engineering, Forestry, and Natural Science > Mathematics and Statistics
Date Deposited: 16 Oct 2015 22:36
URI: http://openknowledge.nau.edu/id/eprint/793

Actions (login required)

IR Staff Record View IR Staff Record View


Downloads per month over past year