Return to search

The analytic center cutting plane method with semidefinite cuts /

We propose an analytic center cutting plane algorithm for semidefinite programming (SDP). Reformulation of the dual problem of SDP into an eigenvalue optimization, when the trace of any feasible primal matrix is a positive constant, is well known. We transform the eigenvalue optimization problem into a convex feasibility problem. The problem of interest seeks a feasible point in a bounded convex set, which contains a full dimensional ball with &egr;(<1) radius and is contained in a compact convex set described by matrix inequalities, known as the set of localization. At each iteration, an approximate analytic center of the set of localization is computed. If this point is not in the solution set, an oracle is called to return a p-dimensional semidefinite cut. The set of localization then, is updated by adding the semidefinite cut through the center. We prove that the analytic center is recovered after adding a p-dimensional semidefinite cut in O(plog(p + 1)) damped Newton's iteration and that the ACCPM with semidefinite cuts is a fully polynomial approximation scheme. We report the numerical result of our algorithm when applied to the semidefinite relaxation of the Max-Cut problem.
Date January 2002
CreatorsOskoorouchi, Mohammad R.
ContributorsGoffin, Jean-Louis (advisor)
PublisherMcGill University
Source SetsLibrary and Archives Canada ETDs Repository / Centre d'archives des thèses électroniques de Bibliothèque et Archives Canada
Detected LanguageEnglish
TypeElectronic Thesis or Dissertation
CoverageDoctor of Philosophy (Faculty of Management.)
RightsAll items in eScholarship@McGill are protected by copyright with all rights reserved unless otherwise indicated.
Relationalephsysno: 001956054, proquestno: NQ85729, Theses scanned by UMI/ProQuest.

Page generated in 0.1102 seconds