297. Asymmetric Long-Step Primal-Dual Interior-Point Methods with Dual Centering
Invited abstract in session MD-35: Nonlinear Optimization Algorithms and Applications: 3, stream Continuous and mixed-integer nonlinear programming: theory and algorithms.
Monday, 14:30-16:00Room: Michael Sadler LG15
Authors (first author is the speaker)
| 1. | Yurii Nesterov
|
| CORE, Université catholique de Louvain (UCL) |
Abstract
We discuss a new way of development of asymmetric Interior-Point Methods for solving primal-dual problems of Conic Optimization. It is very efficient for problems, where the dual formulation is simpler than the primal one. The problems of this type arise often in Semidefinite Optimization (SDO), for which we propose a new primal-dual method with very attractive computational cost.
In this approach, we do not need sophisticated Linear Algebra, restricting ourselves by standard 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 and the dual feasible sets. We show by SDO-examples that the corresponding gain can be very big. We discuss some classes of SDO-problems, where the complexity bounds are proportional to the square root of the number of linear equality constraints and the computational cost of one iteration is as in Linear Optimization. Our theoretical developments are supported by encouraging numerical testing.
Keywords
- Interior Point Methods
- Convex Optimization
- Complexity and Approximation
Status: accepted
Back to the list of papers