- CARMA SEMINAR
- Speaker: Prof Levent Tunçel, University of Waterloo
- Title: Superlinear Convergence of polynomial-time interior-point methods for convex optimization
- Location: Room V205, Mathematics Building (Callaghan Campus) The University of Newcastle
- Time and Date: 4:00 pm, Thu, 17th Sep 2015
We propose new path-following predictor-corrector algorithms for
solving convex optimization problems in conic form.
The main structural properties used in our design and analysis
of the algorithms hinge on some key properties of a special class of
very smooth, strictly convex barrier functions.
Even though our analysis has primal and dual components, our algorithms
work with the dual iterates only, in the dual space.
Our algorithms converge globally at the same worst-case rate as the current
best polynomial-time interior-point methods. In addition, our algorithm
have the local superlinear convergence property under some mild assumptions.
The algorithms are based on an easily computable gradient proximity measure,
which ensures an automatic transformation of the global linear rate of
convergence to the locally superlinear one under some mild assumptions.
Our step-size procedure for the predictor step is related to the maximum
step size (the one that takes us to the boundary).
This talk is based on joint work with Yu. Nesterov.
- [Permanent link]