Skip navigation
  • Home
  • Browse
    • Communities
      & Collections
    • Browse Items by:
    • Publication Date
    • Author
    • Title
    • Subject
    • Department
  • Sign on to:
    • My MacSphere
    • Receive email
      updates
    • Edit Profile


McMaster University Home Page
  1. MacSphere
  2. Open Access Dissertations and Theses Community
  3. Digitized Open Access Dissertations and Theses
Please use this identifier to cite or link to this item: http://hdl.handle.net/11375/21779
Title: New Large Neighborhood Interior Point Methods For Semidefinite Optimization
Authors: Li, Yang
Advisor: Terlaky, Tamas
Department: Computational Engineering and Science
Keywords: Interior point methods, Semidefinite Optimization, Small Neighborhood Algorithm
Publication Date: 2008
Abstract: <p>In this thesis, we extend the Ai-Zhang direction to the class of semidefinite optimization problems. We define a new wide neighborhood N(τ1 ,τ2 ,η) and, as usual, we utilize symmetric directions by scaling the Newton equation with special matrices. After defining the "positive part" and the "negative part" of a symmetric matrix, we solve the Newton equation with its right hand side replaced first by its positive part and then by its negative part, respectively. In this way, we obtain a decomposition of the usual Newton direction and use different step lengths for each of them.</p><p>Starting with a feasible point (X^0 , y^0 , S^0) in N(τ1, τ2 , η ), the algorithm terminates in at most 0(η√( κ∞n)log(1/ε) iterations, where κ∞ is a parameter associated with the scaling matrix and ε is the required precision. To our best knowledge, when the parameter η is a constant, this is the first large neighborhood path-following Interior Point Method (IPM) with the same complexity as small neighborhood path-following IPMs for semidefinite optimization that use the Nesterov-Todd direction. In the case when η is chosen to be in the order of √η, our complexity bound coincides with the known bound for classical large neighborhood IPMs.</p><p>To make this thesis more accessible to readers who are new in this area, we start with a brief introduction to IPMs and SDO. The basic concepts and principles of IPMs and SDO are presented in Chapter 2 and 3.</p>
URI: http://hdl.handle.net/11375/21779
Appears in Collections:Digitized Open Access Dissertations and Theses

Files in This Item:
File Description SizeFormat 
Li_Yang_2008_Masters..pdf
Open Access
2.15 MBAdobe PDFView/Open
Show full item record Statistics


Items in MacSphere are protected by copyright, with all rights reserved, unless otherwise indicated.

Sherman Centre for Digital Scholarship     McMaster University Libraries
©2022 McMaster University, 1280 Main Street West, Hamilton, Ontario L8S 4L8 | 905-525-9140 | Contact Us | Terms of Use & Privacy Policy | Feedback

Report Accessibility Issue