<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> / Thesis / Master of Applied Science (MASc)
| Identifer | oai:union.ndltd.org:mcmaster.ca/oai:macsphere.mcmaster.ca:11375/21779 |
| Date | January 2008 |
| Creators | Li, Yang |
| Contributors | Terlaky, Tamas, Computational Engineering and Science |
| Source Sets | McMaster University |
| Language | en_US |
| Detected Language | English |
| Type | Thesis |
Page generated in 0.0015 seconds