Koç University, Mathematics Seminar
Date & Time: Monday, October 19, 17:00-18:00
Place: ENG B-05
Speaker: Levent Tunçel (University of Waterloo)
Title: Superlinear convergence in modern convex optimization
Abstract:
We propose new algorithms for
solving convex optimization problems. 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 algorithms have the local superlinear convergence
property under some mild assumptions (including on a very general class of
convex optimization problems defined via hyperbolic polynomials). Moreover, our
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.
This talk is based on joint work with Yu. Nesterov.
Speaker Homepage: http://www.math.uwaterloo.ca/~ltuncel/