title:

"Polynomial Convergence of Interior-Point Algorithms on Symmetric Cones"


ABSTRACT

Conic programs are optimization problems where a linear function is
minimized over the intersection of an affine space and a closed convex
cone. An interior-point algorithm for conic programs over symmetric cones
derived from associative algebras is presented. This setting naturally
generalises semidefinite programming. In the process, a Lyapunov-type
lemma is established in this framework. The algorithms start at an initial
point that is in the interior of the cone but not necessarily in the
affine space. The difficulty of analysing such infeasible-interior-point
methods compared to methods that start at a feasible point is highlighted. 
The iterates are restricted to a wide neighborhood of the central path,
inside of the cone. A polynomial convergence result for the algorithm is
presented.


Key Words: Infeasible-Interior-Point Methods, Symmetric Cones, Euclidean
Jordan Algebras, Polynomial Convergence. 

Bharath Rangarajan 

*************************************************************************
Office:                                     Residence: 
------                                      ---------
294, Rhodes Hall,                           315,Summerhill lane,
Cornell University,                         Apartment #5,
Ithaca,                                     Ithaca,
NY 14853                                    NY 14850-2808
email: br47@cornell.edu                     Phone 607-272-0041
**************************************************************************