The Corvinus Centre for Operations Research (CCOR), the Corvinus Institute for Advanced Studies (CIAS), and the Institute of Operations and Decision Sciences invite you to the minicourse by Professor Yurii Nesterov (Corvinus University of Budapest)
Asymmetric Long-Step Primal-Dual Interior-Point Methods with Dual Centering.
Venue: Corvinus University, Building C
Date:
February 12 (Wednesday) 10:00-11:30 (Room C428)
February 13 (Thursday) 10:00-11:30 (Room C428)
Abstract
In this course, we discuss a new way of development of asymmetric Interior-Point Methods (IPMs) for solving primal-dual problems of Conic Optimization. It is efficient for problems, where the dual formulation is simpler than the primal one. The problems of this type arise, in particular, in Semidefinite Optimization (SDO), for which we propose a new method with very attractive computational cost. Our long-step predictor-corrector scheme is based on centering in the dual space. It computes the affine-scaling predicting direction by the use of the dual barrier function, controlling the tangent step size by a functional proximity measure. We show that for symmetric cones, the search procedure at the predictor step is very cheap.
In general, in this approach, we do not need sophisticated Linear Algebra, restricting ourselves only by Cholesky factorization. However, our complexity bounds correspond to the best-known polynomial-time results. Moreover, for symmetric cones the bounds automatically depend on the minimal barrier parameter between the primal or the dual feasible sets. We show by SDO-examples that the corresponding gain can be very big.
We argue that the dual framework is more suitable for adjustment to the actual complexity of the problem. As an example, we discuss some classes of SDO-problems, where the complexity bounds are proportional to the square root of the number of linear equality constraints. Moreover, the computational cost of one iteration there is similar to that one for Linear Optimization. We support our theoretical developments by preliminary but encouraging numerical testing with randomly generated SDO-problems of different sizes.