OPTEC - K.U.Leuven Center of Excellence: Optimization in Engineering

"Gradient methods for convex optimization in relative scale"
Yurii Nesterov, CORE, Universit'e Catholique de Louvain (UCL).

In this talk we propose new efficient gradient schemes, which can solve a structural convex optimization problem with certain {em relative} accuracy $delta$. As an example, we consider two non-trivial classes of linear programming problems, which can be solved in $O({sqrt{n ln m} over delta}ln n)$ iterations of a gradient-type method ($n$ and $m$, $n < m$, are the sizes of the corresponding problems). The proposed schemes are based on preliminary computation of an ellipsoidal rounding for some polytopes in $R^n$. In both cases this computation can be performed very efficiently, in $O(n^2m ln m)$ operations at most.